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

Operations Research and Fuzziology
Vol.07 No.03(2017), Article ID:21849,9 pages
10.12677/ORF.2017.73010

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

Zhihua Song1, Han Zhang2

1Equipment Management and Safety Engineering College, Air Force Engineering University, Xi’an Shaanxi

2Science College, Air Force Engineering University, Xi’an Shaanxi

Received: Aug. 7th, 2017; accepted: Aug. 19th, 2017; published: Aug. 28th, 2017

ABSTRACT

Multi-trips whole-transport vehicle scheduling problem is one kind of Vehicle Scheduling Problem (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 network 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.

Keywords:Multi-Trips Whole-Transport, Vehicle Scheduling Problem, Multi-Stage Network Flow, Dynamic Programming, Tabu List

1空军工程大学装备管理与安全工程学院，陕西 西安

2空军工程大学理学院，陕西 西安

1. 多阶段网络流模型的建立

1) 状态定义

2) 状态转移

Table 1. State definition of multi-stages decision model

3) 网络流模型

2. 求解算法分析

Table 2. Unit flow cost and capacity of the edges in the network

，且有

3. 算法设计

3.1. 基于禁忌列表的Bellman方程

1) 在第阶段的物资运送任务中，从车辆当前的状态开始，根据物资需求点不重复的约束，采用策略只有在满足以下条件的时候才可行，

2) 在第阶段的物资运送任务中，从车辆当前的状态开始，根据物资需求点不重复的约束，采用策略只有在满足以下条件的时候才可行，

(k)在第阶段的物资运送任务中从车辆当前的状态开始，根据物资需求点不重复的约束，采用策略只有在满足以下条件的时候才可行，

3.2. 基于禁忌列表的动态规划算法

4. 计算实例及算法性能分析

Figure 1. Position of vertices and the structure of the network

Figure 2. Multi-stages network flow model

Table 3. Coordinates of vertices in the network

Table 4. Minimum cost augmenting chains found by the algorithm

5. 结束语

Study on Multi-Trips Whole-Transport Vehicle Scheduling Problem Based on the Multistage Network Flow Model[J]. 运筹与模糊学, 2017, 07(03): 81-89. http://dx.doi.org/10.12677/ORF.2017.73010

1. 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. 2. Toth, P. and Vigo, D. (2014) Vehicle Routing: Problems, Methods, and Applications. Siam. https://doi.org/10.1137/1.9781611973594

3. 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. 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. 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. 6. Bertsekas, D.P. (2014) Abstract Dynamic Programming. Tsinghua University Press, Beijing, 1-25.