A column generation approach for a dynamic ridesharing problem

References

• Agatz, N., A. L. Erera, M. Savelsbergh, and X. Wang. 2011 . “Dynamic ride-sharing: A Simulation Study in Metro Atlanta .” Procedia-Social and Behavioral Sciences 17: 532–550. doi:10.1016/j.sbspro.2011.04.530.
   Google Scholar
• Agatz, N., A. Erera, M. Savelsbergh, and X. Wang. 2012. “. Optimization for Dynamic ride-sharing: A Review .” European Journal of Operational Research 223 (2): 259–303. doi:10.1016/j.ejor.2012.05.028.
   Web of Science ®Google Scholar
• Alonso-Mora, J., S. Samaranayake, A. Wallar, E. Frazzoli, and D. Rus, 2017 . On-demand high-capacity ride-sharing via Dynamic trip-vehicle Assignment . Proceedings of the National Academy of Sciences 114, 462–467. doi:10.1073/pnas.1611675114.
   Google Scholar
• Asghari, M., D. Deng, C. Shahabi, U. Demiryurek, and Y. Li, 2016 . “Price-aware real-time ride-sharing at Scale: An auction-based Approach.” in: Proceedings of the 24th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, San Francisco Bay Area, California, USA, pp. 3.
   Google Scholar
• Attanasio, A., J. F. Cordeau, G. Ghiani, and G. Laporte. 2004 . “Parallel Tabu Search Heuristics for the Dynamic multi-vehicle dial-a-ride Problem.” Parallel Computing 30 (3): 377–387. doi:10.1016/j.parco.2003.12.001.
   Web of Science ®Google Scholar
• Baldacci, R., V. Maniezzo, and A. Mingozzi. 2004 . “An Exact Method for the Car Pooling Problem Based on Lagrangean Column Generation .” Operations Research 52 (3): 422–439. doi:10.1287/opre.1030.0106.
   Web of Science ®Google Scholar
• Berbeglia, G., J. F. Cordeau, and G. Laporte. 2010 . “Dynamic Pickup and Delivery Problems .” European Journal of Operational Research 202 (1): 8–15. doi:10.1016/j.ejor.2009.04.024.
   Web of Science ®Google Scholar
• Berbeglia, G., J. F. Cordeau, and G. Laporte. 2012 . “A Hybrid Tabu Search and Constraint Programming Algorithm for the Dynamic dial-A-ride Problem.” INFORMS Journal on Computing 24 (3): 343–355. doi:10.1287/ijoc.1110.0454.
   Web of Science ®Google Scholar
• Bertsimas, D., P. Jaillet, and S. Martin. 2019 . “Online Vehicle Routing: The Edge of Optimization in large-scale Applications.” Operations Research 67 (1): 143–162. doi:10.1287/opre.2018.1763.
   Web of Science ®Google Scholar
• Boland, N., J. Dethridge, and I. Dumitrescu. 2006 . “Accelerated Label Setting Algorithms for the Elementary Resource Constrained Shortest Path Problem.” Operations Research Letters 34 (1): 58–68. doi:10.1016/j.orl.2004.11.011.
   Web of Science ®Google Scholar
• Bruck, B. P., V. Incerti, M. Iori, and M. Vignoli. 2017. “. Minimizing co2 Emissions in a Practical Daily Carpooling Problem.” Computers & Operations Research 81: 40–50. doi:10.1016/j.cor.2016.12.003.
   Web of Science ®Google Scholar
• Chan, N. D., and S. A. Shaheen. 2012 . “Ridesharing in North America: Past, Present, and Future.” Transport Reviews 32 (1): 93–112. doi:10.1080/01441647.2011.621557.
   Web of Science ®Google Scholar
• Cheng, P., H. Xin, and L. Chen, 2017. “Utility-aware Ridesharing on Road Networks.” in: Proceedings of the 2017 ACM International Conference on Management of Data, Chicago, Illinois, USA, pp. 1197–1210.
   Google Scholar
