多顺序时段批量批次车辆调度方法研究*

吴传良，何叶荣，王建华(淮南师范学院经济与管理学院，安徽淮南232038)

多顺序时段批量批次车辆调度方法研究*

吴传良，何叶荣，王建华
(淮南师范学院经济与管理学院，安徽淮南232038)

摘要:多顺序时段批量批次的车辆调度问题就是通过对车辆进行有计划、科学、准确的调度以达到降低物流成本的目的;首先，针对多顺序时段内变化的速度，采用线性最小二乘拟合方法将变化的速度量化;其次，在加入时间窗约束、容量约束的基础之上构建了多顺序时段批量批次货物运输的车辆调度的数学模型;最后，针对基本蚁群算法进行相关改进，并进行了案例仿真分析。

关键词:多顺序时段;车辆调度;蚁群算法

运输是物流中一个直接与消费者相连的环节，也是物流公司成本的重要组成部分，据中国物流与采购联合会2011年相关统计数据显示:运输费用占物流费用的53%左右。而对于车辆调度方法的研究可以均衡物流企业与消费者之间的利益，从而实现物流科学化。车辆调度问题(Vehicle Scheduling Problem，VSP)是在1959年由Dantzig和Ramser提出的［1］，对车辆调度问题的理论与方法进行系统研究是物流集约化发展、构建综合物流系统、建立现代调度指挥系统、发展智能交通运输系统和开展电子商务的基础。车辆运输调度问题应用前景广阔，已经广泛用于生产、生活的各个方面，如报纸或货物投递、垃圾车路线优化和包裹快递等。

对于这种NP难题，多顺序时段货物运输的车辆调度比一般的车辆调度问题更加复杂。目前，在国内外有很多学者在不同的的车辆调度问题上取得了一定的成果。Laporte和Nobert［2］等人探讨了带距离和容量限制的车辆优化调度问题; Taillard等人［3］利用禁忌搜索和模拟退火算法，实现了求解车辆调度问题的并行化。在国内，郎茂祥［4］对于车辆调度问题的研究可谓颇深，在其出版的《配送车辆优化调度模型与算法》一书中，详细阐述了当配送车辆优化调度的约束条件(如容量、时间窗、车型、多车场、发车时间等)不同时，其对应的数学模型及其优化算法。

1　多顺序时段批量批次货物车辆调度问题的描述及构建数学模型

1.1问题的描述

研究的多顺序时段批量批次货物运输的车辆调度问题所涉及的约束条件主要有:交通流量(即变化的车速)、车辆容量、货物需求量、货物需求时间窗以及服务时间等。它可以描述为:货物运输是由1个配送点，n个需求点组成，在货物运输过程中，其路径上交通流量是不断变化的，每个需求点的需求量为gi，每辆车限定容量为q，每个需求点有时间窗要求并且服务时间已经确定。

1.2多顺序时段批量批次货物运输的车辆调度的数学模型

主要通过对车辆调度约束条件的描述构建课题的数学模型。

1.2.1多顺序时段内车辆速度的量化处理

传统的车辆调度问题是基于理想状态下进行优化的，在建模时忽略了每个顺序时段内的不稳定因素，以至于现有多数优化方法以及模型的建立的前提是车辆速度恒定。而每个顺序时段情况不同都会对车辆速度产生影响，如早上班、晚下班高峰期车辆的速度较慢，据有关统计在北京奥运会期间实行单双号限行后，车流量降低27%左右，而车速也提高了相应的比例，也就是说在货物运输中配送车辆速度在一天不同时段处于动态变化并与车流量成反比。

由于动态变化的速度会增加车辆调度问题的复杂程度，拟采用将变化的速度量化并结合现有车辆调度算法进行课题的研究。将变化的速度量化的步骤为:首先对配送区域内配送需求点之间的路径上的车流量进行统计;然后将数据转换为车速数据，利用曲线拟合思想并通过Matlab实现车辆速度与时间函数的建立;最后将变化的速度量化，主要思想是通过对局部点进行逐步曲线拟合，用定积分的思想进行求解在多顺序时段内的总路程，再除以总时间即是多顺序时段内的平均速度。公式如下:

其中n表示时间段总间隔时间，例如:8∶00－17∶00则时间间隔为11 h; t =［n/m］+ 1; m为设定的小段时间间隔; f(x)为小段时间间隔内利用线性最小二乘法拟合出的速度关于时间的函数。

1.2.2多顺序时段批量批次货物运输车辆调度数学模型的建立

