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

交通运输系统工程与信息 ›› 2013, Vol. 13 ›› Issue (6): 140-146.

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

轩华^*

郑州大学管理工程学院，郑州 450001

收稿日期:2013-04-11 修回日期:2013-06-10 出版日期:2013-12-24 发布日期:2014-01-14
作者简介:轩华（1979-），女，河南睢县人，副教授，工学博士.
基金资助:
国家自然科学基金（71001091，71001090）；中国博士后科学基金面上资助项目（2013M531683）.

Fleet Scheduling Problem with Time Windows Based on FCFS Strategy XUAN Hua

XUAN Hua

School of Management Engineering, Zhengzhou University, Zhengzhou 450001, China

Received:2013-04-11 Revised:2013-06-10 Online:2013-12-24 Published:2014-01-14

摘要/Abstract

摘要：

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

关键词: 综合交通运输, 车队调度, 启发式算法, 先到先服务, 时间窗

Abstract:

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.

Key words: integrated transportation, fleet scheduling, heuristic algorithms, first come first served, time windows

中图分类号:

轩华. 基于FCFS策略的带时间窗车队调度问题研究[J]. 交通运输系统工程与信息, 2013, 13(6): 140-146.

XUAN Hua. Fleet Scheduling Problem with Time Windows Based on FCFS Strategy XUAN Hua[J]. Journal of Transportation Systems Engineering and Information Technology, 2013, 13(6): 140-146.

导出引用管理器 EndNote|Ris|BibTeX

链接本文: http://www.tseit.org.cn/CN/abstract/abstract18691.shtml

http://www.tseit.org.cn/CN/Y2013/V13/I6/140

参考文献

[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 of time 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 distribution of industrial gases with an online 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 vehicle type[J]. Journal of Industrial Engineering and Engineering Management，2006，20(3)：52-56.]

[16]Powell W B, Wayne Snow, Raymond K Cheung. Adaptive labeling algorithms for the dynamic assignment problem[J]. Transportation Science, 2000, 34(1): 50-66.