The Multi-Visit Vehicle Routing Problem with Drones under Carbon Trading Mechanism

In the context of the carbon trading mechanism, this study investigated a multi-visit vehicle routing problem with a truck-drone collaborative delivery model. This issue involves the route of a truck fleet and drones, each truck equipped with a drone, allowing drones to provide services to multiple customers. Considering the carbon emissions during both the truck’s travel and the drone’s flight, this study established a mixed integer programming model to minimize the sum of fixed costs, transportation costs, and carbon trading costs. A two-stage heuristic algorithm was proposed to solve the problem. The first stage employed a “Scanning and Heuristic Insertion” algorithm to generate an initial feasible solution. In the second stage, an enhanced variable neighborhood search algorithm was designed with problem-specific neighborhood structures and customized search strategies. The effectiveness of the proposed algorithm was validated with numerical experiments. Additionally, this study analyzed the impact of various factors on carbon trading costs, revealing that there exists an optimal combination of drones and trucks. It was also observed that changes in carbon quotas do not affect carbon emissions but do alter the total delivery costs. These results provide insights for logistics enterprise operations management and government policy-making.