基于实时路况的配送路径优化问题研究

徐耀群，尹逊芹

(哈尔滨商业大学管理学院，哈尔滨150028)

车辆路径问题(Vehicle Routing Problem，VRP)最早是由Danting和Ramser[1]于1959年首次提出，自此以后一直是物流领域的核心和热点问题，吸引了众多学者和业者的研究和关注.现代物流市场的激烈竞争和顾客的个性化需求不断提高，使得现代物流配送配送运作更加复杂，要求物流配送系统更加灵活、高效地针对变化的环境调整作业计划，计算机及通讯技术的迅速发展，使得交通状况及运输工具的实时信息更易获取，为解决物流配送面对的新问题提供了基础.动态VRP正是在这样的背景下开始受到关注和研究.Eilon[2]等人首先提出了动态规划法，主要针对固定车辆数的VRP，采用递归方法求解.这种方法通过引入可行性规则或松弛过程减少状态的数量，从而减少问题的计算规模.Christofields之后提出了状态空间松弛，极大地减少了状态数量.这种方法认为:转化空间松弛数易于求解，映射出来的范围小，可求得很好的下界.Fisher[3]等人提出了三下标车辆流方程，主要是针对带有能力约束、时间约束窗口以及无停留时间的VRP问题.Clark和Wright[4]提出了Clarke－Wright算法，用来解决车辆数的不固定问题.

目前，国内对基于实时路况的动态随机车辆路径问题的研究还不多见，并且大多数采用预测的方法.主要具有以下特点:1)大部分研究的问题类型是确定性;2)研究手段比较单一;3)该领域的研究群体较小;4)对该领域的专有名词没有统一规范的提法[5].本文针对基于实时交通信息的配送路径问题建立数学模型，建立实时动态网络模型，在此基础上提出动态调度策略.

1 问题描述及数学模型

基于实时路况的车辆配送路径问题描述为:在完成任务的过程中，根据实时交通状况和车辆状况调整车辆任务安排，制定新的行车路径.1)一个中心仓库，拥有容量为q的车辆R辆，负责对N个客户进行货物配送工作;2)R辆车辆在初始时刻停靠在仓库中心，并在调度周期结束前返回;3)客户i的需求确定为gi(i=1，2，…N)，且gi＜q，1个客户只能由1辆车来服务，需求有时间窗要求，只允许等待，不允许延迟;4)1个调度周期由若干离散的区间，各个时间区间内部的车辆行驶速度是一定的;5)求满足需求的路程最短行驶路径，并使用尽量少的车辆，从而使费用最低.

设仓库中心的编号为0，客户的编号为1，2，…N，定义变量为:

建立数学模型如下:

在上述模型中，α、β为配送路径优化调度周期的开始、结束的时刻，gi为客户i的需求量cx为车辆的启动单位费用，Cr为车辆r行驶单位费用，P为等待单位费用，rijr(t)表示车辆r在t时刻从i出发开往j的到达时间.

模型中的(2)代表了目标函数，表示此次配送费用达到最低.其中，式(2)包括配送车辆的启动费用、车辆的行驶费用及等待费用3个部分，式(3)、(4)表示所有的车辆从仓库中心出发，在调度结束内返回仓库中心;式(5)表示仓库中心派出去的车辆的数目不能超过中心仓库所拥有的车辆数;式(6)定义了车辆容量约束;式(8)表示所有车辆必须在调度周期内返回仓库中心[6].

为了满足客户对准时化的要求，从而引入了配送不准时程度这个概念，用来处理时间窗的约束条件.配送不准时程度U是指车辆到达客户的时间早于或晚于时间窗边界的值与时间窗跨度的比，根据这个定义可以发现，若配送时间刚好在时间窗的要求之内，则其配送的不准时程度0，配送不准时程度U的数学表达式为:

其中:[Ei，Li]为客户点的配送时间窗要求(τ)为在τ时刻出发，车辆在弧(vi，vj)上的行程时间;为客户服务时间为车辆到达配送路线上第j个客户的时间.到达客户点的时间等于到达前一个客户点的时间加上服务时间，再加上两点之间的行程时间，即，且通过配送准时程度就可以将时间窗约束转化为客户配送不准时程度最低这样一个新的目标，其中

通过引入配送不准时程度这一概念，可将原有的单一目标路径规划问题转化成多目标路径规划问题，不仅仅考虑到配送成本费用最低，还考虑到配送不准时程度最低这个目标，并为这两个目标赋予一定的权重η1和η2，用来表示这两个目标的重要程度.由此得到基于实时路况的配送路径优化模型的目标函数可表示为:

约束条件不变仍为式(3)、(4)、(5)、(6)、(7).

2 实时动态网络分析

针对上述模型，提出了进行配送的两个目标，一是成本最低;二是准时化.本文使用静态的网络模型来处理动态的VRP问题，从而更好的满足上述两个配送目标.下面用有向图来表示静态网络模型，图中的每一条边都标有固定的权值，此权值表示两个客户之间的行驶时间，此处假设车辆的行驶速度是一致的，客户之间的行驶时间由客户之间的直接距离确定的.

在实际的配送路径优化中，两个客户之间的最佳路径有两个方面来确定，一是客户之间的物理距离;二是客户之间的行驶时间.用最短的时间，行驶最短的路径，才能降低配送成本，提高配送的准时性.本文设计了一个动态网络模型，考虑到两种情况:①VRP问题的实时最短路径;②两个客户之间的实时最短路径[7].

1)VRP问题的实时最短路径

假设有9个客户由2辆车服务、仓库中心用0来表示.在时的最短路径如图1所示.

