混合启发式算法求解多配送人员车辆路径问题

苏欣欣， 王红卫， 秦 虎， 王 恺

(1.青岛理工大学 管理工程学院,山东 青岛 266000; 2.华中科技大学 管理学院,湖北 武汉 430074; 3.武汉大学 经济与管理学院,湖北 武汉 430000)

0 引言

带时间窗和多配送人员的车辆路径问题(Vehicle Routing Problem with Time Windowsand Multiple Deliverymen, VRPTWMD)是Dantzig和Ramser[1]于1959年提出的车辆路径问题(Vehicle Routing Problem，VRP)的推广。此问题不但适用于货物要求多个配送人员合作才能配送的情况，还适用于配送时间相对于行程时间较长的情况。配送时间不但与货物需求量有关而且与配送人员数目有关。因此，如何调节每辆车的配送人员数目和设计车辆行驶路线成为本文研究的主要问题。

近年来，学者们对VRPTWMD进行了一系列的研究。该问题由Pureza，Morabito和Reimann[2]在2012年提出，他们指出此类问题主要分为两个决策问题：(1)将顾客进行区域划分，同一区域的顾客共享一个停车场；(2)优化路径，车辆到达停车场后，配送人员服务该区域的全部顾客。该文假设区域划分为已知，并提出禁忌搜索算法和蚁群算法求解该问题。2016年, De Grancy和Reimann[3]分别基于蚁群算法和随机自适应搜索提出了两种新的启发式算法求解VRPTWMD。2018年，Munari和Morabito[4]提出分支定价割平面算法来求解该问题。2015年，De Grancy[5]首次考虑区域划分，解决完整的VRPTWMD，同时提出通过路径的优化方案来引导区域划分的自适应元启发式算法。

对于启发式算法，Luo等[6]提出了适应性的弹射池与灵活多变的方法解决团队定向问题。Hu和Lim[7]提出了迭代三分量启发式算法求解带时间窗的团队定向问题。受以上论文的启发，针对本文的VRPTWMD，我们提出了混合启发式算法。通过与其他算法进行比较，验证了该算法具有较强的全局寻优能力和较高的搜索效率。

1 多配送人员的车辆路径问题

1.1 问题描述

本文考虑的VRPTWMD通过调节每辆车的配送人员数目和设计车辆路线来满足顾客对货物和时间窗的要求。假设区域划分为已知，不考虑顾客与停车场的距离，则顾客集合与对应停车场可以看作是一个顾客。VRPTWMD的描述如下：1)车辆和配送人员从配送中心出发服务顾客，并最终返回配送中心；2)每个顾客最多被访问一次；3)顾客有严格规定的时间窗，包括最早开始服务时间和最晚完成时间。顾客的服务时间与需求量和配送人员数目有关。VRPTWMD的首要目标是效益总值最大，次要目标是行驶总距离最短。

1.2 模型构建

模型参数：

K：配送中心的车辆集合；

V：所有点的集合，包括顾客和配送中心，V={0,1,…,n+1}；

C：顾客的集合，C={1,2,…,n}；

m：车辆关于人员的最大承载量；

L：车辆可能承载的配送人员数目的集合，L={1,2,…,m}；

m：配送中心的配送人员总数目；

Q：车辆关于货物的最大承载量；

pi,i∈{0,1,…,n+1}：服务顾客获得的效益值，假设p0=pn+1=0；

ei,i∈{0,1,…,n+1}：顾客的货物需求量，假设c0=cn+1=0；

dij,i∈{0,1,…,n},j∈{1,2,…,n+1}：车辆在配送中心或顾客i与配送中心或顾客j之间的行驶时间，假设与行驶距离数值相等；

ai,i∈{0,1,…,n+1}：顾客i可接受服务的最早时间；

bi,i∈{0,1,…,n+1}：顾客i可接受完成服务的最晚时间；

w1,w2：每个目标函数的权重，且w1>w2；

R：一个无限大的数。

决策变量：

此问题的具体模型如下:

(1)

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

∀k∈K,i∈C∪{0},j∈C∪{n+1}

(10)

(11)

(12)

(13)

其中，式(1)最大化两个不同目标的加权组合，即总效益值和总距离；式(2)和式(3)确保每条路径的连续性；式(4)和式(5)确保每辆车从配送中心出发并最终返回配送中心；式(6)表示每辆车的载重约束；式(7)表示每辆车与承载的配送人员数目一一对应；式(8)表示配送人员总数目的约束；式(9)表示每个顾客最多被访问一次；式(10)确保子回路消除；式(11)和式(12)确保服务的开始时间和完成时间均在时间窗内；式(13)表示变量属性。

2 混合启发式算法

2.1 算法的主流程设计

混合启发式算法首先生成L个初始解，然后将产生的解以路径为单位分解并放入路径库，通过重组路径库中的路径产生新的可行解，最后利用局部搜索算法和模拟退火算法分别产生邻域解，更新全局最优解和路径库。算法流程如图1所示。

图1 混合启发式算法流程图

2.2 初始解的生成

采用贪婪法生成初始解。首先所有路径均为空路径，每条路径的配送人员数目随机分配，打乱未被服务顾客的顺序并放入unrouted集合中。按照从前至后的顺序把unrouted集合中的顾客尝试插入到路径中，若满足载重和时间窗的限制则进行插入操作，直至所有顾客不能插入到任何路径中为止，则一个初始解生成。

