0.   引言

物流配送是指按用户的订货要求, 在配送中心进行分货、配货, 并将配好的货物及时送交收货人的过程。物流配送中的车辆路径问题(VRP问题), 是物流系统中较受关注的一个重点问题, 也一直是学者们研究的热点问题。VRP问题是指在客户需求位置与需求量均已知的情况下, 满足一定的约束条件(如车辆载重限制、交货时间窗限制、车辆容积限制等) 确定车辆在各个客户间的行程路线, 使得运输路线最短或者运输成本最低。VRP问题已经被证明是一个NP-hard问题, 当规模较大时, 很难得到一个全局最优解或满意解。并且, 随着问题规模的扩大, 计算时间将不断增加, 因此, 很多学者对解决VRP问题的算法进行了研究, 在既有文献中可以将求解该问题的算法大致分为精确算法和近似算法^[1]。Kallehauge在已有的TSP问题的建模和求解技术的基础上构建了带时间窗的车辆路径问题的精确算法^[2]; Ralphs等采用分枝剪枝算法对车辆载质量限制的车辆路径问题进行了求解^[3]; Kohl等基于拉格朗日松弛方法, 通过对每个顾客必须接受服务的约束集进行松弛, 从而对带时间窗的VRP问题进行求解^[4]; Julien等将带时间窗的VRP问题转化成集合覆盖问题, 并通过列生成方法对线性松弛问题进行求解^[5]; 吴勇等提出了求解带时间窗车辆路径问题的多群并行的粒子群算法^[6]; 刘霞等采用局部搜索算法求解了带时间窗的动态车辆路径问题^[7]; 刘志硕等在分析VRP问题与TSP问题区别的基础上, 构造了求解VRP问题的自适应蚁群算法^[8]; 潘立军等设计了求解带时间窗车辆路径问题的时差插入式启发式算法^[9]; Banos等采用基于模拟退火算法的并行多目标方法求解了带时间窗的VRP问题^[10]; Gillett等采用扫描法求解了车辆调度问题^[11]; Glover采用禁忌搜索算法求解了车辆调度问题^[12]。随着遗传算法的兴起, 很多学者又采用遗传算法或混合遗传算法对VRP问题进行了研究。周屹等采用遗传算法对物流配送中带时间窗的VRP问题进行了求解, 在传统VRP问题的基础上, 对配送人员在客户点的服务时间做了限制^[13]; 龚延成等通过将时间窗约束和车辆容量约束转嫁到最小费用目标函数中去, 建立了适合于遗传算法的车辆调度模型^[14]; 郎茂祥等采用了混合遗传算法求解了物流配送的路径优化问题^[15]; 马宇红等针对分区的多配送中心的多车型车辆调度问题设计了遗传算法进行求解^[16]。尽管采用遗传算法可以求得物流配送中的路径优化问题的可行解或满意解, 但总体上解的质量不是很高, 主要是由于遗传算法局部搜索能力不强造成的。并且, 遗传算法只考虑到个体之间的竞争, 而没有考虑到个体之间协作的可能性, 真实情况是协作与竞争并存, 协作常常是群体得以更好发展的重要条件。近年, 兴起了关于智能体的新型进化算法。袁志给出了求解数字优化的多智能体优化算法, 结果表明该算法具有更好的全局寻优能力, 而且收敛性更好^[17]; 曾聪文等设计了求解装配序列规划的多智能体进化算法^[18], 与其他各类计划算法相比, 该算法具有明显的优越性。

本文在已有研究的基础上, 针对单配送中心带时间窗的VRP问题, 构造了基于配送人员总的行驶时间最小和客户等待时间最短的双目标优化模型, 运用整数编码的多智能体进化算法, 通过设定进化代数和网络规格, 对智能体网络中的智能体进行竞争和自学习, 反复验证得出网络中能量最高的智能体, 并与已有的遗传算法进行对比分析。

1.   问题描述与模型建立

1.1   问题描述与假设

VRP问题一般是指从物流配送中心用多辆车向多个客户需求点送货, 每个客户需求点的位置和需求量是已知的, 车辆的最大载质量是一定的, 要求合理安排配送路线使得目标函数最优, 并且满足以下条件: 每个客户需求点只能被一辆车访问, 并且只能访问一次; 每辆车都是从配送中心出发, 最后回到配送中心; 每个客户需求点的需求量必须满足。带时间窗的VRP问题是在该基础上, 还需要满足服务时间约束, 即配送人员需要在一定的时间窗内到达客户需求点进行服务。

