反转卡车无人机网络问题以找到最佳配置

摘要

许多行业都在寻找方法，经济地使用配备无人机技术的卡车/铁路/轮船，以增加“最后一英里”的交付工作。虽然无人机技术比比皆是，但很少有研究根据问题的显著特征来考虑无人机的正确配置:投递密度、操作区域、无人机范围和速度。在这里，我们首先提出了卡车-无人机问题，然后将网络路由问题倒置，以便在给定的场景下，基于网络交付密度，最优情况下无人机速度和距离适合卡车。通过倒置问题，企业可以快速确定无人机配置(适当的无人机射程和速度)，以优化投递系统。此外，我们提供了一个更有用的卡车-无人机路由问题的混合整数程序版本，可以很容易地使用用于解决线性规划的标准化软件。此外，我们为支持这项工作而进行的计算元启发式和实验可供下载。这里使用的元启发式算法超过了目前在文献中发现的最佳类内算法。

1.导言

将无人机或其他平行受限资源与主要交付资产结合使用可提供潜在的性能改进，这可能证明是有益的。无人机卡车（DTSP）的基本问题可以很容易地想象为两个购物者一起工作，尽可能高效地从超市货架上取货。当一个购物者推购物车时，第二个购物者可能会在旁边散步，或者分开并平行操作取回购物车上的物品。而两个购物者可以独立地并行操作n、 有时一起走会更有效率。事实上，很明显，每个购物者都有一套最佳路线，但不那么直观的是，平行购物者的必要速度和范围会阻止任何此类优化，或者可能会显著延迟主顾。在这里，我们检查这种关系.

对于卡车-无人机(比如UPS)包裹递送系统来说，很容易想象，速度非常慢的无人机对卡车几乎没有好处。因为在几乎每一站，卡车都会无所事事地等待无人机的返回。这架笨重的无人机在一条平行路径上运送它唯一的一个包裹，不管它的射程如何，它实际上是无用的。此外，如果一架非常快速的无人机只有很短的射程，那么它在交货时间上根本不会有真正的改善。只有当无人机的射程和速度与卡车的速度正确成比例时，无人机才会成为一个有用的仆人。因此，不难想象卡车速度、无人机飞行距离、无人机飞行速度与网络配送密度之间存在最优关系。

对于这个问题，我们假设卡车可以从任何送货地点发射无人机，只携带一个包裹，然后与无人机在相邻的送货地点下游会合，而无人机在平行路径上向卡车交付。描述了这个卡车-无人机路由(图1)．

本文的其余部分如下所述。部分2讨论“最佳”情况下无人机射程和速度的倒置问题和其他理论见解3.讨论有关卡车-无人机问题的文献。部分4为混合整数规划(MIP)定义了一个更有用的版本。部分5将卡车-无人机问题作为一种进化算法(EA)类型的元启发式算法，用于进行计算实验。部分6针对文献和第节中发现的同类最佳启发式，执行EA计算实验7对研究结果进行了总结，并对未来的研究方向进行了展望。

2.系统模型:理论见解

