无接触式“卡车+无人机”联合配送问题研究

Research on Contactless “Truck+Drone” Joint Distribution Problem

新型冠状病毒(简称“新冠”)因其高传染性,在隔离措施下进行应急物资配送时避免接触是一大难题。考虑无人机具有无人参与,可做到无接触的特点,提出“卡车+无人机”联合配送模式。构造三阶段求解方法,第一阶段,采用改进K-means算法对客户点进行归类,选出卡车配送点;第二阶段,采用模拟退火算法以旅行商问题为背景对卡车配送路线进行确定;第三阶段提出尾部客户判断法改进模拟退火算法对无人机飞行路线进行确定。三个阶段均采用C++编程进行实现。算例测算结果表明,“卡车+无人机”联合配送模式相较于卡车单独配送可有效提高配送效率,减少配送成本;尾部客户判断法可显著提高算法收敛速度。

Novel Coronavirus is highly contagious.Avoiding contact when delivering emergency supplies under isolation measures is a big problem.This article considered that drones had the characteristics of unattended and could be contactless,and proposed a“truck+drone”joint delivery model.A three-stage solution method was constructed.In the first stage,an improved K-means algorithm was used to classify customer points,and truck delivery points were selected.In the second stage,simulated annealing algorithm was used to determine truck delivery routes based on the TSP problem.The third stage proposed the tail customer judgment method to improve the simulated annealing algorithm to determine the flight route of the drone.The three stages were all implemented using C++programming.The calculation results show that the“truck+drone”combined distribution model can effectively improve the distribution efficiency and reduce the distribution cost compared with the truck alone.The tail customer judgment method can significantly improve the speed of algorithm convergence.