Matheuristic for a two-echelon capacitated vehicle routing problem with environmental considerations in city logistics service

摘要

This paper addresses a two-echelon capacitated vehicle routing problem (2E-CVRP) with environmental considerations (2E-CVRP-E). A new arc-and-route-based mathematical model is constructed to formulate the problem in which the sum of drivers' wage, fuel cost, and handling cost is minimized. A matheuristic based on variable neighborhood search (VNS) and integer programming is designed to solve the 2E-CVRP-E. The integer programming in the matheuristic is used as a post-optimization technique to find better solutions missed by the VNS algorithm or to construct the least-cost first-level routes. To validate its effectiveness, the matheuristic first performs tests on 2E-CVRP instances and improves 13 current best-known solutions out of 234 instances. Then it performs tests on the 2E-CVRP-E instances modified from the 2E-CVRP. For 2E-CVRP-E instances, the total cost of the best solution found by the matheuristic is smaller than that of the best-known 2E-CVRP solution with an average relative gap of 6.37%. Computational results prove that the proposed matheuristic can find high-quality solutions for the 2E-CVRP and the 2E-CVRP-E.