Application of Adapt-Cmsa To the Electric Vehicle Routing Problem With Simultaneous Pickup and Deliveries

Abstract

The Vehicle Routing Problem (VRP) has long been a cornerstone in combinatorial optimization, aiming to optimize the fleet of vehicles delivering goods in a transportation network. With the global shift towards sustainability, Electric Vehicles (EVs) have emerged as a green logistics alternative, leading to the Electric Vehicle Routing Problem with Simultaneous Pickup and Delivery (EVRP-SPD). This problem variant introduces the complexities of EV constraints, such as battery limitations and recharging necessities, coupled with handling delivery and pickup demands simultaneously during a single customer visit. This paper presents the application of the recent hybrid metaheuristic Construct, Merge, Solve & Adapt (CMSA) to the EVRP-SPD. Our self-adaptive version of CMSA, combined with a set covering-based mathematical formulation, offers a promising approach to efficiently tackle larger instances of the problem, aiming to provide high-quality solutions. © The Author(s), under exclusive license to Springer Nature Switzerland AG 2025.