时变网络下多车型同时取送货车辆路径优化

赵佳欣，雷 斌，3，王菀莹

(1.兰州交通大学 机电技术研究所，甘肃 兰州 730070；2.甘肃省物流及运输装备信息化工程技术研究中心，甘肃 兰州 730070；3.甘肃省物流与运输装备行业技术中心，甘肃 兰州 730070)

0 引 言

随着互联网及电子商务的普及，顾客的物流需求越来越多样化，从原来的单一送货或取货需求演变为兼备二者的物流需求。车辆在进行配送任务时，车辆行驶速度常常会因为道路交通情况改变[1]。在规划车辆配送路线时，不仅需要考虑客户需求还需要结合道路交通状况。针对时变车辆路径问题，刘思远等[2]、张景玲等[3]采用分段函数表现车速随时段变化，刘文琪[4]分段函数的基础上考虑车辆行驶加速度，范厚明等[5，6]混合时间窗用多个三角函数关系式及多项式表现车速随时间连续变化关系。目前的研究主要考虑时间对车辆行驶速度的影响，未考虑路段的影响。针对同时取送货车辆路径问题，现有研究主要将其与选址问题和不确定环境相结合。陈希琼等[7，8]结合选址和路径问题，同时考虑车辆容量和行驶里程约束，通过缩短最优目标值和行驶距离的差值进行寻优。马艳芳等[9，10]对模糊需求和不确定环境下的同时取送货问题进行研究。李博威等[11]引入非线性约束对时变网络下的同时取送货问题进行研究。大部分的研究成果都默认路网内的客户关系单一，没有对多样的取送货情况进行刻画。本文综合考虑路段和时段对车速的影响、不同客户的取送货需求及客户关系、多种车辆的载重约束，建立时变路网下多车型同时取送货车辆路径模型(simultaneous pickup and delivery vehicle routing problem under time-varying road network，SPDVRPTN)。

1 模型建立

1.1 问题描述

假定道路网络内存在一个配送中心，客户位置已给定，每个客户都有取送货需求，取送货量已知，当取货量为0时代表该客户点只有送货需求，反之亦然。配送中心共有K辆车可调配，共L种类型，以l(l∈L) 表示车辆类型，每种类型车辆载重为Q1，Q2，…，QL， 即Ql(l∈L)， 车辆数量为K1，K2，…，KL， 即Kl(l∈L)， 每个客户仅由一辆车进行服务一次。车辆从配送中心出发，在行驶过程中其行驶速度随路段和时段的改变而改变，且不允许超载，在完成配送后返回配送中心。道路网络内包含路段a个，将配送中心的服务时段划分为b个。要求合理规划车辆行驶路线，使配送总成本达到最小值。总成本包括车辆固定成本、车辆派遣成本以及未满足客户时效要求产生的时间惩罚费用。

1.2 参数及变量说明

dij客户点i到客户点j的运输距离

pj客户点j的取货量

dj客户点j的送货量

A共有a个路段

B将配送中心服务时段划分为b个

Sb第b个时间段的开始时间

Eb第b个时间段的结束时间

yij车辆k从客户点i到客户点j路径中的送货量

zij车辆k从客户点i到客户点j路径中的取货量

QL类型为L的车辆最大载重

tij车辆从客户i到客户点j的行驶时间

ej客户点j的期望最早服务时间

lj客户点j的期望最晚服务时间

e0送中心的最早服务时间

l0配送中心的最晚服务时间

tj车辆在客户点j的取送货时间

wj车辆到达客户点j的时间

wj0车辆从客户点j返回配送中心的时间

Pi(ti) 时间窗惩罚函数

1.3 考虑多种取送货情况

针对同时取送货问题，从路网内的客户间关系出发，考虑以下两种情况：

(1)路网内客户间不存在服务与被服务关系：所有客户的送货量等于从配送中心出发的车辆的总载货量，返回配送中心的车辆载货总量为所有客户的总取货量，此时车辆无固定服务顺序。