• Chen, P. Y., J. W. Liu, and W. T. Chen, 2010 . “A fuel-saving and pollution-reducing Dynamic taxi-sharing Protocol in Vanets.” in: 2010 IEEE 72nd Vehicular Technology Conference-Fall, Ottawa, ON, Canada, pp. 1–5.
   Google Scholar
• Chen, Z. L., and H. Xu. 2006. “Dynamic Column Generation for Dynamic Vehicle Routing with Time Windows.” Transportation Science 40 (1): 74–88. doi:10.1287/trsc.1050.0133.
   Web of Science ®Google Scholar
• Cordeau, J. F. 2006. “A branch-and-cut Algorithm for the dial-A-ride Problem.” Operations Research 54 (3): 573–586. doi:10.1287/opre.1060.0283.
   Web of Science ®Google Scholar
• Cordeau, J. F., and G. Laporte. 2003. “A Tabu Search Heuristic for the Static multi-vehicle dial-A-ride Problem.” Transportation Research Part B: Methodological 37 (6): 579–594. doi:10.1016/S0191-2615(02)00045-0.
   Web of Science ®Google Scholar
• Cordeau, J. F., and G. Laporte. 2007. “The dial-a-ride Problem: Models and Algorithms.” Annals of Operations Research 153 (1): 29–46. doi:10.1007/s10479-007-0170-8.
   Web of Science ®Google Scholar
• Delhomme, P., and A. Gheorghiu. 2016. “Comparing French Carpoolers and non-carpoolers: Which Factors Contribute the Most to Carpooling?” Transportation Research Part D: Transport and Environment 42: 1–15. doi:10.1016/j.trd.2015.10.014.
   Web of Science ®Google Scholar
• Diana, M., and M. M. Dessouky. 2004. “A New Regret Insertion Heuristic for Solving large-scale dial-A-ride Problems with Time Windows.” Transportation Research Part B: Methodological 38 (6): 539–557. doi:10.1016/j.trb.2003.07.001.
   Web of Science ®Google Scholar
• Dror, M. 1994. “Note on the Complexity of the Shortest Path Models for Column Generation in Vrptw.” Operations Research 42 (5): 977–978. doi:10.1287/opre.42.5.977.
   Web of Science ®Google Scholar
• Dumas, Y., J. Desrosiers, and F. Soumis. 1989. “Large scale multi-vehicle dial-a-ride problems . École des hautes études commerciales, Groupe d’études et de recherche en analyse des décisions.”
   Google Scholar
• Dumas, Y., J. Desrosiers, and F. Soumis. 1991. “The Pickup and Delivery Problem with Time Windows.” European Journal of Operational Research 54 (1): 7–22. doi:10.1016/0377-2217(91)90319-Q.
   Web of Science ®Google Scholar
• Fagnant, D. J., and K. M. Kockelman. 2014. “The Travel and Environmental Implications of Shared Autonomous Vehicles, Using agent-based Model Scenarios.” Transportation Research Part C: Emerging Technologies 40: 1–13. doi:10.1016/j.trc.2013.12.001.
   Web of Science ®Google Scholar
• Furuhata, M., M. Dessouky, F. Ordóñez, M. E. Brunet, X. Wang, and S. Koenig. 2013. “Ridesharing: The state-of-the-art and Future Directions.” Transportation Research Part B: Methodological 57: 28–46. doi:10.1016/j.trb.2013.08.012.
   Web of Science ®Google Scholar
• Hosni, H., J. Naoum-Sawaya, and H. Artail. 2014. “The shared-taxi Problem: Formulation and Solution Methods.” Transportation Research Part B: Methodological 70: 303–318. doi:10.1016/j.trb.2014.09.011.
   Web of Science ®Google Scholar
• Ioachim, I., J. Desrosiers, Y. Dumas, M. M. Solomon, and D. Villeneuve. 1995. “A Request Clustering Algorithm for door-to-door Handicapped Transportation.” Transportation Science 29 (1): 63–78. doi:10.1287/trsc.29.1.63.
   Web of Science ®Google Scholar
