优化 | 详解资源受限的基本最短路问题(ESPPRC)：模型、复杂度证明及C++调用CPLEX代码实现

• 资源受限的基本最短路问题

• 问题描述

• 数学模型

• 复杂度证明

• ESPPRC的松弛

• 数学模型

• 补充完善

• 总结与展望

• C++调用CPLEX完整代码获取方式

• 参考文献

资源受限的基本最短路问题

在使用列生成求解车辆路径规划问题（Vehicle Routing Problem）和人员排班问题（Crew Scheduling Problem）时，定价子问题通常可以看成资源受限基本最短路问题（Elementary Shortest Path Problem with Resource Constraints，）或者其变种问题。因此， 及其变种问题在列生成的应用中是非常重要的。

本篇推文首先介绍 的问题描述以及数学模型，然后详细证明了 的复杂度为强 难（ hard in the strong sense）。鉴于 的复杂度，在求解时会将其松弛为资源受限最短路问题（Shortest Path Problem with Resource Constraints，）。 的数学模型在推文中也会进行详细的介绍。推文中出现的模型由 Brian Kallehauge 等人提出，并收录于《Column Generation》一书中（见文献5）
。对于书中的模型，我们使用了 CPLEX 进行数值实验，并根据实验结果对模型进行了相应的补充。

问题描述

有一辆装载容量为 的货车，这辆货车从起点 出发为客户送货，最后到达终点

有两种资源：时间和货车容量（容量可以折算成重量）

有 个需要服务的客户，这些客户分布在不同的地点，客户集合用 来表示。每个客户 都有各自的商品需求量 和服务开始时间窗，也就是说，客户 的服务开始时刻（即货车到达客户 的时刻）必须落在时间区间 内。

将起点 记作 ，将终点 记作 ，则有节点集合

从节点 到节点   的运输时间为 ，运输成本为

目标：在货车容量不超载，每个客户最多被访问一次且服务开始时刻落在相应的服务时间窗内的情况下，最小化运输总成本

也可以表示为：

• 给定 (参数)

• 约束

• 目标

数学模型

这一节主要参考的是 Column Generation 书中的第三章，引用 Brian Kallehauge 等人提出的模型：

• 变量

• 表达式

• 详解

• 补充完善

在使用CPLEX求解器进行数值实验时（完整代码获取方式见文末），返回的解出现如下问题：

x_2_2: 1
x_5_5: 1
x_6_6: 1
x_8_8: 1
x_10_10: 1

任何节点都不能是自己的前继节点或者后继节点，所以我们应该加上约束：

在原来的模型中加上这个约束之后，得到如下结果：

solving time: 0.034 sec
route cost: -214.43
x_0_9: 1
x_5_10: 1
x_7_5: 1
x_9_7: 1
x_10_11: 1
route: 
0-9-7-5-10-11
arrival time at node 0 : 0 
arrival time at node 9: 281
arrival time at node 7: 391
arrival time at node 5: 888
arrival time at node 10: 1091
arrival time at node 11: 1114.76

复杂度证明

在这一节中，我们证明 是一个强 难问题，主要参考的是 Moshe Dror 于1994年发表在 Operations Research 上的文章，并在其基础上做了一些补充。具体证明过程的步骤如下：

• 步骤 0：将 转化成相应的判定问题

  在 中， 的参数和约束都保留，并将 的目标替换成如下判定：

  “是否存在一条可行路径，其运输总成本为 ?”

• 步骤 1：证明 是 类问题

  我们可以在多项式时间（Polynomial Time）内“瞎猜”一条路径，并在多项式时间内验证

• 步骤 2：选择一个合适的强 完备问题

  这里我们选择收录于 Computers and Intractability 书中的一个强 完备问题，称为“带时间区间的排序问题（Sequencing Within Intervals, ）”， 的问题描述如下：

• 步骤 3：使用伪多项式归约，把 转化成 （即任意一个 的算例都可以用固定的转化成 的算例）。

详解：

可以看到， 算例中的数取自 算例或设为常数。其中， 中的客户对应 中的任务； 的服务开始时间窗对应 中的任务执行时间窗，但是需要做一些调整。因为 中的 是任务 的最晚结束时刻（latest conclusion time），换算成任务 的最晚开始时刻（latest start time）就是 。因此， 中的 设为 。而 中的弧 的弧值   和 则设为 。另外，货车容量 设为 。最后，在 中需要判定，是否存在一条可行路径，其运输总成本为 。

在此算例设计下，如果 的判定为“是”，即存在一个可行的排序方式，使得所有任务在时间上互不重叠的情况下被完成，那么 的判定也为"是"，反之亦然。

