基于FCFS策略的带时间窗车队调度问题研究

轩 华

(郑州大学管理工程学院,郑州450001)

基于FCFS策略的带时间窗车队调度问题研究

轩 华*

(郑州大学管理工程学院,郑州450001)

对货运车辆和运输任务进行科学有效调度,有助于提高资源利用率,实现货物运输科学化.对一类带时间窗的车队调度问题进行分析,建立其数学规划模型.由于传统算法求解该类模型较为困难,为此,设计一类启发式算法.该算法利用FCFS规则进行运输任务和车辆的分配,并为车辆设计一组简单的编号来标记车辆所处的位置和到达节点的时间,通过不断更新车辆标号生成一条条车辆任务发送链,最后形成一整套车队调度方案.实例分析验证了该算法的可行性.

综合交通运输;车队调度;启发式算法;先到先服务;时间窗

1 引 言

运输企业为了最大限度地满足运输网络中不同时段不同地域上所产生的运输任务需求,以达到最少的资源投入获得最优经济效益的目的,需要对所掌握的车队资源进行有效管理.考虑影响实际车队调度工作执行的诸多制约因素,从而制定出合理的车队调度计划是整车和零担货物运输公司、各大物流企业在实际工作中直接面对且亟待解决的难题.

本文研究的带时间窗车队调度优化问题,来源于货物运输行业和物流企业的货物运输组织工作.通过对货运车辆和运输任务的科学有效调度,可以大大提高资源利用率,实现货物运输科学化.同时,对车队调度问题进行研究也是构建高效货物运输组织体系、建立现代调度指挥系统、实现物流集约化和科学化、发展智能交通运输系统的基础与关键.

2 问题的描述

带时间窗的车队调度问题可描述为:运输网络N中各节点处的运输任务分布情况已知,即运输任务l的产生地i∈N,目的地j∈N和服务时间窗均为已知.如果任务l在时间窗内没有分配到车辆,则该任务自动消失[1-6].现有一个车队承担该运输网络上的运输任务,要求制定出该车队的调度方案,使得调用最少的车辆数完成最多的运输任务[1].

国内对货物运输系统优化方面的研究主要集中在车辆路线问题(Vehicle Routing Problem, VRP),而非本文所研究的车队调度问题(Fleet Scheduling Problem).文献[7-11]分别设计了遗传算法、改进遗传算法、禁忌搜索算法、节约里程法和线性规划技术等方法解决不同类型的车辆路线安排问题.

国外对车队调度问题的相关研究多是基于传统数学规划技术(包括线性规划、非线性规划、动态规划等).文献[12]和[13]针对油罐车调度问题分别建立了线性整数规划模型和集划分模型.文献[14]在对动态车队调度问题进行分析的过程中同时考虑了载货车辆和空车,并设计了动态规划模型描述确定性动态车辆调度问题.为了迎合数学规划常规求解算法的需要,通常都对问题进行了简化处理.这种处理方式虽然便于问题的解决,却偏离了车队调度工作的实际情况,从而使得研究成果无法应用于实际工作.而且,基于数学规划理论所建立的模型与设计的求解算法大多不适合大规模问题求解,当车队规模增加时,算法的计算时间将呈指数增加.

鉴于带时间窗车队调度问题的数学模型利用传统数学规划方法难以求解,本文设计出一套基于FCFS策略的启发式算法,该算法利用一套FCFS规则进行运输任务和车辆的分配,同时为车辆设计一组简单的编号来标记车辆所处位置和到达节点时间,并通过不断更新车辆标号生成一条条车辆任务发送链,最后形成一整套车队调度方案,从而使问题得到有效解决.

3 变量表示

为了便于问题的讨论,对问题中所涉及的变量做出如下说明.

3.1 运输网络的表示

G(N,E):运输网络,其中N、E分别表示G中的节点集合和弧集合.

tij:运输网络中车辆从节点i装货出发,运行到节点j并完成卸货的总时间,i,j∈N.

3.2 运输任务的表示

Li:运输网络中节点i处产生的运输任务集合.

l[i,j,t1,t2]:运输网络中节点i处产生的目的地为j的运输任务,其服务时间窗为[t1,t2].显然Li和l[i,j,t1,t2]二者之间存在关系Li=∪j∈Nl[i,j, t1,t2].

3.3 运输车辆的表示

Vi:节点i处的可调配车辆集合.