2.3 整数规划重组

将路径库中的路径进行重组，需建立如下数学模型并定义模型参数：

qk：路径k含有顾客的总效益值；

dk：路径k的长度；

nk：路径k使用的配送人员数目；

S:路径库中含有路径的总数目；

我们还需要定义模型决策变量：

则构建的数学模型如下:

(14)

(18)

其中，式(14)表示最大化两个不同目标(效益总值和总距离)的加权组合；式(15)表示每个顾客最多被服务一次；式(16)表示车辆总数目的约束；式(17)表示配送人员总数目的约束；式(18)表示变量属性。

根据上述数学模型，CPLEX将路径进行重组，并将得到的解记为S1。

2.4 局部搜索算法和模拟退火算法

局部搜索算法首先随机选择两条路径，分别增加一位配送人员和减少一位配送人员。随后进行邻域操作，产生一个邻域解。重复运行L次，产生L个邻域解。若超过已定的循环数目局部搜索未更新最优解，则在下一次循环前对初始解进行扰动。若更新了最优解，则也更新初始解。局部搜索算法产生的最优解记为S2。

与局部搜索算法不同，若在模拟退火算法中更新了最优解，则也更新初始解；否则，以一定的概率接受此解为初始解。模拟退火算法产生的最优解记为S3。

局部搜索算法和模拟退火算法采用的邻域操作有6个，如图2所示。

图2 邻域操作示例图

2.5 扰动

随机删除顾客，若顾客的效益值大于平均值，以概率ph删除；否则，以概率pl删除，其中ph

3 实验结果及分析

3.1 算例说明与参数设置

本文提出的混合启发式算法使用Java语言编写，运行环境采用Intel(R) Core(TM) i7- 4790 CPU @ 3.60GHz(8.00 GB内存)，整数规划重组使用CPLEX(Studio1251)进行求解。

参考苏等[8]中对Solomon标准测试问题[9]修改的过程，本文也进行相同的修改。我们标记每个算例为“P”+“name”，其中P是与原标准测试算例作区分，name是原标准测试算例的名称。

经过反复实验，混合启发式算法的参数设定如表1，其中itermax表示最大循环数目；improveno表示最大未更新循环数目。

3.2 与CPLEX对比实验

为验证算法的求解精度和运算效率，本文使用CPLEX(Studio1251)求解数学模型并用于实验对比。

表1 参数设置

在改造后的标准测试算例中随机选取24个算例，且每个算例包含100个顾客。我们将其延伸为两个小规模算例，分别包括25个顾客和50个顾客。混合启发式算法运行每个算例10次，求解结果的最大值表示为fbest，平均值表示为favg；CPLEX运行每个算例一次，且限制运行时间为7200s。为了评价混合启发式算法的性能，我们使用最大值的相对误差Gbest和平均值的相对误差Gavg用于两种算法的对比，表达式分别如下:

(19)

(20)

其中，BSK表示已知的最优解。

针对25个顾客，2辆车，4个配送人员的小规模算例，求解结果如表2所示，加粗的结果代表混合启发式算法取得的最大值与CPLEX的求解结果相同。从表2中可以看出，24个算例中只有9个算例CPLEX可以在7200s内得出结果，其中5个算例混合启发式算法得到的最大值与CPLEX得到的结果相同，其余算例的相对误差可视为0.00%。对于运算时间，9个算例中有7个算例的运算时间均远小于CPLEX的运算时间。因此混合启发式算法具有准确性和高效性。

针对50个顾客，3辆车，6个配送人员的小规模算例，由于篇幅限制我们并没有将结果统计于表中。CPLEX只有PC106可以在7200s内得出结果，而混合启发式算法得到的最大值和平均值与CPLEX得到的结果相同，且运算时间远小于CPLEX的运算时间。混合启发式算法的平均值相对误差只有PR102平均值的相对误差为0.07%，其余均为0.00%。因此混合启发式算法具有稳定性和有效性。

表2 小规模算例求解结果(25个顾客,2辆车,4个配送人员)

3.3 与已知算法对比实验

为了进一步说明混合启发式算法的有效性, 本文与苏等[8]提出的禁忌搜索算法进行比较。针对24个标准规模测试算例，混合启发式算法独立运行每个算例10次，且限定运行时间为300s。将结果统计在表3，加粗的数据代表该算法可以得到更优的结果。

对比最大值，24个算例中有7个算例混合启发式算法得到的结果比禁忌搜索算法得到的结果好；只有2个算例混合启发式算法得到的最大值比禁忌搜索算法得到的结果差，且相对误差均在2%之内。对比平均值，有13个算例混合启发式算法得到的结果比禁忌搜索算法得到的结果好；只有1个算例混合启发式算法得到的结果比禁忌搜索算法得到的结果差,且相对误差为1.86%。由此说明，混合启发式算法相对禁忌搜索算法更稳定，更准确。

表3 标准规模算例求解结果(100个顾客, 5辆车, 9个配送人员)

4 结论

根据现实生活中的物流配送，本文对带时间窗和多配送人员的车辆路径问题展开研究。该问题考虑了配送人员数目对服务时间的影响，并且要求在时间窗内完成配送的情况。本文提出的混合启发式算法主要以整数规划重组、局部搜索算法和模拟退火算法三部分为循环运行。通过将混合启发式算法与其他算法进行对比，证实了该算法实用价值更高，求解效果更好。