Bi-objective speed and load-dependent multi-depot electric vehicle routing problem with half-open rotations: an exact and heuristic algorithms
Аннотация
This paper addresses a novel variant of Multi-Depot Electric Vehicle Routing Problem in which a finite number of EVs with limited capacity distribute orders to designated customers. Each EV may depart from and return to different depots, can be used multiple times, and be recharged at either recharging stations or depots. EVs operate under adjustable and discrete speed modes, where lower speeds result in lower $${CO}_{2}$$ emissions—modeled as a function of both speed and vehicle load. Customers place their orders with specific due dates, failing to meet leads to tardiness penalty. Higher speed modes can be chosen to avoid tardiness, though at the cost of increased $${CO}_{2}$$ emissions. Therefore, we simultaneously consider two contradicting objectives, minimizing total $${CO}_{2}$$ emission and total tardiness penalty. Operational decisions involve determining both the customer visitation sequence and the travel speed for each segment. Since the objectives are incommensurable or prioritizing them is challenging, we introduce bi-objective optimization techniques to provide pareto (non-dominated) solutions. To this end, we formulate the problem as a bi-objective mixed-integer linear program and implement Augmented ε-Constraint (Augmecon) method. Due to problem intractability, we develop Non-dominated Sorting Genetic Algorithm-II (NSGA-II) and Improved Multi-Directional Local Search (IMDLS). Augmecon exhibits better performance versus metaheuristics in terms of Quality Metric and Hypervolume Index for test instances involving 5–7 customers, derived from recent literature. Considering all small-sized instances, IMDLS outperforms NSGA-II. In all large-sized instances, while NSGA-II shows favorable performance against its counterpart, IMDLS beats NSGA-II for instances in which customers are geographically clustered.