论文拾萃|用MOLS+算法解决包含外包和收入平衡的VRP问题

一.问题描述：VRPOPB问题

（Vehicle Routing Problem with Outsourcing and Profit Balancing）

从前有一位商人，他要把货物送到他的顾客手中，那么他现在就必须做好运输的规划，让自己的运输成本最小。这就是我们熟知的VRP（Vehicle Routing Problem，车辆路径）问题。

但是，作为一个小小的商人，怎么可能自己拥有那么大一支车队呢？

就算能买下一支车队，保养车辆，发放司机的工资，这不是白白地给企业增加风险吗？

在这时，一种新的业态就产生了：「外包」。一个人跳出来说：你给钱，我运货，你告诉我路线，剩下的，你不用管！这个人就是专业运输公司的老板。

粗略了解企业运营的小伙伴们都知道，运输外包把固定成本变成了可变成本，而企业的固定成本越低，则企业风险越可控。想象一下，当你快要倒闭时，你的货车司机来找你要工资时的感觉？

然而，新的问题也随之产生。一句谚语说：“不要把鸡蛋全都放到同一个篮子里。”对于一个初具规模的公司来说，把所有的物品都交给一个外包公司去运送，风险是很大的。

这时，我们就要考虑把货物交给不同的公司去运送。这样一来，不同公司之间的竞争必然导致相互压价，我们渔翁得利，况且，一旦有哪个公司的服务不合我意，把它替换掉也是非常容易的。

这样一来，又有一个新的问题产生了。如何确保我们所雇佣的几个外包公司之间的公平？要知道，几个状况差不多的外包公司，如果相互之间的利润差距过大，是要和我们闹矛盾的。到最后，利润少一些的公司要么要求我们增加报酬，要么就直接拒绝同我们合作，最终吃亏的还是我们。

综上所述，VRPOPB问题要求我们达到两个目标：「最小化运输成本（由车辆路径决定）」、「各外包公司之间的收益平衡」。也就是说，这是一个 「多目标优化」 问题。

本问题中，我们以帕累托最优为优化目标。

二.问题转化

A.前置定义

由上，VRPOPB问题可以抽象成为如下的模型：

给定一个包含N个节点和完全无向图G，N个节点中，一个0号节点代表仓库即运输的起点和中点，n个节点代表着顾客。ci,j表示从节点i到节点j的边权即运输距离。每个顾客都有一个需求货物量di和报酬wi，当然，需求不可被分割，报酬是在满足顾客需求后立马获得。

共有m台车辆（即总集合V），其运载量由C1，C2...Cm给定。有T个运输公司，每个公司拥有的车辆属于Vt集合之中。显然，有Vt1∩Vt2=∅,(t1≠t2)；且V=∪t∈TVt.

在这个问题中，我们还要用到如下定义：

二元决策变量yi,k，表示顾客i是否已经被车辆k服务过

二元决策变量xi,j,k，表示车辆k是否经过边(i,j)

连续变量ui,k，表示车辆k在访问顾客i之前的剩余容量

B.多目标优化模型

根据常理，我们可以得到如下的多目标决策模型。（限制条件都很好理解，就不详细解释啦！）

opt符号可表示最大或最小，函数f1和f2分别与最小化运输成本和利润平衡相关

下面来确定f1和f2。

目标函数f1是为了最小化运输费用，那么我们直接把它定义为运输费用即可。即：

为了表达我们的第二个优化目标即利润平衡，我们需要先引入一个变量pk来表示车辆k所获得的总利润，即：

于是我们可以得到一个企业内每个车辆的平均利润 ：（Wt为t公司的车辆数）

每个运输公司之间的状况不同，我们所谓的“利润平衡”，肯定是平衡各公司之间每辆车的「平均利润」，而不是平衡这些公司的总利润。

于是我们很自然地想到：，然后我们最小化f2。

看起来很有道理罢。

果真如此吗？看下图：

扭曲的解.png

