A decomposition-based approach for large-scale pickup and delivery problems

With the advent of self-driving cars, experts envision autonomous mobility-on-demand services as a promising solution to improve the status quo in overloaded transportation systems. In this context, we are interested in solving very large-scale pickup and delivery routing problems that arise in the context of on-demand mobility. We provide an algorithmic framework that sets a new state of the art in solving instances with more than 20,000 requests. Our framework comprises a decomposition based matheuristic, an iterative local search (ILS), and a hybrid algorithm that uses the matheuristic to warmstart the ILS. We provide thorough computational analyses of each algorithm’s performance, advantages, and disadvantages. Moreover, we show that our algorithmic framework allows to improve upon the state of the art for existing large-scale benchmark instances. We round off our analyses by providing managerial insights based on system improvement bounds from a full-information perspective, analyzing a real-world case study with more than 20,000 requests.