(2)路网内存在客户间服务与被服务关系：在特定客户取到的货物能够为路网内其他客户进行送货服务。假设存在客户集m=(1，2，3，…，m) 为客户集n=(1，2，…，n) 服务，客户集m的供给能力能够满足客户集n的需求。车辆在配送时需先对客户集m中的客户进行服务，再对客户集n中的客户进行服务。

综合考虑以上两种情况，将路网内的客户编号为 (1，2，3，…，m，m+1，…，m+n)， 对网络内流量设定以下约束条件

(1)

(2)

(3)

(4)

(5)

(6)

式(1)和式(2)表示从配送中心出发的载货量大于等于前m个客户点的总送货量并且小于等于总送货量；式(3)表示总取货量小于等于返回配送中心的总载货量；式(4)表示前m个客户点的取货量大于等于后n个客户点的送货量；式(5)和式(6)保证客户服务顺序符合规定。

1.4 时变网络下行驶时间计算

本文采用多个分段函数表现不同道路下的速度随时间变化的曲线，定义出不同路段不同时段的车辆行驶速度集F，如式(7)所示，每个路段下车辆行驶速度随时段变化

(7)

假设车辆从客户点i行驶到客户点j时处于路段a中，此时存在跨时段行驶和不跨时段行驶两种情况，非跨时段行驶时，行驶时间计算公式如式(8)所示

(8)

跨时段行驶时，按式(9)计算到达下一节点的时间

(9)

若tj仍处于时段[tb-1，tb]， 则根据式(10)计算车辆在下个时段仍需行驶的距离。再根据行驶距离更新行驶时间，计算公式如式(11)所示，当tj≤tb+1时停止计算，否则继续上述步骤

(10)

(11)

1.5 模型建立

(12)

(13)

(14)

(15)

(16)

(17)

(18)

(19)

ai+ti+tij-M(1-xijk)≤aj

(20)

(21)

tjo≤l0

(22)

式(12)为目标函数，以车辆租赁成本、派遣成本和时间惩罚费用最小为总目标；式(13)保证车辆从配送中心出发去往一条路径；式(14)表示最多使用k辆车；式(15)为车辆最大容量限制；式(16)和式(17)为取送货量定义式；式(18)保证车辆在客户点a完成服务后必须前往下一客户点；式(19)表示惩罚费用函数；式(20)表示车辆k由客户点i行驶到下一个客户点时的到达时间关系；式(21)为流量平衡约束；式(22)保证车辆需在配送中心开放的时段进行服务。

2 改进的自适应遗传算法设计

遗传算法(genetic algorithm，GA)作为求解VRP问题的常用算法已被多次验证其有效性，具有较强的全局搜索能力，但达到一定迭代次数后求解效率低下且易出现早熟。本文涉及问题考虑了包括了时变网络、多车型、同时取送货等约束，问题复杂，需要在标准遗传算法的基础上进行改进，提高求解效率和精确性。根据本文所建SPDVRPTN模型特点，主要从以下两个方面进行改进：①自适应遗传算法(adaptive genetic algorithm)与普通遗传算法相比能够通过调整交叉变异概率使在求解次数到达一定规模时引导算法往更优的方向进化[12]，交叉变异概率在算法迭代时根据迭代情况发生自适应改变。②针对遗传算法容易出现早熟的问题，对算法中的选择、变异算子进行改进，引导其搜索方向，提高算法搜索能力。改进的自适应遗传算法通过其自适应机制和改进后的选择、变异算子提高求解效率和求解精度。

2.1 编码与初始种群生成