在这张图中，我们用方点代表仓库，圆点代表顾客（每个顾客的报酬都是10），左边（路线1）和右边（路线2）分别由两个只有一台车的运输公司来运送。

如果两辆车都走实线，我们可以得到一组帕累托最优解：S1(f1=22,f2=0).

但是假如右边的车辆走了虚线，我们就可以得到一个新的帕累托最优解：S2(f1=19,f2=3).

这两组解都是帕累托最优的，如果用上述的f2的表示方法的话，都是我们的可行解。

但是，作为供货商，我们当然优先选择总运输费用最低的那一种了！这时，搜索S1的过程就变成了浪费时间。

因此，为了避免这种所谓 “低效平衡” 的产生，我们用一种全新的方式来定义f2:

我们让f2尽量大就好。这就叫做max-min fairness，可以保证每个解都是路径最短的（即TSP最优），完全符合我们作为供货商的利益。

为什么改变f2的表示方式就可以实现稳定的TSP最优呢？下面我们用反证法来证明一下：

给定一个解s(f1,f2)，符合帕累托最优但不是TSP最优。那么我们必然可以用一条TSP最优路线r1来替换路线r，得到一个新的解s1。此时必然有f1(s1)≤f1(s)。

然而，我们只是减少了路径花费，并没有减少运输公司所获得的利润，所以肯定是不会变小的，对吧？也就是说，f2(s1)≥f2(s)。

这时我们发现，既然在s1中f1和f2都没有被负优化，那s还能是帕累托最优吗？肯定不是！

于是这时我们推出了矛盾，所以，解s(f1,f2)符合帕累托最优那一定也保证了TSP最优。

这时，我们终于能愉快地写出我们的目标函数啦！

也即：

决策空间就是前面图中的(2)——(9)。

三.问题解决

我们用「多目标进化算法（MOEAs）」 来解决这个问题。由于VRPOPB是一个离散型优化问题，所以我们在此使用该问题特化的启发式算法（例如改良局部搜索）作为我们MOEAs的主要部分。

在这个板块中，我们首先会引入一些前置定义，然后，我们会设计一个标准的多目标局部搜索算法（MOLS），最后，我们会在MOLS中加入一些实用的优化小技巧，使它成为更强大的MOLS+。

A.前置定义

• S:VRPOPB可行解的集合
• O={O∈R²: o=( f1(s) , f2(s) ), ∀s∈S}是数对的集合（f1(s) , f2(s) 在上文已经给定）
• 当：(1) f1(s1) ≤ f1(s2) 且 -f2(s1) ≤ -f2(s2) (2) f1(s1)＜f1(s2) 或 -f2(s1)＜-f2(s2) (1)(2)条件被同时满足时，则称s1严格支配了s2，记作s1＜s2。
• 给定一个可行解集P，非支配集P1包含不受P中任何元素支配的解。可行搜索空间S的非支配集称为Pareto最优解集。Pareto最优解在目标空间中的图像称为Pareto前沿面。

由上定义可知， VRPOPB问题和CVRP的相似性是很高的。因此，哪怕想要找到一个帕累托最优解也是十分困难甚至不可能的。所以作为替代，我们的目标就是找到一些尽可能接近帕累托最优的解，并且最大化它们的多样性。

B.MOLS

MOLS算法在多目标进化过程中采用了多种局部搜索算子，每个算子都可以从某个方向改进解决方案，每个种群被用来保存一组“有希望的”解。

下图是MOLS算法的大致框架：

Algorithm 1

如上图，在内层循环中，我们每次都会随机生成一组加权向量ω=（ω1 , ω2），其中ω1+ω2=1。

然后，我们用「select_a_solution(P , ω)」 函数在P中找出一组解，再分别用全部的K个算子，用这个选中的解生成K组帕累托最优解，最后再把它们全都加入种群P1中。「LSk(s)」 就是实现用第k个算子生成帕累托最优解的函数。

由于VRPOPB与CVRP的相似性，所以大多数用于CVRP中的局部搜索算子可以被使用到VRPOPB里。

