车队动态调度优化模型与算法研究
详细信息    本馆镜像全文|  推荐本文 |  |   获取CNKI官网全文
摘要
目前我国道路运输企业普遍面临着货源不足、车辆闲置率和空载率较大等问题,如何提高自身的管理水平和运输组织的科学性、有效地调配车辆、降低企业的物流成本、增加核心竞争力已成为道路运输企业急需解决的问题。其中车队调度是影响道路运输企业运营质量的重要因素之一,也是本文的研究重点。
     首先,本文在分析总结目前国内外车队动态调度研究成果的基础上,采用多阶段决策的思想和动态规划方法对车辆调配形式、影响调度的因素以及调度流程进行了系统分析,并将整个服务周期划分为若干个任务时段,从优化任务发运计划的角度入手,对单个任务时段,分别建立了单车型、多车型车队动态调度模型。
     其次,利用遗传算法分别对单车型、多车型车队动态调度模型进行求解。同时,为提高算法解的质量和计算速度,利用多线程技术设计了模拟分布式遗传算法,并探讨了相应的子群体划分策略、信息交换模型和信息交换频率。仿真实验结果表明,在计算时间方面,模拟分布式遗传算法的计算时间比标准算法提高了1倍,解的质量也优于标准遗传算法,并在处理较大规模数据时具有明显优势。
     然后,在单时段车队调度的基础上,本文进一步提出了综合滚动调度算法,分析了影响滚动调度的主要因素,设计了相应的滚动时域窗口和调整策略。
     最后,利用VB和C++语言联合开发了车队动态调度优化仿真平台,并以山东某快运企业真实数据为测试数据,分别测试了标准遗传算法与模拟分布式遗传算法的性能、不同计划长度对调度结果的影响以及综合滚动调度算法得到的整个服务周期的车辆平均空载率。仿真结果中,本文所设计的综合滚动调度方法在控制车辆平均空载率上优于社会货运平均空载率5.26%。由此也表明了此方法高效、实用,具有重要的实际应用价值。
The road freight enterprises face the severe questions of deficient freight sources, the higher empty-loading ratio of vehicles. How to improve their managing level, to organize and schedule vehicle effectively, to low the running cost of the enterprises and strengthen core advantages has been an urge problem to governors of road transport. And the fleet scheduling management is a very important factor which can impact the quality of operating management of road freight enterprises, which also is the studying emphasis of the paper.
    Firstly, the paper makes use of Multi-Phased Decision and Dynamic Programming theory systemically analyzes the scheduling forms of fleet and the factors which affect the scheduling, and also analyzes the whole scheduling process at the basement of at the basement of analyzing the studying production of the dynamic fleet scheduling both here and abroad. After these works done, the whole serving cycle is divided to many periods, and the paper designs relevant dynamic scheduling models aim to the fleets which own single vehicle-type or multiple types in the sense of making optimize the mission plan as a breakthrough.
    Secondly, the paper also designs corresponding genetic algorithm to get the results. At the same time, the paper utilizes the Mock Distributed-Genetic Algorithms which design relevant dividing-strategy of the sub-colony, the commutative information model and the commutative information frequency in order to improve the efficiency and evolving quality of the algorithm. The simulated experiment indicates that the calculative speed of the Mock Distributed-Genetic Algorithm is a/one half of the standard Genetic Algorithm. And the quality of results also is superior to the standard one.
    Successively, the paper farther brings forward the rolling horizon scheduling algorithm for the dynamic fleet scheduling management, and analyzes the main factors which affect the rolling horizon scheduling and designs the relevant the relevant rolling horizon procedure and the adjustive strategy after dealing with the fleet scheduling management at the single-period, for dealing with the missions which appear in the whole periods at random.
    At last, the paper develops a simulated platform for the rolling horizon scheduling of the dynamic fleet management with the computer technologies of VB and c++ languages. And the paper also does the experiment of testing the performances both the standard genetic algorithm and the mock-distributed genetic algorithm and the experiment of testing the influence of the scheduling at the conditions of different lengths of the mission plan and the experiment of testing the empty-load ratio of the fleet at the whole periods with using the rolling horizon scheduling. The results of experiments prove that the rolling horizon scheduling algorithm in this paper reduce more 5.26% at the empty-loading ratio of vehicle than the social average empty-loading ratio. So the results can prove that the algorithms in the paper is effective and practicable, owning the important value for actual applications.
