1. Relocation in Carsharing Systems using Flows in Time-Expanded Networks
- Author
-
Annegret Wagler, Jan-Thierry Wegener, Alain Quilliot, Sven O. Krumke, Courbin-Coulaud, Martine, University of Kaiserslautern [Kaiserslautern], Laboratoire d'Informatique, de Modélisation et d'optimisation des Systèmes (LIMOS), SIGMA Clermont (SIGMA Clermont)-Université d'Auvergne - Clermont-Ferrand I (UdA)-Ecole Nationale Supérieure des Mines de St Etienne-Centre National de la Recherche Scientifique (CNRS)-Université Blaise Pascal - Clermont-Ferrand 2 (UBP), This work was founded by the French National Research Agency, the European Commission (Feder funds) and the Region Auvergne in the Framework of the LabEx IMobS3., Laboratoire d'Informatique, de Modélisation et d'Optimisation des Systèmes (LIMOS), Ecole Nationale Supérieure des Mines de St Etienne-Université Clermont Auvergne [2017-2020] (UCA [2017-2020])-Centre National de la Recherche Scientifique (CNRS), University of Kaiserslautern (Department of Mathematics), University of Kaiserslautern (Department of Mathematics)-University of Kaiserslautern (Department of Mathematics), Société française de recherche opérationnelle et d'aide à la décision, Université Blaise Pascal - Clermont-Ferrand 2 (UBP)-Université d'Auvergne - Clermont-Ferrand I (UdA)-SIGMA Clermont (SIGMA Clermont)-Ecole Nationale Supérieure des Mines de St Etienne (ENSM ST-ETIENNE)-Centre National de la Recherche Scientifique (CNRS), and Ecole Nationale Supérieure des Mines de St Etienne (ENSM ST-ETIENNE)-Université Clermont Auvergne [2017-2020] (UCA [2017-2020])-Centre National de la Recherche Scientifique (CNRS)
- Subjects
Engineering ,Profit (real property) ,Operations research ,[INFO.INFO-RO] Computer Science [cs]/Operations Research [cs.RO] ,Heuristic (computer science) ,Computation ,[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM] ,Urban area ,integer linear programming ,Transport engineering ,11. Sustainability ,G.1.6 Optimization ,Integer programming ,geography ,geography.geographical_feature_category ,business.industry ,coupled flows in time-expanded networks ,[INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO] ,coupled flows in time ,expanded networks ,Flow (mathematics) ,Order (business) ,relocation problem ,business ,Relocation ,carsharing system - Abstract
A manuscript on this topic can be found at: http://hal.archives-ouvertes.fr/hal-00908242; International audience; 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.
- Published
- 2014
- Full Text
- View/download PDF