A machine learning-driven two-phase metaheuristic for autonomous ridesharing operations

Albareda-Sambola, 2014, The dynamic multiperiod vehicle routing problem with probabilistic information, Comput. Oper. Res., 48, 31, 10.1016/j.cor.2014.02.010 Alonso-Mora, 2017, On-demand high-capacity ride-sharing via dynamic trip-vehicle assignment, Proc. Natl. Acad. Sci., 114, 462, 10.1073/pnas.1611675114 Archetti, 2018, A two-phase solution algorithm for the flexible periodic vehicle routing problem, Comput. Oper. Res., 99, 27, 10.1016/j.cor.2018.05.021 Attanasio, 2004, Parallel Tabu search heuristics for the dynamic multi-vehicle dial-a-ride problem, Parallel Comput., 30, 377, 10.1016/j.parco.2003.12.001 Bengio, 2021, Machine learning for combinatorial optimization: A methodological tour d’horizon, European J. Oper. Res., 290, 405, 10.1016/j.ejor.2020.07.063 Beojone, 2021, On the inefficiency of ride-sourcing services towards urban congestion, Transp. Res. C, 124, 10.1016/j.trc.2020.102890 Berbeglia, 2010, Dynamic pickup and delivery problems, European J. Oper. Res., 202, 8, 10.1016/j.ejor.2009.04.024 Bergstra, 2012, Random search for hyper-parameter optimization, J. Mach. Learn. Res., 13, 281 Bertsimas, 2017, Optimal classification trees, Mach. Learn., 106, 1039, 10.1007/s10994-017-5633-9 Bertsimas, 2019, Online vehicle routing: The edge of optimization in large-scale applications, Oper. Res., 67, 143, 10.1287/opre.2018.1763 Bertsimas, 2007, Classification and regression via integer optimization, Oper. Res., 55, 252, 10.1287/opre.1060.0360 Bonami, 2018, Learning a classification of mixed-integer quadratic programming problems, 595 Bonfietti, 2015, Embedding decision trees and random forests in constraint programming, 74 Bongiovanni, 2020 Bongiovanni, 2019, The electric autonomous dial-a-ride problem, Transp. Res. B, 122, 436, 10.1016/j.trb.2019.03.004 Braekers, 2014, Exact and meta-heuristics approach for a general heterogeneous dial-a-ride problem with multi depots, Transp. Res. B, 67, 166, 10.1016/j.trb.2014.05.007 Breiman, 1996, Bagging predictors, Mach. Learn., 24, 123, 10.1007/BF00058655 Breiman, 2001, Random forests, Mach. Learn., 45, 5, 10.1023/A:1010933404324 Breiman, 2017 Burke, 2013, Hyper-heuristics: A survey of the state of the art, J. Oper. Res. Soc., 64, 1695, 10.1057/jors.2013.71 Chen, 2004 Chen, 2019, Learning to perform local rewriting for combinatorial optimization Cordeau, 2003, A tabu search heuristic for the static multi-vehicle dial-a-ride problem, Transp. Res. B, 37, 579, 10.1016/S0191-2615(02)00045-0 Cordeau, 2007, The dial-a-ride probelm: models and algorithms, Ann. Oper. Res., 153, 29, 10.1007/s10479-007-0170-8 Cordeau, 2001, A unified tabu search heuristic for vehicle routing problems with time windows, J. Oper. Res. Soc., 52, 928, 10.1057/palgrave.jors.2601163 Coslovich, 2006, A two-phase insertion technique of unexpected customers for a dynamic dial-a-ride problem, European J. Oper. Res., 175, 1605, 10.1016/j.ejor.2005.02.038 Diana, 2004, A new regret insertion heuristic for solving large-scale dial-a-ride problems with time windows, Transp. Res. B, 38, 539, 10.1016/j.trb.2003.07.001 Dunning, 2017, JuMP: A modeling language for mathematical optimization, SIAM Rev., 59, 295, 10.1137/15M1020575 Elshaer, 2020, A taxonomic review of metaheuristic algorithms for solving the vehicle routing problem and its variants, Comput. Ind. Eng., 140, 10.1016/j.cie.2019.106242 Ferrucci, 2015, A general approach for controlling vehicle en-route diversions in dynamic vehicle routing problems, Transp. Res. B, 77, 76, 10.1016/j.trb.2015.03.003 Ferrucci, 2016, Pro-active real-time routing in applications with multiple request patterns, European J. Oper. Res., 253, 356, 10.1016/j.ejor.2016.02.016 Ferrucci, 2013, A pro-active real-time control approach for dynamic vehicle routing problems dealing with the delivery of urgent goods, European J. Oper. Res., 225, 130, 10.1016/j.ejor.2012.09.016 Funke, 2005, Local search for vehicle routing and scheduling problems: Review and conceptual integration, J. Heuristics, 11, 267, 10.1007/s10732-005-1997-2 Gao, 2020 Goeke, 2015, Routing a mixed fleet of electric and conventional vehicles, European J. Oper. Res., 245, 81, 10.1016/j.ejor.2015.01.049 Gomes, 2001, Algorithm portfolios, Artificial Intelligence, 126, 43, 10.1016/S0004-3702(00)00081-3 Gschwind, 2019, Adaptive large neighborhood search with a constant-time feasibility test for the dial-a-ride problem, Transp. Sci., 53, 480, 10.1287/trsc.2018.0837 Gunluk, 2016 Hastie, 2009 Ho, 2018, A survey of dial-a-ride problems: Literature review and recent developments, Transp. Res. B, 111, 395, 10.1016/j.trb.2018.02.001 Hottung, 2019 Hyland, 2020, Operational benefits and challenges of shared-ride automated mobility-on-demand services, Transp. Res. A, 134, 251 Ichoua, 2006, Exploiting knowledge about future demands for real-time vehicle dispatching, Transp. Sci., 40, 211, 10.1287/trsc.1050.0114 Jaw, 1986, A heuristic algorithm for the multi-vehicle advance request dial-a-ride problem with time windows, Transp. Res. B, 20, 243, 10.1016/0191-2615(86)90020-2 Jun, 2019, Learning dispatching rules using random forest in flexible job shop scheduling problems, Int. J. Prod. Res., 57, 3290, 10.1080/00207543.2019.1581954 Kerschke, 2019, Automated algorithm selection: Survey and perspectives, Evol. Comput., 27, 3, 10.1162/evco_a_00242 Kruber, 2017, Learning when to use a decomposition, 202 Larsen, 2021, Predicting tactical solutions to operational planning problems under imperfect information, INFORMS J. Comput., 34, 227, 10.1287/ijoc.2021.1091 Lerman, 1984, A note on the calculation and interpretation of the gini index, Econom. Lett., 15, 363, 10.1016/0165-1765(84)90126-5 Li, 2016, An adaptive large neighborhood search heuristic for the share-a-ride problem, Comput. Oper. Res., 66, 170, 10.1016/j.cor.2015.08.008 Liaw, 2002, Classification and regression by randomforest, R News, 2, 18 Liu, 2019, Exploring demand patterns of a ride-sourcing service using spatial and temporal clustering, 1 Lodi, 2017, On learning and branching: a survey, Top, 25, 207, 10.1007/s11750-017-0451-6 Lu, 2019, A learning-based iterative method for solving vehicle routing problems Malitsky, 2013, Algorithm portfolios based on cost-sensitive hierarchical clustering Mann, 1947, On a test of whether one of two random variables is stochastically larger than the other, Ann. Math. Stat., 50, 10.1214/aoms/1177730491 Marković, 2015, Optimizing dial-a-ride services in maryland: benefits of computerized routing and scheduling, Transp. Res. C, 55, 156, 10.1016/j.trc.2015.01.011 Masmoudi, 2016, Three effective metaheuristics to solve the multi-depot multi-trip heterogeneous dial-a-ride problem, Transp. Res. E, 96, 60, 10.1016/j.tre.2016.10.002 Molenbruch, 2017, Multi-directional local search for a bi-objective dial-a-ride problem in patient transportation, Comput. Oper. Res., 77, 58, 10.1016/j.cor.2016.07.020 Nabian, 2019, Predicting near-term train schedule performance and delay using bi-level random forests, Transp. Res. Rec., 2673, 564, 10.1177/0361198119840339 Nikolaev, 2010, Simulated annealing, 1 Parragh, 2011, Introducing heterogeneous users and vehicles into models and algorithms for the dial-a-ride problem, Transp. Res. C, 19, 912, 10.1016/j.trc.2010.06.002 Parragh, 2010, Variable neighborhood search for the dial-a-ride problem, Comput. Oper. Res., 37, 1129, 10.1016/j.cor.2009.10.003 Parragh, 2009, A heuristic two-phase solution approach for the multi-objective dial-a-ride problem, Netw. Int. J., 54, 227 Peled, 2019 Pelletier, 2017, Battery degradation and behaviour for electric vehicles: Review and numerical analyses of several models, Transp. Res. B, 103, 158, 10.1016/j.trb.2017.01.020 Pisinger, 2010, Large neighborhood search, 399 Potvin, 1993, A parallel route building algorithm for the vehicle routing and scheduling problem with time windows, European J. Oper. Res., 66, 331, 10.1016/0377-2217(93)90221-8 Ritzinger, 2021, Comparison of anticipatory algorithms for a dial-a-ride problem, European J. Oper. Res. Ropke, 2006, An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows, Transp. Sci., 40, 455, 10.1287/trsc.1050.0135 Sacramento, 2019, An adaptive large neighborhood search metaheuristic for the vehicle routing problem with drones, Transp. Res. C, 102, 289, 10.1016/j.trc.2019.02.018 Savelsbergh, 1992, The vehicle routing problem with time windows: Minimizing route duration, ORSA J. Comput., 4, 146, 10.1287/ijoc.4.2.146 Schilde, 2011, Metaheuristics for the dynamic stochastic dial-a-ride problem with expected return transports, Comput. Oper. Res., 38, 1719, 10.1016/j.cor.2011.02.006 Schilde, 2014, Integrating stochastic time-dependent travel speed in solution methods for the dynamic dial-a-ride problem, European J. Oper. Res., 238, 18, 10.1016/j.ejor.2014.03.005 Shaw, 1997, 46 Simonetto, 2019, Real-time city-scale ridesharing via linear assignment problems, Transp. Res. C, 101, 208, 10.1016/j.trc.2019.01.019 Vinyals, 2015, Pointer networks Weisstein, 2020 Wu, 2017, A comparative study on machine learning algorithms for smart manufacturing: tool wear prediction using random forests, J. Manuf. Sci. Eng., 139, 1, 10.1115/1.4036350 Wu, 2021, Learning improvement heuristics for solving routing problems, IEEE Trans. Neural Netw. Learn. Syst., 1 Zalesak, 2021, Real time operation of high-capacity electric vehicle ridesharing fleets, Transp. Res. C, 133, 10.1016/j.trc.2021.103413 Zhang, 2021, Learning-based branch-and-price algorithms for the vehicle routing problem with time windows and two-dimensional loading constraints, INFORMS J. Comput., 34, 1419, 10.1287/ijoc.2021.1110