Heuristic Algorithms for Heterogeneous and Multi-Trip Electric Vehicle Routing Problem with Pickup and Delivery

Abstract

In light of the widespread use of electric vehicles for urban distribution, this paper delves into the electric vehicle routing problem (EVRP): specifically addressing multiple trips per vehicle, diverse vehicle types, and simultaneous pickup and delivery. The primary objective is to minimize the overall cost, which encompasses travel expenses, waiting times, recharging costs, and fixed vehicle costs. The focal problem is formulated as a heterogeneous and multi-trip electric vehicle routing problem with pickup and delivery (H-MT-EVRP-PD). Additionally, we introduce two heuristic algorithms to efficiently approximate solutions within a reasonable computational time. The variable neighborhood search (VNS) algorithm and the adaptive large neighborhood search (ALNS) algorithm are presented and compared based on our computational experiences with both. Through solving a series of large-scale real-world instances for the H-MT-EVRP-PD and smaller instances using an exact method, we demonstrate the efficacy of the proposed approaches.

Keywords

• electric vehicle routing
• heterogeneous fleet
• multi-trip
• pickup and delivery
• heuristics