基于有时间窗的城市配送车辆路径方案优化

卢尔赛，李汉卿，赵 辉，王 硕

（交通运输部科学研究院，北京 100013）

基于有时间窗的城市配送车辆路径方案优化

卢尔赛，李汉卿，赵 辉，王 硕

（交通运输部科学研究院，北京 100013）

在城市配送业务中，配送线路安排的合理与否对配送速度、成本、效益影响很大。提出了基于有时间窗、单出发点的城市配送车辆配送模式，在对有时间窗的车辆调度问题进行描述的基础上，建立了有时间窗的城市配送路径优化问题的数学模型。利用Lingo软件，对城市配送路径进行优化实证，验证模型的适用性。

城市配送；路径优化；时间窗

1 引言

城市配送是现代物流服务体系的重要组成部分。城市配送提供的是门到门的服务，其特点不同于干线运输，需求往往是分散的，且具有随机性。基于城市配送的这个特点，合理地规划城市配送车辆路径，不仅可以提高企业自身配送效率，节约配送时间，提高配送响应速度，还可以降低配送成本，为客户提供优质服务。同时，城市物流运输也给一些大城市交通带来高负荷、多拥挤以及交通污染现象，使得交通管理部门越来越多地对城市配送车辆实施交通限制管理。目前，国内一线城市都对城市配送车辆有相关的限行时间管理控制措施，所以城市配送的路径优化不仅要考虑传统的成本和速度问题，还要考虑通行时间问题，这样的优化方法才更具现实意义。

从城市配送基础设施的角度，考虑时间窗的城市配送车辆路径优化，有助于更高效地利用城市配送的基础设施，不会造成局部区域基础设施的闲置浪费，也不会造成热点地区基础设施的供不应求，实现资源的合理利用。

从城市配送运输组织模式的角度，考虑时间窗的城市配送车辆路径优化，在有条件的区域施行城市共同配送，有利于优化现有的城市运输组织模式，提高车辆的利用率，降低车辆空驶率，疏解城市道路拥堵情况，降低配送成本。

从城市配送信息化的角度，考虑时间窗的城市配送车辆路径优化，是创建智慧城市配送体系的基础条件。通过对道路情况、车辆配载情况的信息数据采集，在远端实现对城市配送车辆的精细管理，精确指导城市配送车辆的路径选择，使城市配送更加智能化。

从城市配送绿色安全的角度，考虑时间窗的城市配送车辆路径优化，有助于减少车辆空驶带来的尾气排放，从而减低碳排放，实现一定程度的节能减排。同时，对城市配送车辆进行路径优化管理，有助于对车辆实施跟踪管控，降低事故的发生率，减少其对社会产生的负面影响。

2 国内外研究现状

配送车辆的优化问题一般可根据空间特性和时间特性分为车辆路径规划问题和车辆调度问题。当不考虑时间要求，仅根据空间位置安排车辆的线路时称为车辆路径规划问题(VRP--Vehicle Routing Problem)；考虑时间窗要求安排运输线路时称为车辆调度问题VSP (VSP--Vehicle Scheduling Problem)。某些学者将有时间要求的车辆路径规划问题称为Vehicle Routing Problem With Time Windows(VRPTW)。从国内外研究上可以分为三大类：第一类是传统车辆路径优化问题的拓展问题，即在传统城市配送车辆路径优化模型的基础上增加能力约束、随机需求等约束条件，使模型更加复杂并贴近实际；第二类是对现有城市配送车辆路径优化问题进行算法改进，用交叉学科里的优化算法试图为车辆路径优化提供最优解集；第三类是应用研究，即在模型和算法固定的基础上，根据城市具体的配送车辆路径优化实际案例，提出应用问题解决方案。本文属于第一类和第三类的融合，既考虑了增加时间窗的约束，以期更满足现实配送情况，另一方面也是具体配送问题的应用。

