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

23.3 约束规划方法

约束规划方法对于许多问题的类型是要逐步寻找问题的解，当检测到不可行性时，就会返回到之前的步骤重新求解，直到解被发现或能够证明该问题无解。

这种方法可以适用于VRP问题，但它通常是效率太低而不被使用。在绝大多数的实际问题中，解的存在性是毋庸置疑的。真正的问题是如何确保解的质量。

与约束规划方法在所有优化问题中的应用一样，该方法是在大量的可行的方案中寻找最优解或者次优解，而不是在大量的不可行方案中找到一个可行解。

我们进行搜索的方法反应了重点的变化。本地搜索方法和修复方法能够吸收约束规划框架中的优点，所以它们已经得到了发展。

这些搜索方法将在23.5节中讨论。下面我们介绍两个有效的基于约束规划的VRP求解问题。

23.3.1 用约束条件描述路径问题

本章节详述带有时间窗的且每条路线上都具有很多货物约束条件的VRP问题的约束规划方法。这个模型可以作为很多问题的基础，比如限量的车辆路径问题，带有时间窗的车辆路径问题，货物的装在和运输问题，和其他的车辆路径问题的变种问题。约束规划的主要优点是多变性，即它允许建模者添加不同的复杂问题和扩展，而不调整的基本模型。

这里所描述的约束规划模型是在[19，90，31]和[94]中描述的最早的在路径问题中运用约束方法的一个拓展。这些方法实质上都用同样的方法去建模，在路径方面，使用路径约束。多车辆方面在[31，69]中有介绍。我们在本节中描述的传播规则由[90]描述的模型来实现。 他们也被用于C 工具包ILOG求解程序[62]和ILOG分派器[61]，两者分别用于一般约束规划和基于约束的车辆路径问题。

像之前所说的，我们有n个客户订单和m个车辆。条件会在每次车辆停止的时候进行访问。每次停止时，每个客户有一次访问，每个车辆有两个特殊的访问。这两次额外的访问会在每个车辆模型的出发时刻和停止时刻进行。用C = {1 . . .n}表示客户，M = {1 . . .m}表示车辆，V = {1 . . .n 2m}来表示访问。对于某一个车辆k的第一次和最后一次这两次特殊的访问，我们引进符号f_k和l_k。访问n k是车辆k的第一次访问(f_k = n k)，l_k是车辆k的最后一次访问(l_k = n m k)。集合F = {n 1 . . .n m} 和 L = {n m 1 . . .n 2m}分别表示所有首次访问和所有最后一次访问的集合。

为了模拟路线，整数变量P_i，iisin;V( V={1 . . .n 2m})描述每一次访问i的直接前身。按照惯例，车辆的每一个“第一次”访问的前身是车辆的“最后一次”访问(forall;_kisin;M p_fk = l_k)。前身变量形成一个V的排列并受到不同条件的约束：

p_ine;p_j forall;i, j isin; V and; i lt; j (23.11)

这就是说在ILP模型中，每个节点的流入量和流出量都必须等于1。一个不同的约束传播遵循下面的规则。参照[90]中，我们用{{X}}来表示变量x的当前域。

x ne; y:{{x}}={a} → y ne; a (23.12)

x和y是约束整数变量，a是一个整数。传播规则在这里被写为LHS→RHS，其中LHS是一个真实性可以容易地被检查的可变域的条件逻辑组合，RHS是一个一元的约束或可以通过简单的域滤波来执行的结合。上述规则只有当x的域被减少到单个值a的时候失效。RHS将在从y的域中删除a的时候被执行。

每次访问i的时候，s_i表示它的直接继承。继承变量通过以下约束元素与前身变量保持“连贯”（一致），表示为：

s_pi = i forall;iisin;V–F p_si = i forall;iisin;V minus; L (23.13)

元素约束采用两个整型变量y和z和整数向量，在这种情况下，整数变量的X。该约束指定z必须等同于x的第y个元素。这种类型的约束在约束规划模型中很普及，并且，以作者所知，它被所有知名的约束规划引擎所支持。它传播如下所示：

z = x[y]

{{y}}={a}and;exist;b notin; {{z}} → x[a] ne; b

exist;a{{x[a]}}cap;{{z}} = empty; → y ne; a (23.14)

exist;b(forall;aisin;{{y}} b notin; {{x[a]}}) → z ne; b

相干约束23.13可以像下面这样实现（我们只展示两种形式中的一种）：

s_pi=i:z=s[p_i]and;z =i (23.15)

请注意，使用的前身变量和继承变量会创建一个我们现在将要介绍的将在约束中反映出来的对称模型。严格地说，VRP的解空间的提出可以仅通过可变集（前身变量或继承变量）中的一个，而不改变该问题的解决方案的设置。然而，通过同时添加（冗余模型），我们就可以得到附加推论，而它可以大大减小搜索空间。

对于多车辆模型，一个属于域{1 . . .m}的车辆变量v_i在每次访问i时会被介绍。自然地，对于第一次和最后一次访问，约束条件forall;k isin; M v_fk = v_lk = k会被施加。对于整个路径，所有的访问都会被同一辆车执行。这个约束条件如下所示：

