Inverse Optimization for Routing Problems

References

• Akhtar SA, Kolarijani AS, Mohajerin Esfahani P (2021) Learning for control: An inverse optimization approach. IEEE Control Systems Lett. 6:187–192.Crossref, Google Scholar
• Amazon.com Inc. (2021a) Amazon last mile routing research challenge. Accessed July 5, 2024, https://routingchallenge.mit.edu/.Google Scholar
• Amazon.com Inc. (2021b) Amazon routing challenge: Scoring. Accessed July 5, 2024, https://github.com/MIT-CAVE/rc-cli/tree/main/scoring.Google Scholar
• Amazon.com Inc. (2021c) Last-mile routing challenge team performance and leaderboard. Accessed July 5, 2024, https://routingchallenge.mit.edu/last-mile-routing-challenge-team-performance-and-lead erboard/.Google Scholar
• Arslan O, Abay R (2021) Data-driven vehicle routing in last-mile delivery. Winkenbach M, Parks S, Noszek J, eds. Tech. Proc. Amazon Last Mile Routing Res. Challenge (MIT Center for Transportation & Logistics, Cambridge, MA), 65–78.Google Scholar
• Aswani A, Shen Z-J, Siddiq A (2018) Inverse optimization with noisy data. Oper. Res. 66(3):870–892.Link, Google Scholar
• Bärmann A, Pokutta S, Schneider O (2017) Emulating the expert: Inverse optimization through online learning. Precup D, The YW, eds. Proc. Internat. Conf. Machine Learn. (JMLR.org), 400–410.Google Scholar
• Bertsekas DP (2008) Nonlinear Programming (Athena Scientific, Belmont, MA).Google Scholar
• Bertsekas DP (2015) Convex Optimization Algorithms (Athena Scientific, Belmont, MA).Google Scholar
• Bodur M, Chan TCY, Zhu IY (2022) Inverse mixed integer optimization: Polyhedral insights and trust region methods. INFORMS J. Comput. 34(3):1471–1488.Link, Google Scholar
• Burton D, Toint PL (1992) On an instance of the inverse shortest paths problem. Math. Programming 53(1):45–61.Crossref, Google Scholar
• Canoy R, Guns T (2019) Vehicle routing by learning from historical solutions. Proc. 25th Internat. Conf. Principles Practice Constraint Programming (Springer, Berlin, Heidelberg), 54–70.Google Scholar
• Canoy R, Mandi J, Bucarey V (2021) TSP with learned zone preferences for last mile vehicle dispatching. Winkenbach M, Parks S, Noszek J, eds. Tech. Proc. Amazon Last Mile Routing Res. Challenge (MIT Center for Transportation & Logistics, Cambridge, MA), 361–370.Google Scholar
• Canoy R, Bucarey V, Mandi J, Guns T (2021) Learn-n-route: Learning implicit preferences for vehicle routing. Preprint, submitted January 11, https://arxiv.org/abs/2101.03936.Google Scholar
• Canoy R, Bucarey V, Mandi J, Mulamba M, Molenbruch Y, Guns T (2024) Probability estimation and structured output prediction for learning preferences in last mile delivery. Comput. Industrial Engrg. 189:109932.Crossref, Google Scholar
• Chan TCY, Mahmood R, Zhu IY (2023) Inverse optimization: Theory and applications. Oper. Res., ePub ahead of print December 19, https://doi.org/10.1287/opre.2022.0382.Link, Google Scholar
• Chow JYJ, Recker WW (2012) Inverse optimization with endogenous arrival time constraints to calibrate the household activity pattern problem. Transportation Res. Part B Methodological 46(3):463–479.Crossref, Google Scholar
• Chow JYJ, Ritchie SG, Jeong K (2014) Nonlinear inverse optimization for parameter estimation of commodity-vehicle-decoupled freight assignment. Transportation Res. Part E Logist. Transportation Rev. 67:71–91.Crossref, Google Scholar
• Chung Y, Demange M (2012) On inverse traveling salesman problems. 4OR 10(2):193–209.Google Scholar
• Contreras I, Le D (2021) Learning routing models with cluster precedence constraints. Winkenbach M, Parks S, Noszek J, eds. Tech. Proc. Amazon Last Mile Routing Res. Challenge (MIT Center for Transportation & Logistics, Cambridge, MA), 163–180.Google Scholar
• Cook W, Held S, Helsgaun K (2022) Constrained local search for last-mile routing. Transportation Sci. 58(1):12–26.Link, Google Scholar
• Dantzig G, Fulkerson R, Johnson S (1954) Solution of a large-scale traveling-salesman problem. J. Oper. Res. Soc. Amer. 2(4):393–410.Link, Google Scholar
• Duan Z, Wang L (2011) Heuristic algorithms for the inverse mixed integer linear programming problem. J. Global Optim. 51:463–471.Crossref, Google Scholar
• Faragó A, Szentesi Á, Szviatovszki B (2003) Inverse optimization in high-speed networks. Discrete Appl. Math. 129(1):83–98.Crossref, Google Scholar
• Fosgerau M, Frejinger E, Karlstrom A (2013) A link based network route choice model with unrestricted choice set. Transportation Res. Part B Methodological 56:70–80.Crossref, Google Scholar
• Google (2021) Traveling salesperson problem. Accessed July 5, 2024, https://developers.google.com/optimization/routing/tsp.Google Scholar
• Guo X, Mo B, Wang Q (2021) Last-mile delivery trajectory prediction using hierarchical tsp with customized cost matrix. Winkenbach M, Parks S, Noszek J, eds. Tech. Proc. Amazon Last Mile Routing Res. Challenge (MIT Center for Transportation & Logistics, Cambridge, MA), 17–29.Google Scholar
• Gurobi Optimization (2021) Traveling salesperson problem. Accessed July 5, 2024, https://www.gurobi.com/jupyter_models/traveling-salesman/.Google Scholar
• Helsgaun K (2017) An Extension of the Lin-Kernighan-Helsgaun TSP Solver for Constrained Traveling Salesman and Vehicle Routing Problems (Roskilde University, Roskilde, Denmark).Google Scholar
• Kivinen J, Warmuth MK (1997) Exponentiated gradient vs. gradient descent for linear predictors. Inform. Comput. 132(1):1–63.Google Scholar
• Lacoste-Julien S, Schmidt M, Bach F (2012) A simpler approach to obtaining an o (1/t) convergence rate for the projected stochastic subgradient method. Preprint, submitted December 20, https://arxiv.org/abs/1212.2002.Google Scholar
• Liu S, Jiang H, Chen S, Ye J, He R, Sun Z (2020) Integrating Dijkstra’s algorithm into deep inverse reinforcement learning for food delivery route planning. Transportation Res. Part E Logist. Transportation Rev. 142:102070.Crossref, Google Scholar
• Merchán D, Arora J, Pachon J, Konduri K, Winkenbach M, Parks S, Noszek J (2022) Amazon last mile routing research challenge: Data set. Transportation Sci. 58(1):8–11.Google Scholar
• Mishchenko K, Khaled A, Richtárik P (2020) Random reshuffling: Simple analysis with vast improvements. Larochelle H, Ranzato M, Hadsell R, Balcan MF, Lin H, eds. Advances in Neural Information Processing Systems, vol. 34 (Curran Associates Inc., Red Hook, NY), 17309–17320.Google Scholar
• Mohajerin Esfahani P, Shafieezadeh-Abadeh S, Hanasusanto GA, Kuhn D (2018) Data-driven inverse optimization with imperfect information. Math. Programming 167(1):191–234.Crossref, Google Scholar
• ORTEC (2022) Euro meets neurips 2022 vehicle routing competition. Accessed July 5, 2024, https://euro-neurips-vrp-2022.challenges.ortec.com/.Google Scholar
• Pitombeira-Neto AR (2021) Route sequence prediction through inverse reinforcement learning. Winkenbach M, Parks S, Noszek J, eds. Tech. Proc. Amazon Last Mile Routing Res. Challenge (MIT Center for Transportation & Logistics, Cambridge, MA), 40–51.Google Scholar
• Song J, Shukla A, Coad J (2021) Inverse reinforcement learning for learning driver utility function for package delivery routing problems. Winkenbach M, Parks S, Noszek J, eds. Tech. Proc. Amazon Last Mile Routing Res. Challenge (MIT Center for Transportation & Logistics, Cambridge, MA), 200–211.Google Scholar
• Toth P, Vigo D (2002) The Vehicle Routing Problem (SIAM, Philadelphia).Crossref, Google Scholar
• Wang L (2009) Cutting plane algorithms for the inverse mixed integer linear programming problem. Oper. Res. Lett. 37(2):114–116.Crossref, Google Scholar
• Winkenbach M, Parks S, Noszek J, eds. (2021) Tech. Proc. Amazon Last Mile Routing Res. Challenge (MIT Center for Transportation & Logistics, Cambridge, MA).Google Scholar
• Wouda NA, Lan L, Kool W (2024) PyVRP: A high-performance VRP solver package. INFORMS J. Comput., ePub ahead of print January 29, https://doi.org/10.1287/ijoc.2023.0055.Link, Google Scholar
• Wu C, Song Y, March V, Duthie E (2022) Learning from drivers to tackle the amazon last mile routing research challenge. Preprint, submitted May 10, https://arxiv.org/abs/2205.04001.Google Scholar
• Wulfmeier M, Rao D, Wang DZ, Ondruska P, Posner I (2017) Large-scale cost function learning for path planning using deep inverse reinforcement learning. Internat. J. Robotics Res. 36(10):1073–1087.Crossref, Google Scholar
• Xu SJ, Nourinejad M, Lai X, Chow JYJ (2018) Network learning via multiagent inverse transportation problems. Transportation Sci. 52(6):1347–1364.Link, Google Scholar
• Zattoni Scroccaro P (2023a) Inverse optimization for the amazon challenge. Accessed July 5, 2024, https://github.com/pedroszattoni/amazon-challenge.Google Scholar
• Zattoni Scroccaro P (2023b) InvOpt: Inverse optimization with Python. Accessed July 5, 2024, https://github.com/pedroszattoni/invopt.Google Scholar
• Zattoni Scroccaro P, Atasoy B, Mohajerin Esfahani P (2024) Learning in inverse optimization: Incenter cost, augmented suboptimality loss, and algorithms. Oper. Res. Forthcoming.Google Scholar