基于多阶段网络流模型的多回合整车装卸车辆调度问题研究
Study on Multi-Trips Whole-Transport Vehicle Scheduling Problem Based on the Multistage Network Flow Model

作者: 宋志华 :空军工程大学装备管理与安全工程学院,陕西 西安 ; 张 晗 :空军工程大学理学院,陕西 西安 ;

关键词: 多回合整车装卸车辆调度问题多阶段网络流动态规划禁忌列表Multi-Trips Whole-Transport Vehicle Scheduling Problem Multi-Stage Network Flow Dynamic Programming Tabu List

摘要:
多回合整车装卸约束下的车辆调度问题是一种特殊的车辆调度问题,普通的车辆调度问题算法没有利用问题的特殊结构,计算效率低。首先通过分析多回合整车装卸车辆调度问题的特点,将其转换为多阶段网络流问题并建立模型;然后针对模型有后效性的特点,提出了基于禁忌列表的Bellman方程,并以此为基础,设计了基于动态规划算法的最小费用流求解算法。通过实例计算表明,模型和算法适合描述及求解多回合整车装卸车辆调度问题,能够较为快速高效地求解问题的优化行动方案。

Abstract: Multi-trips whole-transport vehicle scheduling problem is one kind of Vehicle Scheduling Prob-lem (VSP), and the ordinary VSP algorithms haven’t made use of its special structure and behave poorly. Firstly, its structure is analyzed and the problem is transformed into a multistage net-work flow model. Secondly, the Bellman equation with tabu list is designed to deal with the non-monotonicity of the model, and then the dynamic programming algorithm for finding the minimum cost flow is designed. Finally, the effectiveness of the model and algorithm is verified through an example.

文章引用: 宋志华 , 张 晗 (2017) 基于多阶段网络流模型的多回合整车装卸车辆调度问题研究。 运筹与模糊学, 7, 81-89. doi: 10.12677/ORF.2017.73010

参考文献

[1] Kumar, S.N. and Panneerselvam, R. (2012) A Survey on the Vehicle Routing Problem and Its Variants. Intelligent Information Management, 4, 66-74.

[2] Toth, P. and Vigo, D. (2014) Vehicle Routing: Problems, Methods, and Applications. Siam.
https://doi.org/10.1137/1.9781611973594

[3] Song, Z.H., et al. (2015) Algorithm for Distance Constrained Aerial Vehicle Routing Problem: Based on Minimum Spanning Tree and Genetic Computation. 2015 11th International Conference on Computational Intelligence and Security (CIS), IEEE.
https://doi.org/10.1109/CIS.2015.10

[4] Rivera, J.C., Afsar, H.M. and Prins, C. (2016) Mathematical Formulations and Exact Algorithm for the Multitrip Cumulative Capacitated Single-Vehicle Routing Problem. European Journal of Operational Research, 249, 93-104.
https://doi.org/10.1016/j.ejor.2015.08.067

[5] Novoa, C. and Storer, R. (2009) An Approximate Dynamic Programming Approach for the Vehicle Routing Problem with Stochastic Demands. European Journal of Operational Research, 196, 509-515.
https://doi.org/10.1016/j.ejor.2008.03.023

[6] Bertsekas, D.P. (2014) Abstract Dynamic Programming. Tsinghua University Press, Beijing, 1-25.

分享
Top