The ridesharing problem without predetermined drivers and riders: formulation and heuristic

References

• Agatz, N., A. Erera, M. Savelsbergh, and X. Wang. 2010. “Sustainable Passenger Transportation: Dynamic ride-sharing.” ERIM Report Series Reference No. ERS-2010-010-LIS.
   Google Scholar
• Agatz, N., A. 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): 295–303. doi:10.1016/j.ejor.2012.05.028.
   Web of Science ®Google Scholar
• Baldacci, R., E. Bartolini, and A. Mingozzi. 2011. “An Exact Algorithm for the Pickup and Delivery Problem with Time Windows.” Operations Research 59 (2): 414–426. doi:10.1287/opre.1100.0881.
   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
• Bei, X., and S. Zhang. 2018. “Algorithms for trip-vehicle Assignment in ride-sharing.” In AAAI Conference on Artificial Intelligence. New Orleans, LA, USA.
   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
• Bian, Z., and X. Liu. 2019. “Mechanism Design for first-mile Ridesharing Based on Personalized Requirements Part I: Theoretical Analysis in Generalized Scenarios.” Transportation Research Part B: Methodological 120: 147–171. doi:10.1016/j.trb.2018.12.009.
   Web of Science ®Google Scholar
• Calvo, R. W., F. de Luigi, P. Haastrup, and V. Maniezzo. 2004. “A Distributed Geographic Information System for the Daily Car Pooling Problem.” Computers & Operations Research 31 (13): 2263–2278. doi:10.1016/S0305-0548(03)00186-2.
   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
• Cortes, C. E., M. Matamala, and C. Contardo. 2010. “The Pickup and Delivery Problem with Transfers: Formulation and a branch-and-cut Solution Method.” European Journal of Operational Research 200 (3): 711–724. doi:10.1016/j.ejor.2009.01.022.
   Web of Science ®Google Scholar
• Dailey, D. J., D. Loseff, and D. Meyers. 1999. “Seattle Smart Traveler: Dynamic Ride Matching on the World Wide Web.” Transportation Research Part C: Emerging Technologies 7 (1): 17–32. doi:10.1016/S0968-090X(99)00007-8.
   Web of Science ®Google Scholar
• Department for Transport Statistics. 2020. “Data on Vehicle Mileage and Occupancy.” Technical Report, Government of the United Kingdom.
   Google Scholar
• Di Febbraro, A., E. Gattorna, and N. Sacco. 2013. “Optimization of Dynamic Ridesharing Systems.” Transportation Research Record: Journal of the Transportation Research Board 2359 (1): 44–50. doi:10.3141/2359-06.
   Google Scholar
• Duan, R., and S. Pettie. 2014. “Linear-time Approximation for Maximum Weight Matching.” Journal of the ACM (JACM) 61 (1): 1–23. doi:10.1145/2529989.
   Web of Science ®Google Scholar
• Dumitrescu, I., S. Ropke, J.-F. Cordeau, and G. Laporte. 2010. “The Traveling Salesman Problem with Pickup and Delivery: Polyhedral Results and a branch-and-cut Algorithm.” Mathematical Programming 121 (2): 269–305. doi:10.1007/s10107-008-0234-9.
   Web of Science ®Google Scholar
• Edmonds, J. 1965. “Maximum Matching and a Polyhedron with 0, 1-vertices.” Journal of Research of the National Bureau of Standards B 69 (125–130): 55–56.
   Google Scholar
• Federal Highway Administration. 2017. “National Household Travel Survey.” Technical Report, U.S. Department of Transportation.
   Google Scholar
• Furuhata, M., M. Dessouky, F. Ordo´n˜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(C), 28-46.
   Google Scholar
• Herbawi, W. M., and M. Weber. 2012. “A Genetic and Insertion Heuristic Algorithm for Solving the Dynamic Ridematching Problem with Time Windows.” In Proceedings of the 14th Annual Conference on Genetic and Evolutionary Computation, GECCO ’12, 385–392, New York, NY, USA. ACM.
   Google Scholar