在建立多顺序时段批量批次货物运输车辆调度的数学模型之前，需要做假设:配送中心和配送点的位置坐标已知;配送车辆车型为同种车型，并且最大载重量已知;配送点需求量已知;配送点要求的时间窗已知;每个客户必须只能访问一次且必须满足每个客户的配送需求;配送主要路段车流量已知。

数学模型的决策变量和参数定义:配送中心编号为0，客户点为1，2，…，n，车辆数为m; Dij表示各配送中心之间的距离;表示已通过上文提出的方法将变化的速度量化后的速度(常数); w1表示单位距离车辆所耗费的成本; xijk=0或1，当其为1时表示车辆k由客户点i(或配送中心)开往客户点j(或配送中心); yki=0或1，当其为1时表示客户点i的任务由车辆k完成; si为车辆在客户点i的服务时间; gi为客户点i的需求量;时间窗为［aj，bj］，车辆到达客户j时间为Tj，e和f时间窗惩罚系数。

建立数学模型为［5，6］

式(3)表示车辆k所承担的客户总需求不大于车装载最大容量;式(4)表示任务i只能由一辆车完成; 式(5)－(8)表示到达和离开某一客户点的车辆只有一辆;式(9)和(10)表示时间窗约束;车辆数m可以根据式进行估计，其中［］表示取整，μ为参数且在［0，1］之间表示装卸车复杂程度以及约束多少的估计，一般μ取值为0.85。

2　多顺序时段批量批次货物车辆调度算法的设计

2.1改进的蚁群算法［7，8］

(1)局部最优搜索策略。蚁群算法容易出现早熟停滞等现象，即搜索过程达到一定迭代次数后，对解的空间不再进行进一步搜索，这样不利于发现最优解。针对这种情况，采用2－opt策略，其原理就是对每次迭代产生的最优解进行相邻边的交换，这样以来更加容易寻找到最优解。2－opt必须满足的一个条件就是相邻边交换后路径总长度减小，即:

(2)参数α的改进。在基本蚁群算法中，蚁群在搜索的过程中很容易出现过早收敛和停滞现象，认为在搜索过程中，由于信息素不断累积，加强了局部路径的重要性，使得蚁群过早收敛陷入局部最优解，不再探索新的路径。但是若使信息素启发因子α在一定的迭代次数范围内是一个增函数，也就是说在迭代的过程中适当信息素积累量是一个逐步慢慢累加的过程而不是迅速积累的过程，这样更有利于寻找到更好的路径。

通过上述分析提出了信息素启发因子α与迭代次数之间的一个增函数:

其中a＞1，Nc为迭代次数，n为常数。信息素启发因子α与迭代次数函数图形形状(图1):α(Nc)是一个指数函数，初始时，信息素启发因子α较小，蚁群在逐步搜索更广阔的区域，但随着迭代次数的增加，信息量达到一定程度后，几乎无法在进行最优解的探索，此时Nc=n，当Nc＞n时，蚁群快速收敛。

图1　改进蚁群算法路径优化结果

2.2算法步骤

Step1:初始化参数，读取配送中心和客户点坐标以及其他数据，另外设置全局参数;

Step2:构造时间窗惩罚函数;

Step3:将m只蚂蚁均匀的放在配送中心节点上，初始时间t=0和迭代次数Nc=0，建立禁忌表;

Step4:对于每一只蚂蚁，从客户点列表中寻找没有走到的点，并按照改进后的状态转移概率公式选择下一个客户节点j;

Step5:累加路径(i，j)的货运量得到q，若q大于车辆最大载重Q，那么就跳转到下一步;若q小于车辆最大载重Q，则将其加入可行点集;

Step6:生成最优路径并应用2－opt方法对最优解进行更新;

Step7:对每只蚂蚁所走过的路径的局部信息素和信息素增量进行更新;

Step8:如果迭代次数达到最大或者找到全局最优路径，程序结束，否则，清空禁忌表，返回步骤4，并且重复上述步骤。

3　仿真分析

以上通过详细分析，构建了多顺序时段批量批次货物运输的数学模型，并设计出一种新的蚁群算法。现将运用以上介绍的知识进行案例仿真。仿真数据由Matlab 7.0软件随机生成。

3.1量化变化的速度

物流配送时间段一般在早7:00－18:00，在进行车流量统计之前，需要制定相关表格，并且确定车流量统计时间间隔，借助Matlab随机生成以下数据，时间间隔确定为30 min，具体数据见表1。

首先将上述22个时间段分成7个时间段，对这六类时间段逐一进行线性最小二乘拟合。