v[i,t]:在时刻t到达节点i并完成卸货的车辆.显然Vi和vi[t]二者之间存在关系Vi=∪vi[t].

3.4 车辆和运输任务的匹配

v[i,t]{l[i,j,t1,t2]}:时刻t到达节点i处的车辆分配到了一项运输任务l,该运输任务l的时间窗为[t1,t2],目的地为节点j.显然,车辆到达节点i的时刻t要位于运输任务l的时间窗允许范围内[t1, t2],否则该车辆不能承担运输任务l.

3.5 参数

rl:车辆发送运输任务l所能创造的纯利润.

3.6 决策变量

xl′,l:0-1变量,如果车辆装载运输任务l′到达目的地后,在目的节点又装载运输任务l运出,则xl′,l=1；如果车辆装载运输任务l′到达目的地后,在目的节点没有再装载运输任务,则xl′,l=0.

yl:0-1变量,如果车辆装载了运输任务l,到达目的地后没有再装载其他运输任务,则yl=1；如果车辆装载了运输任务l,到达目的地后又装载其他运输任务,则yl=0.

3.7 车辆任务发送链

{l1,l2,…,ls}:表示车辆先后承担了运输任务l1、l2、…、ls-1和ls,共s个运输任务[1,15,16].

显然如果车辆任务发送链为{l1,l2,…,ls},则其所对应的变量值为

yl1=0,xl1,l2=1,xl2,l3=1,…,xls-1,ls=1,yls=1

4 问题的模型

根据上述对车辆调度问题的描述,建立数学模型如下:

问题的目标函数式(1)是为了使车队调度方案所创造的总收益达到最大化.约束条件(2)确保车辆到达节点后或者被安排另一项运输任务或者没有被安排任何运输任务；约束条件(3)确定了初始车辆分配方案,确保每辆车在刚开始至少分配了一项运输任务；约束(4)和(5)保证在同一时刻每项运输任务至多被一辆车运输,一辆车至多只能承担一项运输任务；约束条件(6)确保决策变量xl′,l和yl为0-1变量；约束条件(7)保证车辆任务发送链中的任务数s多于2个时,决策变量xl′,l=1的个数为s-1个.

很明显,上述所建立的问题模型是一个0-1规划模型.对上述模型进行分析可以发现,除了初始各节点运输任务分布情况(Li,i∈N)已知之外,完成这些运输任务所需的车辆数和车辆分布情况(Vi,i∈N)均为未知.而且各运输任务又有不同的时间窗约束l[t1,t2],从而集合Li需要进行及时更新,这也就导致了在解决实际问题时,上述数学模型利用传统数学规划算法很难处理.

5 基于FCFS的启发式算法设计

在前面分析的基础上设计车队调度问题的启发式算法如图1所示.

图1 算法流程图Fig.1 The algorithm flow chart

5.1 初始车辆分布的确定过程

Step 1产生车辆和运输任务的初始匹配.

根据运输任务在路网上的分布情况Li,为每一项运输任务分配一辆车v{l[i,j,t1,t2]}.

Step 2确定初始车辆分布方案.

将车辆标号由v{l[i,j,t1,t2]}形式更新为v[i,t]形式,更新方法如式(8)所示:

从而生成初始车辆分布方案Vj=∪v[j,t].

5.2 运输任务和车辆匹配的更新过程

Step1基于FCFS的运输任务和车辆匹配.

Step 1.1单节点处的任务和车辆分配.

对于单节点处的车辆分配问题,采取简单的先到先服务(FCFS)策略,即先产生的运输任务优先安排车辆:

(1)根据节点i处L个运输任务产生的时刻,按照从早到晚的顺序排列；

(2)根据节点i处V个车辆到达的时刻,按照从早到晚的顺序排列；

(3)从最早产生的运输任务开始,按照车辆到达时刻从早到晚的顺序依次分配车辆,记为v[i, t]{l[i,j,t1,t2]},即时刻t到达节点i处的车辆分配到了一项时间窗为[t1,t2]的运输任务l,要求车辆到达节点i的时刻t必须要位于运输任务l的时间窗允许范围内[t1,t2],即t1≤t≤t2.

Step 1.2记录车辆任务发送链.

(1)记录车辆任务发送链{l1,l2,…,ln},表示车辆先后发送了运输任务l1、l2、…、ln-1、ln.

(2)确定车辆任务发送链所对应的变量值:

