A Hybrid Ant Colony Optimization Algorithm for Green Two-Echelon Multi-compartment Vehicle Routing Problem with Time Windows

In this paper, a hybrid ant colony optimization algorithm with adaptive large neighborhood search (HACO_ALNS) is proposed to solve the green two-echelon multi-compartment Vehicle routing problem with time windows (G2E-MCVRPTW). Minimizing travel and service time costs, minimizing penalty costs, and maximizing the reduction of carbon emission costs are the objectives that the G2E-MCVRPTW needs to optimize. In the initial phase of the HACO_ALNS algorithm, customers are assigned to satellites using three-dimensional clustering. Then, based on problem characteristics, several high-quality individuals are obtained using two algorithms to initialize the pheromone concentration matrix, thereby accelerating the convergence speed of the algorithm. In the local search phase of HACO_ALNS, three local operations are proposed to enhance the algorithm’s local search capability. The route reduction operation not only searches for better solutions but also further accelerates the convergence speed of the algorithm, bringing the solution space quickly to a more optimal search space. The adaptive large neighborhood search operation efficiently conducts deep search and optimization of the solution space. A perturbation operation based on simulated annealing algorithm is designed to prevent the algorithm from being trapped in local optima. Finally, simulation experiments and algorithm comparisons demonstrate the effectiveness of the proposed HACO_ALNS algorithm.