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

带时间窗的中国邮递员问题的一个约束规划方法

U.F. Aminua, R.W. Egleseb,lowast;

a数学与计算机研究系, 哈桑乌斯曼卡齐纳州理工学院, PMB 2052, 卡齐纳州,尼日利亚卡齐纳州

b管理科学系, 兰开斯特大学, 兰开斯特 LA1 4YX, 大不列颠及北爱尔兰联合王国

摘要

我们为带时间窗的中国邮递员问题 (CPPTW) 建立一个约束规划模型，并基于有69个边的数据测试并得出实验结论。我们基于实际问题提出了两种不同的构思方案。第一种方案可以直截了当的解决问题，而第二种方案则是将带时间窗的中国邮递员问题转化为具有时间窗口的等效车辆路线问题。从实验结果上看，当时间间隙很小时，可以快速获得最优解。然而，实验结果还表明，随着时间间隙的扩大和可行解数量的增加，这些约束规划公式显著地需要花费更长的时间以找到可证明的最优解。实验结论也同样告诉了我们图形的大小和密度是如何影响我们通过计算找到最佳可行方案的时间。

关键词： 弧线路问题；中国邮递员问题；车辆路线问题；时间窗；约束规划

1. 引言

管梅谷[1] 在1962年提出的中国邮递员问题 (CPP)是电弧路由问题 (ARPs) 的一种。它的目的是为无向图论问题找出包含所有边缘的最短路线即最低成本。接下来，正式的给出定图G= (V, E) ，其中 V 是一组顶点，E是一组无向边 ，待解决的问题是从同一个顶点出发，经过E中所有边缘，并且最后回到起点，要求经过的总路线最短。该问题的一个典型情况是时间依赖无向中国邮递员问题(UCPPTW)，或简单的带时间窗的中国邮递员问题 (CPPTW) ，其中一个点被指定为仓库顶点，问题要求起于顶点，走遍整个仓库后再回到仓库顶点。此外，我们引入时间窗约束，以确保每个边沿的到达都满足指定的最早和最晚的时间约束。

CPPTW常常应用在邮政运送和道路治理等领域，例如消除积雪，防止路面结冰等。然而，在许多实际应用上，对该问题进行建模往往一般可能需要考虑另外的因素，例如具有有向边（或弧）和无向边的混合的问题。当没有额外的约束时，可以使用Edmonds 和 Johnson [2] 所描述的方法来有效地最优化地解决中国邮递员问题。而时间窗口约束的添加会使得问题变得难以解决。这也意味着问题是非确定性多项式难题 [3] 。因此，可以预期任何保证最佳解决方案的算法，计算时间都会随着问题的大小呈指增长。

本文提出了使用约束规划（CP）来解决带时间窗的中国邮递员问题（CPPTW）的两个确切模型。约束规划（CP）早已成功应用于路由问题[4,5]。然而，这些路由应用程序的所有已发布的工作都在每一个网络中要访问一组客户（城市）一次的节点路由上。这些城市形成图形上的节点，并以图形上对应位置的坐标来表示 [6]。图上的边长作为节点或者说客户位置的链接，从而用来代替城市之间或者说客户之间的距离。

在这些模型中，已经假设在图上行进的时间等于整个路线上行进的成本。在实际生活应用中，成本和时间通常都不是相同的单位，并且，为了实现服务目的（例如除雪）而在边线上行进的时间和成本可能不同于简单的在边沿上行进的成本，这种情况通常被成为死胡同。当然，这些考虑不会不会影响到本文提出模型的基本结构。

1. 第一个模型

我们添加一个任意边来表示仓库节点。这样以来，图中边的总数为N 1，其中N是图中原始边的数目。我们使用变量来表示图表边沿的顺序。令Ei 为变量，ei E，所以Ei 的值表示ei在实验排序中的位置，并且让Edge_depot作为表示代表节点的任意边的变量，该变量表示代表仓库节点的任意边。定义Edge ={E_i，Edge_depot|i=1,...,N}作为所有模型变量的集合，那么边缘变量的范围将为{1,...,N}，基数是N 1。

定义另一组二进制变量，表示运行时边是在哪个方向上被经过。对于每个边，ei =(p, q)，定义zi为运行时边被经过方向的（0,1）变量。假设plt;q，如果沿边运行方向为pq，那么zi=0；如果沿边运行方向为qp，那么zi=1。为了找出从开始经过ej 到离开ei所花费的成本（或时间），当ej在规则中遵循ei时，方向变量可用于指示ei的最终节点和ej 的起始节点，以便可以从预先给出的算式中计算找到适合的最短路径。任何已知的最短路径算法都可用于计算ei和ej 之间最短路径的成本。

最终变量集合显示了经过每个路径的成本（或时间）。Costi是ei E的成本，Costij 是当路线开始于ej E,结束于ei E的节点的最短路径成本，LCostj是ej E的长度的实际给定成本，Costj是实验中经过ej E的成本。然后对于边ej E连ei E，公式(1)成立。