对于一个三节点问题，结点表示将向节点进行的仓库和包裹递送和 ；然后，系统的最佳交付时间是无人机的最大时间或卡车的最大时间。通过确定卡车的速度总是1，而无人机的速度是卡车速度的倍数(或因数)，这个问题可以很容易地扩大 ．此外，由于无人机的速度作为卡车速度的系数，则当无人机速度等于无人机的射程时，存在最佳配置 ．换句话说，我们没有让无人机使用不必要的资源(射程或速度)来执行交付操作。如(图所示2）卡车发射无人机，以1个单位/距离的速度向1个单元移动，然后用无人机返回与约会。总交货时间是 ，当无人机的射程和速度相等时，存在最佳配置(和 )．

然而，大多数问题不是一辆卡车和一架无人机简单的三节点问题。对于更先进的网络问题，交付密度成为解决无人机射程和速度的关键组成部分 ．交付密度在此定义为数量每地区所需送货量( ）交货舱位的 ．

为了建立案例来求解最优速度和范围 ，我们从“最佳情况”或精益方案开始。在这种情况下，我们预计大约50%的货物将由卡车运送，50%由无人机运送。此外，在这些理想条件下，可以在操作区域内构造一组相同大小的三角形表示所有包裹交付（图3.)，其中三角形的顶点表示投递位置。我们称它为实用最好的情况．

使用这些三角形和简单的平行四边形几何，我们可以很容易地计算出最佳的无人机速度和无人机距离，在每个平行运送操作与卡车准确地在同一时间会合。在这种情况下，我们将不需要在不需要的资源上花费任何额外的费用，同时保证系统将以最佳方式执行。

为实用最好的情况系统中，我们计算出输送密度为 ．使用密度 ，然后我们替换具有 ，其中，平行四边形的面积表示为 ．由于我们在给出问题场景时给出了交付密度，我们可以将问题倒置并解决适当的无人机能力(速度( ）和范围( ））解决问题：

此外，我们进行了几个计算实验，以更好地理解精益交货和随机生成的随机情况之间的关系。对于每个场景，随机配送地点均匀分布在作业区域，无人机速度( )，范围( )，和操作区域（ ）保持不变。交货数量在操作区域内，从10次到200次交付都令人不安。在此，我们希望了解获得的改善百分比（在交付时间）通过独立卡车（无无人机）交付系统。我们发现，作为随机场景的交付密度 接近或移动到瘦溶液的递送密度 表演的时间(在一辆独立的卡车上)改进了。在这种情况下，随机生成实验的交付和路由部分问题是使用下面描述的元启发式算法解决的，而独立卡车的交付时间是使用标准tsp元启发式算法解决的。

结果（图1）4)的结果表明，随机生成场景的问题交付密度接近最优交付密度(定义为 ，无人机的速度( )，和范围( ））这是总的表演时间在不使用不需要的资源使系统过度饱和的情况下进行了改进(X- 基于Alpha和Kappa的Rho最优与问题密度rho表示的差异N和交货区域。纵坐标(y-AXIS）表示对仅卡车交付系统（TSP路由）的改进性能。该图表明，随着两个密度更接近，系统的整体性能提高。鉴于使用的良好结果实用最好的情况方法作为评估系统性能的基础，我们构建了以下最小化问题，以解决基于交付数量的适当的无人机速度和无人机射程以及操作区域的大小 ．因此，本文采用极小化问题来选择系统参数和适用于特定的问题密度 ．值得注意的是，由于问题的随机性，距离和速度的解决方案是无人机配置的适当速度和距离的较低边界:

综上所述，卡车无人机的最优参数定理如下:(我)存在最大值理论上边界对于时间改善系数，如果有，也很少达到[1］.这是基于卡车 - 无人机和仅卡车解决方案的比较： (ii)最低下边界对于卡车无人机在纯卡车上的时间改进（最坏情况），解决方案默认为纯卡车路线时间或tsp路线时间。(3)改进( ）当配送区域内均匀分布的顶点向最佳密度移动时，仅限卡车向最佳密度移动:

因此，对于交付场景，如果我们要在“最佳运行参数集”附近进行优化 ，然后通过最小化传输密度之间的差异来确定系统参数最佳密度 ．由此产生的无人机参数和两个完成参数之间的关系和成为无人机最佳配置的下限。

3.文学

今天，大量的文学存在于与之密切相关的车辆路径问题( )．在调查，报告和论文中可以找到两个问题的几种方法[2- - - - - -4］.作为一种规则问题延伸到通过添加额外的约束。这些限制包括时间窗口、优先级、范围、闲逛时间、允许车辆类型的路线段、负载配置和交通模式[5].而文献中存在将多车包括在内的问题 ，客户取货和交付问题，多个同步约束[6]，多基地车辆调度问题[7，以及多对多牛奶运行路径问题[8，目前只有少数几个研究 ，在解决最佳网络路由问题时，还没有研究解决主工具(卡车)和一个或多个辅助工具的适当配置(能力)。

处理主要工具和受限辅助工具的工作是Agatz等人的工作[1]还有穆雷和朱[9].这两位作者都提出卡车无人机问题是一种带有辅助工具的主要工具。他们的工作通过区分无人机的行驶能力（on/in），描述了现有问题与tsp问题具体版本之间的主要区别卡车以及与卡车一起在多个平行操作中操作，称为发射-交付-会合任务。在此划分之前，没有任何问题直接涉及到独特的范例。具体而言将无人机描述为与卡车由于有效载荷和距离限制而定期与卡车定期与卡车进行的并行资源。默里和楚[9]正式定义飞行助手旅行推销员问题(FSTSP)作为NP难问题。他们的研究提出了混合整数规划(MIP)方法和元启发式方法。他们还考虑了第二个类似的集线器类型的问题，该问题解决了这样的情况，即客户离仓库足够近，可以由无人机直接从仓库提供服务并行无人机调度TSP（PDSTSP）．Murray和Agatz讨论了最优最小时间路线的混合整数公式。它们暗示了这样一个事实，即无人机的射程、容量和速度都受到卡车的限制。然而，它们确实充分地解决了这种相互关系。此外，Agatz只考虑了FSTSP的一个稍微改变的版本，而没有处理PDSTSP。阿加兹和默里一样，将卡车和无人机串联起来作为一个团队，卡车发射无人机，从无人机穿越到一个单独的送货地点，然后再次与无人机会合。然而，两种方法之间的主要区别是Agatz等人[1]要求无人机和卡车沿道路网络系统横移;[未执行的约束]9]他们这样做是为了促进启发式方法的构建，这些方法具有近似值，能够保证交付系统在“纯卡车解决方案”上的最大可实现收益的界限。Murray和Chu[9]正式定义飞行助手旅行推销员问题(FSTSP)作为np困难问题。他们的研究提出了混合整数规划(MIP)和元启发式方法。他们还考虑了第二个类似的中心型问题，即客户离仓库足够近，可以由无人机直接从仓库提供服务的情况并行无人机调度TSP（PDSTSP）．

最近，Agatz等人[10]提出了一种基于动态规划的卡车-无人机问题的精确求解方法，即带无人机旅行商问题(TSP-D)。他们首先将问题建模为整数规划，然后发展了基于局部搜索和动态规划的多路径优先、聚类第二启发式算法。他们的见解表明，与文献中发现的其他数学规划方法相比，动态规划可以更好地解决更大的问题实例。它们展示了启发式的最坏情况近似比，并将性能与较小实例的最优解决方案进行了比较。他们将启发式方法应用到几个具有不同特征和大小的人工实例上，显示出与仅限卡车解决方案相比的实质性改进。

也许这里最相似的问题是Current和Schilling描述的覆盖旅行推销员的问题[11］.覆盖问题通过将“tsp”网络简化为总节点的子集来找到最短的路径。在这种情况下，如果在范围内可以到达或“覆盖”相邻节点，则可以将其分组为单个节点或站点，从而大大减少了问题的最终最优行程和排列次数。对于覆盖问题，他们提出了一种基于元启发式的解决方案来解决更大的问题集。在文献中可以找到一些对覆盖问题的概括和扩展[12］.为main tool with assisting tools, it is not enough to bypass the unvisited or ‘covered’ nodes for three reasons: (1) first, the main and assisting tool requires that the truck and drone rendezvous at the end of each operation, and thus their end of operation timing is a factor of the total time. (2) Secondly, the covered nodes ‘within-range’ are subject to the number of assisting tools fitted to the main tool. (3) And, thirdly, the range, speed, and number of assisting tools are interdependent to the node coordinates and thus determine the total possible ‘coverage’ area which may be different for each operation.

此外，辅助工具的速度和范围对系统的整体性能也很重要。在此，我们给出一种封闭的方法来确定适当的速度和范围所需的辅助工具，以获得最佳的系统性能，而不过度饱和的系统。这在目前的任何文献中都没有发现。许多其他作者创建了主/辅助工具问题的变体，但没有处理这些基本关系。

4.卡车-无人机混合整数规划

当关联的第二资源被限制在与主车辆保持一定距离时，识别并行资源卡车-无人机问题，当第二资源被分离时，它将最终在下游位置与主车辆会合。它被允许暂时与主要资源分离，但由于范围或操作限制，必须很快返回。

为了建立广义数学公式并改进该问题的可处理性和软件建模（Lingo/Lindo®），我们假设如下：（1）客户（节点）之间的数量、位置和距离是已知的和确定的，（2）车辆或车辆组访问每个节点的次数不得超过一次，（3）车辆必须沿节点之间的圆弧（边缘）移动，（4）车辆在节点位置分离并会合，而不是沿节点之间的圆弧空间移动，（5）任何车辆在必须与下游节点处的主车辆（或组）会合之前，可从组中分离以交付给节点；一旦发生会合，每辆车再次被允许分离到另一个交付节点，然后在下游节点再次会合，（6）每个交付节点有一个单元的需求；因此，一架次的无人机或卡车能够运送包裹。

鉴于我们有一架无人机( ）在主运货卡车的相邻空间内操作( )，如果无人机( ）用于交付，它应在节点上从卡车发射 ，遍历到交付节点(客户) ，在第三个节点和送货车会合 ，二进制元组变量 无人机使用路线段的标志。发射无人机后，卡车（ ）有两种选择:(1)直接从发射节点穿越到交会节点( ）如图所示（图5)和（2）遍历到另一个传递节点然后进入无人机会合节点( )．

卡车-无人机dtsp问题的材料要素可以用网络图来描述 ，哪里表示客户的交货站和表示停止点之间的边。每个顶点 和表示基数或总数停止。边缘用两个顶点来描述 ，而两条相连的边被描述为三个顶点 ，在顶点顶点在和 ．此外,二进制变量 表示卡车是否使用边缘三份副本或者是无人机 ；和如果使用,否则或 ．二进制变量如果卡车横穿 然后进一步遍历到 ．如果无人机在一辆处于休眠状态的卡车上飞行，它将被分配到卡车的位置元组索引变量 ；否则，无人机可能担任主动交付角色，因此被分配二进制变量表示无人机从顶点发起 ，交付给 ，然后在顶点处恢复 ．这个问题的一个重要特征是，卡车和无人机的第一个和最后一个顶点索引必须始终相同。距离矩阵三重态距离作为元组的构造表示穿越道路的成本或距离 和 ．子巡回消除变量确保遵循如果 是解决方案的一部分；因此，它限制了我们的形成。

极小极大目标函数使最大值最小化 卡车或无人机的时间，因为每个都在操作中访问三个节点。像这样，用来评估每辆车的时间，在哪里是卡车的三个已访问节点中的第一个和最后一个节点 或者无人机的 ．自大于或等于卡车或无人驾驶飞机的时间，我们强制评估每辆车的使用时间这表示卡车在行驶时的时间 表示无人机时间除以速度因子这是卡车速度的一个因素:

方程(5)使任意路由三元组的起始点的最大时间之和最小结束于 ．方程(6)规定，对于任何给定的操作，最大时间的总和是卡车时间或无人机时间的最大值，其中一个操作可以是卡车专用或卡车-无人机。方程(7)任何三元组都不能包含的指令 ．每个操作都必须是一个移动节点不同于节点或节点 ．确保车辆游荡。方程式(8)实施了一种操作概念，即卡车和无人机必须使用相同的发射和恢复节点进行操作；但是，交付节点可以不同。等式(9）强制卡车或无人机或其组合访问的每个节点。方程(10)限制卡车只能访问一次城市。方程式(11）约束无人机只需访问一个城市即可送达。方程(12)约束卡车输入的每个元组段应退出卡车输入的元组段。方程式(13)是一个子行程消除约束，强制对路线进行排序，使任何子行程都不可能。方程(14)强制无人机在其交付操作范围内交付所有无人机（发射、交付和会合）除非在这种情况下乘坐卡车禁用约束。方程(15)将所有欧几里德距离限制为大于零。方程式(16)为变量赋值和作为二元;和实用程序排序变量取值范围为1到节点总数(或客户交付)之间的整数。

5.卡车-无人机进化算法方法

基于锦标赛的进化算法（EA）采用了路由过程中的群集解决卡车无人机问题的方法。更准确地说，它分配了卡车和嗡嗡声路由过程中的标签。这与文献中发现的所有其他算法有很大不同全班最优文献中发现，首先执行整个路由操作，然后执行算法标签卡车或嗡嗡声．相反，在这里的算法表示为EA创建了一个随机允许的路由的群体矩阵，其中巡回赛中的每个节点被评估为潜在的无人机递送节点，除非该节点超出范围。由于同时评估了许多随机生成的旅行的人群，因此无人机范围内的任何节点都是自动划分和标记的嗡嗡声．EA执行以下过程步骤:（a）对总体进行随机置换的每次巡回赛的旅游都表示为基因组序列 为了交付节点在tour中。（b）根据总旅行团交付时间确定每个人口成员（旅行团）的适合度。所有适合度时间都会保存为种子锦标赛。（c）总人口分为五组，每组进行一组种子比赛。（d）对于每个组，选择种子组（五个组中）中最好的一个作为单个基因，为种子组的其余四个成员进行突变。(1）基因突变(巡回突变)首先在种子比赛中复制五组中最适合的成员，以取代四个不适合的成员。（2）四个不太适合的成员(现在与最适合的相同)然后轻微变异，以提高适合度。（3）突变包括（a）随机选择和交换巡更中的两个节点，（b）两个节点之间的巡更顺序相反，（c）在节点之间向左或向右滑动巡更段，以及（d）用任何其他节点替换巡更中的最后一个节点。（e）重复步骤（b）直到收敛。停止条件基于在改进中发现的预定迭代预算、容差或饱和。（f）返回整个种群中最适合的成员。

种子竞赛遗传算法的优势在于能够在过程中保留多条优化路径，这对于任何网络路由问题都是至关重要的。此外，由于种子比赛中有多个成员，该算法允许对种子比赛的成员执行各种已证实的变异方法。在这种情况下，交换，翻转和滑动突变已经被证明是健壮的，快速的，和非常准确的许多路线问题，包括tsp，多卡车tsp，以及车辆路线问题(vrp)。

算法的性能基于以下基本理论原则:(1）通过初始化相对较大的总体（即5N)在随机排列的旅行中，多条路径（种子竞赛）增加了最优收敛的概率。（2）通过将最适合的基因保存在一个种子中，然后轻微地扰动(突变)五个种子组中发现的最佳基因(巡回)，确保解决方案永远不会变差，同时在每次迭代中促进改进。（3）通过自动分配无人机到任何“范围内”节点，无人机的使用在整个路由过程中最大化，同时减少卡车的总行程长度。通过先用随机排列初始化种群，然后保持多条优化路径，可以降低为无人机分配错误节点的风险。（4）与其他算法相比，多径随机搜索比必须计算可达范围内每个邻域的贪婪度或精确性要快得多。因此，该算法依赖于计算速度和迭代次数，而无需承担不必要的计算负担。

对于该算法，我们随机排列一个旅行种群，表示为初始种群矩阵组成m旅游各有N巡视中的节点(旅游长度）。在这种情况下，表示种群矩阵中第一次游程(1)和第一次游程的所有节点(:)。而变量表示人口中的第一次旅行 ，然后也表示第一个巡更或路线内的节点。函数表示一个距离函数，它可以正确地计算路由各段之间的距离。距离函数命名法 表示节点之间的距离( ）和节点( ）在途中发现 ．此外，邻域功能的下三个节点或路由段如 用于评估给定约束的无人机是否可以到达某个段 ．在这种情况下，算法的距离函数可以处理两个节点之间的距离，或三个节点的邻域，如中所示 ．返回距离D然后将功能除以卡车或无人机到达的速度 ．

6.元启发式比较

如前所述，我们的进化算法（EA）（算法1)元启发式使用a路由过程中的群集方法，即每个无人机自动分配到巡更中的任何下一个交付节点（如果在范围内）。这迫使无人机得到高度利用。接下来，我们使用多条随机排列的路线初始化总体，以改进潜在的优化路径，从而帮助排除局部最优。在每次迭代中，总体中的每个巡更使用包含随机节点交换、随机巡更段翻转和随机段向右或向左滑动的突变，可以稍微改进ion。

具体地说，我们的路由过程中的群集EA是健壮的，快速的，并且能够比文献中发现的任何其他方法更好地解决大型问题。为了说明这一点，我们将其性能与数学过程(MIP)、基于人工智能约束的编程过程(CP)以及Agatz等人进行的“同类中最好的”启发式进行了比较。13]为了证明最优性，我们将EA与封闭形式的混合整数规划方法进行了比较，用于小于15个节点的小规模问题，然后将EA与IBM基于约束的编程（CP）进行了比较，用于大于80个交付节点的大规模问题。

将EA与以下方法进行比较:(1）闭形式混合整数规划(MIP)的小问题(小于12节点)证明最优性。（2）基于约束的编程(CP)用于更大的问题(少于80个节点)以证明最优性。（3）MST gp all（首先路由MST，使用贪婪算法进行集群，所有迭代改进）（4）MST ep all（路由MST优先，具有精确分区的集群，具有所有迭代改进的动态规划）（5）tsp -gp-all(路由tsp优先，采用贪婪算法聚类，所有迭代改进)(6)tsp -ep-all(先路由tsp，使用精确分区和所有迭代改进的集群)

6.1。比较研究1（较小的问题尺寸：反对阶级）

为了简单起见，我们在( ）在笛卡尔坐标系下，假设卡车或无人驾驶飞机的距离是基于欧几里德距离的均匀分布。在原始的比较问题中[13]元启发式比较实验来自三种不同的分布：均匀（随机）分布节点、单中心高斯分布节点和双中心高斯分布节点。在我们的研究中，我们分析了从不同分布获得的结果，发现潜在分布与我们的EA元启发式没有统计相关性；因此，为了简单起见，我们采用均匀分布来进行实验。具体地说，本文中用于问题比较的所有节点都是从{0，1，2… , 100}.

表(表1)下面提供了10个随机生成的实例的结果，每个实例类型有10个节点。对于每个实例，最优性增量间隙定义为

结果表明，该方法优于文献中发现的其他方法。在此，对于当前文献中发现的类似问题规模的10/10实例，EA证明了最优。因此，我们增加了问题的规模，构建了一个基于约束的模型(CP)，以便与最优模型进行比较，并进行了额外的实验。

6.2。计算研究2（较大的问题尺寸：MIP，CP和EA）

该研究在64位版本的Xumbutu®15.04上运行，virtualBox™4.3.12管理程序，windows 7™为主机操作系统。EA在MATLAB®中进行编码。我们为实验目的创建的文件可以在Mathworks®文件交换(dtsp_ga_basic)中进行评估/比较。硬件配置由Intel®Core i7-4770 CPU和16gb RAM组成。而且，MIP和CP都是在IBM OPL 12.8.0中编码的，在一台搭载英特尔酷睿i5-3537 @ 2.5 Ghz处理器和8gb RAM的个人电脑上。

总共有10个具有节点(在10到100之间)的测试问题实例被随机生成，然后取平均值。和其他研究一样，无人机的速度是卡车的两倍 ．在这种情况下，所有客户分布在一个8平方英里的区域内。最大飞行耐力(无人机射程)设置为14英里作为无人机的射程。表格2总结测试问题实例的计算结果。第1列显示了不同的作业大小（节点数）N).第2-4、5-7和8-10列记录了经过的计算处理时间(消逝.)，目标函数( )，分别表示MIP、CP和EA与最优值之间的总时间和差距。如果保证了最优性，则间隙是根据最优解计算的。然而，如果不能保证更大的问题的最优性，那么将根据MIP、CP和EA交付时间的最佳情况计算差距。在这种情况下，IBM CP和LINDO/LINGO MIP优化软件无法保证当前计算机系统中大于20+的作业(节点数)或计算时间大于1800秒的作业(节点数)的最优性。在这种情况下，CP报告它找到的最佳解决方案，并给出最优的可能性(即多达80个作业实例)。相反，EA始终以最短的计算时间提供有效的解决方案。规模较大的问题需要更多的计算机处理能力来进行比较研究。

所有的测试实例以及MIP和CP日志都位于以下链接:https://drive.google.com/open?id=19ZZ9ukEwSSfjCqNID1P1kPsGMOyMefXC．

7.结论

目前的文献缺乏关于卡车-无人机配置的设计空间(速度、范围和无人机数量)的最高产量区域的任何可用信息，任何考虑使用送货-无人机的公司都没有办法指导无人机参数的选择对操作空间的高收率区域没有一些可见性。的精益几何方法这里所示的是将问题空间倒置，以求解给定随机生成的场景下的无人机速度和无人机射程的实际最佳情况。因此，它对于实际的设计决策是非常有用的，关于适当的/最有效的无人机速度和范围，以达到最大的期望产量，而不是只有卡车的解决方案。因此，它可以作为一种方法来筛选无意中选择的低性能设计。

该研究还提供了在任何其他研究中未发现的MIP的简化版本，以及解决无人机问题的最佳路线和最佳时间所需的有用且易于实现的元启发式。我们使用一个简单的单染色体进化算法（EA）元启发式来测试每个案例。EA在MATLAB®开发环境语言中被建模为函数，这些文件在Mathworks®文件交换（dtsp_ga_basic）中可供评估。EA根据文献中发现的当前同类最佳启发式进行测试，并在准确性和计算时间性能方面显著超过它们。

总之，这项研究回答了预期的时间内预期的效率，预计会有一种卡车 - 无人机配置以及在无人驾驶范围内的适当配置以及卡车 - 无人信机的速度是什么“典型的交付场景。它为企业提供了评估各种配置的基础，以防止其典型的日常的最后一英里包裹交付方案。这项工作还为未来的研究开设了几个额外的问题。最明显的问题涉及1卡车的设计空间时间和/或效率，包括许多无人机。

数据可用性

元启发式代码和算法可在MATLAB.com以及根据要求的相应作者。

的利益冲突

作者声明不存在利益冲突。

参考文献

1. N. Agatz，P. Bouman和M. Schmidt，“无人驾驶旅行推销员问题的优化方法”社会科学研究网络，社会科学电子出版公司由elsevier，阿姆斯特丹，荷兰，2015年。视图:谷歌学术搜索
2. B.Golden、S.Raghavan和E.Wasil，“车辆路径问题：最新进展和新挑战”，年操作研究/计算机科学界面， vol. 43，施普林格，柏林，德国，2008。视图:出版商网站|谷歌学术搜索
3. P.Toth和D.Vigo，车辆路径问题：关于离散数学和应用的SIAM专著，《离散数学与应用SIAM专论》，费城，美国宾夕法尼亚州，2002年。
4. S. N. Kumar和R. Panneerselvam，“车辆路径问题及其变体的调查，”智能信息管理，第4卷，第4期。3, 2012。视图:出版商网站|谷歌学术搜索
5. C.E.Miller、E.W.Tucker和R.A.Zemlin，“整数规划公式和旅行商问题，”美国计算机学会杂志一九六零年第7卷第326-329页。视图:谷歌学术搜索
6. M. Drexl，“车辆路径的同步化——具有多重同步约束的vrp调查”，交通科学第46卷，第46期3, pp. 297 - 316,2012。视图:出版商网站|谷歌学术搜索
7. A.-S.Pepin、G.Desaulniers、A.Hertz和D.Huisman，“多基地车辆调度问题五种启发式方法的比较，”安排期刊，第12卷，第2期1，第17-30页，2009。视图:出版商网站|谷歌学术搜索
8. 林颖，卞正忠，孙胜，“考虑管道库存成本的多对多奶源运行路径问题的两阶段模拟退火算法”，工程中的数学问题，第2015卷，文章编号428925，共22页，2015年。视图:出版商网站|谷歌学术搜索
9. C.C.Murray和A.G.Chu，“飞行伙伴旅行推销员问题：无人机辅助包裹递送的优化，”交通研究C部分:新兴技术， vol. 54, pp. 86-109, 2015。视图:出版商网站|谷歌学术搜索
10. P. Bouman，N. Agatz和M. Schmidt，“Traveling Salesman问题的动态编程方法与无人机，”2017年，https://ssrn.com/abstract=3035323．视图:谷歌学术搜索
11. J.R.Current和D.A.Schilling，“覆盖推销员问题，”交通科学，第23卷，第2期。3，第208-213页，1989。视图:出版商网站|谷歌学术搜索
12. D. J. Gulczynski, J. W. Heath, C. C. Price，《足够接近的旅行推销员问题:若干启发式的讨论》，刊于运筹学/计算机科学接口系列，F. B. Alt，M. C.Fu，B. L. Golden，EDS。，Vol。36，PP。271-283，Springer，波士顿，马，美国，2006年。视图:出版商网站|谷歌学术搜索
13. N. Agatz, P. Bouman, M. Schmidt，“无人机旅行推销员问题的优化方法”，交通科学号，第52卷。4, pp. 965-981, 2018。视图:出版商网站|谷歌学术搜索

版权

版权所有©2020 Robert Rich。这是一篇发布在知识共享署名许可协议，允许在任何媒介上不受限制地使用、传播和复制，但必须正确引用原作。