多模式下的车辆和无人机联合配送模型与优化算法

无人机已广泛用于物流配送,具有快速投递和低成本的优势.针对远离仓库中心、交通受限制客户的需求,在车机并行配送模式上引入车载无人机以服务该类客户,提出多模式下的车辆和无人机联合配送模型及其路径优化问题.该模型融合了车机协同配送模型和并行配送模型,包括搭载无人机的卡车和独立的无人机舰队.在此基础上建立以最小化交付时间为优化目标的混合整数规划模型,并设计基于知识学习策略的多算子遗传算法来提高搜索效率.实验结果表明,与传统交付方式相比,车辆与无人机联合配送模型可显著减少交付时间.在大规模数据集上,改进的遗传算法表现出更好的性能.该研究成果可为解决物流配送中的复杂动态的“最后一公里”问题提供指导和参考.     

农村电商物流下无人机与车辆协同配送路径优化研究

无人机配送正在成为解决物流末端配送难题的重要手段。无人机与车辆协同配送模式克服了无人机配送能力不足、安全性不高的弊端，是无人机参与配送的重要途径之一。针对农村电商物流“最后一公里”配送难、配送贵问题，考虑无人机与车辆协同方式、多无人机多包裹配送等约束，以配送成本最小化为目标构建混合整数规划模型并提出一种两阶段算法对无人机与车辆协同配送路径优化问题进行求解。第一阶段通过带约束的自适应K-means算法确定车辆停靠点范围，第二阶段设计爬山算子与分裂算子改进遗传算法，求得无人机与车辆配送路径。最后，通过算例实验验证了模型和算法的可行性与有效性。研究成果有望为农村电商物流末端配送降本增效提供新思路和参考价值。     

基于集群的卡车与无人机联合配送调度研究

基于集群提出卡车与无人机联合配送新模式,来解决农村地区送货上门难的问题。考虑无人机载重和续航能力,以总运营成本最小为目标建立带时间窗的混合整数规划模型,并提出两阶段算法,通过改进后的K-means算法求出卡车停靠点,采用遗传模拟退火算法优化卡车与无人机联合配送路线。将其与传统K-means算法加CPLEX结果对比,可证明算法和模型的可行性与有效性。案例分析选取江苏某农村地区来进行末端物流配送的应用研究,结果表明卡车与无人机联合配送模式与纯卡车运输模式相比可有效减少总运营成本。研究成果可为农村地区末端配送中无人机的应用提供新思路和参考价值。     

无人机骑手联合外卖配送路径优化问题研究

外卖配送是外卖业务中的重要环节,而配送成本和准时送达率是决定外卖配送质量的关键因素,因而对外卖配送路径优化问题的研究尤为重要。基于无人机骑手联合外卖配送模式,引入时空距离度量方法,以最小化送餐成本为目标建立了无人机骑手联合外卖配送的路径优化模型,设计了一种两阶段启发式算法进行求解。第一阶段使用结合K-means的遗传算法对顾客聚类,形成骑手初始路径,第二阶段分别使用改进的变邻域搜索算法和A*算法优化骑手路径和无人机送餐航迹。实验结果表明,与传统骑手配送模式相比,考虑时空距离的无人机骑手联合外卖配送模式能减少送餐成本,提高准时送达率。     

考虑交付期限的订单配送策略

近年来,一种新兴的高效同城配送服务模式迅速发展,即针对随机到达的订单实现当天从点到点送货上门具有交付期限的订单配送服务.针对具有交付期限的、随机到达的订单配送问题,考虑平台可通过自有车辆服务订单,同时也可委托第3方物流服务订单的特点,提出一种决定是否接受该订单和确定车辆服务订单集合的订单配送策略.首先,以平台的运营成本最小为目标,建立订单配送的马尔可夫决策模型;然后,分析最优策略的性质;最后,与FCFS策略和按时交付策略进行对比分析.实验结果表明:所提出订单配送策略相比于FCFS策略与按时交付策略,不仅能够降低平台的总运营成本,且能够提高顾客满意度,保证服务质量,并通过数值分析验证了所建立的模型和求解算法的有效性.     

