英语原文共 13 页，剩余内容已隐藏，支付完成后下载完整资料
车调度问题
G.B.DANTZIG 和J.H.RAMSER
本文研究的是汽油运输车队在一个散货码头和由码头提供的大量服务站之间的的最佳路线。 文中给出了系统中任意两个点之间的最短路线，并为分配系统中的一些站点指定了对一个或多个产品的需求。本文 希望找到一种方式，将车站分配给卡车，使车站的要求得到满足，车队的总里程最低。 文中给出了一种基于线性规划公式的求最优解的方法。这种计算可以很容易地通过手工或自动数字计算机进行。 该方法尚未得到实际应用，但已经计算了一些试验问题。
- 引言
本文提出的“货车调度问题”可以看作是“旅行商问题”的一种概括。（1）在最简单的形式中，旅行商问题是关于车辆必须经过给定的n个点一次条件下的最短的路线， 假设每对点由一个链接连接，则通过n个点的不同路线的总数为！ 。即使是n的小值，路线的总数也是非常大的。例如， 对于n=15，有653837184000条不同的路线。 其中一位作者与Fulkerson和Johnson合作开发了一个“切割平面”的方法，测试路线是否是最佳的，如果不是最佳方案就找到一个改进的解决方案。（2)，(3）
旅行商问题可以通过引入附加条件来推广。 因此，每当他接触到n-1里的m点，销售员可能被要求返回“ 终点”，m就是n-1的除数。 对于给定n和m，要解决的问题是找到循环，使所有循环都有一个指定的公共点并且总循环的长度是最小的。 由于循环有一个共同点，这个问题可以称为“ 三叶草问题”。 如果m很小，则最优的m点集通常可以通过检查包含点和连接它们的弧的地图来确定。 人们会寻找“点群”，并通过尝试和错误来确定应该遍历它们的顺序，同时注意不要有任何循环交叉。 然而，当点群不足或当m很大时，这个过程就不适用了。 在这种情况下，本文的算法可以得到接近最优的解。
2 卡车调度问题
旅行商问题也可以通过施加条件来推广，即指定的交付在每个点Pi（终端点除外）来使qi特殊化。 如果车辆的载货量
这个问题在形式上与旅行商问题的原始形式是相同的，因为车辆可以在一次将所有的点联系在一起的旅途中为每个交货点服务。
在“卡车调度问题”中，C和qi之间的关系使得车辆只能在每次旅行中进行1和t之间的交付。 因此，卡车调度问题的特点是这种关系
显然，当车辆具有相同的容量时，不会考虑它们的数量。 即使涉及不同容积的汽车，或将若干不同产品交付到每一点，也可以使用下面所示的相同的数学模型。 为了简单的表示，首先将假定只有一个产品将交付，并且所有卡车具有相同的容量C。
方法从基本思想出发，将解合成若干个“聚集阶段”，其中亚优化是在成对的点或组上进行的。 要使用的聚合阶段的数量确定如下：给投递qi按q1,q2,.......qi 1,.....qn排序，对于任何一个i=1，....n-1，满足。确定t
and
显然，t代表容量为C的卡车可以为给定的一组交付qirsquo;s的最大数量，因为序列q1,q2,.....qi代表可能在最优解中的一个可行的组合，因此，计算要使用的聚合数的方法必须承认组合q1,q2,.....qi在最终聚合中。 如果聚合的阶段数N被确定为
n是聚集的第N阶段和最后阶段的最大点数。
例如，如果C=6000，q是表1第Q栏所示的值，则qirsquo;s的有序序列是
1100,1200,1200,1400,1400,1500，...1900
并且Z=4, 因此N=log2 4=2. 在聚合的第一阶段，只有那些点被允许配对，其合并需求不超过。 在聚合的第二阶段，包含在第1阶段的次优解中的任何对，在不超过卡车容量前提下与任何其他对组合。 如果C=7000且qirsquo;s再次是表1中的序列，则t=5，N=3。 在聚合的第一阶段，只有那些点被允许配对，其组合需求不超过
第二阶段不超过，第三阶段不超过C。 虽然n=2与log25比较接近而不是N=3，必须使用三个阶段，因为总共有两个阶段不允许可行的组合1100，1200，1200，1400，1400，这可能是最优的。
读者应该注意到，如果卡车被限制精确地访问两个点并返回，所覆盖的总距离将是从终端到每个点Pi的恒定距离之和加上间对距离之和（因此，我们之后将寻求最小化）。 因此，在每个中间阶段，确定了最小对间距离对应的最佳配对。 在最后阶段，确定最佳配对，使行程长度之和为最小。 下面将通过一个数字示例说明这一程序的细节。
卡车调度问题现在可以正式说明如下：
给定一组指定的n个点“Pi(i=1，2···n)，从P0点交付到该点o，叫做终点,,.
给定“距离矩阵”， [D]=[dji]，特殊的，dij=dji，给定了每对点之间的距离(i,j=0，1，···n)。
给出了一个“传递向量”(Q)=（qi），它指定了将气体传递到每个点P分的数量(i=1,2...n)。
卡车容量为C，其中Cgt;max。qi。
如果xij=xji=1被解释为Pi点和Pj点是配对的(i,j=0，1...n)，如果xij=xji=0表示点不配对，则得到条件
(i=1,2.....n)
每个点Pi要么与P0连接，要么至多连接另一个点Pj。此外，根据定义，xii=0，每个i=0，1，··n。
问题是找出xij的那些值，它们使总距离
在[2]至[5]规定的条件下的最低限度。
3 计算过程
3.1一般意见
根据条件[5]，xij只能假定值为1或0。 目前还没有解决离散变量问题的一般适用方法，除了最近的R.Gomory（4）提案的一些变体可能外，该提案处于发展的早期阶段，无法对手头的问题进行评估。 然而，如果承认条件较差，就可以确定“最佳解决方案”
然后应用众所周知的线性规划方法。（5）“解”中可能出现的分数值表明存在点或点组的替代配对。 经验表明，这种替代配对的数量很少，因此，通过尝试和错误，可以很容易地找到产生最小里程的配对。 然后得到的“解”满足了xij为0或1的要求；然而，该方法与其他现有的离散变量问题解的算法一样，不能保证得到绝对最优解。 这很可能是“用这种方法得到的最佳解，随着点数的增加而接近最优。 此外，由于xij=0或1位于“最佳解”之间，所以最小D的估计值在最小D的误差上。n 通过本文方法得到了满足的最小值.
3.2第一阶段
详细的计算过程可以通过表1所示的数值示例来说明。 从P0点交货o 指向P1，...P12。 每个框右下角的条目是点Pi和Pj之间的最短距离dij。 这些条目是[2]中讨论的距离矩阵的元素。 传递向量(Q)显示在三角阵的左边。 如果C=6000加仑，则阶段数为2（见第2节）。 将Xij输入到每个框的左上角。 作为开始，所有交付点PI，...Pi2可以与终端P配对o因此，有12个条目xo,i=1，其中i=1，···12。 这12个条目构成开始计算时的“基本集合”。 在接下来的每一次迭代中，基本集合中的一个元素被消除并替换为一个新元素。 因此，在第一阶段，基本xij的总数保持不变。 每个盒子里剩下的左上角要么是空的，要么是永久提供一颗星星。 空箱子构成了”所有等于0的条目的非基本集。 然而，输入零并不是为了区分它们与属于基本集合的零。 这种区分是必要的，因为在这个特定的例子中没有超过12个基本条目。 一个明星条目表明，在第一阶段聚合期间，不允许对各自的点进行配对，因为对这些点的合并需求超过了卡车容量的一半。 因此，对P5的综合需求 而P6是1700 1900=3600，大于C/2=3000。
3.3快速矫正
启动解，其中每个点与终端配对，可以很容易地通过一系列快速校正来改进。 这是可取的，因为随后的迭代次数随着起始和最优解之间的差异的减少而减少。
可以通过在解决方案中引入与相对较小的值相对应的非基本条目来进行快速校正。 因此，d6,7=7是相对较小的，可以通过将尚未确定的值0输入到相应的左上角而进入基本集。 为了满足方程（3），任何i=1，2...n的基本项之和必须等于1。 由于距离矩阵(D)是对称的，因此表1所示的三角形数组中第6行和第6列中的基本值之和也必须等于1。 第7行和第7列也是如此。 因此，下列条目如下：
X6,7 = (非基础输入X6,7 =0增加)
X0,6 =1- (基础输入 X0,6 =1 正确）
X0,7 =1- (基础输入X0,7 =1 正确）
与不等式（5）一致的的最大值是1。因此
X6,7=1 X0,6 = 0 X0,7 = 0
由于必须删除一个基本 ，所以在X0,6和X0,7之间要有一个选择。 由于距离d0,7大于d0,6，基本X0,7英镑从基本集合中删除，以尽可能减少总距离。 刚才讨论的操作顺序的总体效果是，X0,6，X0,7已添加到基本集合中，即a的值。X0,6已从1改为0，X0,7已被删除。 在几何上，这意味着点6和7已经从终端分离并相互连接。 只要具有明显低當值的非基本项可用，就会重复这种快速修正的过程。 快速改进解决方案的规则是，如果x0,i或y0,j已经从基本集合中删除或具有值0，则跳过任何必厂值dij, 从表1开始，前四次迭代如下
新的基本集合如表2所示，其中 目前应被忽略。 由于前四次快速校正，对间距离之和已从364个单位减少到170个单位。
3.3三角洲功能（相对成本因素）
当有足够数量的点对具有较小的点间距离时，如果不计算每种情况下的总距离，就会越来越难以引入额外的点对。 这相当于一个试错过程，这将需要大量的计算，即使点的数量只是中等大。 因此，需要的是一个标准，它使计算机能够接受或拒绝一个非基本输入，因为表2中的数组是逐框扫描的。 这一标准由“Delta-Function”提供，定义为
当是适当确定的常数特征的第n次迭代。 按定义和确定了，所以
0
对于所有对应于基本条目的dij。 非基本输入
增量函数表示非基本输入xij。单位增加值D的总距离将减少.如果gt;0，如果非基本条目工订的值增加，则总距离D减小；如果lt;0。如果相应的非基本值增加，则总距离D增加。 因此，在扫描表2中的数组时，lt;0的框将被忽略，除非所有非基本项为负值。 在这种情况下，每一种可能的非基本条目的选择都会导致由基本条目集表示的总距离D的增加。 此时获得的特定集合表示“最佳解决方案”。
然而，只要至少有一个是正的，总距离的减少是可能的。 如果几个gt;0，则以最大的值xij获得相对于增加的距离的最大可能减少值xij。因此，在扫描数组时，如果它的大于先前认为最大的值，则接受非基本条目，如果它的扩小于先前注意到的最大的值，则拒绝非基本条目。在平等的情况下，它也可能被拒绝，以消除正式程序的任意性。
常数 和在增量函数（6)中，可以从条件(7）中确定。 这就产生了方程式
-dij =0
可任意设定= 0(整数0的任何选择都可以接受). 由于表2的数值例子中有12个基本条目，因此有12个类型（9）的方程，从中可以确定对应于每个传递点Pi的12个值。 这些=0值和被输入到包含点标识的框的右下角，如表2所示。
在得到这些值之后，将是由（6）和最大按上述方式确定的。 然后，非基本条目仍須被设置为等于0，必要时通过减去0来修正基本条目，使第r行和第r列以及第s行和第s列中的条目之和分别等于1。 在表2中，max==25 42-17=50；因此，非基本条目=0被=取代。然后对基本条目进行校正，如图所示。 应该注意的是，校正不能应用于基本条目初
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[238654]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
