作者：陈恺杰，东方航空信息部，算法工程师
修改 & 审校：刘菲雪，清华大学，清华大学深圳国际研究生院，清华-伯克利深圳学院，硕士在读
修改 & 审校：刘兴禄，清华大学，清华大学深圳国际研究生院，清华-伯克利深圳学院，博士在读
-
资源受限的基本最短路问题
-
问题描述
-
数学模型
-
复杂度证明
-
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 等人提出的模型：
-
变量
: 到达点 的时刻
-
表达式
-
详解
-
式为目标函数，目标是最小化运输总成本。
-
式为容量约束（capacity constraint），规定总运输量不能超过货车容量。
-
式-式 为流平衡约束(flow conservation constraints)，其中，
式规定，路径中存在一条起始节点为 的弧。
式为客户节点之间的流平衡约束。
式规定，路径中存在一条目标节点为 的弧。
-
式和式为时间窗约束(time window constraints)，其中，
式规定，若路径中存在弧 ，那么到达节点 的时刻不早于到达节点 的时刻加上经过弧 的运输时间。
值得注意的是，式同时防止了路径中子回路（subtour）的产生，从而确保每个点 在路径中最多出现一次。
式规定，到达点 的时刻必须落在给定的相应时间窗内。同时，式也规定了变量 的值域。
-
式规定了变量 的值域。
-
补充完善
式中需要设定 的值， 满足足够大但是尽量小，可以设为 。
在使用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 等人对 也给出了如下数学模型：
在模型中定义了一个额外的集合 ，用来表示路径中弧的顺序。由于每个客户都可以多次访问，所以无法确定最后求得的路径中包含几条弧，但是路径所包含的弧的个数的上限 是可以确定的。路径长度受限于容量资源和时间资源，所以 。
需要注意的是，虽然在 中，每个客户允许被多次访问，但是，起点和终点在路径中还是只能出现一次。
-
变量
: 第 条弧上到达点 的时刻
-
表达式