英语原文共 13 页，剩余内容已隐藏，支付完成后下载完整资料

卡车调度问题

Dantzig, George Bernard; Ramser, John Hubert

本文涉及的是在大型码头和该码头提供的大量服务站之间的汽油运输卡车车队的最佳路线。给出了系统中任何两个点之间的最短路径，并为配电系统中的多个站点指定了对一种或几种产品的需求。期望找到一种方式，以这样的方式将站点分配给卡车，使得站点需求得到满足并且车队所覆盖的总里程最小。给出了基于线性规划公式以获得接近最佳的解的过程。该计算可以容易地用手或通过自动数字计算机来执行。尚未对该方法进行实际应用。但是，已经计算出许多实验问题。

1.介绍

本文中提出的“卡车派遣问题'可以看作是'旅行推销员问题'的概括。(1)形式最简单的旅行推销员问题涉及确定穿过n个给定点一次的最短路径。假设如果每对点都由一个链接连接，则通过n个点的不同路线的总数为aring;n!。即对于n的较小值，路由总数也非常大，例如，对于n=15，仍有653,837,184,000条不同的路由。其中一位作者与Fulkerson和Johnson合作开发了一种“切割平面”方法，用于测试提议的游览方案是否最佳，或者如果不是，则寻求改进的解决方案。(2)，(3)

可以通过引入附加条件来推广旅行商问题。因此，只要推销员已经联系了n-1个剩余点中的m个（其中m是n-1的除数），就可能需要推销员返“终点”。 对于给定的n和m，问题在于找到这样的循环：所有循环在公共点上都具有指定点，并且总循环长度最小。由于循环有一个共同点，因此可以将此问题称为“三叶草问题”。如果m小,通常可以通过检查包含这些点和连接它们的弧的地图来确定m个点的最佳集合。人们会寻找“点的簇”，并通过反复试验来确定遍历它们的顺序,并注意不要让任何循环交叉。但是，当群集数量不足或m大时，此过程将不适用。在这种情况下，可以通过本文的算法获得近乎最佳的解决方案。
2.卡车调度问题
旅行商问题也可以通过强加规定在每个点P (终点除外)进行指定交付的条件来推广。如果承运人的能力

这个问题在原始形式上与旅行商问题相同，因为承运人可以在一次行程中为每个交货点提供服务连接所有点。

在“卡车调度问题”中，C与q_i的关系是这样，承运人每次只能进行1到t次运输。因此，卡车调度问题的特征是

很明显，当有同样的能力，承运人的数量不会出现问题。即使涉及到不同容量的运营商，或者当要向每个点交付许多不同的产品时，可使用如下所示的相同数学模型。为了简化演示，首先假设只交付一个产品，所有的卡车都有相同的容量C。

解的方法从基本思想出发，把解综合成若干个“聚合阶段”，其中在成对的点或组上进行次优化。确定聚合的阶段数所采用的方法如下：按顺序q₁，hellip;qi, q_{i 1},hellip;q_n对排序，使得对于任意i=1，hellip;n-1，有q_ile;q_{i 1}。那么确定t，使

t显然代表一辆卡车的容量C可以为给定的一组q_i作出的最大交货数，因为序列q₁,q₂hellip;q_t代表一个可行的组合，它可能是在最优的解决方案中。因此 计算要使用的聚合数的方法必须在最终聚合中承认q₁,q₂hellip;q_t的组合。如果是这样的话，聚合的阶段数N的确定为

因为2^N是聚集的第n阶段和最后阶段聚集的最大点数。

例如，如果C=6000，q_i是表一中Q栏的值，那么q_i的顺序是

1100，1200，1200，1400，1400，1500，bull;bull;bull;1900

t=4。因此N=log₂4=2。在聚合的第一阶段仅允许这些点对其总需求不超过1/2C。在聚合的第二阶段，在不超出卡车的容量的前提下，可以将阶段1的次优解决方案中包含的任何对与其他任何对合并。如果C=7000且q_i还是表1中列出的值。此时t=5,N=3。在聚合的第一阶段，只允许那些组合需求不超过1/4C的点配对。