①如果车辆承担一项运输任务,即车辆任务发送量为{l1},则所对应的变量值为yl1=1.

②如果车辆仅承担多项运输任务,即车辆任务发送量为{l1,l2,…,ln},按式(9)确定车辆任务发送链所对应的变量值为

Step 1.3记录车辆运输任务集合.

将安排车辆的运输任务l记入已安排车辆的运输任务集合L^i.

Step 2更新车辆分布和未发送运输任务分布.

Step 2.1车辆分布的更新过程.

按照式(10)更新节点i处的车辆集合Vi:

式(10)表示根据运输任务和其分配的车辆,比较车辆的到达时刻t和运输任务l时间窗的起始时间t1,确定车辆的发送时刻为t和t1中较晚的时刻,从而确定车辆到到目的节点j的时刻为min(t, t1)+tij,最终得到下一阶段的车辆分布情况.

Step 2.2未发送运输任务分布的更新过程.

按照式(11)更新未发送运输任务集合Li:

5.3 算法的终止条件设计

Step 1如果未发送运输任务集合Li非空,转5.2节；

Step 2如果未发送运输任务集合Li为空集,则算法停止,记录每辆车的任务发送链,从而得到车队调度方案.

6 实证分析

6.1 实例设计

运输网络由5个节点组成,各节点之间的运行时间为图中边上的权值,如图2所示.

图2 运输网络Fig.2 The transportation network

在运输网络中随机产生了14项运输任务,其中节点1处4项,节点2处3项,节点3处3项,节点4处2项,节点5处2项,运输任务必须在规定的时间窗口内完成,否则运输任务消失.运输任务的具体分布情况如表1所示.

表1 运输任务的分布Table 1 The distribution of transportation task

6.2 算法运行过程

Step 1产生车辆和运输任务的初始匹配.

按照为每一项运输任务分配一个车辆的方法产生初始车辆和运输任务的匹配关系,如表2所示.

Step 2确定初始车辆分布方案.

按式(8)更新节点1-5处的车辆标号,从而得到初始车辆分布方案,如表3所示.

Step 3第一次基于FCFS的运输任务和车辆匹配,如表4所示.

生成车辆的任务发送链={车辆1:l[1,2, 6:00-12:00]；车辆2:l[1,5,9:00-16:00]；车辆3:l[2,1,9:00-12:00]；车辆4:l[2,4,10:00-16:00]；车辆5:l[2,5,12:00-18:00]；车辆6: l[3,5,10:00-18:00]；车辆7:l[3,2,12:00-23:00]；车辆8:l[4,5,9:00-17:00]；车辆9: l[4,3,10:00-15:00]；车辆10:l[5,2,14:00-19:00]；车辆11:l[5,4,15:00-20:00]}.

Step 4第一次更新车辆和未发送运输任务分布.

按式(10)和式(11)更新车辆分布集合Vi和运输任务集合Li,如表5和表6所示.

表2 初始车辆和运输任务的匹配Table 2 The initial matching relation on the vehicle and task

表3 初始车辆分布方案Table 3 The initial distribution of the vehicle

表4 车辆和运输任务的匹配Table 4 The matching on the vehicle and task

表5 当前车辆分布Table 5 The current distribution of the vehicle

表6 未发送的运输任务的分布Table 6 The distribution of the unallocated transportation task

Step 5第二次基于FCFS的运输任务和车辆匹配.

根据车辆分布集合Vi和未发送运输任务集合Li,为运输任务分配车辆如表7所示.

表7 车辆和运输任务的匹配Table 7 The match on the vehicle and task

更新车辆的任务发送链:

车辆3:l[2,1,9:00-12:00]-l[1,3,6:00 -13:00],即x{l[2,1,9:00-12:00],l[1,3,6:00 -13:00]}=1.

车辆9:l[4,3,10:00-15:00]-l[3,1,13:00 -21:00],即x{l[4,3,10:00-15:00],l[3,1,13: 00-21:00]}=1.

Step 6第二次更新车辆和未发送运输任务分布.

更新车辆分布集合Vi和运输任务集合Li如表8和表9所示.

表8 当前车辆分布Table 8 The current distribution of the vehicle

表9 未发送的运输任务的分布Table 9 The distribution of the unallocated transportation task

Step 7第三次基于FCFS的运输任务和车辆匹配.

根据车辆分布集合Vi和运输任务集合Li,为运输任务分配车辆如表10所示.

