Solving a selective dial-a-ride problem with logic-based Benders decomposition

Abstract

Today's society is facing an ever-growing demand for mobility. To a high degree these needs can be fulfilled by individual and public transport. People that do not have access to the former and cannot use the latter require additional means of transportation. This is where dial-a-ride services come into play. The dial-a-ride problem considers transportation requests of people from pick-up to drop-off locations. Users specify time windows with respect to these points. Requests are served by a given vehicle fleet with limited capacity and tour duration per vehicle. Moreover, user inconvenience considerations are taken into account by limiting the travel time between origin and destination for each request.

Previous research on the dial-a-ride problem primarily focused on serving a given set of requests with a fixed-size vehicle fleet at minimal traveling costs. It is assumed that the request set is sufficiently small to be served by the available vehicles. We consider a different scenario in which a maximal number of requests shall be served under the given constraints, i.e., it is no longer guaranteed that all requests can be accepted. For this new problem variant we propose a compact mixed integer linear programming model as well as algorithms based on Benders decomposition. In particular, we employ logic-based Benders decomposition and branch-and-check using mixed integer linear programming and constraint programming algorithms. We consider different variants on how to generate Benders cuts as well as heuristic boosting techniques and different types of valid inequalities. Computational experiments illustrate the effectiveness of the suggested algorithms.