为便于建立模型, 本文进行以下假设: 所有的货物都可以混装在一起; 不考虑车辆的容积限制; 每辆车的最大载质量相同。

1.2   变量定义

令客户需求点的集合为I, 集合中有n个元素, i、j为I中任意一点, c为中间点(不包括起点和终点); 车辆集合为V, v∈V; 配送中心为o; 配送车辆在点i和点j (包括配送中心) 的运行时间为t_ij; 配送车辆到达点i的时间为t_ia; 点i的配送服务时间为t_is; 点i要求的最早到达时间为T_iE; 点i要求的最晚服务到达时间为T_iL; 点i的需求量为p_i; 车辆的最大载质量为p; 决策变量x_ijv表示配送车辆v是否从点i到点j进行配送, 当配送车辆从点i到点j进行配送时取1, 否则取0;决策变量x_ojv表示车辆v是否从配送中心发出, x_ojv取1表示车v从配送中心出发到点j, 否则取0;决策变量x_iov表示车辆v是否回到配送中心, x_iov取1表示该车从点i返回配送中心, 否则取0;N为需求车辆的数量。由以上分析, 有

式中: [·]为取整操作。

1.3   模型建立

以最小总行驶时间与最小用户等待时间为目标函数, 建立模型为

式中: Z₁为总的行驶时间; Z₂为总的用户等待时间; 式(4) ~ (6) 保证车辆从配送中心出发最后回到配送中心; 式(7) 保证每个客户点只能被一辆车访问而且只能访问一次; 式(8) 为车辆到达客户需求点的时间约束; 式(9) 为服务时间窗约束; 式(10) 为车辆载质量约束。

2.   多智能体进化算法设计思路

多智能体进化算法(Multi-Agent Evolutionary Algorithm, MAEA) 是用智能体(初始可行解) 网络构造进化环境, 每个智能体依据目标自我学习以提升能量, 并在邻域中参与竞争, 竞争失败便被邻域中能量最大的智能体淘汰, 不需要全局消息, 这样更接近于自然界的进化模式。曾聪文等采用整数编码的多智能体算法(NC-MAEA) 对旅行商问题进行了求解^[18], 证明了该算法在用于旅行商问题中时具有更好的全局寻优能力, 并且稳定性更好。本文针对解的特点, 采用整数编码的多智能体算法(NC-MAEA) 对带时间窗的VRP问题进行求解。

2.1   初始智能体的产生

对待服务的客户需求点按照顺序进行编号, 客户需求点的个数为n, 构造m×m个智能体网格。然后对每个智能体进行实数编码(1~n的随机排列), 看其是否满足所有的约束条件, 如果满足, 则判断为初始智能体, 将其放入网格中, 如果不行, 则循环产生, 直至产生m×m个可行智能体为止, 并将初始状态设为0。

为方便算法的执行, 在编码过程中没有包括配送中心(配送中心用编号0表示), 而对载质量约束和时间窗约束进行检验时需要将配送中心涵盖在上述智能体编码中以便检验。比如随机产生的智能体为1-4-5-7-9-6-3-4-2, 则从左到右累加计算各个需求点的载质量, 倘若载质量超过配送车辆最大载质量, 则在前一客户需求点添加0, 然后将累加后的载质量重置为0, 再依次进行累加。比如添置后的结果为0-1-4-5-0-7-9-0-6-0-3-4-2-0, 表示在此配送过程中需要3辆配送车辆, 对应的路径分别为0→1→4→5→0、0→7→9→6→0、0→6→3→4→2→0。

2.2   竞争算子

竞争算子是指网格中的每个智能体与其邻域中的智能体竞争。邻域是智能体生存的局部环境, 智能体可以根据自己的位置找到其邻域的其他智能体。智能体的生存环境设置如下: 令处于网格中的智能体为M, 竞争算子只能和其邻域中的智能体竞争, 因此, 1个智能体的竞争对象是4个邻域智能体。

每个智能体都有一定的能量, 令智能体M的能量为E (M), 邻域中能量最大的个体为M′。考虑决策者偏好程度, 设目标函数的权重向量为λ= (λ₁, λ₂), 不改变约束条件, 以λ₁与λ₂为系数, 将以配送人员总的行驶时间最短和客户等待时间最小的双目标优化模型转化为单目标模型Z, 即

智能体的能量为

从邻域中选择能量最大的个体M′, 如果E (M′) > E (M), 则用M′去感染M, 具体方法为: 在M′智能体的随机位置处取一段随机长度的编码插入到M的相应位置, 然后去掉M中相同的编码, 编码段不变, 将其他位置处的编码重新排序并随时检验约束是否满足, 如果不满足, 则继续排列, 直至找到可行的智能体。