表10 车辆和运输任务的匹配Table 10 The matching relation on the vehicle and task

更新生成车辆的任务发送链:

车辆9:l[4,3,10:00-15:00]-l[3,1, 13:00-21:00]-l[1,4,10:00-18:00],即

x{l[3,1,13:00-21:00], l[1,4,10:00-18:00]}=1

Step 8第三次更新车辆分布和未发送运输任务分布.

未发送运输任务分布Li为空集.

Step 9算法终止.

因为未发送运输任务分布Li为空集,算法停止,得到车队调度方案如下:

车辆1:l[1,2,6:00-12:00]；车辆2:l[1,5, 9:00-16:00]；车辆3:l[2,1,9:00-12:00]——l[1,3,6:00-13:00]；车辆4:l[2,4,10:00-16:00]；车辆5:l[2,5,12:00-18:00]；车辆6:l [3,5,10:00-18:00]；车辆7:l[3,2,12:00-23:00]；车辆8:l[4,5,9:00-17:00]；车辆9: l[4,3,10:00-15:00]——l[3,1,13:00-21:00]——l[1,4,10:00-18:00]；车辆10:l[5,2,14:00 -19:00]；车辆11:l[5,4,15:00-20:00].

该车队调度方案由11条车辆任务发送链组成,该方案共使用了11辆车.将该方案转变为问题解的形式:

y{l[1,2,6:00-12:00]}=1；y{l[1,5,9:00-16:00]}=1；

y{l[2,1,9:00-12:00]}=0,x{l[2,1,9:00-12:00],l[1,3,6:00-13:00]}=1,y{l[1,3,6:00 -13:00]}=1；

y{l[2,4,10:00-16:00]}=1；y{l[2,5,12:00 -18:00]}=1；y{l[3,5,10:00-18:00]}=1；y{l[3,2,12:00-23:00]}=1；

y{l[4,5,9:00-17:00]}=1；y{l[4,3,10:00 -15:00]}=0,x{l[4,3,10:00-15:00],l[3,1,13:00-21:00]}=1,x{l[3,1,13:00-21:00], l[1,4,10:00-18:00]}=1,

y{l[1,4,10:00-18:00]}=0；y{l[5,2,14:00 -19:00]}=1；y{l[5,4,15:00-20:00]}=1.

6.3 算法的有效性分析

算法针对运输网络中单节点处运输任务和车辆分配问题设计了先到先服务原则,从而确保了各运输任务都能够最大限度地在其时间窗约束要求范围内,分配到所需的车辆.同时,算法通过对每辆车设计一条车辆任务发送链,使得每辆车都能够尽可能地承担多项运输任务,使得车辆的利用率达到最大.

综上所述,本文所设计的基于FCFS策略的求解算法能够有效地解决车队调度问题,不但可以减少车队中车辆的数量,而且可以给出每辆车的具体行车路线、具体安排的运输任务和到达各节点的时间.

7 研究结论

本文对一类带时间窗的车队调度问题进行了分析,建立了其数学规划模型.鉴于数学规划模型利用传统数学规划算法难于求解,设计了一类启发式算法.该算法设计了一套FCFS规则进行运输任务和车辆的分配,同时算法为车辆设计了一组简单的编号来标记车辆所处的位置和到达节点的时间,并通过不断更新车辆标号生成一条条车辆任务发送链,最后形成一整套车辆调度方案.本文最后通过实例验证了算法的可行性.

[1] 轩华,李冰.动态车辆调配问题中的车辆供给变动分析[J].中原工学院学报,2007,18(3):59-63. [XUAN H,LI B.Vehicle supply change analysis of the dynamic vehicle allocation problem[J].Journal of Zhongyuan University of Technology,2007,18(3): 59-63.]

[2] 李冰.动态车队调度问题的模型及优化控制方法研究[M].北京:机械工业出版社,2011.[LI B. Study on the model and optimal control method of the dynamic vehicle allocation problem[M].Beijing: Mechanical Industry Press,2011.]

[3] 李冰.多车型动态车队调度问题的算法设计及求解[J].系统管理学报,2011,20(4):503-509.[LI B. Algorithm for dynamic fleet scheduling with multiple vehicle types[J].Journal of Systems&Management, 2011,20(4):503-509.]

[4] 李冰.随机动态车队管理问题研究[J].系统工程, 2005,23(1):96-101.[LI B.The stochastic dynamic fleet management[J].Systems Engineering,2005,23 (1):96-101.]

