Improvements in Large Neighborhood Search for the Electric Autonomous Dial-A-Ride Problem

Abstract

We consider a practical extension of the classical dial-a-ride problem (DARP) called the electric autonomous DARP where electric and autonomous vehicles provide service for transportation requests with time windows. The planning and scheduling of routes that minimize not only the vehicles’ travel cost but also the user excess ride time while considering charging requirements and operational constraints is a challenging optimization problem. In a previous work, we proposed a large neighborhood search (LNS) with a novel route evaluation approach that heuristically inserts charging stops on-the-fly as needed. Here, we go into more detail regarding the preprocessing procedure for reducing the size of instances as well as the tuning of certain LNS parameters. We further investigate this solving approach by evaluating its performance on different configurations of common benchmark instances, illustrating its successful application throughout. An analysis of the performance and impact of different repair operators provides further insights and reveals improvement opportunities.