姚 薇，丁必荣，吕 堃

（合肥工业大学 机械与汽车工程学院，安徽 合肥 230009）

·交通运输·

基于时间约束的物流运输路线优化

姚 薇，丁必荣，吕 堃

（合肥工业大学 机械与汽车工程学院，安徽 合肥 230009）

0 引 言

在物流调度中经常涉及到车辆路线问题 （VRP），即如何使运输的路线最短、运输费用最少等，这些都需要对路线进行优化设计。VRP是一个典型的NP难题，其路线优化算法很多，但主要分为两大类：精确算法和近似算法[1-2]。精确算法包括分枝定界法、动态规划法等[3-4]；近似算法则包括禁忌搜索法、遗传算法等[5]。

在分析VRP中运输成本和时间基础上，本文采用一种新的方法解决车辆调度路线优化问题，即在Dijkstra方法基础上，添加时间约束，构造出两个权 （费用权和时间权），进行迭代。

1 数学模型的建立

研究车辆物流调度的路线问题，就是研究车辆行走的最短路问题。最短路问题，简单地说就是寻求某网络中，从起点到终点的最短路径[6]。为此，首先应建立数学模型，而数学模型主要由变量、目标函数和约束条件等三部分组成。下面针对运输行业的具体情况，讨论一下运输成本的组成和具体计算公式，进而给出物流调度路线优化问题的数学模型。

车辆运输成本包括固定成本和可变成本两部分。固定成本包括车辆购买费用、税费和管理费用等，可变成本包括驾驶员的工作量、车辆消耗油量和过路费用等。参照公路运输部门计算运输成本的方法，可以制定出相邻两点之间的运费计算方法[7]：

其中，路况费用系数为不同路况对各种型号车辆造成的燃料油消耗、机械磨损 （反映在维修维护费用上）等形成的费用。

其中，车型修正系数为某车型 （车辆型号、新旧程度等）每单位吨公里的费用修正系数。

车辆到达某一个地点的时刻主要取决于发车时间、行驶时间和沿途停靠三个方面，其中影响沿途行驶时间的因素较为复杂，通过对相邻两地点之间的标准行驶进行定额，可以判断物流调度方案是否能在规定的时间内将货物送到目的地。根据下述方法来估算并根据实际情况加以修正，即相邻两点之间的运输时间T为：

其中，装载修正系数是对于不同的装载量 （重载和轻载）具有不同的速度限额，其他参数同上。这样就可以计算出每一条线路所需的时间。

以在规定的时间内，运输费用最低为目标函数，可建立以下的数学模型：

目标函数：

式中：Xij表示车辆从点i到点j行驶，有则为1，没有则为0；Cij表示从点i到点j的运输费用成本，可按照公式 （1）进行计算；n为途中的节点数。

约束条件：

式中：Tij表示车辆从点i到点j行驶的时间，可按照公式 （3）进行计算；Tm表示累计等待的时间；T表示规定到达的时间；其他符号的含义同上。

2 算法思路

上述问题可以构成一个赋权有向图D=（V,A ）， 对每一个弧aij=（vi,vj）， 相应地有费用权 ω（ aij）=ωij和时间权 θ（ aij）=θij。 目前，公认Dijkstra方法是解决具有正权的最短路问题的最佳方法[7]。其算法基本思想是：假设已经求出从vs到vt的最短路μ*如下： vs,…,vj,…,vk,…,vt。

根据最短路的性质，从vs沿μ*到vj或vk的路，就是vs到vj或vk的最短路。这就是说μ*不仅是起点vs到终点vt的最短路，而且，由vs到μ*上任意中间点的最短路也在μ*上。为了求得vs到vt的最短路，可先求vs到某中间点的最短路，然后再逐步扩展到终点vt。

Dijkstra方法只讨论解决具有一个权的最短路问题，本文在其基本思想基础上，引入时间约束作为判断条件，对费用权和时间权同时进行迭代。

在计算过程中，需要将已经求出到起点最短路的点与尚未求出到起点最短路的点区分开来，以正确执行迭代。为此，用标号法求解，即从vs开始，对每个节点给以标号。标号分为两类：临时标号Lj和永久标号dj。Lj表示从vs开始到被标号点vj的最短路权的一个上界，dj表示从vs开始到被标号点vj的真正最短路权。另外，引进集合N表示永久性标号集合。开始时，对vs有ds=0，其余各节点vj（j≠s ）则有Lj=ωij。算法的每一轮迭代都得到一个永久性标号，直到所有点都得到永久性标号为止。具体的算法流程图如图1所示。

