Search Space Reduction Through Machine Learning for the Electric Autonomous Dial-A-Ride Problem

Abstract

The complexity of combinatorial optimization problems typically leads to a steep performance decrease of solving approaches with increasing problem size. We explore the usage of machine learning (ML) to substantially reduce the search space size of large problem instances by predicting and removing unpromising parts in order to accelerate the subsequent solving process. More specifically, we explore graph sparsening techniques for the electric autonomous dial-a-ride problem (E-ADARP), where self-driving electric vehicles are used to provide an efficient and sustainable ride-sharing service by serving customer transportation requests between pickup and drop-off locations within specified time windows. Approaches utilizing support vector machines as well as gradient boosted trees are compared to and also combined with a common k-nearest neighbor heuristic. Our goal is to boost the performance of a state-of-the-art large neighborhood search for the E-ADARP to make it well applicable to instances with up to 5200 requests and 260 vehicles. Our ML models are trained on representative instances and close-to-optimal solutions obtained from excessively long runs in a weakly supervised fashion. We uncover challenges, a fundamental limitation, and benefits of this approach and are able to achieve the intended scalability.