• Hou, L., D. Li, and D. Zhang. 2018. “Ride-matching and Routing Optimisation: Models and a Large Neighbourhood Search Heuristic.” Transportation Research Part E: Logistics and Transportation Review 118: 143–162. doi:10.1016/j.tre.2018.07.003.
   Web of Science ®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
• Karp, R. M. 1972. “Reducibility among Combinatorial Problems.” In Complexity of Computer Computations, The IBM Research Symposia Series, 85–103. Yorktown Heights, NY, USA: Springer US.
   Google Scholar
• Lee, A., and M. Savelsbergh. 2015. “Dynamic Ridesharing: Is There a Role for Dedicated Drivers?.” Transportation Research Part B: Methodological 81: 483–497. doi:10.1016/j.trb.2015.02.013.
   Web of Science ®Google Scholar
• Lenstra, J. K., and A. H. G. R. Kan. 1981. “Complexity of Vehicle Routing and Scheduling Problems.” Networks 11 (2): 221–227. doi:10.1002/net.3230110211.
   Web of Science ®Google Scholar
• Li, Y., and S. H. Chung. 2020. “Ride-sharing under Travel Time Uncertainty: Robust Optimization and Clustering Approaches.” Computers & Industrial Engineering 149: 106601. doi:10.1016/j.cie.2020.106601.
   Web of Science ®Google Scholar
• Lloret-Batlle, R., N. Masoud, and D. Nam. 2017. “Peer-to-peer Ridesharing with ride-back on high-occupancy-vehicle Lanes: Toward a Practical Alternative Mode for Daily Commuting.” Transportation Research Record 2668 (1): 21–28. doi:10.3141/2668-03.
   Google Scholar
• Lu, Q., and M. M. Dessouky. 2004. “An Exact Algorithm for the Multiple Vehicle Pickup and Delivery Problem.” Transportation Science 38 (4): 503–514. doi:10.1287/trsc.1030.0040.
   Web of Science ®Google Scholar
• Lu, Q., and M. M. Dessouky. 2006. “A New insertion-based Construction Heuristic for Solving the Pickup and Delivery Problem with Time Windows.” European Journal of Operational Research 175 (2): 672–687. doi:10.1016/j.ejor.2005.05.012.
   Web of Science ®Google Scholar
• Lu, W., L. Lu, and L. Quadrifoglio. 2011. “Scheduling Multiple Vehicle Mobility Allowance Shuttle Transit (m-mast) Services.” In Intelligent Transportation Systems (ITSC), 2011 14th International IEEE Conference on, Washington, DC, USA, 125–132.
   Google Scholar
• Lu, W., and L. Quadrifoglio. 2019. “Fair Cost Allocation for Ridesharing services–modeling, Mathematical Programming and an Algorithm to Find the Nucleolus.” Transportation Research Part B: Methodological 121: 41–55. doi:10.1016/j.trb.2019.01.001.
   Web of Science ®Google Scholar
• Martins, L. D. C., R. de la Torre, C. G. Corlu, A. A. Juan, and M. A. Masmoudi. 2021. “Optimizing ride-sharing Operations in Smart Sustainable Cities: Challenges and the Need for Agile Algorithms.” Computers & Industrial Engineering 153: 107080. doi:10.1016/j.cie.2020.107080.
   Web of Science ®Google Scholar
• Masoud, N., and R. Jayakrishnan. 2017a. “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
• Masoud, N., and R. Jayakrishnan. 2017b. “A real-time Algorithm to Solve the peer-to-peer ride-matching Problem in A Flexible Ridesharing System.” Transportation Research Part B: Methodological 106: 218–236. doi:10.1016/j.trb.2017.10.006.
   Web of Science ®Google Scholar
• Miller, C. E., A. W. Tucker, and R. A. Zemlin. 1960. “Integer Programming Formulation of Traveling Salesman Problems.” Journal of the ACM (JACM) 7 (4): 326–329. doi:10.1145/321043.321046.
   Web of Science ®Google Scholar
• Morency, C. 2007. “The Ambivalence of Ridesharing.” Transportation 34 (2): 239–253. doi:10.1007/s11116-006-9101-9.
   Web of Science ®Google Scholar