3 算 例

在实际运用中，由于两个城市间的道路连接形式可能多种多样，如高速公路、普通公路、国道、铁路、水路等，每一种形式的运费、距离以及所需要的运输时间都不相同，如果每个城市当作一个节点，则无法反映上述情况，为了解决这个问题，本文采用增加节点的方法，即一个城市多个节点。但这样又会出现终点不唯一的情况，可用虚拟点加以解决，即将几个终点汇总成一个终点，其间的运费、运输时间、距离都为零。下面以某汽车股份公司的物流调度为例，首先根据实际运输情况，得出运输线路有向图如图2所示。

图中V4、V11为虚拟点，虚线表示0费用，0时间，第一个权为费用权 （单位：元），第二个权为时间权 （单位：小时），并根据销售情况得到时间约束T=13小时。其求解过程如下：

（1）迭代过程见表1所示，表的左边表示迭代次数，中部为迭代过程中累计成本和累计运输时间，每一次得到的永久性标号的先行节点，表示在表的右边。

表1 迭代过程

（2）反向跟踪得满足约束的最小费用路径。根据表1迭代结果，由终点V11反向跟踪先行节点V10，依次跟踪到起始点V1，得到满足约束的最小费用路径为：V1—V3—V4—V6—V7—V10—V11。该路径所需要的成本费用为840元，运输时间为13小时。

4 结束语

本文通过分析车辆运输的费用和时间情况，以最小运输费用为目标，规定时间为约束条件，建立车辆调度路线优化的数学模型，并在Dijkstra算法基本思想的基础上，提出解决多权约束的最短路问题的方法，给出了该方法的算法流程，同时利用增加节点和虚拟节点的方法，解决了实际中可能遇到的问题，为降低车辆调度的运输费用提供理论依据和实现方法，最后通过实例加以验证，表明该算法能够得到优化的结果。

[1] 肖建辉.车辆路径优化文献综述[J].广东技术师范学院学报，2010(12):31-37.

[2] 李仁安，袁际军.基于改进遗传算法的物流配送路线优化研究[J].武汉理工大学学报，2004(12):99-101.

[3] Lee C.G.,Marina A.,Cheslsea C.,et al.A shortest path approach to the multiple-vehicle routing problem with split pickups[J].Transportation Research,2006(40):265-284.

[4] 杨跃武.一种新的基于最小生成树的物流配送优化路线算法[J].计算技术与自动化，2008(3):24-28.

[5] 郭淑红，杨晓慧.遗传算法在物流配送路径优化问题中的应用[J].硅谷，2009(1):46-47.

[6] 程理民，吴江.运筹学模型与方法教程[M].北京：清华大学出版社，2003:45-50.

[7] 冯辉宗，陈勇，刘飞.基于遗传算法的配送车辆优化调度[J].计算机集成制造系统，2004(12):81-84.

The Optimization of Logistics Transportation Routing Based on Time Restriction

YAO Wei,DING Bi-rong,LV Kun
(School of Machinery and Automobile Engineering,Hefei University of Technology,Hefei 230009,China)

在分析车辆运输费用和运输时间的基础之上，建立一个以规定时间内最小费用为目标的物流调度路线优化数学模型。同时给出车辆路线问题的求解算法思路和计算流程，并结合实例，采用Dijkstra迭代方法，讨论该算法的应用。从而为在物流调度的车辆运输路线优化中实现在满足时间约束条件下达到运输费用最低提供依据和方法。

时间约束；物流调度；车辆路线问题；最短路问题

Through analyzing cost and time of automobiles transportation,practical mathematic model of route optimize in logistics distribution was established,which object was lowest costs in stated time.The algorithmic method and flow of vehicle route problem was presented,and based on example,adopted Dijkstra relaxation,discussed application of the algorithmic method.So it can offer gist and means for carrying out lowest transport costs during the optimization of logistics distribution routing in vehicle transportation,and satisfying time restriction.

time restriction;logistics distribution;vehicle route problem;shortest path theory

U116.2

A

2010-12-13

姚 薇（1975-），女，安徽桐城人，合肥工业大学机械与汽车工程学院硕士研究生，研究方向：物流工程；丁必荣（1978-），男，安徽合肥人，合肥工业大学机械与汽车工程学院，讲师，主要从事企业信息化工程和物流管理信息系统等方面的研究。

1002-3100(2011)03-0087-03