通过直观判断可以假设每一类的函数都满足于g(x) = a+bx2，下面就以第一类数据为例，通过Matlab 7.0编程得到第一类顺序时段速度与时间的函数为

将程序中数据改变得到其他几类函数分别为

通过求解得到V =40.06。将不探讨车辆在特殊顺序时段内的配送，故路径优化时速度取值为V =40。

3.2配送路径生成

通过Matlab随机生成客户点坐标以及客户点服务时间及时间窗要求，假设车辆最大载重量为4 t，详见表2。利用MATLAB 7.6.0语言工具实现编程，各参数设置为:γ= 5，m = 15，ρ= 0.5，Q = 100，NC = 200，W = 4 000。随机运行10次，运行结果见表3:

表1　多顺序时段车流量

表2　各配送区域点的坐标位置、货物的需求量及服务时间

表3　改进蚁群算法计算结果

表3中大多数目标函数值都是相同数值，则利用改进后蚁群算法求得的最优解为386.27，路径如图1所示。

车辆1－6改进蚁群算法下的最优路径依次为:0-14-9-2; 0-18-8-11-0; 0-6-17-7-0; 0-12-15-4; 0-1-15-13; 0-3-16-10。改进后的蚁群算法较平稳，不容易陷入局部最优解，且收敛速度相对于基本蚁群算法并没有放慢许多。

4　结语

主要研究多顺序时段批量批次货物运输的车辆调度问题。首先，借助于线性最小二乘拟合思想以及相关数学知识并结合matlab编程对多顺序时段内变化的速度进行了量化。其次，通过建立时间窗惩罚函数将时间成本量化，在满足客户需求点的需求量大小及时间窗等约束条件的前提下，构建了多顺序时段批量批次货物运输的车辆调度的数学模型。最后，针对车辆调度实际问题进行了蚁群算法的改进，通过仿真分析，改进后的蚁群算法收敛速度平稳，且容易寻找到最优解。

目前，对于车辆问题的研究仍处于探索阶段，故研究工作尚存在不足，例如:车辆调度问题不仅仅是车辆路径的优化，其包括货物配装、人员安排等，现只研究了车辆路径的优化;同时，将多顺序时段内不断变化速度量化并不是最好的优化思想，而应建立一种随时间变化而变化的速度模型，这更有利于寻找到最优路径。

参考文献:

［1］DANTZIT G B，RAMSER R H.The Truck Dispatching Problem［J］.Management Science，1959(4):1128-1131

［2］LAPORTE G，NOBERT Y，DESROEHERS M.Optimal Routing with Capacity and Distance Restrictions［J］.Operations Research，1985(4):1050-1073

［3］TAILLARD E.Parallel Interactive Search Method for Vehicle Routing Problem［J］.Networks，1993，23:661-673

［4］郎茂祥.配送车辆优化调度模型与算法［M］.北京:电子工业出版社，2009

［5］李琳，刘士新，唐加福.改进的蚁群算法求解带时间窗的车辆路径问题［J］.控制与决策，2010，25(9):1379-1382

［6］李秀娟，杨玥.蚁群优化算法在物流车辆调度系统中的应用［J］.计算机工程与应用，2013，33(10):2822-2826

［7］吴洁明.物流配送车辆路径优化问题的仿真研究［J］.计算机仿真，2011，28(7):357-360

［8］潘斌斌.多目标路径规划问题的算法综述［J］.重庆工商大学学报:自然科学版，2012，29(5):78-81

Research on the Vehicle Scheduling Method with
Multiple Sequential Time and Batch

WU Chuan-liang1，HE Ye-rong1，WANG Jian-hua1
(School of Economic and Management，Huainan Normal University，Huainan 232038，China)

Abstract:Through plan，scientific and accurate scheduling，scheduling vehicle with multiple sequential time and batch is to achieve the purpose of reducing logistics cost.Firstly，according to multiple sequential period change speed，this paper adopts the linear least squares method to change speed quantization.Secondly，adding time window constraints，capacity constraint，this paper construct good vehicle scheduling model of smultiple sequential time and batch.Finally，according to the basic ant algorithm，the model is improved and simulated.

Key words:multiple sequential time; vehicle scheduling; ant algorithm

中图分类号:C931

文献标识码:A

文章编号:1672－058X(2015) 08－0038－06

doi:10.16055/j.issn.1672－058X.2015.0008.009

收稿日期:2014－10－26;修回日期:2014－12－10.

*基金项目:国家自然科学基金资助(51374114).

作者简介:吴传良(1989-)，男，安徽六安人，硕士，从事物流与供应链管理研究.