• Psaraftis, H. N. 1980. “A Dynamic Programming Solution to the Single Vehicle many-to- Many Immediate Request dial-A-ride Problem.” Transportation Science 14 (2): 130–154. doi:10.1287/trsc.14.2.130.
   Web of Science ®Google Scholar
• Psaraftis, H. N. 1983. “An Exact Algorithm for the Single Vehicle many-to-many dial-a-ride Problem with Time Windows.” Transportaiton Science 17 (3): 351–357. doi:10.1287/trsc.17.3.351.
   Web of Science ®Google Scholar
• Quadrifoglio, L., M. M. Dessouky, and F. Ord´on˜ez. 2008. “Mobility Allowance Shuttle Transit (Mast) Services: Mip Formulation and Strengthening with Logic Constraints.” European Journal of Operational Research 185 (2): 481–494. doi:10.1016/j.ejor.2006.12.030.
   Web of Science ®Google Scholar
• Quadrifoglio, L., M. Dessouky, and K. Palmer. 2007. “An Insertion Heuristic for Scheduling Mobility Allowance Shuttle Transit (Mast) Services.” Journal of Scheduling 10 (1): 25–40. doi:10.1007/s10951-006-0324-6.
   Web of Science ®Google Scholar
• Savelsbergh, M. W. P., and M. Sol. 1995. “The General Pickup and Delivery Problem.” Transportation Science 29 (1): 17–29. doi:10.1287/trsc.29.1.17.
   Web of Science ®Google Scholar
• Schrank, D., B. Eisele, and T. Lomax. 2019. “2019 Urban Mobility Report.” Technical report, Texas A&M Transportation Institute.
   Google Scholar
• Schwieterman, J., and C. S. Smith. 2018. “Sharing the Ride: A paired-trip Analysis of Uberpool and Chicago Transit Authority Services in Chicago, Illinois.” Research in Transportation Economics 71: 9–16. doi:10.1016/j.retrec.2018.10.003.
   Web of Science ®Google Scholar
• Sexton, T. R., and L. D. Bodin. 1985. “Optimizing Single Vehicle many-to-many Operations with Desired Delivery Times: I. Scheduling.” Transportation Science 19 (4): 378–410. doi:10.1287/trsc.19.4.378.
   Web of Science ®Google Scholar
• Stiglic, M., N. Agatz, M. Savelsbergh, and M. Gradisar. 2015. “The Benefits of Meeting Points in ride-sharing Systems.” Transportation Research Part B: Methodological 82: 36–53. doi:10.1016/j.trb.2015.07.025.
   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
• Tafreshian, A., and N. Masoud. 2020. “Trip-based Graph Partitioning in Dynamic Ridesharing.” Transportation Research Part C: Emerging Technologies 114: 532–553. doi:10.1016/j.trc.2020.02.008.
   Web of Science ®Google Scholar
• Tafreshian, A., N. Masoud, and Y. Yin. 2020. “Frontiers in Service Science: Ride Matching for peer-to-peer Ride Sharing: A Review and Future Directions.” Service Science 12 (2–3): 44–60. doi:10.1287/serv.2020.0258.
   Web of Science ®Google Scholar
• Vidal, T., T. G. Crainic, M. Gendreau, and C. Prins. 2013. “Heuristics for Multi Attribute Vehicle Routing Problems: A Survey and Synthesis.” European Journal of Operational Research 231 (1): 1–21. doi:10.1016/j.ejor.2013.02.053.
   Web of Science ®Google Scholar
• Vidal, T., T. G. Crainic, M. Gendreau, and C. Prins. 2014. “A Unified Solution Framework for multi-attribute Vehicle Routing Problems.” European Journal of Operational Research 234 (3): 658–673. doi:10.1016/j.ejor.2013.09.045.
   Web of Science ®Google Scholar
• Vidal, T., G. Laporte, and P. Matl. 2020. “A Concise Guide to Existing and Emerging Vehicle Routing Problem Variants.” European Journal of Operational Research 286 (2): 401–416.
   Web of Science ®Google Scholar
• Wang, X. (2013). Optimizing ride matches for dynamic ride-sharing systems. PhD thesis, Georgia Institute of Technology.
   Google Scholar