0.   引言

中国的城市交通是一种以小汽车为主的混合交通。随着汽车工业的发展, 城市汽车保有量大幅度增加, 而交通设施的建设速度远远低于小汽车数量增长的速度, 所以越来越多的城市出现交通拥挤与交通堵塞现象。交通拥挤不仅给城市居民出行带来很大的不方便, 也给适时物流系统带来很大的不确定性。这种不确定性使得传统上以运输时间为常数的静态车辆调度方法已经不符合实际需要, 要求配送活动必须根据交通状况进行调整。

动态交通下的配送车辆调度问题可以描述为: 从配送中心用多辆车向多个用户送货, 每个用户的位置和需求量一定, 要求将货物按时间窗的约定送达用户, 过早到达需要等待, 过晚到达要给予惩罚。在配送过程中由于交通流量的不稳定性, 用户之间的运输时间随着交通状况而动态变化。这种动态性使得配送车辆的准时性难以完全满足, 所以必须设计一种调度方案, 在满足用户时效性要求的同时, 寻求配送成本最小的车辆调度方案。

1.   文献综述

大量文献对配送系统路径优化进行研究, 并通过不同的优化算法对此予以求解, 但这些研究都以静态交通为主, 假定任意2个用户之间的运输时间是确定的, 忽略了城市交通拥挤带来的运输时间的不确定性^[1-9]。有些学者曾对交通不确定性予以考虑: Orda等对随机运输时间进行研究, 但解的收敛性不好^[10]; Halpern将运输时间作为分段函数进行考虑^[11]; Hill等通过相邻区域的平均速度来求解跨区域运输时间^[12]; Soumia等假定运输速度在不同区域不同, 但在同一区域是相同的方法来分解运输时间^[13]; 徐同连等考虑了运输时间小变异的随机性, 并将道路状况进行分类^[14]。比较而言, 这些文献对运输时间的研究更接近现实情况, 相对于确定性配送有了很大的改进。但这些研究仍然假定用户之间的运输时间要么在一天内是相同的, 但不考虑日交通流的差异性; 要么假定一天内运输时间是动态的, 但不考虑日交通流的随机性。而现实中的交通状况是动态的, 日交通量既具有差异性, 又具有随机性, 所以现实配送问题既要考虑运输时间在不同时段的分布规律, 也要考虑同一时段运输时间的不确定性。

2.   动态交通下运输时间分析

正常条件下, 车辆运输时间主要影响因素是交通流量^[15]。图 1显示, 交通流量和运输时间存在反比例关系, 随着道路中交通流量的增加, 运输时间也在增加。图 2描述了在大量统计情况下交通量在不同时间段的分布情况, 明显地看出交通流量是分阶段分布的, 在交通高峰期变动较大, 其余时间交通流量较低, 且比较平稳^[16]。由图 1、2可以看出, 中国城市交通量大致在交通高峰期运输时间明显增加, 而且发生交通拥堵的概率也高, 所以平均运输时间不稳定。而对于非高峰期, 平均运输时间较低, 而且分布比较平均。由此, 本文根据交通流量的这种分阶段分布规律将运输时间分为高峰时段和非高峰时段, 运输时间在不同时段服从不同的分布。

图  1  交通量与运输时间关系

Figure  1.  Relation between traffic and transport time

下载: 全尺寸图片 幻灯片

图  2  日交通量分布

Figure  2.  Distribution of daily traffic

下载: 全尺寸图片 幻灯片

3.   车辆路径选择模型

车辆路径选择的目的是在满足一定准时性的前提下, 在车辆容量及时间窗的约束下, 求得最低配送成本的配送方案。

3.1   模型基本假设

(1) 交通状况分为高峰期和非高峰期2个阶段。

(2) 运输时间在各阶段服从一定的概率分布(正态分布或者均匀分布)。

(3) 车辆成本可以分为固定成本和与工作时间成正比的可变成本2部分。

(4) 各用户的需求量确定。

3.2   模型描述

设物流中心有m辆车, 车辆k的载质量为Q_k(k∈m), 需要向n个用户送货; 用户i的需求量为q_i, 时间窗为[a_i, b_i]; c_k^f为车辆k的固定成本; c_k^v为车辆k的可变成本; c_k^p为车辆k违背时间窗的惩罚成本; r_k为车辆k所服务的用户数量; t_ki^a为车辆k到达用户i的时间; t_ki^o为车辆k在第i个用户的作业时间; t_ki^l为车辆k离开第i个用户的时间; t_kij为车辆k在用户i和j之间的运输时间; T_kmax为车辆k的最大工作时间; T_k为车辆k的实际工作时间; μ_kij^ε为在ε时段车辆k在用户i和用户j之间运输时间的均值; σ_kij^ε为在ε时段车辆k在用户i和用户j之间运输时间的均方差; θ_i为用户i的服务水平约束; δ_k∈{0, 1}, 值为1表示车辆k参与配送, 值为0时, 表示该车不参与配送活动; x_ij^k∈{0, 1}, 值为1时, 表示车辆k服务完i后, 接着服务j, 值为0表示相反。

