旅行时间不确定下的车辆路径问题研究

武小平，寇艺槟，樊相宇

（西安邮电大学 现代邮政学院 邮政研究院，西安 710061）

0 引言

近年来电子商务的兴起，网购的人数和线上订单量不断增加，线下需要将货物安全及时的送达客户必须有物流配送的支持。而现实配送过程中路况复杂，交通状况、节点客户需求变化、车辆故障等情况的发生难以预测，从而使得配送状况存在不稳定性，在这种情况下，配送员到达节点的时间难以把握，使得配送需求点的时间窗无法完全满足，从而降低客户满意度，同时这些不确定状况也会使决策者在配送路径规划时面临干扰。因此有必要研究不确定状况下的配送路径优化问题，从而尽可能的降低成本并满足客户需求。

在实际配送过程遇到的不确定环境主要有两类，一是交通状况，天气，车辆故障等因素导致的时间不确定，二是需求的不确定，包括需求节点的增减，需求量的变化等，目前针对这两类不确定因素下的配送路径选择优化问题已取得一定进展。张婷[1]研究了信息在配送过程中动态变化的城市配送车辆路径优化问题，通过引入虚拟变量，将动态问题转化为静态问题，最后用遗传算法寻找出最优配送路径。李妍峰[2]等研究了在实时交通信息下的车辆路径优化问题，其中考虑了偶发性交通拥堵，设计了在路径关键点更新路线的机制。张文博[3]针对需求点及时间窗变动下的车辆路径问题，以配送成本最小化和服务准时性为优化目标，提出初始阶段和动态优化阶段的两阶段优化策略，结合遗传算法和模拟退火算法寻找出最优路径方案。王海军[4]在应急物流的背景下，考虑应急物流需求量及运输时间的不确定，利用机会约束的理论建立了配送选址-路径问题的随机规划模型，并利用遗传算法进行求解，最终得出配送路径。王淑云[5]探讨了需求变动下的冷链物流带时间窗车辆路径优化问题，比较了需求确定性模型和需求随机性模型下路径和成本的差异，根据需求变动的幅度选择合适的模型来指导决策，并给出降低需求不确定的对策。

上述学者大多采用概率论，动态规划法来处理配送过程中遇到的配送时间不确定，需求点变化，需求量增减等不确定信息，但是现实中这类不确定事件的发生缺乏足够的样本数据来预测其发生的可能性，需要借助经验或专家意见来估计事件发生的把握程度。基于这种情况，Liu B[6]在2007年提出了不确定理论，可以借助该理论来描述在没有历史数据或实验数据作为参考而只能依靠来自专家经验数据的非精确信息。Liu B[7～9]在2009年把不确定理论应用于实际，提出应用该理论可以解决的一些实际问题。自此，利用不确定理论解决现实中存在的不确定问题得到了众多学者的关注，已有学者应用该理论解决不确定环境下的网络优化问题。Zhang B等[10]建立了中国邮路问题的不确定规划模型。Gao Y[11]研究了不确定条件下的最短路径问题。吴攀峰[12]等研究了以超市日需求量和车辆行驶时间为不确定变量下的超市物流配送问题，建立不确定机会约束模型，对模型进行转化并设计算法进行求解，最终找出路径。

本文主要研究以旅行时间作为不确定变量的带时间窗配送路径优化问题，以配送成本优化目标并建立不确定规划模型，利用不确定理论，将网络中不确定变量进行转化，再运用遗传算法对模型进行求解。

1 问题描述及数学符号说明

1.1 问题描述

不确定旅行时间下的车辆路径优化问题可描述为：一个配送中心负责多个配送需求点的物流服务，每个配送点都有时间窗要求，该配送中心有多辆车且每辆车都有载货量的限制，每一辆车都从这一配送中心出发，服务完所有配送点后回到该配送中心，每辆车所经历的配送点的物流需求总和不能超过该车辆的载货量限制，同时每个需求点只能被一个车辆所访问，最终使得所有配送网点的需求都被满足。由于在实际配送过程中会受到交通，天气状况等因素的影响，使得车辆在节点之间的旅行时间是不确定的，同时到达配送点的时间也是不确定的，本文就基于时间的不确定因素，考虑如何安排车辆配送路线，使得所有车辆在时间窗内将货物送到客户手中并使得配送成本较低。

1.2 数学符号说明