Costi Costij LCostj trade; Costj . (1)

让Eli Eui分别成为更低和更高的时间窗口，对于边ei，定义CE为完整旅途费用的上限。带时间窗的中国邮递员问题（CPPTW）的第一个模型现在可说明如下：

min CostN 1 (2)

s.t.

Costi Costij LCostj trade; Costj forall;i /= j, ei, ej isin; E, when ej follows ei , (3)

Eli trade; Costi trade; Eui for i = 1,...,N , (4)

0 trade; CostN trade; CE, (5)

Edge:: [1 ...N 1], (6)

alldifferent(Edge), (7)

EdgeDepot = N 1. (8)

目标函数（2）表示在指定为仓库的节点开始和完成的网络的所有边上完成服务的可能最短时间。（3）可用于计算当前部分路径的成本，（4）表示为了服务于当前边的时间窗口，（5）则定义了图表边的时间窗口。（6）给出了边缘变量的范围，并给出了这些变量必须全部受不同的约束（7）。如（8）所示，仓库节点的变量被约束为具有N 1的值。这样就可以确保整个过程在仓库节点启动并完成。我们还可以在模型中加入其他几个约束条件，以加强约束规划模型的普及率。

1. 第二个模型

第二个模型的灵感来自于Pearn等人 [7]。在他们的论文中，他们提出用图一所示的三个侧中节点sij , mij , sji替换图G= (V, E)的每个边(i, j)。

从图一中我们可以看到，假设x是边(i, j)的长度，那么中间节点刚好在(i, j)的x/2处，而sij位于i的x/4处，sji位于j的x/4处。相应的节点路线问题定义在节点集N={1} 上，1表示仓库节点。本文将为此转型提供公式为F1。转换为F1将使形成问题所需的变量数量增加3阶，因为需要三个节点来表示原始问题中的每个边。

i j

sij mij sji

图一. 使用Pearn等人的方法将CPP转化为节点路由

i j

sij sji

图二. 对Pearn等人方法的修改

使用这种方法，问题被转换为车辆路线问题（VRP），不需要任何额外的约束，因为中间节点的使用可以确保边缘的三个节点被连续经过。这样一来，可以使用任何已知的VRP方法来解决变换的问题。然而，这种方法可以通过配上Pearn等人使用的“中间节点”并仅使用侧节点s_ij 和s_ji来表示每个边(i, j)E并添加其他约束来改进[7]，如图二所示。

对于具有时间窗口（CCPPTW）的中国邮递员问题，它们代表要求节点s_ij 和s_ji上的d_ij和d_ji等于边（i，j）的需求的一半。我们在节点集上定义相应的节点路由问题N = {1}cup;{s_ij ,s_ji|(i,j)isin;E}，其中1表示仓库节点。节点间距离现在根据以下公式定义：

其中，dist(i, k)是从i到k的最短路径。在本文中，将作为F2提及该公式。转换的问题现在可以被形成为具有时间窗口的群集旅行商问题的特殊情况，其中在访问不同群集中的节点之前，必须在其时间窗口内访问群集的每个单位。在这种情况下，集群由s_ij和s_ji配对组成。因此，我们添加额外的约束来保证s_ij和s_ji是任意路线中的连续节点。令变量S_ij 和S_ji分别表示点s_ij和s_ji在边edge_k isin; E上的交点。假设节点s_mn是s_kl的后继。令NCostkl成为完成S_kl的成本，令NCostmn成为完成Smn的成本。那么，NCostkl NCost(Skl, Smn)NCostmn，其中NCost(Skl, Smn)是点S_kl和点Smn之间的最短路径的成本。NCost的实际值(Skl，Smn)预处理和一个正方形矩阵。

我们使用两个变量来表示库节点。每个节点分配一个介于0和2Nminus;1中的数，其中N是在原无向图的边数。让SDepot(start) 和SDepot(end)作为表示巡回开始和结束时的库节点的变量。模型变量的集合可以定义为S = {S_ij , S_Depot(start), S_Depot(end) | S_ij = 0, . . . , 2N - 1}，则表示G的节点的变量的范围为{0，hellip;，2N 1}。因此,每个S_ij的值将被赋值为0和2N 1之间的值，这包括开始和返回路径的两个附加值2N 1和2N。这些值是由IlcPath()约束保留和实现的。对于每个边k = (i, j)，将ECostk定义为从i或j的最小成本路径返回仓库的较大成本，如果随后将CE定义为所有边缘的Eu_k ECost_k的最大值,则每个成本变量将有一个范围。假设l_k是实验在edge_k上开始的时间，Eu_k是相应的上限时间窗口。对于S中的所有变量，Next_ij是在S_ij之后选择的变量，即Next

全文共8722字，剩余内容已隐藏，支付完成后下载完整资料

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