A Reinforcement Learning Guided Large Neighborhood Search for the Dynamic Electric Autonomous Dial-a-Ride Problem

Abstract

We consider a version of the Dynamic Electric Autonomous Dial-a-Ride Problem (DynEADARP) recently proposed and approached by means of a Genetic Programming (GP) hyperheuristic. This problem integrates the challenges of the static dial-a-ride problem with those of considering the charging of the fleet of electric vehicles and the dynamic nature of customer requests, i.e., the online aspect. The objective is to minimize the total travel time for serving all requests in a given time horizon together with penalties for late request pickups. We consider an optimization-based solution framework that utilizes a Large Neighborhood Search (LNS) for the static variant of the problem. This LNS is (re-)applied whenever new requests arrive and always considers the current state of the vehicles and all available, not yet served requests. Analyzing results of a first version in which the LNS performs in a pure myopic way that does not consider expected future requests, we observe two major weaknesses: (a) charging is often done much too late, and (b) it is not always good to head to planned pickup locations as early as possible. To address these weaknesses, we utilize reinforcement learning (RL) for learning two functions offline that are used within the LNS to incentivize earlier charging and waiting dependent on features of the current state and the expected number of future requests in a sensible way. An experimental evaluation shows that (a) the LNS-based approach can scale well to large instances with up to 10000 requests, (b) it outperforms the former GP hyperheuristic with a gap of up to 100%, and (c) the RL-guided LNS substantially improves upon the myopic LNS on instances up to 20 times larger than the training instances.