英语原文共 9 页

印达维出版公司

工程数学问题卷2016，文章ID 5040513，8页http://dx.doi.org/10.1155/2016/5040513

研究文章

导航AGV具有优先约束的的精确启发式路径算法

梁旭，¹姚王，¹林刘，¹王嘉兴²

西南财经大学工商管理学院，成都6111302

西南财经大学经济数学系，成都611130

通讯地址：yao wang；ywangswu@163.com

收到日期：2016年1月4日；修订日期：2016年4月19日；接受日期：2016年6月28日

学术编辑：刘飞

版权所有copy;2016 Liang Xu等人这是一篇开放访问的文章，根据创作共享归属许可证分发，允许在任何媒介中不受限制地使用、分发和复制，只要原作被正确引用。

当一辆自动导引车（AGV）被派去拜访一组结点时，这些结点通常放置在一条固定的导线，这些导线中的传输信号用来导航AGV的，这时就会出现一些问题。为了使总行程（或时间）最小化，需要一个最佳的访问顺序。当优先约束被限制在目标身上时，该问题被称为具有优先约束的路径上的旅行商问题（TSPP-PC）。无论它是否是NP完全，在文献中都没有答案。本文设计了TSPP-PC的动态规划，这是第一个优先约束数为常数时的多项式时间精确算法。对于多个优先级约束的问题，部分输入可以任意大，因此我们提供了一种基于精确算法的高效探索性算法。

1. 介绍

在派一辆自动导引车（AGV）沿着里面有传输信号以导航AGV的导线访问一组位置时，出现了一个“路径上的旅行推销员”问题（简称TSPP）。对于有线AGV，在放置电线的地板上切割一个槽，并沿着AGV要遵循的路径切割槽。安装在AGV底部的传感器检测来自导线的无线电信号以导航AGV。应用AGV的领域越来越广。通过对Vis[1]的调查，AGV的典型应用包括制造、分销和转运。TSPP的其他出现场景也可以在其他线性服务网络的应用中找到，例如制造业中的激光钻孔、集装箱码头中的履带式起重机和校车来往运输。

然后，我们通过图1中的示例来说明TSPP

在本例中，AGV沿电线（灰色）行进，将两个输送带之间的物料运送到四个工作站。它总共有四个工作站需要访问，其中传送带1是工人的起点。我们将起点表示为0，将四个工作站分别表示为1、2、3和4。对四个目标有两个优先限制，如下所示：

P₁: 0 → 3 → 1，

P₂: 0 → 4 → 2 （1）

即客户3应先于客户1访问，客户4应先于客户2访问。

TSPP是一个典型的旅行推销员问题的特例，它嵌入了特殊的底层网络。无约束条件下，TSPP的求解十分繁琐。尽管对TSP及其种类的研究层出不穷，但据我们所知，还没有直接涉及TSPP-PC的文献。尽管具有优先约束的TSP作为TSP的一个特例被认为是完全NP（Garey和Johnson[2]），但无论TSPP-PC是否是完全NP在文献中都是未知的。本文设计了TSPP-PC的动态规划，这是第一个优先约束数为常数时的多项式时间精确算法。对于多个优先级约束的问题，部分输入可以任意大，因此我们提供了一种基于精确算法的高效探索性算法。

精确算法是基于动态规划的，它考虑了销售人员访问的所有优先约束中的最后一个顶点，而不是访问的所有顶点。由于优先约束的个数是一个常数k，因此动态规划需要实现一种多项式时间运行时间要求。

本文的组织结构如下：第二节是相关研究的文献综述，第三节介绍了问题的正式定义。第四节给出了TSPP-PC的动态规划，证明动态规划是TSPP-PC的第一个多项式时间精确算法，优先约束数为常数。在第五节中，我们研究了具有任意大优先级约束的TSPPPC，并开发了一种基于精确算法的探索性算法。我们在第6节中给出了一个结论，并对今后的工作提出了建议。

2. 文献综述

TSP因为文献[3]有很高的知名度，同时也在该文献中被研究得很深入，其中包括两个主要的类型：时间窗（Foccacie et al. [4]）和优先约束（Mingozzi et al. [5]）。众所周知，这是一个NP难题，因此没有一般的多项式时间精确算法。然而，许多精确而非多项式时间算法被用来求解TSP。可以参考Lawler等人[6] TSP解决方案的一般方法的简要介绍。