上述问题描述的数学语言表达：V=（V0，V1，…，Vn）为配送网络中所有节点的集合，其中V0表示配送中心，V＇=（V1，V2，…，Vn）表示n个配送需求点的集合，i，j表示配送网络中节点的下标，ωij={i，j=0，1，2，…，n}表示节点i到j的不确定旅行时间，其不确定分布记为Φij，旅行时间的期望置信度设为α，tij（i，j=0，1，2，…，n）表示在期望置信度下的节点i到j的旅行时间，dij={i，j=0，1，2，…，n}表示节点i到j的距离，c表示车辆单位距离的运输成本，qi（i=0，1，2，…，n）表示配送点的需求量，[ai，bi]表示配送点顾客需求的时间窗，其中ai表示顾客期望的最早送达时间，bi表示顾客所能容忍的最晚送达时间，ts表示在配送需求点处理一件货物的平均服务时间，tj表示车辆到达配送节点的时间，则tj=ti+qits+tij。配送中心有m辆车，k表示车辆，那么k＇={ki|i=1，2，…，m}表示配送车辆的集合，每辆车的载货量都相同且用Q表示。

利用罚函数的思想来处理时间窗约束，若车辆到达配送点的时间早于时间ai，则会延长配送时间，若车辆到达配送点的时间晚于bi，则顾客需要等待，客户满意度降低，因此早到和晚到的单位惩罚成本分别为e1和e2，且e2大于e1。

xik表示车辆k为配送点Vi服务，yijk表示车辆k从节点Vi行驶到Vj，两者都为决策变量，xik=1，说明车辆k服务于配送点Vi，否则Xik=0；yijk=1（i≠j），说明车辆k从节点Vi行驶到Vj，否则yijk=0。

2 模型建立

2.1 不确定理论知识

Liu B[5]提出不确定理论，给出不确定测度、不确定分布、逆不确定分布的定义。

定义1：设T是一个非空集合，L是T上的σ代数，L中的每个元素Λ称为事件，如果一个从L到实数集R的集函数满足以下公理：

公理1：规范性，对于全集T，有M{T}=1；

公理2：对偶性，对于任意的事件Λ，有M{Λ}+M{ΛC}=1；

公理3：次可加性，对于可数的事件序列{Λ}，有M{∑Λi}≤∑M{Λi}；

则称M为不确定测度，可知0≤M{Λ}≤1。

定义2：对于不确定变量ζ，它的不确定分布定义为Φ(α)=M{ζ≤α)，其中αϵR，它的反函数即为不确定分布的逆分布，记为Φ-1(α)。

2.2 模型建立

约束条件中配送点之间的旅行时间是一个不确定变量，各个不确定旅行时间之间是相互独立的，且决策必须在不确定变量实现之前作出，可以用不确定规划来解决，给不确定变量一个期望的置信度，从而根据变量的分布状况来指导决策。建立的模型如下：

目标函数式(1)表示总成本最小，包括车辆的运输成本和违反时间窗的惩罚成本，式(2)表示车辆在节点之间旅行时间的分布状况，约束式(3)表示车辆守恒限制，即m个车辆都是从配送中心出发并最终回到配送中心，约束式(4)表示车的载货量限制，式(5)表示每个配送点经过且只经过一次，顾客节点不能被重复访问，式(6)表示节点时间窗限制，式(7)、式(8)表示决策变量的取值。

根据不确定分布的定义2，约束条件式(2)可转化为：

进一步利用不确定变量逆分布的定义3，式(9)可转化为：

3 模型求解步骤

本文模型中含有不确定变量，需要对模型进行求解，首先需要估计不确定变量所服从的分布状况，进而利用不确定理论得出其逆不确定分布，可以引用Liu B[7]提出的99表算法来求解逆分布。为了简化，本文假设不确定旅行时间服从正态不确定分布。

步骤1：不确定旅行时间服从正态不确定分布

尽管现实中节点之间的旅行时间是不确定的，但可以根据经验或专家意见预测出其大致趋势，一般而言，所选择路径的可信度越强，所要花费的旅行时间就越长，即旅行时间与置信度呈递增关系。假设旅行时间服从正态不确定分布，正态不确定分布的函数及逆分布如下：

1）正态不确定分布

若不确定变量ξ具有如下正态不确定分布函数：

则称ξ为正态不确定变量，其逆不确定分布如下：