卡车-无人机协同救灾物资避障配送问题研究

针对洪涝灾害中存在积水障碍区的卡车-无人机协同配送的最优路径及最短配送时间问题,建立了一种整数规划模型,并提出了一种两阶段启发式算法,第一阶段将积水障碍区进行二维网格化处理并确定无人机运输救灾物资时卡车的安全等待点以及各等待点无人机运送客户的集合,第二阶段提出阶段性规划算法,结合改进A*算法与非线性收敛因子的模拟退火鲸鱼算法对卡车绕积水障碍区的配送路径进行优化,在确保卡车行使安全的前提下,将A*算法的全局寻优性及鲸鱼算法的局部搜索精确性结合。解决存在积水障碍区的救灾物资配送问题,最后通过实例验证了所提出方法可以快速安全地解决洪涝灾害中救灾物资的避障配送问题。     

即时配送下无人机全自动机场分区选址模型

随着城市即时配送及餐饮业迅猛发展带来的高时效性配送热潮,配送员自身安全及配送效率的矛盾急剧突出,一种兼具安全与效率的无人机即时配送新模式应运而生。无人机全自动机场正是实现零接触式配送的落脚点。基于无人机及无人机全自动机场自身特性的约束,构建以取货时间最短为目标的选址模型,确定无人机全自动机场的选址位置及根据排队论确定机场数量。随着顾客对于无人机全自动机场取货距离的减小,无人机机场选址位置的数量也会相应增加,而每个选址位置下的机场数目变少,相对应的顾客在无人机机场前的排队等候时间会逐渐上升。     

车辆与无人机组合配送研究综述

随着无人机技术的成熟,无人机配送已成为近几年工业界和学术界共同关注的热点.由于无人机仍存在续航能力不足、空中管制等限制,车辆与无人机组合配送具有较大的发展空间.对此,研究车辆与无人机组合配送问题的5种运行模式,包括车辆与无人机协同配送、车辆与无人机并行配送、车辆支持无人机配送、无人机支持车辆配送,以及混合模式配送.根据不同运行模式的特性和应用场景,从运载工具、道路网络、节点构成、弧段约束和优化目标等方面,分析车辆与无人机组合配送问题的经典要素;并从速度比、无人机单程配送量和停靠策略等方面研究其拓展要素.介绍并对比了求解车辆与无人机组合配送问题的方法,梳理了常用的测试数据集.最后指出车辆与无人机组合配送问题未来可能的发展趋势.     

装备联合配送路径优化及算法分析

针对传统的装备配送模式存在着分区复杂、物资无法共享以及配送路径优化不合理等问题,提出了装备联合配送的方式,综合考虑配送时间、部队服务满意度和配送成本的目标,构建带时间窗的联合配送路径优化模型。并针对模型,提出了一种自适应改进遗传算法。该算法利用PFIH算法构建初始解,采用新颖的变异算子和自适应的交叉变异概率,利用relocate和2-opt进行中间解的优化,加快算法收敛。多目标权重处理采用RCA算法进行量化。最后实验证明该算法性能优良,求解高效,能够应用于军用装备联合配送的实际场景。     

基于自适应大规模邻域搜索算法的多车辆与多无人机协同配送方法

针对物流配送需求大、“最后一公里”交付困难等问题,提出带有动态能耗约束的多车辆与多无人机协同配送问题,并以最小化配送时间为目标建立混合整数规划模型(MIP).为解决该问题,设计K-means聚类和最近邻协同的初始解生成算法,并提出基于问题领域知识的自适应大规模邻域搜索算法(adaptive large neighborhood search,ALNS).在不同规模算例上的实验结果表明,所提出的算法相比于模拟退火算法、变邻域搜索算法和遗传算法在求解质量和求解效率方面都具有一定的优势,求解质量分别平均提升23.8$%$、23.3$%$和5.7$%$,表明ALNS较对比算法能够更好地平衡全局搜索和局部搜索.此外.灵敏度分析实验表明,无人机载重能力和无人机续航能力是影响包裹配送时间的两个关键因素.     

