基于近似动态规划的动态车辆调度算法

中国机械工程 ›› 2015, Vol. 26 ›› Issue (5): 682-688.

基于近似动态规划的动态车辆调度算法

李雪;聂兰顺;齐文艳;战德臣

哈尔滨工业大学，哈尔滨，150001

出版日期:2015-03-10 发布日期:2015-03-06
基金资助:
国家自然科学基金资助项目(61273038)；国家科技支撑计划资助项目(2013BAH17F03)；国家重点基础研究发展计划(973计划)资助项目(2010CB328004)；山东省自主创新成果转化重大专项(2012ZH1A0411)

An Algorithm of Dynamic Vehicle Scheduling Problem Based on Approximate Dynamic Programming

Li Xue;Nie Lanshun;Qi Wenyan;Zhan Dechen

Harbin Institute of Technology,Harbin,150001

Online:2015-03-10 Published:2015-03-06
Supported by:
National Natural Science Foundation of China（No. 61273038）;The National Key Technology R&D Program（No. 2013BAH17F03）;National Program on Key Basic Research Project (973 Program)（No. 2010CB328004）

摘要/Abstract

摘要：

针对物流配送服务业中，车辆调度问题日渐呈现任务规模大，车辆类型多、属性多，调度实时性要求越来越高等特点，提出了基于近似动态规划的动态车辆调度算法。根据当前的任务需求与车辆状态以及相应的约束条件作出相应的调度，并且对一些样本进行训练，得到了一个近似价值函数。通过该价值函数，即可对任务迅速作出相应的决策。仿真模拟实验证明了该算法的有效性和优越性。

关键词: 服务资源, 近似动态规划, 动态调度, 价值函数

Abstract:

Vehicle scheduling in service industry of logistics distribution was presenting features including the tasks tended to be of large scale, vehicles were multi-type and had multiple attributes as well as high demands for real-time scheduling. To solve these problems, this paper proposed a dynamic vehicle scheduling algorithm based on the approximate dynamic programming. An approximate value function was obtained through training of some samples, and according to mission requirements, vehicle state and conditions, and quick scheduling decisions could be made with the value function. The simulation test has proved the correctness and effectiveness of the algorithm.

Key words: service resource, approximate dynamic programming, dynamic scheduling, value function

中图分类号:

TP311.52

李雪, 聂兰顺, 齐文艳, 战德臣. 基于近似动态规划的动态车辆调度算法[J]. 中国机械工程, 2015, 26(5): 682-688.

Li Xue, Nie Lanshun, Qi Wenyan, Zhan Dechen. An Algorithm of Dynamic Vehicle Scheduling Problem Based on Approximate Dynamic Programming[J]. China Mechanical Engineering, 2015, 26(5): 682-688.

参考文献

[1]Gendreau M,Potvin J Y. Dynamic Vehicle Routing and Dispatching[J]. Fleet Management and Logistics,1998:115-126.
[2]Powell W B. Stochastic and Dynamic Networks and Routing[J]. Department of Civil Engineering and Operations Research, Program in Statistics & Operations Research, 1995,8:141-295.
[3]Minkoff A S. A Markov Decision Model and Decomposition Heuristic for Dynamic Vehicle Dispatching[J]. Operations Research, 1993,41:77-90.
[4]张景玲，赵燕伟，王海燕，等. 多车型动态需求车辆路径问题建模及优化[J].计算机集成制造系统，2010,16(3):544-550.
Zhang Jingling,Zhao Yanwei, Wang Haiyan, et al. Modeling and Algorithms for a Dynamic Multi-vehicle Routing Problem with Customers’ Dynamic Requests[J].Computer Integrated Manufacturing Systems, 2010,16(3):544-550.
[5]王旭，葛显龙，代应. 多车型动态需求车辆路径问题建模及优化[J].控制与决策，2012，27（2）：175-181.
Wang Xu, Ge Xianlong, Dai Ying,Research on Dynamic Vehicle Routing Problem Based on Two-phased Algorithm[J]. Control and Decision, 2012，27（2）：175-181.
[6]袁建清.基于TS的动态车辆调度问题的混合算法研究[J].计算机现代化，2012(6):73-75.
Yuan Jianqing.Mixed Tabu Search Algorithm for Dynamic Vehivle Scheduling Problem[J].Jisuanji Yu Xiandaihua, 2012(6):73-75.
[7]Azi N, Gendreau M, Potvin J Y. A Dynamic Vehicle Routing Problem with Multiple Delivery Routes[J]. Annals of Operations Research, 2012, 199(1): 103-112.
[8]Warren B. Powell，Approximate Dynamic Programming for Operations Research[M]. Princeton:Department of Operations Research and Financial Engineering Princeton University, 2005.
[9]Clara Novoa,Robert Storer.An Approximate Dynamic Programming Approach for the Vehicle Routing Problem with Stochastic Demands[J]. European Journal of Operational Research,2009,196(2):509-515.
[10]Si J,Barot A G,Powell W B,et al.Handbook of Learning and Approximate Dynamic Programming: Sealing up to the Real World[M]. New York: IEEE Press and John Wiley & Sons,2004.
[11]Kirk D E. Optimal Control Theory: An Introduction[M]. Englewood Cliffs:Prentice_Hall,1970.