• Irnich, S., and G. Desaulniers. 2005. “Shortest Path Problems with Resource Constraints.” In Column Generation, edited by Desaulniers G, Desrosiers J, and Solomon M, 33–65. Boston, MA, USA: Springer.
   Google Scholar
• Jaw, J. J., A. R. Odoni, H. N. Psaraftis, and N. H. Wilson. 1986. “A Heuristic Algorithm for the multi-vehicle Advance Request dial-A-ride Problem with Time Windows.” Transportation Research Part B: Methodological 20 (3): 243–257. doi:10.1016/0191-2615(86)90020-2.
   Web of Science ®Google Scholar
• JOINS, 2019. “Tada Achieves 600,000 Members in Just Seven Months of Operation. How Is It Different from Regular Taxis?” https://news.joins.com/article/23480123 . Accessed: 2019-08-27 .
   Google Scholar
• Kleiner, A., B. Nebel, and V. A. Ziparo, 2011. “A Mechanism for Dynamic Ride Sharing Based on Parallel Auctions.” in: Twenty-Second International Joint Conference on Artificial Intelligence, Barcelona, Spain.
   Google Scholar
• Korean Transport Database, 2016. Passenger Traffic Status Survey. https://www.ktdb.go.kr/www/contents.do?key=16 . Accessed: 2019-08-27 .
   Google Scholar
• Li, Y., R. Chen, L. Chen, and J. Xu. 2015. “Towards social-aware Ridesharing Group Query Services.” IEEE Transactions on Services Computing 10 (4): 646–659. doi:10.1109/TSC.2015.2508440.
   Web of Science ®Google Scholar
• Martinez, L. M., G. H. Correia, and J. M. Viegas. 2015. “An agent-based Simulation Model to Assess the Impacts of Introducing a shared-taxi System: An Application to Lisbon (Portugal).” Journal of Advanced Transportation 49 (3): 475–495. doi:10.1002/atr.1283.
   Web of Science ®Google Scholar
• Masoud, N., and R. Jayakrishnan. 2017. “. A Decomposition Algorithm to Solve the multi-hop peer-to-peer ride-matching Problem.” Transportation Research Part B: Methodological 99: 1–29. doi:10.1016/j.trb.2017.01.004.
   Web of Science ®Google Scholar
• Ma, S., Y. Zheng, and O. Wolfson. 2015. “Real-time city-scale Taxi Ridesharing.” IEEE Transactions on Knowledge and Data Engineering 27 (7): 1782–1795. doi:10.1109/TKDE.2014.2334313.
   Web of Science ®Google Scholar
• Ministry of Land, Infrastructure and Transport, 2017. “A Study on Complementing and Improving Taxi Total Amount System.” 3rd edition. https://www.prism.go.kr/homepage/origin/retrieveOriginDetail.do?cond_organ_id=1613000research_id=1613000-201600139pageIndex=1.leftMenuLevel=120. Accessed 27 august 2019.
   Google Scholar
• Mobility, K., 2019. “Kakao mobility report 2018.” https://brunch.co.kr/@kakaomobility/19. Accessed 27 august 2019.
   Google Scholar
• Nanry, W. P., and J. W. Barnes. 2000. “Solving the Pickup and Delivery Problem with Time Windows Using Reactive Tabu Search.” Transportation Research Part B: Methodological 34 (2): 107–121. doi:10.1016/S0191-2615(99)00016-8.
   Web of Science ®Google Scholar
• Nourinejad, M., and M. J. Roorda. 2016. “Agent Based Model for Dynamic Ridesharing.” Transportation Research Part C: Emerging Technologies 64: 117–132. doi:10.1016/j.trc.2015.07.016.
   Web of Science ®Google Scholar
• Peng, Z., W. Shan, P. Jia, B. Yu, Y. Jiang, and B. Yao. 2018. “Stable ride-sharing Matching for the Commuters with Payment Design.” Transportation 45 (1): 1–21. doi:10.1007/s11116-016-9716-4.
   PubMedGoogle Scholar