表一

第二阶段中的配对不超过1/2C，第三阶段不超过 C。虽然N＝2比N＝3更接近log₂5，但三个阶段必须采用，因为共有2个阶段不允许可行组合1100、1200、1200、1400、1400，这可能是最佳组合。

读者应该注意到，如果一辆卡车只能访问两点并返回，所覆盖的总距离是 从终端到每个点Pi的距离，加上中间距离之和。（因此，我们将尽量减少后者）。因此，在每个中间阶段，确定对应于最小对间距离的最佳配对，在最后阶段确定最佳配对使得总行程为最小值。下面将通过一个数值例子来说明这个过程的细节。 卡车调度问题现在可以正式表述如下：

[1] 给定一组“站点数”Pi（i=1，2bull;bull;bull;n），由P₀向Pi交付，称为“终点”。

[2] 给出了一个“距离矩阵”[D]=[d_ij]，它指定了每对点之间的距离 d_ij=d_ji（i，j=0，1，hellip;n）。

[3] 给出了一个“传递向量”（Q）=（q_i），它指定要传递到每个点Pi（i=1，2hellip;n）的量q_i。

[4] 卡车容量为C，其中Cgt;max.q_i。

[5] 如果x_ij=x_ji=1被解释为P_i点和P_j点是成对的（i，j=0，1，hellip;n）如果x_ij= x_ji =0表示点没有配对，得到条件

因为每个点P_i，要么与P₀相连，要么至多与另一个点P_j相连。此外，根据定义，x_ii=0, i=0，1，bull;bull;bull;n。

[6] 问题是找到x_ij的值，在[2]到[5]中指定的条件下，使总距离最小。

3.计算程序

3.1.一般性意见

根据条件[5] x_ij只能假定值为1或0。目前，尚无解决离散变量问题的通用方法，但可能是R. Gomory（4）的最新提议的某些变体，该提议尚处于发展阶段，无法评估当前问题。然而，如果一个人承认较弱的条件

然后应用著名的线性规划方法。可能在“解”中出现分数值表示点或点群的可选配对。经验表明这样的可选对的数目很小，因此通过反复试验可以很容易地找到最小行驶里程。然后得到满足x.y为0或1要求的“解”；但是，其他现在可用的求解离散变量问题的算法，不能保证得到绝对最优解。很可能用这种方法得到的“最佳解”在点数增加时接近于最优解。此外，因为x_ij=0或1介于用本文方法得到的“最佳解”和满足0le;x_ijle;1的最小值之间，对最小距离D的误差进行估计。

3.2.第一阶段聚集

详细的计算过程最好用表1所示的数值例子来说明。从点P₀到点P₁hellip;P₁₂交货。每个框右下角的条目是P_i和P_j之间的最短距离。这些条目是[2]中讨论的距离矩阵。传递向量（Q）显示在三角形阵列的左侧。如果C=6000 gal，阶段数为2（见第2节） 。x_ij被输入到每个框的左上角。首先所有传输点P₁bull;bull;bull; P₁₂可与终端P₀配对，以便有12个条目x_0,i =1，其中i=1，bull;bull;bull;12。这12个条目构成了 在计算开始时的基本集。在接下来的每次迭代中，基本集合的元素被删除，并被一个新元素替换。因此，在第1阶段，基本条目x_ij的数量保持不变。每个框中剩余的左上角保持为空或永久有一颗星星。空框构成条目的“非基本集合”，都等于0。然而，实际上并不是为了将它们与属于基本集的零区分开。这一区别是必要的，因为在这一特殊情况下，基本条目不超过12个。星号条目表示各个点的配对在第一阶段不可接受，因为点数超过卡车容量的一半。因此，P₅和P₆的总需求为1700 1900=3600，大于C/2=3000。

