A Heuristic for a Heterogeneous Automated Guided Vehicle Routing Problem

다국어 초록 (Multilingual Abstract)

The article addresses a Heterogeneous Automated Guided Vehicle (AGV) Routing Problem that distributes given jobs to one of the AGVs and finds a route for each AGV while minimizing the sum of tour costs. AGVs are heterogeneous as the cost of traveling between any two locations varies depending on the type of AGV. The problem is a generalization of multiple heterogeneous asymmetric Hamiltonian path problem and a primal-dual heuristic has been developed. Despite the complexity of the problem, the computational results show that the proposed algorithm produces good quality solutions within a relatively short computation time.

참고문헌 (Reference)

1 Oberlin, P., "Today's Traveling Salesman Problem" 17 (17): 70-77, 2010

2 Frieze, A. M., "On the Worst-Case Performance of Some Algorithms for the Asymmetric Traveling Salesman Problem" 12 (12): 23-39, 1982

3 Fazlollahtabar, H., "Methodologies to Optimize Automated Guided Vehicle Scheduling and Routing Problems : A Review Study" 77 (77): 525-545, 2015

4 Rathinam, S., "Lower and Upper Bounds for a Multiple Depot UAV Routing Problem" 5287-5292, 2006

5 Keld Helsgaun, "LKH, Version 2.0.7"

6 Levy, D., "Heuristics for Routing Heterogeneous Unmanned Vehicles with Fuel Constraints" 2014 : 131450-, 2014

7 Lagoudakis, M. G., "Auction-Based Multi-Robot Routing" 343-350, 2005

8 Yadlapalli, S., "Approximation Algorithms for a Heterogeneous Multiple Depot Hamiltonian Path Problem" 2789-2794, 2011

9 Vazirani, V. V., "Approximation Algorithms" Springer 2004

10 Hoogeveen, J., "Analysis of Christofides' Heuristic: Some Paths are More Difficult than Cycles" 10 (10): 291-295, 1991

11 Helsgaun, K., "An Effective Implementation of the Lin–Kernighan Traveling Salesman Heuristic" 126 (126): 106-130, 2000

12 Bae, J. Y., "Algorithms for Multiple Vehicle Routing Problems" Texas A&M University 2014

13 Dahari, M., "A Review of Auto-Guided-Vehicles Routing Algorithms" 479-481 : 443-456, 2012

14 Rathinam, S., "A Resource Allocation Algorithm for Multivehicle Systems with Nonholonomic Constraints" 4 (4): 98-104, 2007

15 Kaarthik Sundar, "A Primal-Dual Heuristic for a Heterogeneous Unmanned Vehicle Path Planning Problem" SAGE Publications 10 (10): 349-, 2013