Genetic Programming Hyper-Heuristic for the Dynamic Electric Dial-a-Ride Problem

Abstract

This paper studies the Dynamic Electric Dial-A-Ride Problem (DEDARP), which is a combinatorial optimisation problem that has applications in real-world ridesharing services with electric vehicles. In addition to the challenges from classical scheduling and route planning, we consider here the extra challenge of making real-time dispatching decisions in dynamic environments with new requests arriving over time and selecting proper times for the vehicles to recharge. To solve DEDARP effectively, we propose a Genetic Programming Hyper-Heuristic (GPHH) that evolves heuristics/policies to dispatch vehicles in real time. We have developed a simulation process that generates a solution for any given instance by two policies, one for vehicle allocation and the other for request allocation, and design fitness evaluations based on the simulation. Moreover, we propose a multi-tree GP to evolve these two policies simultaneously, which makes use of advanced terminals to comprehensively represent the state. Experimental results on a wide range of instances show that GPHH can evolve effective policies that make significantly better real-time dispatching decisions than human-designed policies based on prior knowledge.