B.1. 种群初始化

所谓初始种群，就是一组可行的解。在这里我们分两步进行。

第一步：

先聚类再排路线，也就是说，先确定顾客被哪辆车所服务，然后再去编排每辆车的路线。

这一步我们用扫描法决定分类。

以仓库为极点（0,0）建立平面极坐标系，把所有顾客的位置用坐标（θ，ρ）表示出来。其中，θ代表极角，ρ代表极径。

我们把所有点按照θ的升序排列（θ相同时按照ρ的升序排列）。这样一来，所有的顾客就组成了一个排列π=（π1，π2，......πn）,πi即顾客i的索引。

然后我们使用贪心算法，把π分到m个车辆中去。

首先，我们用一辆空车来「按顺序」满足π中顾客的需求。对于π中的下一位顾客，我们总是尝试用已经装过货物的车子去满足ta的需求。当所有已经装上过货物的车子都装不下下一个顾客的需求时，换一辆新车来即可。

所有的顾客需求都被分配到车辆中之后，我们对每辆车的路线都分别跑一次TSP就好啦！

第二步：

第一步过后，我们已经可以计算出每辆车的利润情况。所以第二步，我们便要用一个整数规划模型来平衡各运输公司之间的单位利润。

用二元变量ztk表示路线k是否被安排到了公司t的路径中。用表示所有公司里最少的单位利润，我们用以下模型来实现利润平衡。

Model2

于是我们发现，这个问题可以简化成一个标准NP完全问题——线性分割：给定一个非负数集合和一个整数k，将集合划分为k个部分，以使每个部分的和的最大值最小化。在实际应用中，由于T和V的数值都比较小，所以我们用普通的IP求解器（如ILOG-CPLEX）也是可以把该问题求解到最优的。当然，也可以用DP自己求解

上面的两步只是求解出了一组可行的解。要获得更多的初始解，我们只需要改变坐标系的原点，更新顾客们的坐标并重复上述过程即可。

B.2 局部搜索

一个解的邻域由如下4个算子定义：

• exchange(i,j)：把运输顾客i和顾客j货物的车辆交换一下，产生一组新的解
• relocate(i,j)：把节点i放到节点j之前，也就是在送顾客j的货物之前强行插入运输顾客i的货物的任务
• 2-opt(i,j)：交换连接（i，i+1）和（j，j+1）的两条边在两条车辆路径中的位置，也就是说，把路径（0，...，i，i+1，...，0）和（0，...，j，j+1，...，0）变成（0，...，i，j+1，...，0）和（0，...，j，i+1，...，0）
• reverse(i,j)：在一条路径上，把（i，j）区间里所有的节点顺序颠倒，也就是说，把路径（0，...，i，i+1，...，j-1，j，...，0）变成（0，...，j，j-1，...，i+1，i，...，0）

都是我们在LS里的老朋友了。这几个邻域的大小都是O(n2)，相对而言确实比较小，是在可接受的范围内的。我们用s1来表示由我们的算子产生的解，并引入如下的适应度评价函数：

评价函数

要注意，等式右边的部分其实是一个负数。

依据上述的评价函数，当f(s1,ω)<f(s,ω)时，我们则接受这个新的解。

B.3 解的挑选和种群的更新

我们用锦标赛选择法（在上文中称为随机联赛选择）来从种群P中选出一个解s。

所谓锦标赛选择法，就是每次随机选出固定数目的个体来进行“联赛”，并依据评价函数值选出其中的“胜者”，最终，评价函数值最小的解会被我们通过“联赛”选出。