v_i=v_pi forall;iisin;Vminus;F v_i=v_si forall;iisin;Vminus;L (23.16)

这些约束条件规定了路径的信息，这就是所谓的路径约束。以上是路径约束的最简单的形式;更复杂的将被用于约束路径的时间和货物的数量。以上路径约束只用约束元素就能实现。

或者，减少一些严格的约束形式，被称为“边界一致性”。它只要求最低和最高合法值被保留。存储和使用变得更加便宜，但是它会变得不那么强大。然而在特定的情况下，它也是够用的。我们将边界条件写成x:=e，表示所有ilt;e的将被从x的域中移除；如果写成x:=e，表示所有igt;e的将被从x的域中移除。

在车辆上的货物的数量将改变域的大小和使用的模型，只有保持边界一致性才会有高效率。我们用一个实数或者一个整数变量去表示每次的访问。让q_i ge; 0代表一个约束变量，表示在进行访问i之后车上的货物数量。让r_i ne; 0表示在访问i处装载的货物数量，如果这个数量是负数，则代表卸载货物。下面的路径约束规定了路上的车辆在它们的路径中的每个点的装载及卸载情况。

q_i = q_pi r_i forall;i isin; V – F q_i = q_si minus; r_si forall;i isin; V – L (23.17)

由于变量q的域很大，只有边界一致性能使问题变得高效。下面是上述约束条件的传播规则：

q_i = q_pi r_i

Let P = {k | k isin; {{p_i}} and;

min{{q_k}} r_i le; max{{q_i}} and;

max{{q_k}} r_i ge; min{{q_i}}}

Then (23.18)

exist;k isin; {{p_i}} k notin; P → p_i ne;k

exist;k isin; P forall;l isin; P min{{q_k}} le; min{{q_l}} → q_i ge; min{{q_k}} r_i

exist;k isin; P forall;l isin; P max{{q_k}} ge; max{{q_l}} → q_i le; max{{q_k}} r_i

q_i = q_si minus; r_si

Let S = {k | k isin; {{s_i}} and;

min{{q_k}} minus; r_k le; max{{q_i}} and;

max{{q_k}} minus; r_k ge; min{{q_i}}}

Then (23.19)

exist;k isin; {{s_i}} k notin; S → s_i ne; k

exist;k isin; S forall;l isin; S min{{q_k}} le; min{{q_l}} → q_i ge; min{{q_k}} minus; r_k

exist;k isin; S forall;l isin; S max{{q_k}} ge; max{{q_l}} → q_i le; max{{q_k}} minus; r_i

车辆具有有限的容量。为了表示这一特征，我们用一个简单的不等式来约束变量a。假设车辆k的容量是Q_k，我们用以下约束条件来表示：

q_i le; Q_vi forall;i isin; V (23.20)

这个模型中每个车辆可能有不同的容量。注意，没有像forall;i isin; F q_i = 0这样的表示车辆变成空的约束条件被施加。我们可以通过这些约束来建立不同的模型。这包括装载和卸载，其中车辆可以在开始的时候（部分）满载和结束的时候（部分）满载，和在途中装载和运送的问题的混合问题（见下节）。

时间大概用跟车辆负载同样的方式表示，但是通常等待是被允许的。所以路径约束条件是一个不等式而不是一个等式。用变量t_i ge; 0表示访问i开始的时间。

下面的约束条件表示车辆行驶的时间：

t_i ge; t_pi tau;_pi,i forall;i isin; V – F t_i le; t_si minus; tau;_i,si forall;i isin; V minus; L (23.21)

传播方法之前在传播负载(23.18, 23.19)中介绍了，这里就不在赘述，唯一的不同就是它是一个累积的不等式而不是一个累积的等式，去描述允许等待。

客户时间窗由变量t来表示。举例来说，约束条件a le; t_i le; b表示客户i必须在a和b之间的某个时间被服务。我们也可以建立多时间窗[90]的模型，举个例子，两个约束条件a le; t_i le; d和 t_i le; b or; t_i ge; c表示客户i要么在ac时间点之间被服务，要么在cd时间点间被服务(a le; b le; c le; d)。

不同的车辆可以拥有不同可用时间窗。假定车辆的最早的启动时间是O_k，最后停止时间是H_k。车辆的可得性由下列式子约束（再一次用到约束元素和不等式）：

O_vi le; t_i le; H_vi forall;i isin; V (23.22)

为了避免不包括起点和终点的环形路径（消除子回路），一个专门的约束条件会在23.3.3中叙述。然而，还有另一个传播更少而且具有不需要常规约束的优点的简单方法，就是让每辆车都有一个有限的视野，而且每次服务的时间都是严格大于零的。

最后是成本函数，通常包含总路程d，还可以包括别的元素，比如使用车辆的数量，由下列式子表示：

其中delta;_i,j是从i到j的行驶距离。注意要同时使用前身变量和继承变量去约束成本，那样的话可以比只用一个变量去描述更高效。在总数中的每一项由一个约束元素限制，但总数会被一个合计约束条件限制，它的继承细节在这里跳过，除了再次提起它，只有变量的边界保留在合计中。 剩余内容已隐藏，支付完成后下载完整资料

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