本文采用整数编码。随机生成n条长度为客户点数的染色体，引入贪婪算法的思想，选择容量约束最大的车辆按随机生成的客户排列顺序先进行取送货，直到其达到容量约束，再选择容量约束次之的车辆进行服务，直到所有客户点都被服务完毕。每辆车在开始服务时，在开始服务的客户点前插入数字0，代表此时车辆从配送中心出发。遗传算法编码及解码如图1所示。本文建立的SPDVRPTN模型存在固定车辆服务顺序即需先对客户集m服务再对客户集n服务。将两个客户集同时编码时会因交叉变异产生许多不可行解，导致算法效率降低。因此对两类客户采用分段编码，客户集m在前，客户集n在后，二者各自交叉变异互不影响。

图1 编码与解码

2.2 适应度函数与选择策略

本文建立模型的目标为总成本最小，适应度函数的取值为总成本的倒数。在选择操作时，本文结合精英保留和轮盘赌策略，保留每次迭代前m个精英个体，将其复制到下一代，非精英个体进行轮盘赌选择，保留种群中的优秀个体，使其不因交叉变异而丢失，从而提高算法的求解速率。

2.3 交叉与变异操作

2.3.1 自适应策略

本文采用文献[13]提出的正弦自适应遗传算法，将交叉概率与当代遗传中种群适应度值的平均值和最大值相联系。算法交叉变异概率按式(23)和式(24)计算

(23)

(24)

其中，Pc、Pm为交叉、变异概率，Pc1、Pc2分别为最大最小交叉概率值，Pm1、Pm2为最大最小变异概率值Pc1、Pc2∈[0.4，0.99]，Pm1、Pm2∈[0.001，0.1]，fm为最大适应度值，f′为个体适应度值，fa为种群平均适应度值。

2.3.2 交叉操作

本文采用部分匹配交叉。遗传算法进行交叉后容易产生无效个体，部分匹配交叉能够通过建立不同染色体基因之间的映射关系对交叉后的染色体进行修复。这里选用交叉点为2的部分匹配交叉，具体操作如图2所示。

2.3.3 变异操作

文献[14]在用禁忌搜索算法进行车辆路径规划时运用了一个混合算子，丰富算法的搜索方向，从而避免算法陷入局部最优。本文将该混合算子作为IAGA的变异算子，即在变异时，随机从以下4种变异方式中选择一种执行。

(1)进化逆转算子：染色体在随机的两个客户点间发生断裂，逆转其基因顺序后再插入，并且逆转后适应度值有所提高的才接受下来，否则逆转无效，如图3所示。

图3 进化逆转算子

(2)1-opt交换搜索算子：随机截取一个基因插入到染色体中的另一个位置，如图4所示。

图4 1-opt交换搜索算子

(3)2-opt交换搜索算子：随机选择两个基因交换其位置，如图5所示。

图5 2-opt交换搜索算子

(4)3-opt交换搜索算子：随机选择3个基因从前往后依次调换位置，如图6所示。

图6 3-opt交换搜索算子

3 仿真实验

3.1 仿真数据与参数设置

本文采用solomn100数据集中的c101进行改造。假设路网内有一个编号为0的配送中心和25个客户点，配送中心及客户点坐标采用原数据。客户间存在服务与被服务关系，车辆在客户编号为1-13的客户处取货后，为后续编号为14-25的客户送货，算例构建时需保证客户接受服务的时间在配送中心的服务时间窗内，编号为1-13的客户其取货量大于编号14-25客户的送货量，确保供大于需，详细信息见表1。时间窗的开始时间以早上8点为计算的零时刻，配送中心时段为早8点至下午14点，共6个小时，360分钟。以客户1举例，其时间窗为152-199，即早上10点32分至11点19分。车辆参数见表2，客户的时间惩罚系p1=3，p2=5， 将不同时段不同路段下的行驶速度用多个分段函数表示，并整理为表3。

表1 客户信息

表2 车辆参数

表3 不同路段时段下的车辆行驶速度集/(km/h)

进行实验时从3个维度验证模型和算法有效性：①将IAGA算法用于求解本文SPDVRPTN模型，验证算法的有效性；②将IAGA算法与其它智能算法在不同客户规模下的求解结果对比，验证本文设计算法的优越性；③将本文的多车型配送与单车型配送成本对比，验证多车型配送的优越性。