虽然TSP不具有多项式时间可解性，除非NP=P，但有许多特殊情况是能够被很好地解出来。劳勒等人[6]和Burkard等人[7]对TSP可很好解决的特殊情况进行全面研究。可解TSP最重要的特殊情况是所谓的金字塔可解TSP。金字塔路线有两个好地方。首先，在计算复杂度方面，找到一个最低成本的金字塔路线只需要O(n²)时间。其次，存在一定的距离矩阵结构，保证了金字塔最优路线的存在。到目前为止，这种距离矩阵结构已经被发现可以保证最短的金字塔路线：Monge矩阵、Supnick矩阵、Demidenko矩阵、Kalmanson矩阵、van der veen矩阵和广义分布矩阵。所有这些特殊的矩阵都对距离矩阵施加了一定的条件，从而保证了金字塔最优路线的存在。

尽管一般欧几里得TSP仍然存在NP难题（sanjeev[8]），但有一些情况是可以很好地解决的。其中之一类似于TSPP，是De˘ıneko和Woeginger[9]中引入的k线TSP，其中顶点位于欧几里得平面中的k平行（或几乎平行）线上。TSPP是k线欧几里得TSP的一个特例，其中k=1。然而，以前对这个范围的研究并没有考虑优先约束。

Burkard等人[10]引入的排列的Monge TSP还形成了广泛的一类可解TSP。矩阵C被称为排列矩阵，如果存在排列phi;，使得Cphi;是一个排列矩阵。与欧几里得TSP相似，尽管排列矩阵上的一般TSP不是多项式可解的，但许多特定形式的矩阵提供了多项式求解算法的可能性。

对于TSP，一些著作提出了近似算法而不是精确算法。基于用于提供近似TSP路线的树算法，Rathinam等人[11]针对多个销售人员路线问题开发了一个2-近似算法。后来，Xu等人[12]通过为这个问题提供扩展的Christofides启发式方法，将这个结果改进为（2minus;1/k）。后来，Xu和Rodrigues[13]针对同一个问题开发了一种3/2近似算法，称为交换算法，除非可以进一步改进TSP的3/2 Christofides启发式算法，否则这是可以获得的最佳近似比。

Mingozzi等人[5]提出了一种具有时间窗和优先约束的TSP动态规划策略，并采用一个良好的边界函数来减少状态空间图。在Mingozzi[5]等人的动态规划中的状态定义为（S,tau;,j），可以解释为从起点开始的所有可能路径的族，访问结点子集S中的所有地点，在结点j停止，并在时间tau;结束访问。由于集合S明显具有与问题规模成指数的大小，因此不能期望动态编程实现多项式时间运行时间，以返回TSPP-PC的最优解。对于具有优先约束的TSP，Moon等人[14]提出了一种利用拓扑排序的高效遗传算法，并针对遗传算法提出了一种新的交叉运算。

尽管文献中对具有优先约束的TSP进行了研究，但我们仍然需要克服TSPP-PC的缺陷，第一个缺陷在于对问题是否是完全NP的开放性问题缺乏答案。第二个缺陷是没有一个高效探索性的AGV产业。

3. 问题定义

在TSPP-PC中，销售人员应该访问一组顶点，这些顶点位于一条路径上。两个顶点之间的距离是通过路径上的欧几里得距离来测量的。TSPP-PC的目标是在不违反给定优先约束的情况下，以最小的总移动距离确定要访问的顶点的最佳序列。

形式上，我们可以表示TSPP-PC如下。假设销售员最初位于0处，即所谓的起点，他将沿着路径访问一组顶点𝑉 = {1, 2, . . . , 𝑛}。当i=1,2,hellip;,n时，我们用x_i来顶点i,用X来表示集合{𝑥1, 𝑥2,...,𝑥𝑛}。 因此，i和j之间的距离，定义为d_ij，表示为

（2）

这个问题的实质是确定一个顶点序列(𝑖₁, 𝑖₂,...,𝑖_n) ，使得总行程距离

