混合变邻域搜索算法求解大规模电动车辆路径优化问题

基于真实的物流场景,研究了带时间窗的多车型和多循环电动车辆路径问题.建立了一个基于路径的混合整数线性规划模型,可精确求解小规模算例.提出了将变邻域搜索算法和标签算法相结合的混合启发式算法,用以求解大规模情形.该算法提出了一种带随机因子的启发式算法构造初始解,并对时间窗和里程约束进行了松弛,使用邻域算子进行变邻域搜索,使...

Hybrid Variable Neighborhood Search algorithm for the Multi-trip and Heterogeneous-fleet Electric Vehicle Routing Problem

Based on the real business practice, the multi-trip and heterogeneous-fleet electric vehicle routing problem (MTHF-EVRP) with time windows in green logistics is studied. A path-based mixed-integer linear model is built for the precise solution to the small-scale instances. A hybrid variable neighborhood search algorithm (Hybrid VNS) combined the variable neighborhood search algorithm with the labeling algorithm is proposed for the large-scale instances. The algorithm generates a modified insertion heuristic with random factor to construct the initial solution, allows the time window and range violation, adopts the neighborhood operators for the local search, and applies a labeling algorithm to solve the fixed-route recharging problem precisely. The methods are tested on the real-world benchmark instances for MTHF-EVRP. The results on the small-scale instances show that Hybrid VNS can find the optimal solutions in a very short time. Compared with the state-of-the-art algorithm on the large-scale instances, the algorithm can significantly reduce the logistics cost and the great competitiveness of Hybrid VNS is showed.