Heterogeneous Electric Vehicle Routing Problem with Multiple Compartments and Multiple Trips for the Collection of Classified Waste

Abstract

This paper studies the collection of classified waste using electric commercial vehicles (ECVs). The fleet of ECVs is heterogeneous, and ECVs have separated compartments, namely, they have different capacities for each type of waste. Each ECV is allowed to deliver multiple times and can be recharged more than once in public recharging stations during its route. A mathematical model is proposed for the heterogeneous electric vehicle routing problem with multiple compartments, multiple trips, and time windows (HEVRP-MCMT). The objective of the problem is to minimize the vehicle fixed cost and variable energy consumption cost. A hybrid ant colony optimization (ACO) with variable neighborhood search (VNS) is developed and applied to a number of problem instances and a real-life instance. Numerical results show that, for small-scale problem instances, our approach finds better or the same optimal solutions in a significantly shorter computational time than CPLEX; for large-scale problem instances, our approach outperforms two meta-heuristics. Experiments on a real-life problem instance show that using a fleet of multicompartment vehicles can save considerable cost compared with using single-compartment vehicles only.

Keywords

• collection of classified waste
• electric vehicle routing problem
• ant colony optimization
• variable neighborhood search