（3）

最小化，并且不违背所施加的优先约束。也就是说，销售员从起点开始，依次访问所有顶点，最后返回起点，满足优先级约束。让P表示所有k优先约束的集合，P_i表示i=1,2hellip;k时的约束。严格地说，

我们用v_i,0=0对于 i=1,2hellip;k表示每个优先约束必须从顶点0开始。对于任何具有l_i 1顶点的单优先级P_i，需要注意的是，v_i,j具有第j级优先级。如果具有更高优先级（tlt;j）的所有顶点v_i,t已经被访问了，那么顶点v_i,j可以被访问。为了便于表示，我们将优先级P_i表示为(v_i,0,v_i,1,hellip;,v_i,lj)。以第一节中的P₂为例，P₂=（v_2,0,v_2,1, v_2,2）=（0，4，2），其中l₂₌₂，在访问顶点4和顶点2之前，必须顶点0，除非已经访问了顶点4。因此，TSPP-PC的任何实例都可以描述为（V,X,P）。

我们可以注意到，例如（V,X,P）对于TSPP-PC，在单个优先约束中，顶点v恰好出现一次；否则，在单个优先约束中的多个v会导致矛盾，因为在连续vrsquo;s之间的任何顶点mu;都应该在v之后和v之前访问。此外，如果超过一个ENCE约束共享一个公共顶点v，实例（V,X,P）可能没有可行的解决方案，因为两个优先约束共享可能相互矛盾的公共顶点。例如，两个优先约束P₁=（0,2,1,3）和P₂=（0，1，4，5，2）共享两个顶点1和2，这两个约束是矛盾的，因为2应该在P₁中的1之前访问，而2应该在P₂中的1之后访问，这意味着对于这种情况没有可行的解决方案。为了保证可行解的存在，我们只考虑P中所有优先约束都不共享公共顶点的情况，这意味着每个顶点最多在P中所有优先约束中出现一次。对于优先级P_i，其中i=1，2,hellip;,k，当且仅当访问了v之前P_i中的所有顶点，则可以访问任何顶点v。

本文首先考虑优先级约束个数与实例输入无关，设计了基于动态规划的时间复杂度多项式时间精确算法。由于精确算法在问题实例中具有指数运行时间，并且可以任意大，因此我们针对两个优先约束的TSPP-PC设计了一种基于精确算法的启发式算法。

接下来，我们展示如下，对于TSPP-PC的任何实例，在P中找到一个最佳访问序列就足以满足V中的一个最佳访问序列。让chi;_R表示 P中所有顶点中最大的坐标。也就是说chi;_{R =}arg max{chi;_i|iisin;P}，我们进一步将顶点chi;_R右侧的一组顶点定义为R，也就是说，R ={iisin;V|chi;_igt;chi;_R}。

此外，我们定义了集合L={iisin;_V \ P| chi;_i le;chi;_R}。显然，集合V分解为P,R,和L；也就是说，V=Pcup;Rcup;L。

现在，我们可以提出TSPP-PC的第一个属性，以消除对R和L中顶点的考虑。

属性1。对于TSPP-PC的任何实例，最优解的形式都必须是(hellip;,chi;_R,R，hellip;)，其中访问顶点chi;_R后逐个访问R中的顶点。

这是正确的，因为在R中没有对顶点施加优先级约束，最终到达顶点n时，chi;_R到chi;_n和chi;_n到chi;_R的往返距离不能缩短。

由于属性1的原因，我们可以去掉对R中顶点的考虑。在得到不含R的顶点集V的最优访问序列后，我们在R中插入顶点以建立最终序列。

此外，我们甚至可以删除对L中顶点的考虑。这是因为当我们在P中调度顶点时，为了达到chi;_R的顶点，销售人员将通过L中的所有顶点保证路线的连续性。因为L中的顶点没有优先级约束，所以销售人员可以在经过这些顶点时访问它们。

基于以上事实，我们可以通过去掉对L和R中顶点的考虑来简化这个问题。在获得P中的最佳访问序列后，我们可以用L和R解决问题，如算法1所示：

算法1（将P中的最佳序列转换为

资料编号：[5573]