无人机
启发式
计算机科学
皮卡
卡车
有效载荷(计算)
布线(电子设计自动化)
车辆路径问题
水准点(测量)
整数规划
数学优化
模拟退火
启发式
运筹学
工程类
计算机网络
算法
网络数据包
汽车工程
数学
人工智能
大地测量学
地理
操作系统
遗传学
图像(数学)
生物
作者
Shanshan Meng,Xianguang Guo,Dong Li,Guoquan Liu
标识
DOI:10.1016/j.tre.2022.102990
摘要
Unmanned aerial vehicles, commonly known as drones, have gained wide attention in recent years due to their potential of revolutionizing logistics and transportation. In this paper, we consider a variant of the combined truck-drone routing problem, which allows drones to serve multiple customers and provide both pickup and delivery services in each flight. The problem concerns the deployment and routing of a fleet of trucks, each equipped with a supporting drone, to serve all the pickup and delivery demands of a set of customers with minimal total cost. We explicitly model the energy consumption of drones by their travel distance, curb weight and the carrying weight of parcels, develop a mixed-integer linear programming model (MILP) with problem-customized inequalities, and show a sufficient condition for the benefit of the combined truck-drone mode over the truck-only mode. Considering the complexity of the MILP model, we propose a novel two-stage heuristic algorithm in which a maximum payload method is developed to construct the initial solutions, followed by an improved simulated annealing algorithm with problem-specific neighborhood operators and tailored acceleration strategies. Furthermore, two methods are developed to test the feasibility for both trucks and drones in each solution. The proposed algorithm outperforms two benchmark heuristics in our numerical experiments, which also demonstrate the considerable benefit of allowing multiple visits and both pickup and delivery operations in each drone flight.
科研通智能强力驱动
Strongly Powered by AbleSci AI