In a carsharing system, a fleet of cars is distributed at stations in an urban area, customers can take and return cars at any time and station, provided that there is a car available at the start station and a free place at the final station.
To ensure the latter, customers have to book their demands in advance; hereby, customer requests can be accepted or rejected by the operator.
The stations have to keep a good ratio between available cars and free places in each station, in order to serve already accepted customer requests and to refuse as few new customer requests as possible.
This leads to the problem of relocating cars between stations, which can be modeled as Pickup and Delivery Problem in a metric space induced by the urban area or, alternatively, by means of flows of cars in convoys in a time-expanded network.
Note that we consider an innovative carsharing system with partly autonomous cars which allows to build convoys of cars, each moved by only one driver. This leads to a similar situation as in bikesharing systems, where trucks can simultaneously move several bikes, but no requests are booked in advance.
Hereby, two flows are coupled in the sense that the flow of cars is dependent from the flow of drivers (since cars can only
be moved in convoys); the flow coupling constraints reflect the complexity of the studied problem.
We present integer programming formulations for two variants of the relocation problem: a min-cost flow problem to serve a given set of customer requests at minimal costs (quality of service aspect), and a max-profit flow problem to additionally solve the decision problem of accepting or rejecting customer requests (economic aspect).
Both models take advantage of users booking their demands in advance and can be applied to the offline as well as the online version of the relocation problem in order to fully capture the dynamic evolution of the system over time.