步骤2：计算逆分布的值

步骤3：遗传算法设计

目前针对此类问题模型的求解主要采用启发式算法，而遗传算法是启发式算法的一种，是借鉴生物界适者生存，优胜劣汰的遗传机制演化而来的随机搜索方法，具有较快的运算速度和更好的全局寻优能力。

1）染色体编码

采用自然数编码，配送需求点编号为1，2，…，n，将其从小到大进行排列生成一条配送点染色体，再对每个配送点随机安排一辆车，生成一条车辆染色体。以3个车辆（编号为1～3）9个配送点（编号为1～9）为例，随机生成的一个可行解如图1所示。

图1 3个车辆9个配送点的染色体编码示例

由图1可知，车辆1的配送路径为：1-4-6，车辆2的路径为：2-3-7，车辆3的路径为：5-8-9。

2）生成初始种群

初始种群的规模为S，其中包括了N条染色体。把n个配送点进行排列，首先给车辆一分配其所要服务的配送点，同时考虑车的载货量要大于其所服务配送点的需求之和，从而生成车辆一的配送路径，剔除掉车辆一所服务的配送点后，在剩下的配送点里按照同样的方法得出车辆二的配送路径，直到所有的配送点都被服务，从而得到第一条车辆染色体，再重复以上操作生成N条染色体构成初始种群。

3）选择

遗传算法中利用适应度函数来评估一个个体解的好坏，本文希望找到成本最小的路径，为了将其转化为最大值问题，因此选取目标函数的倒数作为适应度函数。根据适应度函数计算出每个个体的适应度，采用精英法，选取适应值最大的个体直接保留到下一代，再利用轮盘赌法选择其他的父代染色体进入下一代。

4）交叉

两个待交叉的不同的染色体根据交叉概率按某种方式交换其部分基因，Pc记为交叉概率，对于选择的两个车辆染色体A1和B1，随机产生两个交叉点，将两个交叉点之间的基因移动另一个染色体的头部，再将编号相同的基因删掉，即交叉完产生新的染色体A2和B2。

5）变异

变异操作能够保证种群的多样性，避免过早收敛，Pm记为变异概率，采用互换算子，即在一条染色体上随机选取两个非零变异位置，将其基因进行交换。

6）算法终止

经过一次迭代后，产生新的种群作为下次迭代的父代，随着遗传算法的进行，种族的基因差异会趋于一致，并且满足迭代次数，此时算法终止，否则回到选择操作继续迭代。

表1 节点之间旅行时间

4 算例分析

4.1 算例描述

某一配送中心（编号为0）负责15个客户节点的配送任务，节点之间的旅行时间服从正态不确定分布tij～N（dij/50，0.2），取置信度α=0.95，得到节点之间的旅行时间如表1所示，配送中心有6辆车，车的载货量都为100，配送点服务一件需求的平均时间是2分钟，车辆单位距离运输成本c=5元/km，各配送点的信息如表2所示，配送节点之间的距离采用欧式距离。

表2 配送节点信息

表2 （续）

4.2 结果分析

利用MATLAB遗传工具箱进行仿真，设置种群规模S=100，迭代次数为300次，交叉概率Pc=0.8，变异概

表3 最优路径结果分析

率Pm=0.1，算例计算20次，对运行结果统计分析可得，平均运行时间501.15s，总配送成本的平均值为8040.05元，平均行驶距离1551.85km。目标值收敛趋势如图2所示，在迭代前期，曲线下降较快，遗传算法的搜索速度较快，随着迭代次数的增加，曲线逐渐趋于平稳，最优解逐渐收敛，在迭代100次以后，曲线稳定到某一固定水平，进而得到最优解。

图2 目标值收敛趋势图

最优的配送路径及结果分析如下。

图3 最优配送路径图

车辆的最优路径如表3所示，此时总配送成本为7579.8元，总配送距离为1434.4km。

5 结论

在不确定理论的框架下，研究了旅行时间不确定因素下的带时间窗的车辆路径选择问题，建立了以配送成本最小为优化目标的不确定规划模型，并运用遗传算法进行求解，最后给出数值例子，通过计算机仿真，从而找到最优的配送路径。实际的配送过程中会有多种不确定情况，进一步研究还可以考虑需求点变动，需求量增减等多种不确定情形下的路径优化问题，使之更接近实际。