传统车辆路径优化问题的拓展问题方面，车辆路径问题在经典VRP问题的基础上产生了许多不同的延伸和变化型态，包括TSP、带能力约束的车辆路径问题、随机需求车辆路径问题、带时间窗的车辆路径问题、动态车辆路径问题、追求最佳服务时间的车辆路径问题、多车型车辆路径问题、车辆多次使用的车辆路径问题、考虑回路的车辆路径问题。国内学者杨锦冬，徐丽群（2004）基于交通条件约束、客户时间窗约束以及车辆承载能力约束条件下，以车辆的配送路径最短、拼装货品最多为优化目标，提出车辆配送与配载的两目标优化调度模型组。国外专家Fisher（1997）研究了有时间窗的多配送中心车辆调度问题；Tailllard（1994）将多配送中心车辆调度问题分解成两个子问题：多配送中心的选址问题和一般的单配送中心车辆调度问题。

对现有城市配送车辆路径优化问题进行算法改进方面，国内学者肖健梅，黄有方，李军军，王锡淮（2005）提出一种求解物流配送车辆路径的离散微粒群优化算法，通过此优化算法解决了求解车辆路径离散组合的问题。吴洁明（2011）针对传统优化方法搜索时间长，难以找到最优路径的问题，提出一种蚁群算法的物流配送车辆路径优化算法，最后采用蚁群算法对车辆路径问题的数学模型进行求解。天津大学钟石泉，贺国光（2004）提出一种多车场的智能处理方法，用遗传算法进行优化研究的基本为单车场VRP问题。

在车辆路径优化应用研究方面，国内学者郝瑞卿，闫莉（2015）在分析军事后勤车辆路径问题特点的基础上，建立了单时间窗多目标动态军事后勤车辆路径模型，可有效解决军事后勤车辆动态路径优化问题。贺政纲，刘沙（2015）构建了以总回收时间最短为优化目标的带有时间窗的车辆路径优化模型（VRPTW），以成都市金牛区医疗废弃物回收为例，验证了模型的有效性。国外学者Teo和Taniguchi（2015）通过对Osaka城市具体配送案例的分析，提出针对城市配送需求特点改进的车辆路径优化模型和系统。

3 基于时间窗的路径优化模型

3.1 问题描述

城市配送需要选择合适的线路，在保证需求及时的前提下，尽可能的使运输线路最短，即VRP问题。

设G=(V,A)是一个有向图，其中V={ } 0,1,…,n是顶点集、顶点0表示配送中心，顶点1，2，…，n表示销售点，A是弧集，表示销售点之间或配送中心与销售点之间的道路连接。每一条弧上有一个非负数我们定义这个数为运输距离。将所有的cij写成矩阵的形式，即若C是对称矩阵，将弧集A用边集E代替。另外，我们假定在货场有m个车可用，其中ml≤m≤mu。为简单起见，我们假定所有车辆是相同的，并且有相同的运输能力D。我们的目标就是设计一套运输配送方案，使总费用最少，并且满足下列约束：

（1）V中的每个销售点访问一次并且只能访问一次；

（2）所有车辆必须从配送中心出发并回到配送中心；

（3）满足一些实际的附加约束条件。

3.2 假设条件

现有m辆相同的车停在配送中心V0，它需要给n个销售点提供货物，并且配送中心和销售点的坐标已知。每个客户同一时刻只能接受1辆车的服务，1个子回路对应1辆车。车辆完成运输任务后必须返回配送中心。

（1）集合。ci表示第i辆车对应的路线中销售点的集合，cij∈ci。

（2）常量及变量说明

li：每条回路上的销售点数目；

Qij：第i辆车在其子回路上对应的第j个销售点的需求量；

Cij：第i辆车对应的子回路中顺序为j的点；m：配送中心拥有的车辆数目；

N：满足运输任务需要车的最少数量；M：车辆的最大载重量；L：车辆的最大行驶距离；di(j-1)：第i辆车对应的路线中顺序排列的第j-1个销售点和第j个销售点之间的距离；

di(li)(0)：第i辆车对应的路线中第li个销售点与配送中心V0之间的距离。

3.3 模型建立

约束（1）表示每条回路上的运输总量不能超过车的最大载重量和最大行驶距离；

约束（2）表示各条回路上的销售点数量之和等于n；

约束（3）表示每条回路上的销售点不超过n；

约束（4）表示所用车的数量不能超过备用车的数量；

约束（5）表示1个子回路对应1辆车；

约束（6）表示每个客户同一时刻只能接受1辆车的服务；

约束（7）表示一个0-1整数变量。

下面以沈阳市为例，对一辆车的行车路线进行优化。假设该车负责对2、3、4、5、7、9、10、11的销售点进行配送，各点的坐标已经给出。则目标函数和约束条件如下所示：

