交通堵塞扰动下多车场车辆路径优化

朱冰冰

摘要：为解决物流配送中突发性交通堵塞造成的干扰问题，针对多车场带时间窗的车辆路径问题，建立交通堵塞扰动下多车场车辆路径干扰管理模型，并用离散粒子群算法求解，验证模型和算法的可行性和有效性。

关键词：交通堵塞；干扰管理；粒子群算法

一、引言

物流配送过程中，车辆经常会受到随机事件的干扰，如车辆故障、交通堵塞、顾客需求变化等。因此，如何有效处理此类干扰事件，是物流配送管理的难点。根据美国学者Yu Gang（2004）对干扰管理的定义可知，干扰管理正是处理这类问题的方法论。

P.B.Mirchandani（2007）针对交通事故提出了干扰恢复备用车辆选择。Lorin（2011）针对客户需求和服务时间的变化构建模型求解，验证了模型可行性。王旭坪等（2013）针对客户需求变化干扰，提出了带回程取货车辆调度扰动恢复模型。胡祥培等（2011）提出了多阶段划分方法，形成了处理时间延迟干扰问题的序贯决策方法。

虽然上述文献对干扰事件已经有了一定的研究，但对多车场车辆路径干扰问题研究较少。本文研究交通堵塞多车场带模糊时间窗的车辆路径干扰管理模型及其算法，针对该类事件为物流企业提供决策支持。

二、交通堵塞多车场带时间窗VRP干扰管理模型

三、求解算法

本文基于标准粒子群算法，提出离散粒子群优化算法进行求解。粒子群算法（PSO）是通过模拟鸟群觅食过程中迁徙和群聚行为而提出的基于群体智能的随机搜索算法。PSO是将群中的个体看做在D维搜索空间中的微粒，每个粒子都有自己的适应度值，以一定的速度v在解空间中运动，通过不断的迭代寻找最优解。

（一）编码方案

标准的粒子群算法具有连续本质，不太适宜求解离散问题。因此，本文在属于连续空间的粒子与属于离散空间的行驶方案之间建立一种联系，即设计粒子群编码来映射行驶方案的解。将车场和需求点统一编码，并以车场编号进行划分各个车场要服务的需求点的子窜，得到了每个车场服务的需求点之后，再根据每个需求点的需求量和每个车场的车辆的载重进行指派车辆服务，进而完成整个解码过程。

（二）堵塞问题处理

加入路径干扰或者堵塞的原理：对受到影响的客户点i到客户点j的路径i→j，将其距离乘以一个系数，如此一来使得i到j之间的虚拟距离边长了，也即产生了延迟，如果虚拟距离设置为无限大，那么这段路就是堵塞了。因此，对距离矩阵进行延迟处理，也即改变其距离，然后在进行用算法优化得到相应的结果。公式为Di，j=Di，j*γ，其中Di，j为节点i到节点j的距离，γ>1为延迟系数，γ=inf时发生堵塞。

四、实验结果分析

本文的算法以matlab语言实现，运行程序在Inter Core 2.2GHz的处理器、内存为2G的计算机上。本文数据从算例RC101取部分节点产生，最后计算结果不仅给出调整的路径结果，同时在客户容忍的时间窗内计算客户满意度。在多车场车辆路径的情形里，发生干扰事件后，从成本和客户满意度方面进行量化并建立模型，快速生成新方案，兼顾各方利益，同时，车辆在多个车场之间得到良好协调。

参考文献：

[1]Gang Yu，Xiangtong Qi.Disruption management：framwork，models，and applications[M].World Scientific Publishing Co.Pte.Ltd，2004.

[2]Jing Quan Li，Denis Borenstein，Pitu B.Mirchandani.A decision support system for the single-depot vehicle rescheduling problem[J].Computers and Operations Research，2007，34（4）：1008-1032.

[3]王旭坪，阮俊虎，孙自来，曹海艳.带回程取货车辆路径问题的干扰恢复模型[J].系统工程学报，2013：28（5）：608-616.

[4]胡祥培，于楠，丁秋雷.物流配送车辆的干扰管理序贯决策方法研究[J].管理工程学报，2011，25（2）：186-190.