图1 t=T0时的最短路径

车辆1:0→1→2→3→4→0;车辆2:0→5→6→7→8→9→0.在这种情况下，我们可以实现总路径的最短行驶路径，即车辆1和车辆2的总的行驶路径是最短.

假设t=Tn时，车辆1到达节点4，车辆2到达节点8，这时，在节点8和9之间的路径上出现了较严重的交通事故，如图2所示.

图2 t=Tn时的最短路径

很明显，因为节点8和9之间出现交通事故，需要对初始规划的路径进行重新的设计规划.新设计的路径如图3所示，这是车辆1和车辆2的起点是重新设计规划时车辆所到达的地点(节点4和节点8)，由车辆1来对客户点9服务，车辆2完成对客户点8服务之后直接返回仓库中心.

图3 t=Tn时的最短路径

即由图3可知，车辆1:0→1→2→3→4→9→0;车辆2:0→5→6→7→8→0.这样可以应对节点8到节点9之间出现的特殊状况，也可以实现最大限度的最短路径.

2)两个客户之间的实时最短路径

在图1、2、3中，节点3和节点4是有一条边相连的，这表示车辆1完成对客户3的服务之后，车辆1的下一个客户就是客户4，但并不表示这两个客户之间只存在一条路径.实际上，这两个客户之间一般会有多条路径，到底是那条路径最短，这取决于当时的网络状态来决定.在t=T0时，它们之间的最短路径可能为:3→10→12→4，而在t=Tn时，最短路径有可能变为:3→15→16→13→4.如图4、5所示.

针对模型的目标，在进行动态路径规划时首先对客户的服务顺序进行调度，然后在对客户之间路径进行规划，在这个过程中，充分考虑到配送的成本费用以及行驶时间.

3 调度策略

为了更好的解决性VRP问题，Clarke·G等人构造了节约算法，他们的基本观点是:首先建立所有的客户与配送中心之间的单客户配送线路，然后按照节约值最大的原则将两个客户连接起来形成一条线路，随之将所有客户根据节约值最大的原则纳入线路，直到车辆满载，形成1条配送路线;根据上述方法构造其他配送线路，直到节约值大于0的配送线路不再存在为止.本文针对模型的特点，在考虑到准时性原则前提下，在对客户进行服务顺序的调度时，利用带插入规则的节约算法，从而降低配送成本，又能满足客户在时间上的要求[8－9].本文提出了如下调度策略:

第1步:连接客户点i和客户点j，并且计算连接之后的总的配送费用节约值Mij;

第2步:若配送费用节约值Mij均为0，则调度策略结束;否则，找到Mij最大值所对应的客户点i和客户点j，并考察这两个客户点.

第3步:在考察客户点i和客户点j过程中，如果满足以下4个方面，则继续第4步;否则，直接转到第7步;

1)客户点i在该线路的起点，而客户点j不在该条线路上;

2)客户点i在该线路的终点，而客户点j不在该条线路上;

3)客户点i在一条线路上的起点，而客户点j在一条线路的终点;

4)客户点i和客户点j都不在同一条线路上.

第4步:连接客户点i和客户点j之后，计算此线路的总运量G，如果G≤q，则继续第5步;否则，直接转到第7步.

第6步:计算连接客户点i和j客户点之后所有车辆完成各项任务的的新时间.

第7步:将该节约值Fij赋值为0，转到第2步.

此调度策略运用带插入的节约算法来解决基于实时路况的配送路径问题，第3步中1)和2)可以使得没有进行配送线路的客户点与已有的配送线路在起点或终点相连，3)可以使2条线路首尾相连，而4)可以使得节约值最大的2个没有进入配送线路的客户点相连，通过这四个方面不仅可以协调真实的协调费用，而且可以协调调度裕度.第六步保证了配送中心对客户服务时间不延迟.通过这种方式，一方面满足客户的需求，另一方面降低配送成本.

4 结语

通过建立数学模型、分析实时动态网络模型，提出了针对实时路况的配送路径优化调度策略，并采取带插入规则的节约算法进一步确保策略的有效性.通过考虑实时动态模型，很好的解决道路交通运输过程中的交通运输过程中的交通阻塞问题，通过减少拥塞时间降低总成本，具有一定的实际应用价值.

[1]DANTZING G，RAMSER J.The truck dispatchting problem[J].Management Science，1959，10(6):80－91.

[2]EILON S，CHRISTOFIDES N.Distribution management:mathematical modeling and practical analysis[M].London:Griffin，1971.

[3]FISHER M L，JAIKUMAR R.A generalized assignment heuristic for vehicle routing[J].Networks，1981(11):109－124.

[4]CLARKE G，WRIGHT JW.Scheduling of vehicles from a central depot to a number of delivery point[J].Operations Research，1964(12):568－581.

[5]张 涛.王寿光.遗传算法和3－OPT结合求解带能力约束的VRP[J].东北大学学报，1999，20(3):253－256.

[6]徐 杰，江永亨，黄德先.基于实时交通信息的车辆路径问题研究[J].计算机与应用化学，2009，26(9):1093－1094.

[7]王祥生，马寿峰.实时路况信息下配送路径的优化[J].工业工程，2008，11(1):115.

[8]钱艳婷，王鹏涛，魏国利.动态车辆路径问题的算法研究[J].天津理工大学学报，2010，26(6):73.

[9]李 岚，姜伟强.蚁群遗传算法在物流配送路径选择中的应用[J].哈尔滨商业大学学报:自然科学版，2009，25(6):707－710.