一种联合多信道分配决策的认知Mesh系统数据传输优化算法

在认知Mesh系统进行数据传输的过程中,为了提高数据包投递成功率及网络的吞吐量,减少网络延迟时间,提出一种联合多信道分配决策的认知Mesh系统数据传输优化算法(JCWN)。针对信道的干扰问题,建立了认知Mesh系统的干扰无向图,分析节点链路的网络干扰电平。在节点的路由请求阶段通过提出基于信道干扰电平的路由指标函数,并通过权重阈值来为节点链路分配干扰较小的信道。在路由选择上,联合多路由算法计算每条路由路径的信道干扰程度,为了保障节点传输数据的成功率而选择干扰程度更小的路由。实验仿真结果表明,在数据包投递成功率上,该算法相比POC算法以及基于RL的算法提高了20%以上,在提高网络吞吐量,减少延迟时间上也表现出了更好地效果。     

A variable neighborhood search for flying sidekick traveling salesman problem

The efficiency and dynamism of unmanned aerial vehicles, or drones, have presented substantial application opportunities in several industries in the last years. Notably, logistic companies have given close attention to these vehicles to reduce delivery time and operational cost. A variant of the traveling salesman problem (TSP), called the flying sidekick traveling salesman problem, was introduced involving drone‐assisted parcel delivery. The drone launches from the truck, proceeds to deliver parcels to a customer, and then is recovered by the truck at a third location. While the drone travels through a trip, the truck delivers parcels to other customers as long as the drone has enough battery to hover waiting for the truck. This work proposes a hybrid heuristic where the initial solution is created from the optimal TSP solution reached by a TSP solver. Next, an implementation of the general variable neighborhood search is employed to obtain the delivery routes of truck and drone. Computational experiments show the potential of the algorithm to improve significantly delivery time. Furthermore, we provide a new set of instances based on the well‐known traveling salesman problem library instances.     

On the Scheduling of Conflictual Deliveries in a last-mile delivery scenario with truck-carried drones

In this paper, we investigate the symbiosis between a truck and multiple drones in a last-mile package delivery scenario, introducing the Scheduling Conflictual Deliveries Problem (SCDP). From the main depot, a truck takes care of transporting a fleet of drones that will be used to deliver packages to customers. The route of the truck is predefined. Each delivery is associated with the energy cost of a drone, a reward that characterizes the priority of the delivery, and an interval between two points of the truck’s route: the point from which the drone departs (launch point) and the point at which the drone returns to the truck (rendezvous point). The objective of the SCDP is to find a scheduling for the drones that maximizes the overall reward subject to the drone’s battery capacity while ensuring that the same drone performs deliveries whose delivery intervals do not intersect. After showing that SCDP is an NP-hard problem, we devise an Integer Linear Programming (ILP) formulation for it. Furthermore, we devise a pseudo-polynomial time optimal algorithm for the single drone case and additional approximation algorithms for both the single and multiple drones case. Finally, we thoroughly compare the performances of our presented algorithms on different synthetic datasets.     

运钞车车辆路径规划策略

针对实际运钞网点数每天动态变化问题,提出一种先划分、再优化的动态运钞车路线规划策略。第一阶段先采用Dijkstra算法求出两点之间的最短路径,再利用最近邻算法和均衡工作量因子求出动态需求车辆的车辆数和每条路径上的网点;第二阶段利用前置交叉的改进遗传算法,分别优化每条路径并求出每条路径上的网点顺序,获得距离最短和时间最少的路径。实验结果表明,该策略能有效解决车辆数目和路径根据需求动态变化的问题,达到节约和合理利用资源的目的。     

基于改进遗传算法的连锁便利店配送路径优化