3.3.快速修正

通过一系列快速校正，可以容易地改进每个点与终端配对的起始解。这是可取的，因为后续迭代次数随着初始解和最优解之间的差异减少而减少 。

可以通过将对应相对较小的d_ij值的非基本条目放入解中来进行快速更正。因此，d_6，7=7相对较小，可以通过将尚未确定的theta;值输入相应的左上角而将其带入基本集。为了满足方程式（3），任何i=1，2，hellip;n的基本项之和必须等于1。由于距离矩阵（D）是对称的，因此表1所示三角形数组中第6行和第6列的基本值也必须等于1。第7行和第7列也是如此。因此，以下条目如下：

x_6,7=theta;（非基本项x_6,7=0增加）

x_0,6=1-theta;（基本条目x_0,6=1已更正）

x_0,7=1-theta;（基本条目x_0,7=1已更正）。

与不等式(5)一致的的theta;最大值是1。因此

x_6,7=1 , x_0,6=0和x_0,7=0

因为必须删除一个基本条目，所以可以选择：x_0,6和x_0,7。因为距离d_0,7大于d_0,6，为了尽可能减少总距离,将基本条目d_0,7从基本集合中删除。总的来说 刚才讨论的操作序列的影响是，条目x_6,7=1已经添加到基本集合中，x_0，6的值已经从1更改为0，x_0,7已被删除。从几何角度来说，这意味着第6和第7点 已从终端断开并相互连接。只要具有较低距离值的非基本条目可用，就可以重复快速校正的过程。一个很好的规则来获得快速改进的解决方案是：如果条目x_0,i或者x_0,j已从基本集合中删除或具有值0，则跳过任何距离值d_ij。

表1前四次迭代如下：

迭代（1）：x_1，2 =1 替换x_0,2；x_0,1=1变为x_0,1=0

迭代（2）：x_6，7 =1 替换x_0,7；x_0,6=1变为x_0,6=0

迭代（3）：x_3，4=1 替换x_0,4；x_0,3=1变为x_0,3=0

迭代（4）：x_11，12 =1替换x_0,12；x_0,11=1变为x_0,11=0

新的基本集如表2所示，其中的theta;项目应被忽略。由于前四次快速修正，配对距离之和已从364个单位减少到170个单位。

3.4．Delta函数（相对成本系数）

当足够多的点对具有较小的中间距离时，如果不计算每种情况下的总距离，就越来越难以引入额外的点对。这相当于一个试错程序，即使点数只是中等偏大，也需要巨大的计算量。因此，需要一个标准，使计算机能够在扫描表2中的数组时接受或拒绝非基本项。该标准由Delta函数定义为

其中，pi;_i^（n）和pi;_j^（n）是第n个迭代确定的常数特性。根据定义确定pi;_i^（n）和pi;_j^（n），使得

对于所有与基本条目相对应的dij。非基本分录

delta函数表示每

剩余内容已隐藏，支付完成后下载完整资料

资料编号：[238396]，资料为PDF文档或Word文档，PDF文档可免费转换为Word

您可能感兴趣的文章

• 使用多标准移动通信分层遗传算法的阻抗 匹配网络的宽带优化外文翻译资料
• 移动RFID标签阅读与非重叠串联阅读器在输送带的应用外文翻译资料
• 利用数字图像进行的全场应变测量方法外文翻译资料
• 自然灾害中并发事件的多种应急资源的分配外文翻译资料
• 基于主机的卡仿真：开发，安全和生态系统影响分析外文翻译资料
• 实现基于Android智能手机的主机卡仿真模式作为替代ISO 14443A标准的Arduino NFC模块外文翻译资料
• 探索出行方式选择和出行链模式复杂性之间的关系外文翻译资料
• 信息系统研究、教育和实践的基本立场及其影响外文翻译资料
• 仓储和MH系统决策模型的设计优化与管理外文翻译资料
• 关于近场通信技术的调查外文翻译资料