A two-stage hybrid ant colony algorithm for multi-depot half-open time-dependent electric vehicle routing problem

Abstract

Abstract This article presents a detailed investigation into the Multi-Depot Half-Open Time-Dependent Electric Vehicle Routing Problem (MDHOTDEVRP) within the domain of urban distribution, prompted by the growing urgency to mitigate the environmental repercussions of logistics transportation. The study first surmounts the uncertainty in Electric Vehicle (EV) range arising from the dynamic nature of urban traffic networks by establishing a flexible energy consumption estimation strategy. Subsequently, a Mixed-Integer Programming (MIP) model is formulated, aiming to minimize the total distribution costs associated with EV dispatch, vehicle travel, customer service, and charging operations. Given the unique attributes intrinsic to the model, a Two-Stage Hybrid Ant Colony Algorithm (TSHACA) is developed as an effective solution approach. The algorithm leverages enhanced K-means clustering to assign customers to EVs in the first stage and employs an Improved Ant Colony Algorithm (IACA) for optimizing the distribution within each cluster in the second stage. Extensive simulations conducted on various test scenarios corroborate the economic and environmental benefits derived from the MDHOTDEVRP solution and demonstrate the superior performance of the proposed algorithm. The outcomes highlight TSHACA’s capability to efficiently allocate EVs from different depots, optimize vehicle routes, reduce carbon emissions, and minimize urban logistic expenditures. Consequently, this study contributes significantly to the advancement of sustainable urban logistics transportation, offering valuable insights for practitioners and policy-makers.

Keywords

• Electric vehicle routing problem
• Time-varying vehicle speed
• K-means clustering
• Improved ant colony algorithm
• Multi-depot half-open joint distribution