其中，约束条件是总距离最短。约束条件（1）表示每个点只有一个边出去，（2）表示每个点只有一个边进入，约束（3）、（4）表示形成的回路中没有子回路。

4 模型计算结果

为了方便计算，对2、3、4、5、7、9、10、11用2到9表示，1表示配送中心。各点之间的距离矩阵见表1。

表1 距离矩阵

Lingo编码如图1所示。运行结果如图2所示。

图1 Lingo操作编码页面

图2 Lingo运作结果界面

可以得到最优的配送线路是1-9-10-6-11-4-5-3-2-7-1，对应于沈阳市的配送线路为R-9-10-6-11-4-5-3-2-7-R，此时对应于坐标的最短距离为266。如图3所示。

图3 配送路径优化算例结果示意图

5 结论

本研究提出了基于有时间窗、单出发点的城市配送车辆配送模式，在对有时间窗的车辆调度问题进行描述的基础上，建立了有时间窗的城市配送路径优化问题的数学模型。利用Lingo软件，对城市配送路径进行优化实证，验证模型的适用性。在约束条件设定上考虑了城市配送路径最短且一定没有回程和空驶。算例以沈阳为例，展示了运用有时间窗的城市配送路径优化模型，计算后从配送中心出发给全市11个点无回程和空驶的配送方案。

[1]李明泽.城市农产品冷链物流配送路径优化研究[D].大连:大连海事大学,2013.

[2]郑国华,周小强,张力敏.基于时间窗的城市医药品动态配送路径优化模型与算法[J].铁道科学与工程学报,2011,(4):80-85.

[3]邓爱民.城市配送系统优化研究[D].武汉:武汉理工大学, 2005.

[4]肖健梅,黄有方,李军军,等.基于离散微粒群优化的物流配送车辆路径问题[J].系统工程,2005,(4):12-15.

[5]吴洁明.物流配送车辆路径优化问题的仿真研究[J].计算机仿真,2011,(7):25-27.

[6]杨锦冬,徐丽群.城市物流中心车辆配送配载调度指派模型研究[J].同济大学学报(自然科学版),2004,(11):13-16.

[7]郝瑞卿,闫莉.军事配送式后勤车辆路径问题研究[J].西安工业大学学报,2015,(1):5-7.

[8]贺政纲,刘沙.城市医疗废弃物回收路径优化研究-以成都市金牛区为例[J].物流技术,2015,(1):34-37.

[9]郎茂样.多配送中心车辆调度问题的模型与算法研究[J].交通运输系统工程与信息,2006,(10):34-36.

[10]Fisher M.Vehicle routing with time windows'two optimization algorithms[J].Operations Research,1997,45(3):48-49.

[11]Laporte G.The vehicle routing problem:An over view of exact and approximate algorithm[J].European Journal of Operational Research,1992,59(3):34-35.

[12]Tailllard E.Parallel interative search method for vehicle routing problem[J].Operations Research Socitey,1994,45(10): 115-116.

[13]钟石泉,贺国光.多车场车辆调度智能优化研究[J].华东交通大学学报,2004,21(6):25-26.

[14]Teo Taniguchi.Evaluation of Urban Distribution Center Using Multiagent Model with Geographic Information Systems[A]. Transportation Research Board 94th Annual Meeting[C].2015.

Optimization of Routing Plan of Urban Distribution Vehicles with Time Window

Lu Ersai,Li Hanqing,Zhao Hui,Wang Shuo
(China Academy of Transportation Sciences,Beijing 100013,China)

In this paper,we proposed the urban distribution mode with time window and single point of departure,then on the basis of a description of the VRP with time window,built the corresponding mathematical model and at the end,used Lingo to verify the applicability of the model in urban distribution route optimization.

urban distribution;route optimization;time window

F252.14;F224.0

A

1005-152X(2016)12-0093-04

10.3969/j.issn.1005-152X.2016.12.022

2016-10-18

卢尔赛（1988-），交通运输部科学研究院工程师，研究方向：物流大数据、物流工程咨询、交通规划；李汉卿，男，北京交通大学管理科学与工程博士，美国马里兰大学物流系访问学者，交通运输部科学研究院助理研究员，中国物流学会特约研究员，IJEI和《交通发展研究》国际国内核心期刊审稿人。