基于多阶段网络流模型的多回合整车装卸车辆调度问题研究

Study on Multi-Trips Whole-Transport Vehicle Scheduling Problem Based on the Multistage Network Flow Model

摘要: 多回合整车装卸约束下的车辆调度问题是一种特殊的车辆调度问题，普通的车辆调度问题算法没有利用问题的特殊结构，计算效率低。首先通过分析多回合整车装卸车辆调度问题的特点，将其转换为多阶段网络流问题并建立模型；然后针对模型有后效性的特点，提出了基于禁忌列表的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.