An Exact Method for a First-Mile Ridesharing Problem

References

• Agatz N, Erera A, Savelsbergh M, Wang X (2012) Optimization for dynamic ride-sharing: A review. Eur. J. Oper. Res. 223(2):295–303.Crossref, Google Scholar
• Agius M, Absi N, Feillet D, Garaix T (2022) A branch-and-price algorithm for a routing problem with inbound and outbound requests. Comput. Oper. Res. 146(October):105896.Crossref, Google Scholar
• Archetti C, Jabali O, Speranza MG (2015) Multi-period vehicle routing problem with due dates. Comput. Oper. Res. 61(September):122–134.Crossref, Google Scholar
• Baldacci R, Christofides N, Mingozzi A (2008) An exact algorithm for the vehicle routing problem based on the set partitioning formulation with additional cuts. Math. Programming 115(2):351–385.Crossref, Google Scholar
• Baldacci R, Mingozzi A, Roberti R (2011) New route relaxation and pricing strategies for the vehicle routing problem. Oper. Res. 59(5):1269–1283.Link, Google Scholar
• Balinski ML, Quandt RE (1964) On an integer program for a delivery problem. Oper. Res. 12(2):300–304.Link, Google Scholar
• Battarra M, Cordeau JF, Iori M (2014) Pickup-and-delivery problems for goods transportation. Vehicle Routing: Problems, Methods, and Applications, 2nd ed. (SIAM, Philadelphia), 161–191.Crossref, Google Scholar
• Berbeglia G, Cordeau JF, Laporte G (2012) A hybrid tabu search and constraint programming algorithm for the dynamic dial-a-ride problem. INFORMS J. Comput. 24(3):343–355.Link, Google Scholar
• Bongiovanni C, Kaspi M, Geroliminis N (2019) The electric autonomous dial-a-ride problem. Transportation Res. Part B Methodological 122(April):436–456.Crossref, Google Scholar
• Bräysy O, Gendreau M (2005a) Vehicle routing problem with time windows, part I: Route construction and local search algorithms. Transportation Sci. 39(1):104–118.Link, Google Scholar
• Bräysy O, Gendreau M (2005b) Vehicle routing problem with time windows, part II: Metaheuristics. Transportation Sci. 39(1):119–139.Link, Google Scholar
• Cattaruzza D, Absi N, Feillet D (2016) The multi-trip vehicle routing problem with time windows and release dates. Transportation Sci. 50(2):676–693.Link, Google Scholar
• Chen S, Wang H, Meng Q (2020) Solving the first-mile ridesharing problem using autonomous vehicles. Comput. Aided Civil Infrastructure Engrg. 35(1):45–60.Crossref, Google Scholar
• Chen W, Mes M, Schutten M, Quint J (2019) A ride-sharing problem with meeting points and return restrictions. Transportation Sci. 53(2):401–426.Link, Google Scholar
• Cherkesly M, Desaulniers G, Laporte G (2015) Branch-price-and-cut algorithms for the pickup and delivery problem with time windows and last-in-first-out loading. Transportation Sci. 49(4):752–766.Link, Google Scholar
• Cherkesly M, Desaulniers G, Irnich S, Laporte G (2016) Branch-price-and-cut algorithms for the pickup and delivery problem with time windows and multiple stacks. Eur. J. Oper. Res. 250(3):782–793.Crossref, Google Scholar
• Cordeau JF, Laporte G (2007) The dial-a-ride problem: Models and algorithms. Ann. Oper. Res. 153(1):29–46.Crossref, Google Scholar
• Cordeau JF, Desaulniers G, Desrosiers J, Solomon MM, Soumis F (2002) VRP with time windows. The Vehicle Routing Problem (SIAM, Philadelphia), 157–193.Crossref, Google Scholar
• Costa L, Contardo C, Desaulniers G (2019) Exact branch-price-and-cut algorithms for vehicle routing. Transportation Sci. 53(4):946–985.Link, Google Scholar
• Dabia S, Ropke S, Van Woensel T, De Kok T (2013) Branch and price for the time-dependent vehicle routing problem with time windows. Transportation Sci. 47(3):380–396.Link, Google Scholar
• de Paepe WE, Lenstra JK, Sgall J, Sitters RA, Stougie L (2004) Computer-aided complexity classification of dial-a-ride problems. INFORMS J. Comput. 16(2):120–132.Link, Google Scholar
• Desaulniers G, Desrosiers J, Solomon MM (2006) Column Generation, vol. 5 (Springer Science & Business Media, New York).Google Scholar
• Desaulniers G, Gschwind T, Irnich S (2020) Variable fixing for two-arc sequences in branch-price-and-cut algorithms on path-based models. Transportation Sci. 54(5):1170–1188.Link, Google Scholar
• Desaulniers G, Lessard F, Hadjar A (2008) Tabu search, partial elementarity, and generalized k-path inequalities for the vehicle routing problem with time windows. Transportation Sci. 42(3):387–404.Link, Google Scholar
• Fukasawa R, Longo H, Lysgaard J, De Aragão MP, Reis M, Uchoa E, Werneck RF (2006) Robust branch-and-cut-and-price for the capacitated vehicle routing problem. Math. Programming 106(3):491–511.Crossref, Google Scholar
• Furuhata M, Dessouky M, Ordóñez F, Brunet ME, Wang X, Koenig S (2013) Ridesharing: The state-of-the-art and future directions. Transportation Res. Part B Methodological 57(November):28–46.Crossref, Google Scholar
• Ghilas V, Cordeau JF, Demir E, Woensel TV (2018) Branch-and-price for the pickup and delivery problem with time windows and scheduled lines. Transportation Sci. 52(5):1191–1210.Link, Google Scholar
• Gschwind T, Drexl M (2019) Adaptive large neighborhood search with a constant-time feasibility test for the dial-a-ride problem. Transportation Sci. 53(2):480–491.Link, Google Scholar
• Gschwind T, Irnich S (2015) Effective handling of dynamic time windows and its application to solving the dial-a-ride problem. Transportation Sci. 49(2):335–354.Link, Google Scholar
• Gschwind T, Irnich S, Rothenbächer AK, Tilk C (2018) Bidirectional labeling in column-generation algorithms for pickup-and-delivery problems. Eur. J. Oper. Res. 266(2):521–530.Crossref, Google Scholar
• Ho SC, Szeto WY, Kuo YH, Leung JM, Petering M, Tou TW (2018) A survey of dial-a-ride problems: Literature review and recent developments. Transportation Res. Part B Methodological 111(May):395–421.Crossref, Google Scholar
• Irnich S (2008) Resource extension functions: Properties, inversion, and generalization to segments. OR Spectrum 30(1):113–148.Crossref, Google Scholar
• Irnich S, Desaulniers G (2005) Shortest path problems with resource constraints. Column Generation (Springer, Boston), 33–65.Crossref, Google Scholar
• Jepsen M, Petersen B, Spoorendonk S, Pisinger D (2008) Subset-row inequalities applied to the vehicle-routing problem with time windows. Oper. Res. 56(2):497–511.Link, Google Scholar
• Jiang G, Lam SK, Ning F, He P, Xie J (2019) Peak-hour vehicle routing for first-mile transportation: Problem formulation and algorithms. IEEE Trans. Intelligent Transportation Systems 21(8):3308–3321.Crossref, Google Scholar
• Kumar P, Khani A (2021) An algorithm for integrating peer-to-peer ridesharing and schedule-based transit system for first mile/last mile access. Transportation Res. Part C Emerging Tech. 122(January):102891.Crossref, Google Scholar
• Liang X, de Almeida Correia GH, An K, van Arem B (2020) Automated taxis’ dial-a-ride problem with ride-sharing considering congestion-based dynamic travel times. Transportation Res. Part C Emerging Tech. 112(March):260–281.Crossref, Google Scholar
• Long J, Tan W, Szeto W, Li Y (2018) Ride-sharing with travel time uncertainty. Transportation Res. Part B Methodological 118(December):143–171.Crossref, Google Scholar
• Lübbecke ME, Desrosiers J (2005) Selected topics in column generation. Oper. Res. 53(6):1007–1023.Link, Google Scholar
• Luo Z, Liu M, Lim A (2019) A two-phase branch-and-price-and-cut for a dial-a-ride problem in patient transportation. Transportation Sci. 53(1):113–130.Link, Google Scholar
• Lysgaard J, Letchford AN, Eglese RW (2004) A new branch-and-cut algorithm for the capacitated vehicle routing problem. Math. Programming 100(2):423–445.Crossref, Google Scholar
• Ma R, Zhang H (2017) The morning commute problem with ridesharing and dynamic parking charges. Transportation Res. Part B Methodological 106(December):345–374.Crossref, Google Scholar
• Malheiros I, Ramalho R, Passeti B, Bulhões T, Subramanian A (2021) A hybrid algorithm for the multi-depot heterogeneous dial-a-ride problem. Comput. Oper. Res. 129(May):105196.Crossref, Google Scholar
• Molenbruch Y, Braekers K, Caris A (2017) Typology and literature review for dial-a-ride problems. Ann. Oper. Res. 259(1):295–325.Crossref, Google Scholar
• Morrison DR, Jacobson SH, Sauppe JJ, Sewell EC (2016) Branch-and-bound algorithms: A survey of recent advances in searching, branching, and pruning. Discrete Optim. 19(February):79–102.Crossref, Google Scholar
• Najmi A, Rey D, Rashidi TH (2017) Novel dynamic formulations for real-time ride-sharing systems. Transportation Res. Part E Logist. Transportation Rev. 108(December):122–140.Crossref, Google Scholar
• Paquay C, Crama Y, Pironet T (2020) Recovery management for a dial-a-ride system with real-time disruptions. Eur. J. Oper. Res. 280(3):953–969.Crossref, Google Scholar
• Pecin D, Contardo C, Desaulniers G, Uchoa E (2017) New enhancements for the exact solution of the vehicle routing problem with time windows. INFORMS J. Comput. 29(3):489–502.Link, Google Scholar
• Poggi M, Uchoa E (2003) Integer program reformulation for robust branch-and-cut-and-price algorithms. Proc. Conf. Math. Program Rio Conf. Honour Nelson Maculan, 56–61.Google Scholar
• Poggi M, Uchoa E (2014) New exact algorithms for the capacitated vehicle routing problem. Vehicle Routing: Problems, Methods, and Applications, 2nd ed. (SIAM, Philadelphia), 59–86.Crossref, Google Scholar
• Righini G, Salani M (2006) Symmetry helps: Bounded bi-directional dynamic programming for the elementary shortest path problem with resource constraints. Discrete Optim. 3(3):255–273.Crossref, Google Scholar
• Righini G, Salani M (2008) New dynamic programming algorithms for the resource constrained elementary shortest path problem. Networks 51(3):155–170.Crossref, Google Scholar
• Rist Y, Forbes MA (2021) A new formulation for the dial-a-ride problem. Transportation Sci. 55(5):1113–1135.Link, Google Scholar
• Sadykov R, Uchoa E, Pessoa A (2021) A bucket graph–based labeling algorithm with application to vehicle routing. Transportation Sci. 55(1):4–28.Link, Google Scholar
• Savelsbergh MWP (1985) Local search in routing problems with time windows. Ann. Oper. Res. 4(1):285–305.Crossref, Google Scholar
• Shelbourne BC, Battarra M, Potts CN (2017) The vehicle routing problem with release and due dates. INFORMS J. Comput. 29(4):705–723.Link, Google Scholar
• Solomon MM (1987) Algorithms for the vehicle routing and scheduling problems with time window constraints. Oper. Res. 35(2):254–265.Link, Google Scholar
• Sun W, Yu Y, Wang J (2019) Heterogeneous vehicle pickup and delivery problems: Formulation and exact solution. Transportation Res. Part E Logist. Transportation Rev. 125(May):181–202.Crossref, Google Scholar
• Tafreshian A, Masoud N (2020) Trip-based graph partitioning in dynamic ridesharing. Transportation Res. Part C Emerging Tech. 114(May):532–553.Crossref, Google Scholar
• Tafreshian A, Abdolmaleki M, Masoud N, Wang H (2021) Proactive shuttle dispatching in large-scale dynamic dial-a-ride systems. Transportation Res. Part B Methodological 150(August):227–259.Crossref, Google Scholar
• Tilk C, Rothenbächer AK, Gschwind T, Irnich S (2017) Asymmetry matters: Dynamic half-way points in bidirectional labeling for solving shortest path problems with resource constraints faster. Eur. J. Oper. Res. 261(2):530–539.Crossref, Google Scholar
• Vidal T (2017) Node, edge, arc routing and turn penalties: Multiple problems-one neighborhood extension. Oper. Res. 65(4):992–1010.Link, Google Scholar
• Vidal T, Crainic TG, Gendreau M, Prins C (2014) A unified solution framework for multi-attribute vehicle routing problems. Eur. J. Oper. Res. 234(3):658–673.Crossref, Google Scholar
• Wang J, Yu Y, Tang J (2018) Compensation and profit distribution for cooperative green pickup and delivery problem. Transportation Res. Part B Methodological 113(July):54–69.Crossref, Google Scholar
• Yang W, Ke L, Wang DZ, Lam JSL (2021) A branch-price-and-cut algorithm for the vehicle routing problem with release and due dates. Transportation Res. Part E Logist. Transportation Rev. 145(January):102167.Crossref, Google Scholar
• Yao D, He S, Wang Z (2020) A new ride-sharing model incorporating the passengers’ efforts. Naval Res. Logist. 68(4):397–411.Google Scholar
• Yu Y, Wu Y, Wang J (2019) Bi-objective green ride-sharing problem: Model and exact method. Internat. J. Production Econom. 208(February):472–482.Crossref, Google Scholar
• Yu Y, Lou Q, Tang J, Wang J, Yue X (2017) An exact decomposition method to save trips in cooperative pickup and delivery based on scheduled trips and profit distribution. Comput. Oper. Res. 87(November):245–257.Crossref, Google Scholar
• Yu Y, Tang J, Li J, Sun W, Wang J (2016) Reducing carbon emission of pickup and delivery using integrated scheduling. Transportation Res. Part D Transportation Environ. 47(August):237–250.Crossref, Google Scholar
• Zhen L, Ma C, Wang K, Xiao L, Zhang W (2020) Multi-depot multi-trip vehicle routing problem with time windows and release dates. Transportation Res. Part E Logist. Transportation Rev. 135(March):101866.Crossref, Google Scholar