An adaptive large neighborhood search heuristic for the green dial-a-ride problem

This chapter presents a new extension of the Dial-a-Ride Problem (DARP), in which a fleet of Alternative Fuel Vehicles (AFVs) is considered. Due to the limited driving range, the AFVs may visit some Alternative Fuel Stations to be refueled with a partial refueling quantity during its journey to serve all users' demands. The proposed variant is called the Green DARP (G-DARP). The chapter introduces a linear mixed-integer mathematical formulation of the G-DARP, and proposes an efficient Adaptive Large Neighborhood Search heuristic algorithm to solve the G-DARP. The algorithm is supported by efficient local search operators to enhance the search and improve the quality of solutions, as well as a flexible acceptance function to more explore the search space. The chapter also presents numerical experiments to demonstrate that the solution approach provides high-quality solutions for newly generated instances.