一个新的种群由P∪P^经过加工得到。我们在这里要使用NSGA-Ⅱ算法中「非支配排序法」和「拥挤比较法」来维护一个高质量且高多样性的解集。(关于NSGA-Ⅱ，也可直接阅读原论文“A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-II")

C.MOLS+

MOLS算法虽好，但是它却没有完全利用好VRPOPB问题的特征。为了提高解的质量，我们在这里引入「大旅程表示（giant-tour representation）、重组运算（recombination operator）、大邻域搜索（ large neighborhood search，LNS）」 三种技巧。这时，MOLS就被强化成了MOLS+。

下面是MOLS+的框架：

MOLS+

如图，函数「select_a_solution(P , ω)」 和「LSk(s)」 与Algorithm1中基本相同。函数「recombination(P)」 是用交叉算子，生成一个综合了父母信息的子代种群。函数 「LNS(s)」 用来进一步优化解s。

C.1 Giant-tour representation

大旅程表示法是VRP中的一种紧凑编码模组，经过分割（splitting）便可以转化成为一个VRP最优解。C.2中将要说到的重组运算也会在这种方法的帮助下变得十分简单。

给定一组含有m个车辆路径的解，我们用rj=（rj1，rj2，...，rjR(j)）来表示第j条车辆路径（R(j)表示j路径服务的顾客数量）rji则表示j路径经过的第i个顾客。

我们定义 “⊕”为串联运算符，其作用是连接上一条路线的最后一位顾客和这条路线的最后一位顾客。也即，

我们所谓的Giant-tour，就是指所有路径的连接，也即：

事实上，我们的“大旅程”就是所有顾客的一种排列，我们不妨直接把它叫做“大旅程序列”。这样一来，我们就把搜索空间就包括进了所有的顾客排列方式。

有了“Giant-tour”之后，我们要做的，就是把它分割成一个个的小段，我们的问题，也就变成了寻找把r划分成几条车辆路径的合理方式。

由于VRPOPB是一个双目标问题，所以我们有针对最小化运输成本和利润平衡的两套分割方式。这两种方式的核心，就是OIers所熟知的折磨王：「动态规划(DP)」。

C.1.1 针对最小化运输成本的分割方式

给定一个大旅程序列r=（π1，π2，...，πn）,我们要做的就是把r分割成m条可行的车辆路径，并且使总运输费用最小。

我们用L[k] [i]来表示使用k辆车服务顾客（π1，π2，...πi）的最小运输成本，那么易得其状态转移方程如下：

cost(j,i) 和 cap(j,i)分别表示一条路径为 (0，π j，...，πi，0)的车辆所需的运输成本和运载量，我们的边界条件是L[0] [0]=0，目标则是得到L[m] [n]的值。

但是显然，我们根本无法保证每一个大旅程序列都有其对应的可行解。在这时，我们只需要找到最多能服务的顾客数n1，再计算出L[m] [n1]的值。剩下没有服务到的顾客，我们加上其相应的惩罚性成本即可。

C.1.2 针对利润平衡的分割方式

每个运输公司的规模大概率是不相同的，所以如果真的要直接最大化最小单位利润，也是比较困难的。在这里，我们转而最大化最小单条路径利润（minimum route profit，MRP）

和C.2种相似，我们用F[k] [i]来表示k辆车服务i位顾客的MRP。那么我们就可以得到如下的状态转移方程：

其中，pro(j,i)表示一路径为(0，π j，...，πi，0)的车辆所获利润。

我们的边界条件是F[0] [0]=0，目标则是得到F[m] [n]的值。通过回溯我们的优化过程，我们可以找到m条车辆路径和每条路径的利润pk。保证对于任意的k∈V，都有pk≥F[m] [n]，这也就意味着MRP的最大化。

之后，我们再使用上文中提到的Model2把这m条线路分配给运输公司即可。

这两种分割，真的好像区间DP(仅供参考的类似题目)欸。

C.2 Recombination

所谓的recombination，就是通过配对种群P中的个体（解），形成一个全新的种群P1。

我们在P中多次挑选还未被选出过的两组解，并且让他们按照一定的可能性pm（一个自主定义的常数）配对。首先，我们把这两组解都转化成大旅程序列，然后，我们再用部分交叉匹配算子(PMX)生成两组全新的大旅程序列，最后，我们对两条新的大旅行序列都使用一次上文中提到的两种分割方式，得到四组解，最后，我们找出这四组解里的非支配解，把其加入下一代种群P1中即可。

C.3 LNS

大邻域搜索（ Large Neighborhood Search，LNS）的邻域主要由“ destroy and repair ”的方法产生。我们先把当前解“毁坏（destroy）”成“部分解（partial solution）”，再把这个部分解“修补（repair）”成一个完整的解即可。也即，我们通过毁坏操作和修补操作来形成一个解的邻域。

LNS的伪代码如下：

Algorithm3

non_impr可以理解为记录已经当前解已经有多久没有被优化过的变量。destroy and repair算子用来生成一组新的解。

和之前的局部搜索中，只要有一个目标得到优化就接受当前解不同，在LNS中当且仅当s1＜s。时，我们才接受解s1。如果s≤s1，则non_impr+1；如果s1和s不构成支配关系，LNS什么都不做。当non_impr达到规定值λ时，这说明当前解s已经足够优秀，算法停止。

destroy：在一组解里以概率pr随机去掉一些顾客，形成一个“部分解”。

repair：首先，我们把被移除的顾客按照降序排列好，然后按顺序随机选用如下的两种方式将其放回部分解中。

• 成本导向插入法(Cost-oriented insertion)：用Δg1(k, j)表示把该顾客插入k路线上j的位置给总运输费用带来的变化。我们在 时执行插入操作。
• 公平导向插入法(Fairness-oriented insertion)：用g2(t)表示运输公司t的单位利润，Δg2(t,k,j)表示把该顾客插入k路线上j的位置给公司t带来的单位利润变化。那么，g2(t)+Δg2(t,k,j)就是t公司执行插入操作后的单位利润。那么，我们在时执行插入操作即可。

D.常数表：

Table1

经过反复的实验和校准，我们得到了算法中如下的常数表，供大家参考使用。

四.算法优势

Table2

Table2是MOLS+和Jozefowiez等人所提出的算法在部分经典数据上的比较。在这里，我们为了更好地和Jozefowiez的算法进行比较，把第二个目标微调为最小化最长和最短路径之间的差距。

由图可见，在最小化运输成本方面，MOLS+与J氏的算法基本持平，但是在最小化差距方面有着明显的优势。很显然，我们可以认定MOLS+会生成更优的解。

Table3.png

Table3是在VRPOPB问题中，MOLS+的几种优化方式的比较。其中，参数IGD表示解集与帕累托最优解集之间的“距离”，HV则表示解集的多样性以及与最优解集之间的重合度。由图可知，MOLS+确实在很大程度上对MOLS进行了优化。

五.总结

VRPOPB在物流领域是一个极为复杂的问题，MOLS+算法也只是尽量使答案靠近帕累托最优解。未来的研究方向应该会着眼于设计更加精密的启发式算法来生成更优秀的解。此外，MOLS+算法无疑可以被扩展至解决VRPTW、多仓库问题等更多的实际问题，这也等待着进一步的研究。

参考文献：

"Multi-objective Optimization for the Vehicle Routing Problem with Outsourcing and Profit Balancing", Zizhen Zhang, Hu Qin, Yanzhi Li*， IEEE Transactions on Intelligent Transportation Systems, Volume 21, Issue 5, May 2020, Pages 1987 - 2001.

欲下载本文相关代码，请移步留言区

-The End-

文案&代码注释&排版：黄锐扬（华中科技大学管理学院本科一年级）

指导老师：秦虎老师 （华中科技大学管理学院）

如对文中内容有疑问，欢迎交流。PS：部分资料来自网络。 如有需求，可以联系： 秦虎老师（华中科技大学管理学院，微信号43340630） 黄锐扬（华中科技大学管理学院本科一年级：403006585@qq.com）

欢迎大家加入数据魔术师粉丝群，我们的活动将会通过粉丝群优先发布，学习资料将通过粉丝群分享。

欲入群，请转发此文，然后扫描下方二维码联系数据魔术师小助手