程序采用matlabR2017编程实现，运行环境为主频2.7 GHz的Intel Core i7处理器。算法参数设置如下：种群大小为200，迭代次数为500，算法代沟为0.9，交叉变异概率为Pc1=[0.5，0.8]，Pc2=[0.4，0.6]，Pm1=[0.03，0.05]，Pm2=[0.02，0.1]。

3.2 求解结果分析

利用本文设计的改进的自适应遗传算法求解，得到最优成本配送方案。求解结果共有6条配送路径，调用车辆6台，其中类型一4台，类型二和类型三分别1台，各子路径距离与费用见表4。配送路线如图7所示，算法迭代过程如图8所示。可以看出，算法随着迭代次数的增加呈现快速收敛，求得最优解为6438.2元，车辆行驶总距离为413 km。算法共运行20次，平均运行时间为81.3 s。说明设计的算法对模型有较好的求解效果且具有良好的收敛性。

表4 最优成本配送方案

图7 最优配送方案路线

图8 自适应遗传算法迭代趋势

3.3 单车型和多车型对比

为验证多车型配送对目标成本的影响，针对此算例进行单车型与多车型配送求解结果的对比分析，车辆参数参照上文。Pt表示时间窗惩罚成本，Cr表示车辆固定费用，Ct表示车辆派遣成本，C表示总成本，GAP表示单车型配送各项成本与多车型配送各项成本的相对误差。

由表5知，多车型配送相比于单车型配送在降低成本方面具有更大优势。单独使用车型一时，由于车辆容量小，导致使用车辆数大大增加。单独使用车型二时，配送成本升高了8.6%，单独使用类型三的车辆进行派送时，其配送成本最高。综合来看，多车型配送成本最低，验证了本文所建多车型模型的有效性。

表5 单车型与多车型配送成本对比

3.4 智能算法对比分析

本文将IAGA与文献[15]中的改进蚁群算法(improved ant colony algorithm，IACO)及遗传算法(GA)的在不同客户规模下的最小目标值(Best)、平均目标值(Avg)、计算时间(t)、标准差(Dev)对比，以验证本文算法的有效性。GAP代表本文设计的IAGA算法与IACO、GA最小目标值的偏差。IACO的参数设置：蚂蚁数m=30， 信息素强度q0=20，α=2，β=3， 信息素浓度相对重要性为1。GA参数设置：种群大小200，pc=0.8，pm=0.8。 算法分别运行20次，最大迭代次数为500次。

IAGA求解结果见表6。IACO与IAGA求解结果对比见表7。可以看出，IAGA在保持良好求解精度的同时有效缩短了求解时间，提升求解效率，算法稳定性较好。GA与IAGA求解结果对比见表8。易发现本文设计的IAGA算法相比传统遗传算法在求解精度和鲁棒性方面都有明显提升，算法性能增强。但因为提升了算法复杂度，随着客户规模的扩大，求解时间有所增加。总的来说，本文设计的IAGA算法在求解本文研究问题时具有较好的精确性和鲁棒性，求解效率较高。

表6 IAGA求解结果

表8 IAGA与GA求解结果对比

4 结束语

为提升配送服务质量，需结合现实环境中影响车辆配送的因素进行路线安排。本文综合考虑了路段和时段对车速的影响，定义出不同路段不同时段下的车辆行驶速度，结合客户的取送货需求，站在客户关系角度出发，考虑多种取送货情况和车型多样性，建立时变网络下同时取送货车辆的车辆路径优化模型。根据模型特点，设计改进的自适应遗传算法进行求解。研究结果表明：本文考虑的多车型配送能够有效降低配送成本，设计的改进自适应遗传算法具有较好的性能，建立的模型考虑车速变化和不同取送货情况，约束复杂，求解难度增加，但更符合实际。期望本文能为企业提升配送质量，节约配送成本提供参考。