Heuristics for large instances of the dynamic e-ADARP

The dynamic electric autonomous dial-a-ride problem (e-ADARP) is an extended version of the traditional dial-a-ride problem (DARP). It consists in a ride-sharing service executed by a fleet of electric and autonomous shuttles where the requests appear online. In this report we are presenting a method that allows to tackle large instances of the dynamic e-ADARP. To efficiently answer an incoming request can be time-consuming which can decrease the level of service. There is a lot of feasibility checks to process when trying to insert a new request that is composed of a pick-up and a drop-off node. We propose in our study several strategies to improve responsiveness of an already existing algorithm by decreasing the number of feasible insertions to test without decreasing the quality of the final solution. It means to reduce computation time without decreasing the acceptation rate and still respecting the fundamental constraints of the e-ADARP. The results show improvement in terms of acceptance rate or/and CPU time.