2.3   自学习算子

在经过了竞争算子后, 邻域中能量最大的智能体也要进行相应的提升, 本文称之为自学习。学习的方法有2种, 1种是通过交换编码的位置来提升能量, 另1种是采用移动编码段的方式提升能量。自学习算子的学习方法见图 1。

图  1  学习方法

Figure  1.  Learning method

下载: 全尺寸图片 幻灯片

2.4   算法流程

由以上分析可以得出求解带时间窗的VRP问题的多智能体进化算法流程, 见图 2。

图  2  算法流程

Figure  2.  Algorithm flow

下载: 全尺寸图片 幻灯片

3.   计算结果分析

假设有13个待配送的客户需求点(编号依次为1、2、…、13), 0表示配送中心, 各个待配送的客户需求点的服务时间均为5min, 车辆最大载质量为3t。各客户点的配送量、需求点之间的行驶时间以及时间窗分别见表 1、2。智能体网格规模为7×7, 即初始智能体个数为49, 最大进化代数设为200次, 如果连续进化20代最优解不变或者达到最大进化代数, 则终止运算。此外, 设定式(11) 中的λ₁和λ₂分别为0.4和0.6 (该值可以根据决策者的偏好灵活调整)。在Visual Studio 2008平台上编程求解, 当待配送的客户需求点为13时, 由式(1) 计算出需要的配送车辆数量为3veh。根据遗传算法的一般步骤编写程序^[19], 利用上述数据运算30次进行求解; 同理, 本文设计的NC-MAEA同样运算30次, 得出2种算法的优化结果对比, 见表 3。通过遗传算法求得的最优值为110.3 min, 3条最优路径见图 3, 路径1为0→2→8→12→9→13→0, 路径2为0→1→3→7→4→0, 路径3为0→6→5→11→10→0。

表  1  车辆行驶时间

Table  1.  Vehicle travel times

下载: 导出CSV 

| 显示表格

表  2  配送量与时间窗

Table  2.  Distribution volumes and time windows

下载: 导出CSV 

| 显示表格

表  3  两种算法优化结果比较

Table  3.  Comparison of optimization results for two algorithms

下载: 导出CSV 

| 显示表格

图  3  利用遗传算法求得的最优路径

Figure  3.  Optimal paths by using GA

下载: 全尺寸图片 幻灯片

通过本文算法求得的最优值为103.6 min, 3条最优路径见图 4, 路径1为0→6→4→10→0, 路径2为0→2→8→12→9→13→0, 路径3为0→1→3→5→11→7→0。

图  4  利用多智能体进化算法求得的最优路径

Figure  4.  Optimal paths by using NC-MAEA

下载: 全尺寸图片 幻灯片

由表 3可以看出, 2种算法经过30次计算后, 虽然采用遗传算法最优运行时间为123s, 而采用本文算法的最优运算时间为145s, 比遗传算法时间要长。但是, 对于目标值而言, 采用本文算法能够获得更高质量的最优解, 而且经过多次反复试验, 最终解的变化不大。在本文算例中, 经过30次计算后, 遗传算法的最差值为121.8min, 最优值为110.3min, 采用本文算法求得的最差值为113.6 min, 最优值为103.6min, 所得结果稳定性较遗传算法要好。2种算法的最优情况下的收敛效果分别见图 5、6。

图  5  遗传算法下的收敛结果

Figure  5.  Convergence effect under GA

下载: 全尺寸图片 幻灯片

图  6  多智能体进化算法下的收敛结果

Figure  6.  Convergence effect under NC-MAEA

下载: 全尺寸图片 幻灯片

4.   结语

针对单个配送中心的带时间窗的车辆路径问题, 构建了以配送人员总的行驶时间最短和客户等待时间最小的双目标优化模型, 并设计了多智能体进化算法进行求解。将智能体固定在网格上, 每个智能体为增加自身能量将与其邻域展开竞争合作。为验证该方法的高效收敛性, 并与遗传算法的计算结果进行了比对, 在分别运算30次的情况下, 发现多智能体进化算法虽然在时间的效率上较遗传算法稍长, 但具有更高的收敛性, 不易陷入局部最优。

VRP问题已被证实是NP-hard问题, 本文只是针对静态下的VRP问题进行算法的研究, 并与遗传算法进行了对比分析, 但与其他算法相比是否具有更高的寻优能力却不得而知。此外, 本文缺少了对算法的参数比如网格个数、变异概率等的灵敏度分析, 这些都是需要进一步研究的问题。