英语原文共 15 页，剩余内容已隐藏，支付完成后下载完整资料
初等最短的多面体研究具有资源约束的路径问题
Jiarui Da, Lanbo Zheng and Xin Tang {dajiarui,tangxin,lanbozheng}@whut.edu.cn
School of Logistics Engineering, Wuhan University of Technology, Hubei, China
摘要：具有资源约束的基本最短路径问题（ESPPRC）在带有负周期的图中显示为子问题知名车辆的列生成解决方案方法时间窗（VRPTW）的路由问题。 ESPPRC是N P-hard在强烈的意义上[8]。大多数以前的方法可以解决问题的宽松版本，其中的路径不必一定是基于动态的基本和伪多项式时间算法编程已成功应用。但是，这种方法具有重要意义缺点是下限的削弱并且可能在某些应用中会引起算法故障[9]。另外，先前有关VRP变体的计算研究表明标记算法不会比多面体方法表现更好时间窗口很宽[13]，在某些情况下甚至可能无法应用[7]。此外，整数编程方法更加灵活使人们可以轻松地合并一般的分支决策或有效不平等会改变定价子问题的结构。在本文中，我们介绍了ESPPRC问题的ILP公式使用路径对容量和时间窗口约束进行建模不平等。路径不等式已由Ascheuer等人使用。 [1]和Kallehauge等。 [13]分别解决非对称行进带有时间窗和VRPTW的业务员问题。我们研究并确定ESPPRC多表位。我们提出从一般的割据中消除了新的一类加剧的不平等现象不平等现象，并表明它们在定义方面。计算实验对源自的相同ESPPRC实例执行所罗门的数据集[9]。结果与以前的配方相比证明我们方法的有效性。
关键字：具有资源限制的基本最短路径，车辆时间窗，整数编程，多面体的路径问题研究
一. 引言
考虑资源约束的基本最短路径路径问题本文中的描述如下：对于给定的有向图G =（V，A），其中V = {0，...，n 1}是节点的集合，| V | = n 2，并且A是一组弧。节点0代表起始节点，节点n 1代表目标节点。其他n个节点表示中间节点的集合N = V {0，n 1}。对于每个弧（i，j）isin;A，我们将弧成本cijisin;R与弧行程相关联时间tijisin;Z 。我们假设旅行时间上的三角不等式为对于所有（i，k）isin;A，满足tikle;tij tjk。对于每个节点iisin;N，我们进行关联需求diisin;Z ，dile;q，发布日期aiisin;Z ，处理时间piisin;Z ，最后期限biisin;Z 。参数q通常代表a中的车辆容量车辆路线方案，以及发布日期ai和截止日期bi，表示最早和最可能的维修开始时间节点[i，bi]的间隔称为节点i的时间窗。时间如果aigt; 0或bi lt;infin;，则窗口称为活动窗口；类型为[0，infin;]的时间窗被称为放松。如果维修可能在AI之前开始，则需要等待直到释放该节点。我们假设d0 = dn 1 = 0，a0 = an 1 = 0，和{（0，n 1）}isin;/A。问题是要找到一条最小成本的基本路径从节点0到节点n 1，这样，对于路径上的每个节点i，开始时间为了进行处理（访问），节点i位于给定的时间窗口[ai，bi]内，并且路径上节点的总需求不超过q。一条路径是如果不多次访问任何节点，即不访问，则为基本包含子游览。
由于ESPPRC从严格意义上讲是NP难的，因此在将问题作为车辆选路或人员调度中的子问题解决场景通常看一个宽松的问题版本，其中路径不必须是基本的，称为具有资源约束的最短路径问题（SPPRC）。在列生成主问题的列生成过程中作为一个覆盖问题，这种方法能够产生有效的最优满足三角不等式的VRPTW的解。一个重要的这些方法中的一组基于动态编程（DP），并且具有伪多项式复杂度。该方法已成功应用由Desrochers等人撰写。[6]对于VRPTW和Graves等人。 [10]航班机组调度问题仅举几个例子。但是，这样的放松导致弱下限和大的分支定界树[11]。为一个其他问题的数量，例如有收益的车辆路径问题，基本路径限制对解决方案的影响太大，无法放松甚至可能是必要的[9]。
Feillet等。[9]首先评估ESPPRC扩展的确切方法根据Desrochers等人的标签算法。 [6]。在他们的方法中，客户包含资源以指示是否可以拜访给定的客户通过扩展当前的部分路径。该算法缩小了对偶差距与基于SPPRC限制的常规方法相比，使某些特殊情况可以使用列生成解决方案方法问题或某些不依赖SPPRC的特殊分支方案解决方案。最近，Righini和Salani [16]提出了双向标签用于ESPPRC的算法，它依赖于状态空间松弛。类似的DPBoland等人提出的算法。 [4]随机取得良好的效果80 J. Da等。生成的实例。卢梭等。 [17]使用branch-andprice解决VRPTW通过约束编程处理ESPPRC子问题的方法（CP）。尽管CP组件被证明是灵活的，但是他们的方法是与传统的分支定价策略相比，速度稍慢。巴尔达奇等。[3]通过包含以下内容扩展了Righini和Salani的确切算法基于状态空间松弛的边界函数。他们介绍了这个概念ng-route松弛的量，用于计算部分的完成范围路径，从而通过标签胖化来加速DP算法。非常最近，Lozano等。 [14]提出了一种基于隐式枚举的精确算法采用新的边界方案，可显着减少搜索空间。对于有关资源受限的最短路径的全面综述，请参阅调查Di Puglia Pugliese和Guerriero撰写的论文[15]。
与旅行商问题不同，基础面的多面研究最短路径问题和车辆路线问题非常有限。Kallehauge等。[13]提出了基于VRPTW的公式通过对ATSP-TW多表位的研究得出了不可行的路径不等式[1]。的作者分析了VRPTW多态性的大小，并证明了在某些条件下，一类不可行的路径不平等是刻面定义的。对于没有任何资源限制（ESPP）的基本最短路径问题，Taccari [19]分析了几种整数编程公式并提出了一些多面体结果显示基于两种不同的多表位楷模。 据我们所知，ESPPRC的多面体研究文献中未涉及多表位。
从一般工程的角度来看，整数编程方法更灵活地合并一般分支决策或有效不平等这将改变定价子问题的结构并允许直接使用通用MIP求解器。在本文中，我们提出了一个多面体研究在ESPPRC多义词上得出有效的不等式基于分支剪切的方法。第2节介绍了符号，标准ESPPRC的MIP模型和基于不可行路径的一些新公式不平等。第3节研究ESPPRC多表位的维度并介绍一组定义方面的不平等。几类新颖的有效不等式在第4节中介绍。第5节报告了计算结果，其中特别是旨在显示所提出的不平等现象的有效性改善LP弛豫范围并减小分支定界的大小搜索树。最后，在第6节中，我们将作总结性讨论。进一步的研究主题。
二. 符号和建模
要对此问题进行多面研究，我们需要进一步配置有向图的结构G =（V，A）。 我们假设对于任何iisin;N，max {t0i，ai} tin 1le;bn 1，否则，可以从G中删除节点i影响最佳解决方案。 给定一个节点集Wsube;V，令A（W）：= {（（i，j）isin;A | i，jisin;W}表示在W中具有尾部和头部的所有弧线的集合。对于任何两个节点集U，Wsube;V让，（U：W）：= {（（i，j）isin;A | iisin;U，jisin;W}用U表示尾巴，W表示头弧的集合。为简化表示，我们分别使用（W：j）和（j：W）代替（W：{j}）和（{j}：W）。 给定一个节点集Wsub;V，W̸=empty;，我们还定义delta;minus;（W）：= {（（i，j）isin;A | iisin;V W，jisin;W}，delta; （W）：= {（（i，j）isin;A | iisin;W，jisin;V W}，delta;（W）：＝delta;-（W）cup;delta; （W）。圆弧集合delta;（W）称为切割。 为简单起见，我们使用delta;minus;（v），delta; （v）和delta;（v）分别代替delta;-（{v}），delta; （{v}）和delta;（{v}）。 | delta;minus;（v）|的个数，|delta; （v）|和|delta;（v）| 称为节点v的度数，度数和度数。假设delta;minus;（0）=delta; （n 1）=empty;，并且A（N）= {（i，j）isin;A | ai pi tijle;bjand di djle;q}，否则，可以从G移除弧（i，j）而不会影响最佳解决方案。 令m = | A（N）|，我们有A =delta; （0）cup;A（N）cup;delta;minus;（n 1）和| A | = 2n 米。
文献中有几种方法可以将ESPPRC建模为整数线性程式。 使用最广泛的一个涉及二进制弧变量xij以及节点变量tau;i，指示访问节点i的时间。 一个标准整数编程公式，用于确定从中得出的最短路径满足容量和时间窗口约束的节点0到节点n 1如下：
如果圆弧（i，j）属于路径，则二进制圆弧变量xij的值为1。约束（2），（3）和（4）是流量守恒约束，可确保路径从节点0开始到节点n 1结束。请注意，这些约束82 J. Da等。仅仅保证一个没有子路线的解决方案是不够的。 如果是子巡回赛与基本路径从0到n 1不相交的成本为负，基本路径可能不是所需的真正的最低成本路径。 约束条件（5），（6）和（7）保证了相对于时间窗口的路径可行性和容量限制。 另外，变量集tau;产生一个优先级路径上的节点之间的顺序，从而可以防止子路线。 的二元条件（8）允许x之间存在非线性约束（5）和tau;变量将通过Miller-Tucker-Zemlin的推广而线性化不平等，即：
其中Mij是足够大的正值，可以用max {bi pi tij minus; aj，0}，（i，j）isin;A，并且只需要对（5）或（9）实施约束弧（i，j）isin;A使得Mijgt; 0;否则，所有这些约束都得到满足tau;i，tau;j和xij的变量。但是，这些限制条件涉及一个“大M”字词，已知会导致计算问题。在计算实验中在这项研究中，我们还引入了一组有效的不等式来延长时间窗口约束。
为避免因时间指示变量增加而造成的不利影响和链接约束，可能会导致线性松弛性能变差，Ascheuer等。 [1]引入了一组不可行的路径约束来建模解决非对称行进时隐含的时间窗口约束带有时间窗口的业务员问题（ATSP-TW）。 Kallehauge等。 [13]进一步扩展公式以解决VRPTW实例。在这项研究中，我们ESPPRC的多面体分析基于这种类型的公式。由弧集合{（vi，vi 1）| i = 1，...，k minus; 1}组成的路径P有时是由P =（v1，v2，...，vk）表示。如果没有特别说明，则路径P始终为意为开放和简单，即| P | = k minus; 1且对于i̸= j的vi̸= vj。一种如果路径P在任何可行的路径中都不是子问题，则它是不可行的，即如果“ķi = 1digt; q或tau;vigt; bvi，对于某些iisin;{1，...，k}。一条不可行的路如果P = {vi，vi 1isin;A | i = 1，...，k minus; 1}是最小的不可行的。截短的子路径P {（v1，v2）}和P {（vk-1，vk）}是可行的。我们表示G中作为PG的所有最小不可行路径的集合。对于任何Qsube;A，我们写x（Q）为“（i，j）isin;Qxij。使用这种表示法，ESPPRC中可行的解决方案集是满足流量守恒约束（2）–（4）的xisin;RA的集合，并且约束（8），以及子巡回不等式
路径不等式
因此，我们可以将ESPPRC多表位定义为
从节点0开始的所有可行基本最短路径的特征向量到有向图G =（V，A）上的节点n 1。在下一节中，我们介绍ESPPRC多表位多面体研究的一些结果。继续进行从理论上讲，我们需要更多的符号。由于与每个节点相关的时间窗口，因此可以得出优先级在节点之间。对于任意两个顶点i和j，如果aj pj tjigt; bi，那么如果顶点i都包含在顶点i中，则必须先访问顶点i最短的路径。让i≺j表示i和j之间的优先级关系令GP =（V，R）表示优先级有向图，其中每个弧（i，j）isin;R表示优先关系i≺j。在ATSP-TW的背景下，优先有向图是非循环且可传递的封闭式。 Balas等。 [2]提出所谓的（pi;，sigma;）不等式和Ascheuer等。 [1]提出加强通过明确考虑时间窗口来确定（pi;，sigma;）不等式。在上下文中VR GP的值可以包含周期，例如如果存在2个周期（i minus; j minus; i）这意味着节点对i和j不能属于同一路径。另外，优先关系不是可传递的，即，如果i≺j和j≺k并不意味着i j k是因为j可能不在路径上，因此k可能在i之前。Kallehauge等。 [13]考虑了优先权不平等的两种增强，称为弱pi;不等式和弱sigma;不等式。但是，在在ESPPRC中，上述不等式均不适用，因为节点i可以或最终解决方案中的任何路径都可能不包含此路径。因此，要利用优先级信息，我们对优先级进行了更严格的定义节点之间的关系。
令
分别代表节点iisin;V的前任和后继的集合。注意，此定义可能会缩小之间的优先级关系节点，但它确保节点i的前任必须也必须是前任i的后继项，验证了ESPPRC的优先级不等式在第4节稍后介绍。
此外，对于任何可行路径P =（v1，...，vk），表示
可从路径P延伸的一组边。
三. 多面体分析
在本节中，我们旨在分析（12）中定义的ESPPRC多表位。 我们首先确定多面体的尺寸，然后给出一组构面定义不平等。
命题1 剩余内容已隐藏，支付完成后下载完整资料
资料编号：[239243]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