提出一种针对软时间窗下连锁便利店配送路径规划的带时间窗口的多染色体遗传算法。为解决单车场多车型带密集半软时间窗问题,讨论解决方案预防其陷入局部最优解。对于上述配送路径问题,提出多染色体改进遗传算法在减少车辆运输成本、惩罚成本的目标下进行最优路径求解,并为连锁便利店的路径规划案例提出车辆与路径选择的优化方案,最后将该算法与传统遗传算法进行实验对比分析。实验结果表明,本文算法在密集半软时间窗下,相比传统遗传算法明显减少了总配送成本,从而验证了本文算法的有效性。     

Applying location estimation for reliable routing in tactical unmanned ground vehicle networks

An unmanned ground vehicle (UGV) network operates as an ad hoc autonomous tactical network. In this paper, we study the deployment of a UGV network and its ability to use location estimation to provide reliable data forwarding. This analysis involves (1) location estimation to obtain realistic estimates of the node’s (UGV) spatial positions and (2) real-time path planning to obtain reliable routing among nodes using the estimates of the node positions. Conventional approaches commonly use the popular Random Waypoint (RWP) model (or its variants) as the mobility model. The RWP approach uses randomly selected node positions and has no way to cope with nodes moving in and out of transmission range. These deficiencies cause the route reliability to suffer. Our approach (1) uses an Extended Kalman Filter (EKF) for node mobility/location estimation and (2) uses a modified Ad Hoc On Demand Distance Vector (AODV) algorithm for route selection using a new routing parameter called contact time. We refer to this combined approach as the AODV-LocPred algorithm. We compare the AODV-LocPred algorithm with AODV using the RWP model. This is referred to as AODV-RWP. Our simulations show that the AODV-LocPred algorithm significantly outperforms the AODV-RWP algorithm in terms of packet delivery ratio (PDR), because it provides realistic node position estimates and it copes in a reasonable way with nodes moving in and out of transmission range. However, the AODV-LocPred incurs an increase in end-to-end delay. Nonetheless, we expect that in many real-world settings, this tradeoff is acceptable.     

考虑多投递的带无人机车辆路径规划问题研究

研究一种考虑多投递的带无人机车辆路径规划问题（VRPD-MD）,针对该问题,以执行任务车辆行驶总时间最短为目标函数,建立混合整数规划模型。为对该模型进行求解,提出一种基于遗传思想的自适应启发式算法AAGM,在该算法中,设计访问节点交叉算子和交会节点变异算子这两类邻域搜索算子,分别用于调整车辆与无人机的结合点以及车辆与无人机并行路径的访问点。此外,在AAGM算法中加入算子自适应选择机制与基于Metropolis规则的劣解接受机制,在避免算法陷入局部最优的同时加快模型收敛速度,提升算法的求解质量。基于改进的CVRP数据集对模型与算法进行验证,实验结果表明,多架次多投递的无人机配送模式较多架次单投递、单架次多投递模式更具优势,且AAGM算法能够有效求解VRPD-MD,相比NAAGM算法,增加自适应机制后的AAGM算法的平均求解时间与平均求解质量分别提高30%与1.83%。     

基于锚节点的车载网地理路由算法

车载网络存在节点移动速度快、拓扑结构变化迅速等特点,直接利用全球定位系统(GPS)进行定位存在误差大和路由连通率低等问题。因此现有的基于地理位置的路由算法包递率不高,无法提供可靠路由。提出一种基于锚节点的车载网地理路由算法(GRAN),利用城市路灯作为锚节点,车辆通过锚节点定位自身位置,结合道路网关及中心数据,建立分层次的路由结构。通过这种方式,GRAN去除了路由发现过程及全网广播,达到降低路由开销、提高路由效率和包递率的目的。利用NS-2软件,选取接近现实的城市场景仿真。实验结果证明,与典型的基于地理位置的路由协议如贪婪转发与周边转发相结合的无状态路由(GPSR)和图形源路由(GSR)协议相比,GRAN能以较低的负荷提供较低的平均时延、较高的包递率和吞吐量。