• Qian, X., W. Zhang, S. V. Ukkusuri, and C. Yang. 2017. “. Optimal Assignment and Incentive Design in the Taxi Group Ride Problem.” Transportation Research Part B: Methodological 103: 208–226. doi:10.1016/j.trb.2017.03.001.
   Web of Science ®Google Scholar
• Righini, G., and M. Salani. 2006. “Symmetry Helps: Bounded bi-directional Dynamic Programming for the Elementary Shortest Path Problem with Resource Constraints.” Discrete Optimization 3 (3): 255–273. doi:10.1016/j.disopt.2006.05.007.
   Web of Science ®Google Scholar
• Santi, P., G. Resta, M. Szell, S. Sobolevsky, S. H. Strogatz, and C. Ratti, 2014. Quantifying the Benefits of Vehicle Pooling with Shareability Networks. Proceedings of the National Academy of Sciences 111, 13290–13294. doi:10.1073/pnas.1403657111.
   Google Scholar
• Santos, D. O., and E. C. Xavier. 2015. “Taxi and Ride Sharing: A Dynamic dial-A-ride Problem with Money as an Incentive.” Expert Systems with Applications 42 (19): 6728–6737. doi:10.1016/j.eswa.2015.04.060.
   Web of Science ®Google Scholar
• Savelsbergh, M., and M. Sol. 1998. “Drive: Dynamic Routing of Independent Vehicles.” Operations Research 46 (4): 474–490. doi:10.1287/opre.46.4.474.
   Web of Science ®Google Scholar
• Sayarshad, H. R., and J. Y. Chow. 2015. “A Scalable non-myopic Dynamic dial-A-ride and Pricing Problem.” Transportation Research Part B: Methodological 81: 539–554. doi:10.1016/j.trb.2015.06.008.
   Web of Science ®Google Scholar
• Sivak, M., and B. Schoettle. 2012. “Eco-driving: Strategic, Tactical, and Operational Decisions of the Driver that Influence Vehicle Fuel Economy.” Transport Policy 22: 96–99. doi:10.1016/j.tranpol.2012.05.010.
   Web of Science ®Google Scholar
• Stiglic, M., N. Agatz, M. Savelsbergh, and M. Gradisar. 2016. “Making Dynamic ride-sharing Work: The Impact of Driver and Rider Flexibility.” Transportation Research Part E: Logistics and Transportation Review 91: 190–207. doi:10.1016/j.tre.2016.04.010.
   Web of Science ®Google Scholar
• Techcrunch, 2016. Uber Says that 20% of Its Rides Globally are Now on Uberpool. https://techcrunch.com/2016/05/10/uber-says-that-20-of-its-rides-globally-are-now-on-uber-pool . Accessed: 2019-08-27 .
   Google Scholar
• Toth, P., and D. Vigo. 2014. Vehicle Routing: Problems, Methods, and Applications. Philadelphia, PA, USA: SIAM.
   Google Scholar
• Wang, X., N. Agatz, and A. Erera. 2018. “. Stable Matching for Dynamic ride-sharing Systems.” Transportation Science 52 (4): 850–867. doi:10.1287/trsc.2017.0768.
   Web of Science ®Google Scholar
• Wang, X., M. Dessouky, and F. Ordonez. 2016. “A Pickup and Delivery Problem for Ridesharing considering Congestion.” Transportation Letters 8: 259–269.
   Web of Science ®Google Scholar
• Xiang, Z., C. Chu, and H. Chen. 2006. “A Fast Heuristic for Solving A large-scale Static dial-A-ride Problem under Complex Constraints.” European Journal of Operational Research 174 (2): 1117–1139. doi:10.1016/j.ejor.2004.09.060.
   Web of Science ®Google Scholar
• Yan, S., and C.-Y. Chen. 2011. “An Optimization Model and a Solution Algorithm for the many-to-many Car Pooling Problem.” Annals of Operations Research 191 (1): 37–71. doi:10.1007/s10479-011-0948-6.
   Web of Science ®Google Scholar