[5] 李冰.单车型确定性动态车辆调配问题[J].系统管理学报,2008(3):353-360.[LI B.Research on the deterministic dynamic vehicle allocation problem with homogeneous vehicle type[J].Journal of Systems &Management,2008(3):353-360.]

[6] 李冰,郝越,轩华.基于排队网络的运输排队过程研究[J].重庆交通大学学报,2012,31(4):293-298 [LI B,HAO Y,XUAN H.Transportation queuing processes research based on queuing network[J]. Journal of Chongqing Jiaotong University,2012,31 (4):293-298.]

[7] 宋伟刚,张宏霞,佟玲.有时间窗约束非满载车辆调度问题的遗传算法[J].系统仿真学报,2005,17 (11):2593-2597.[SONG W G,ZHAGN H X, TONG L.Genetic algorithm for VRP of non-full loads with time windows[J].Acta Simulata Systematica Sinica,2005,17(11):2593-2597.]

[8] 黄瑞铭.配送时间窗约束下车辆调度遗传算法研究[J].物流科技,2011,4:116-119.[HUANG R M. Research on the genetic algorithm for vehicle routing problem with delivery time windows[J].Logistics Sci-Tech,2011,4:116-119.]

[9] 钟时泉,杜纲,贺国光.有顾客时间窗和发货量变化的紧急车辆调度研究[J].管理工程学报,2007, 21(4):114-118.[ZHONG S Q,DU G,HE G G. Study on urgency vehicle scheduling problem with the changes oftime windows and delivery weight of customers[J].Journal of Industrial Engineering and Engineering Management,2007,21(4):114-118.]

[10] 王雷.用节约法解带有时间窗的车辆调度问题[J].黑龙江工程学院学报(自然科学学报),2011, 25(3):18-20.[WANG L.Saving algorithm for VRP of with time windows[J].Journal of Heilongjiang Institute of Technology,2011,25(3):18-20.]

[11] 霍佳震,张磊.用节约法解决带有时间窗的满载车辆调度问题[J].工业工程与管理,2006,4:39-49. [HUO J Z,ZHAGN L.Savings based algorithm for full truckload vehicle routing problem with time window [J].Industrial Engineering and Management,2006, 4:39-49.][12] Brown G,Graves G.Real-time dispatch of petroleum tank trucks[J].Management Science,1981,27: 19-32.

[13] Bell W,Delbert M,Fisher M,et al.Improving the distributionofindustrialgaseswithanonline computerized routing and scheduling optimizer[J]. Interfaces,1983,13:4-23.

[14] Powell W B,Carvalho T A,Godfrey G,et al. Dynamic fleet management as a logistics queueing network[J].Annal Operation Research,1998,61: 168-188.

[15] 李冰.多车型确定性动态车辆调配问题[J].管理工程学报,2006,20(3):52-56.[LI B.The determinitic dynamic vehicle allocation problem with multiple vehicletype[J].JournalofIndustrial Engineering and Engineering Management,2006,20 (3):52-56.]

[16] Powell W B,Wayne Snow,Raymond K Cheung. Adaptivelabelingalgorithmsforthedynamic assignmentproblem[J].TransportationScience, 2000,34(1):50-66.

Fleet Scheduling Problem with Time Windows Based on FCFS Strategy

XUAN Hua
(School of Management Engineering,Zhengzhou University,Zhengzhou 450001,China)

It helps improve resource utilization and realize scientific transportation to schedule freight vehicle and transportation tasks effectively.A fleet scheduling problem with time windows is analyzed,and then formulated as a mathematical programming model.A heuristic algorithm is designed because of it is difficult to solve the model using traditional algorithms,where the vehicle is assigned to the transportation tasks using FCFS method.The vehicle label is devised to represent the location and the arrival time of the vehicle.A sub-tour is devised to contain a sequence of chained vehicle-task assignment.Finally,the fleet scheduling solution is proposed.A case validates the feasibility of this algorithm.

integrated transportation；fleet scheduling；heuristic algorithms；first come first served；time windows

U492.312；F542

A

U492.312；F542

A

1009-6744(2013)06-0140-08

2013-04-11

2013-06-10录用日期:2013-06-20

国家自然科学基金(71001091,71001090)；中国博士后科学基金面上资助项目(2013M531683).

轩华(1979-),女,河南睢县人,副教授,工学博士.

*通讯作者:hxuan@zzu.edu.cn