Column Generation for Real-Time Ride-Sharing Operations
作者： Connor Riley , Antoine Legrain , Pascal Van Hentenryck
DOI: 10.1007/978-3-030-19212-9_31
关键词:
摘要: This paper considers real-time dispatching for large-scale ride-sharing services over a rolling horizon. It presents RTDARS which relies on column-generation algorithm to minimize wait times while guaranteeing short travel and service each customer. Experiments using historic taxi trips in New York City instances with up 30,000 requests per hour indicate that the scales well provides principled effective way support dense cities.
springer.com
sci-hub.se 参考文章(9)
Pascal Van Hentenryck, Russell Bent, Waiting and relocation strategies in online stochastic vehicle routing international joint conference on artificial intelligence. pp. 1816- 1821 ,(2007)
Jean-François Cordeau, Gilbert Laporte, The dial-a-ride problem: models and algorithms Annals of Operations Research. ,vol. 153, pp. 29- 46 ,(2007) , 10.1007/S10479-007-0170-8
Siddhartha Jain, Pascal Van Hentenryck, Large neighborhood search for dial-a-ride problems principles and practice of constraint programming. pp. 400- 413 ,(2011) , 10.1007/978-3-642-23786-7_31
Gerardo Berbeglia, Jean-François Cordeau, Gilbert Laporte, A Hybrid Tabu Search and Constraint Programming Algorithm for the Dynamic Dial-a-Ride Problem Informs Journal on Computing. ,vol. 24, pp. 343- 355 ,(2012) , 10.1287/IJOC.1110.0454
Russell W. Bent, Pascal Van Hentenryck, Scenario-Based Planning for Partially Dynamic Vehicle Routing with Stochastic Customers Operations Research. ,vol. 52, pp. 977- 987 ,(2004) , 10.1287/OPRE.1040.0124
Masayo Ota, Huy Vo, Claudio Silva, Juliana Freire, A scalable approach for data-driven taxi ride-sharing simulation 2015 IEEE International Conference on Big Data (Big Data). pp. 888- 897 ,(2015) , 10.1109/BIGDATA.2015.7363837
Masayo Ota, Huy Vo, Claudio Silva, Juliana Freire, STaRS: Simulating Taxi Ride Sharing at Scale IEEE Transactions on Big Data. ,vol. 3, pp. 349- 361 ,(2017) , 10.1109/TBDATA.2016.2627223
Javier Alonso-Mora, Samitha Samaranayake, Alex Wallar, Emilio Frazzoli, Daniela Rus, On-demand high-capacity ride-sharing via dynamic trip-vehicle assignment Proceedings of the National Academy of Sciences of the United States of America. ,vol. 114, pp. 462- 467 ,(2017) , 10.1073/PNAS.1611675114
Dimitris Bertsimas, Patrick Jaillet, Sébastien Martin, Online Vehicle Routing: The Edge of Optimization in Large-Scale Applications Operations Research. ,vol. 67, pp. 143- 162 ,(2019) , 10.1287/OPRE.2018.1763