Bilevel large neighborhood search for the electric autonomous dial-a-ride problem

Abstract

The electric autonomous dial-a-ride problem (E-ADARP) represents a challenging and practically relevant extension of the dial-a-ride problem, which takes electric vehicle charging into account. It introduces battery constraints and the option to recharge vehicles at different charging stations. The present paper proposes a bilevel large neighborhood search approach (BI-LNS) for the E-ADARP. In the outer level of the proposed approach, charging sessions are inserted in the routes of vehicles and in the inner level, the pick-up and drop-off locations of the requests are inserted. In numerical experiments, it is shown that BI-LNS is able to outperform existing approaches on a number of common E-ADARP benchmark instances. Furthermore, the scalability of BI-LNS is evaluated on a set of large problem instances. The results show that the proposed approach is able to find feasible solutions within five minutes for problem instances with up to a few thousand transportation requests.

Keywords

• Dial-a-ride problem
• Large neighborhood search
• Electric vehicles