引文
[1] 国家统计局编.中国(91)统计年鉴[G].北京:中国统计出版社,515p
    [2] 邹生.信息技术在物流业中的应用[N].《人民日报.华南新闻》 (2002年12月13日第三版)
    [3] 荣朝和编著.西方运输经济学[M].北京:经济科学出版社 2002
    [4] 2006年3季度中国物流行业分析报告[R].中国物流与采购网(www.cflp.org.cn)2006年11月
    [5] 李冰.动态车队管理问题的模型及算法研究[D].西南交通大学博士论文,2003.11.01
    [6] DantzigG, Fulkerson D.. Minimizing the number of tankers to meet a fixed schedule[J]. Naval Research Logistics, 1954, 1: 217~222
    [7] Warren B. Powell, Tassio A. Carvalho. Dynamic Control of Multieommodity Fleet Management Problems[J]. Department of Civil Engineering and Operation Research Princeton University Princeton September 25, 1996
    [8] Tassio A. Carvalho, Warren B. Powell. A Multiplier Adjustment Method for Dynamic Resource Allocation Problems[D]. Department of Civil Engineering and Operation Research Princeton University Princeton, May 2000
    [9] Warren B. Powell, Tassio A. Carvalho. Dynamic Control of Logistics Queueing Networks for Large-Scale Fleet Management[D]. Department of Civil Engineering and Operation Research Princeton University Princeton, February, 1998
    [10] W. W. White and A. M. Bomberault A network algorithm for empty freight car allocation[J]. FREIGHT CAR ALLOCATION, 1969 No. 2: 147~168
    [11] Beaujon George J, Turnquist Mark. A Model for fleet sizing and vehicle allocation[J]. Transportation Science, 1991 1(25): 19~45
    [12] Joborn M.. Empty freight car distribution at Swedish railways-analysis and optimization modeling[D]. Ph. D. thesis, Department of Mathematics, Linkoping University, Sweden, 1995
    [13] Jordan W., TurnquistM.. A stochastic dynamic network model for railroad cardistribution[J]. Transportation Science, 1983, 17: 123~141
    [14] Powell W B. An Operational Planning Model for the Dynamic Vehicle Allocation Problem with Uncertain Demands[J]. Transportation Research, 1987, 21B: 217~232
    [15] Frantzeskakis Linos F, Powell Warren B. Successive linear approximation procedure for stochastic, dynamic vehicle[J]. Transportation Science, 1990 1(24): 40~57
    [16] Warren B. Powell, Tassio A. Carvalho. Real-Time Optimization of Containers and Flatcars for Intermodal Operations[D]. Department of Civil Engineering and Operation Research Princeton University Princeton February, 1998
    [17] Gregory A. Godfrey, Warren B. Powell. An Adaptive Dynamic Programming Algorithm for Dynamic Fleet Management[J]. Period Travel Times Transportation Science 2002 2 (36): 21~39
    [18] Martin Joborn, Teodor Gabriel Crainic, Michel Gendreau. Economies of Scale in Empty Freight Car Distribution in Scheduled Railways[J]. TRANSPORTATION SCIENCE, 2004 2 (38): 121~134
    [19] 郭耀煌,李军.满载问题的车辆路线安排[J].系统工程学报1995,10(2):106~118
    [20] 谢秉磊,李军,郭耀煌.遗传算法在非满载车辆线路安排问题中的应用[J].中国学术期 刊,1999,5(8):1068~1069
    [21] 邓薇.带时间窗的车辆路线问题及算法研究[D].武汉大学硕士学位论文,20050420
    [22] 王新华.带时间窗的车辆路线问题研究[D].同济大学硕士学位论文,20051201
    [23] 李军,郭耀煌.物流配送——车辆优化调度理论与方法研究[M].中国物资出版社,2001
    [24] 隆颖.带回程取货的车辆路径若干问题研究[D].东北大学硕士学位论文,20050801
    [25] 刘云霞.动态车辆调度问题分析及算法设计[D].西南交通大学硕士论文,2004.02.01
    [26] 肖增敏.动态网络车辆路径问题研究[D].西南交通大学硕士论文,2005.03.01
    [27] 夏静,许炜,杨琪.物资动态资源变化问题初探[J].物流技术,2002 7:34~36
    [28] 张喜.铁路空车调整综合优化模型与智能决策方法的研究[D].北京交通大学硕士学位论文,20041001
    [29] 许成铁.铁路空车调配模型及应用研究[D].北京交通大学硕士学位论文,20050601
    [30] 谭云江.路网节点间空车调配模型与算法研究[D].西南交通大学硕士学位论文,20060301
    [31] 叶建勇.航班调度信息管理系统技术研究与实现[D].电子科技大学硕士学位论文,20030513
    [32] 蔡毓峰.航班进离港过程优化调度的仿真研究[D].中国民用航空学院,2005.01.05
    [33] 刘云霞.航班进离港调度的模糊优化[D].中国民用航空学院,20060214
    [34] 陈志红主编.运输组织技术[M].北京:人民交通出版社,2003
    [35] 朱隆亮,谭任绩主编.物流运输组织管理[M].北京:机械工业出版社,2003
    [36] 张建伟编著.物流运输业务管理模板与岗位操作流程[M].北京:中国经济出版社,2005
    [37] 李敏强等著.遗传算法的基本理论与应用[M].北京:科学出版社,2002
    [38] Nithya Gnanapandithan, Balasubramaniam Natarajan Parallel Genetic Algorithm based Optimal Fusion in Sensor Networks[J]. Department of Electrical and Computer Engineering Kansas State University IEEE, 2005. 5. 04: 767
    [39] 占书芳.并行遗传算法在带软时间窗车辆路径问题中的应用研究[M].武汉理工大学硕士论文,20060401
    [40] 高睿.混合分布式并行遗传算法的研究与应用[D].电子科技大学硕士论文,2006.1
    [41] 孟凡宇.一种改进的遗传算法在TSP问题中的应用研究[D].辽宁工程技术大学硕士论文,2005.12
    [42] 盛倩蓉.基于改进遗传算法的车辆路径问题研究[D].武汉理工大学硕士论文,2006.5
    [43] 张文修,梁怡编著.遗传算法的数学基础[M].西安交通大学出版社,2000
    [44] 赖鑫生.迁移策略与多群体并行遗传算法的性能[D].贵州大学硕士论文,2004.5
    [45] 邹谷山.运输调度问题的遗传算法研究[M].广东工业大学硕士论文,2005.04
    [46] 杨艳丽,史维祥.一种新的优化算法——遗传算法的设计[J].液压气动与密封,2001年第2期:13~15
    [47] 徐玖平,胡知能,王矮编著.运筹学[M].北京:科学出版社,2004
    [48] 马振华主编.现代应用数学手册—运筹学与最优化理论[M].北京-清华大学出版社,1998-2005
    [49] 周溪召等编著.物流系统工程[M].上海:上海财经大学出版社,2003
    [50] 熊玲.基于动态规划的公交车调度问题的研究[D].湖北工业大学硕士论文,2005.05.01
    [51] Leslie A. Poch and R. T. Jenkins. Dynamic programming models[J]. Environmental Assessment and Information Sciences Division Argonne National Laboratory School of Engineering, University of Tennessee U.S.A, 2003.8
    [52] 邓先礼.最优化技术与应用[M].重庆:重庆大学出版社,2001:47~55
    [53] John J. Murray, Chadwick J. COX, George G. Lendaris. Adaptive Dynamic Programming[J]. IEEE TRANSACTIONS ON SYSTEMS, MAN, AND CYBERNETICS—PART C: APPLICATIONS AND REVIEWS, 2002 2(32): 140~153
    [54] S.-L. Chung, F. B. Hanson. Optimization Techniques For Stochastic Dynamic Programming[D]. Department of Mathematics, Statistics, and Computer Science University of Illinois at Chicago, 1990. 12
    [55] 汤子瀛,哲凤屏,汤小丹著.计算机操作系统[M].西安:西安电子科技大学出版社,2000
    [56] 王险峰,刘宝宏编著.Windows环境下的多线程编程原理与应用[M].北京:清华大学出版社,2002
    [57] 郑健.线程—简述线程概述及原理.http://blog.csdn.net/chengking 2005.11.30
    [58] 贾永基.车辆调度问题优化算法研究[D].上海交通大学博士学位论文,2004.12
    [59] 王冰.静态单机调度问题改善全局性能的滚动策略[J].系统工程学报,2005 20(3):308~311
    [60] 席裕庚.动态不确定环境下广义控制问题的预测控制[J].控制理论与应用,2000,17(5):665~667
    [61] 欧美道路运输业的节约“内功”[N].运输经理世界(http://www.cntransnet.com),2006-7-24
    [62] 荆林波.关于外资进入中国物流产业的状况分析[N].第十一次中国物流专家论坛(http://www.chinawuliu.com.cn),2006-1-13
    [63] 张浩.车辆动态安全监控管理的现状与发展方向[N].北京安防协会(http://www.bspia.com),2006-2-4

© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号

地址:北京市海淀区学院路29号 邮编:100083

电话:办公室:(+86 10)66554848;文献借阅、咨询服务、科技查新:66554700