模型目标函数为

$\begin{array}{l}{\rm Z}=\min \{{\displaystyle \sum _{k=1}^m\delta }{}_{k}c{}_k^{\text{f}}+{\displaystyle \sum _{k=1}^{m}c}{}_k^{\text{v}}{\rm T}{}_k+\\ {\displaystyle \sum _{k=1}^m{\displaystyle \sum _{i=1}^{r{}_k}c}}{}_k^{\text{p}}\max [0,(t{}_{ki}^{\text{a}}-b{}_i)]\}(1)\end{array}$

${\rm T}{}_k={\displaystyle \sum _{i=0}^{r{}_k}\{}\max [(t{}_{ki}^1+t{}_{ki(i+1)}),a{}_{i+1}]+$

$\begin{array}{l}t{}_{kij}\in {\rm N}\left(u{}_{kij}^{\epsilon }‚(\sigma {}_{kij}^{\epsilon }){}^2\right)(3)\\ t{}_{k(i+1)}^{\text{a}}=t{}_{ki}^{\text{l}}+t{}_{ki(i+1)}(4)\end{array}$

约束条件为

$\begin{array}{l}{\displaystyle \sum _{i=1}^{r{}_k-1}{\displaystyle \sum _{j=i+1}^{r{}_k}q}}{}_{i}x{}_{ij}^k\le Q{}_k(5)\\ {\rm T}{}_k\le {\rm T}{}_{k\text{m}\text{a}\text{x}}(6)\\ {\displaystyle \sum _{i=1}^{r{}_k-1}{\displaystyle \sum _{j=i+1}^{r{}_k}x}}{}_{ij}^k=1(7)\\ {\displaystyle \sum _{k=1}^m{\displaystyle \sum _{i=1}^{r{}_k}{\rm P}}}(t{}_{ki}^{\text{a}}\le b{}_i)\ge \theta {}_i(8)\end{array}$

目标函数式(1)是求得配送成本最低的方案, 即固定成本、作业成本及惩罚成本之和最低; 式(2)车辆作业时间表示为服务完所有用户的总时间; 式(3)用户间运输时间在不同时间段服从不同的正态分布; 式(4)车辆达到用户的时间是离开上一个用户的时间与相邻两用户之间运输时间之和。

约束条件中: 式(5)表示每条配送路径上各用户的货物需求量之和不超过配送车辆的载质量; 式(6)表示车辆的实际工作时间不得超过车辆最大工作时间; 式(7)表示每个用户的货物需求必须满足, 且只能由一台配送车辆送货; 式(8)表示服务水平约束。

4.   遗传算法设计

车辆路径问题作为一个NP-Hard问题, 随着用户数量的增加, 可选的车辆路径方案数量将以指数速度急剧增长, 因此, 用启发式算法求解该问题就成为研究的一个重要方向。遗传算法易编码, 操作简单, 是解决此类问题的有效方法之一。

4.1   编码

根据模型解的特点采用自然数插值编码方式, 随机产生n个自然数的全排列, 先对染色体的基因首尾各插入1个“*”, 接着判断车辆容量限制。如第1辆车的车载容量大于前i个用户的需求量之和, 但小于前i+1个用户的需求量之和时, 在第i个基因后插入1个“*”, 表示前i个用户由一辆车进行配送。从第i+1个用户开始再进行车辆容量检测, 以此类推, 直到所有基因都纳入配送路径中, 并将这个排序赋值给y, 表示1个染色体配送方案, 将2个“*”中间的基因定义为1个基因段。例如, 9个用户的配送任务可以由染色体235489617这9个互不重复的自然数表示, 通过插值法可以表示为3个基因段组成车辆调度方案, *235*48*9617*表示共有3辆车为9个用户服务, 第2、3、5用户由1辆车进行配送, 第4、8用户由1辆车进行配送, 第9、6、1、7用户由1辆车进行配送。

4.2   适应度计算

目标函数是极小值问题, 通过界限构造法构造的适应度函数为

$f(y)=C-{\rm Z}(9)$

式中: f(y)为染色体y的适应度; C为一极大数; Z为染色体y的目标函数。对每个染色体进行配送约束条件检验, 对于不满足条件的染色体赋予1个较大的惩罚。

4.3   选择

本文采用精英选择策略, 将每代群体中的h个染色体按适应度由大到小排列, 排在第1位的染色体性能最优, 将它直接复制进入下一代, 并排在第1位。下一代群体的其余h-1个染色体需要根据前代群体的h个染色体的适应度, 采用蒙特卡罗法产生, 这样的选择方法既可保证最优染色体生存至下一代, 又能保证适应度较大的染色体以较大的机会进入下一代。

4.4   交叉

对通过选择操作产生的群体, 以交叉概率选出需要交叉的染色体, 两两配对, 进行交叉。对于双亲*13*245*978*6*和*235*891*476*, 如随机选择出第1个父染色体的第1段基因与第2个父染色体的第2个基因段进行交叉。交叉的方法是: 首先将第2个染色体的第2段基因891填充到第1个子染色体的第1个基因段上, 并将第1个父染色体的基因复制到第1个子染色体的其余基因位, 得到染色体*891*13*245*978*6*, 接着将子染色体1中和基因段中相重复的基因删除。通过上述操作, 就可以得到子染色体1为891324576, 子染色体2为251389476。

4.5   变异

每个基因的取值范围是1至n之间的互不重复的自然数, 而且每个染色体都是n个自然数的全排列。通过变异概率选出需要变异的染色体, 从中随机选出2个基因进行位置交换, 就可以得到较好的变异效果。

5.   算例设计

以下设计9个用户的配送方案, 各用户需求量及时间窗见表 1。

表  1  用户时间窗与需求量

Table  1.  Demands and time windows of consumers

下载: 导出CSV 

| 显示表格

运输时间分为两部分: 高峰期运输时间和非高峰期运输时间, 表 2中, 每行第2组数据表示高峰期(07:30~08:30, 18:00~19:00)运输时间的均值与方差, 第1组数表示非高峰期运输时间的均值与方差。

表  2  用户之间运输时间

Table  2.  Transport times among consumers  min

下载: 导出CSV 

| 显示表格

车辆在各用户点的作业时间为0.2 h, 车辆的可变成本为50元·h^-1, 固定成本为每天200元, 车辆延期惩罚费用为300元·h^-1, 车辆最大工作时间为12 h, 最大载质量为5 t, 要求车辆的服务水平达到80%以上。

基于上述数据, 利用C语言编程。参数为: C为10 000, 种群大小为20, 染色体长度为9, 交叉概率为0.7, 变异概率为0.05, 迭代次数为100代。

图 3显示, 对于确定性运输问题, 在48代遗传过程问题收敛, 最优染色体为967231548, 适应度为8 858.8, 最优配送方案为*967*231*548*, 配送成本为1 141.2元。由于运输时间在不同时段方差的差异性, 所以在算法迭代过程中运输时间的不确定会导致配送成本的差异。取算法最后一代排在前5的5个染色体, 组成5个配送方案, 进行为期1月的仿真, 结果如下。

图  3  历代适应度曲线

Figure  3.  Fitness curves of generations

下载: 全尺寸图片 幻灯片

图 4是交通流较为稳定时的配送仿真结果, 图 5是交通流不稳定时的配送仿真结果(方差扩大1倍), 此时由于运输时间的波动较大, 所以最优方案选择有所变化。表 3显示, 运输时间确定时, 方案1是最优配送方案。在动态交通下, 当交通流比较稳定时, 方案1仍为最优方案; 但当交通流不稳定时, 由于某些路段受到交通拥挤带来的运输时间的不确定性, 方案1已不是最优方案, 方案2成为最优方案。选择方案2可以节约物流成本2%, 服务水平也从88%提高到93%。

图  4  交通流较稳定时的仿真结果

Figure  4.  Simulation result under steady traffic

下载: 全尺寸图片 幻灯片

图  5  交通流不稳定时的仿真结果

Figure  5.  Simulation result under unsteady traffic

下载: 全尺寸图片 幻灯片

表  3  不同交通情况下配送方案

Table  3.  Delivery projects of different traffic situations

下载: 导出CSV 

| 显示表格

6.   结语

在动态交通下, 城市物流配送运输时间取决于道路中的交通流量, 而交通流量在不同时段具有不同的分布规律。本文根据交通流量随机、分段分布的特点, 设计出动态交通下城市物流车辆路径选择模型, 并通过遗传算法寻求不同交通状况下车辆调度方案。该方法不仅可以应用到城市货运车辆的调度, 而且对于城市公交与通勤车辆调度也具有良好的引导性。