我们可以直接将 的可行任务执行顺序看成 中访问客户的顺序，这条相应的路径 在 中是可行的，且运输总成本为 ，因为：

反之，如果我们在找到一个关于 的可行路径，也相当于找到了一个 的可行任务排列顺序。

令 的算例为 ，) 为算例 中最大的数值， 反映算例 的规模，上述的算例归约方式为 ，则规约后的 的算例为 ，上述的算例转化是伪多项式归约（Pseudo-polynomial Transformation），因为：

得证， 是强 完备问题， 所以 是强 难问题。

ESPPRC的松弛

由于 是强 难问题，在求解时通常会松弛问题中的某些约束。其中，应用非常广泛的就是允许路径中存在子回路，即允许客户被多次访问。如此，问题就变成了资源受限最短路问题（ ）。

数学模型

基于前面介绍过的 的模型，Brian Kallehauge 等人对 也给出了如下数学模型：

在模型中定义了一个额外的集合 ，用来表示路径中弧的顺序。由于每个客户都可以多次访问，所以无法确定最后求得的路径中包含几条弧，但是路径所包含的弧的个数的上限 是可以确定的。路径长度受限于容量资源和时间资源，所以  。

需要注意的是，虽然在 中，每个客户允许被多次访问，但是，起点和终点在路径中还是只能出现一次。

• 变量

• 表达式

• 详解

补充完善

我们使用CPLEX求解器对该模型进行数值实验（完整代码获取方式见文末），测试算例中有10个客户，即 。从决策变量的取值发现如下问题：

• 问题一

  x_0_0_0 : 1
  x_11_11_1 : 1
  x_6_6_2 : 1
  

  任何节点都不能是自己的前继或者后继节点，所以，我们应该加上约束：

• 问题二

  x_5_10_1 : 1
  x_6_10_1 : 1
  

  不能存在两条下标（index）一样的弧，所以，我们应该加上约束：

• 问题三

  x_11_0_6 : 1
  

  节点 不能有后继节点，所以，我们应该加上约束：

• 问题四

  x_2_0_3 : 1
  

  节点 不能有前继节点，所以，我们应该加上约束：

• 问题五

  s_9_4 : 281
  s_9_5 : 121.24
  

  客户节点可能会在路径中多次出现，服务开始时刻必须是单调递增的，所以，我们应该加上约束：

在模型中补充了上述约束之后再进行求解，得到如下结果：

route length: -214.43
x_0_9_0 : 1
s_0_0 : 0
s_9_0 : 281
======
x_5_10_3 : 1
s_5_3 : 888
s_10_3 : 1091
======
x_7_5_2 : 1
s_7_2 : 391
s_5_2 : 888
======
x_9_7_1 : 1
s_9_1 : 121.24
s_7_1 : 391
======
x_10_11_4 : 1
s_10_4 : 1091
s_11_4 : 1440
======
0-9-7-5-10-11

推文中数值实验的源码以及测试算例可以通过转发集赞或者打赏的方式获取~

总结与展望

在本篇推文中，我们介绍了 以及 的问题描述和文献中的数学模型，并借助CPLEX求解器对模型进行了数值实验，又根据数值实验的结果对文献中的模型进行了补充完善。另外，我们还证明了 是一个强 难问题。正因如此，在求解大规模算例时，单纯依赖求解器的话无法在合理时间内得到高质量的解。更好的方式是使用动态规划来求解，关于动态规划求解 / 会再之后的推文进行详细的介绍，在数值实验的部分也会将动态规划求解与solver求解进行对比。

C++调用CPLEX完整代码获取方式

参考文献

1. Desrochers, M., Desrosiers, J., and Solomon, M. (1992). A new optimization algorithm for the vehicle routing problem with time windows. Operations Research, 40:342-354.

2. Dror, M. (1994). Note on the complexity of the shortest path models for column generation in VRPTW. Operations Research 42:977-978.

3. Garey, M.R. and Johnson, D.S. (1979). Computers and Intractability, W.H. Freeman and Co., San Francisco.

4. Kallehauge, B., Larsen, J., Madsen, O.B., Solomon, M.M. (2005). Vehicle Routing Problem with Time Windows. In: Desaulniers, G., Desrosiers, J., Solomon, M.M. (eds) Column Generation. Springer, Boston, MA.

5. Desaulniers, Guy, Jacques Desrosiers, and Marius M. Solomon, eds. Column generation. Vol. 5. Springer Science & Business Media, 2006.