Neural Network-Based Metaheuristic Parameterization with Application to the Vehicle Matching Problem in Ride-Hailing Services

Abstract

The majority of transportation problems include optimizing some sort of cost function. These optimization problems are often NP-hard and have an exponential increase in computation time with the increase in the model size. The problem of matching vehicles to passenger requests in ride hailing (RH) contexts typically falls into this category.Metaheuristics are often utilized for such problems with the aim of finding a global optimal solution. However, such algorithms usually include lots of parameters that need to be tuned to obtain a good performance. Typically multiple simulations are run on diverse small size problems and the parameters values that perform the best on average are chosen for subsequent larger simulations.In contrast to the above approach, we propose training a neural network to predict the parameter values that work the best for an instance of the given problem. We show that various features, based on the problem instance and shareability graph statistics, can be used to predict the solution quality of a matching problem in RH services. Consequently, the values corresponding to the best predicted solution can be selected for the actual problem. We study the effectiveness of above described approach for the static assignment of vehicles to passengers in RH services. We utilized the DriveNow data from Bavarian Motor Works (BMW) for generating passenger requests inside Munich, and for the metaheuristic, we used a large neighborhood search (LNS) algorithm combined with a shareability graph.