Title :
A Continuous Time Model of Multi-vehicle Routing Problems: A Column Generation Approach
Author :
Matsushita, Shiho ; Nishi, Tomoki ; Morikawa, Masashi ; Hisano, Takeshi
Author_Institution :
Grad. Sch. of Eng. Sci., Osaka Univ., Toyonaka, Japan
Abstract :
In this paper, we propose a column generation heuristics to a continuous time model of conflict-free pickup and delivery vehicle routing problems. The transportation system is divided into several regions with regular intervals. A network model of conflict-free multi-vehicle routing problem with acceleration and deceleration motions is developed. A column generation heuristics is used to find a near-optimal solution. The pricing problem for each vehicle routing problem is formulated as a resource constrained shortest path problem, which is effectively solved by a labeling algorithm. Computational results demonstrate the effectiveness of the proposed method.
Keywords :
automatic guided vehicles; graph theory; road vehicles; vehicle routing; acceleration motion; column generation heuristics; conflict-free multivehicle routing problem; continuous time model; deceleration motion; labeling algorithm; pickup-and-delivery vehicle routing problem; pricing problem; resource constrained shortest path problem; transportation system; Acceleration; Computational modeling; Heuristic algorithms; Pricing; Routing; Vehicles; acceleration motion; automated guided vehicle; column generation; heuristics; labeling algorithm; routing;
Conference_Titel :
Systems, Man, and Cybernetics (SMC), 2013 IEEE International Conference on
Conference_Location :
Manchester
DOI :
10.1109/SMC.2013.74
