Exact and Heuristic Algorithms for Routing AGV on Path with Precedence Constraints
Joint Authors
Xu, Liang
Wang, Yao
Liu, Lin
Wang, Jiaxing
Source
Mathematical Problems in Engineering
Issue
Vol. 2016, Issue 2016 (31 Dec. 2016), pp.1-8, 8 p.
Publisher
Hindawi Publishing Corporation
Publication Date
2016-07-31
Country of Publication
Egypt
No. of Pages
8
Main Subjects
Abstract EN
A new problem arises when an automated guided vehicle (AGV) is dispatched to visit a set of customers, which are usually located along a fixed wire transmitting signal to navigate the AGV.
An optimal visiting sequence is desired with the objective of minimizing the total travelling distance (or time).
When precedence constraints are restricted on customers, the problem is referred to as traveling salesman problem on path with precedence constraints (TSPP-PC).
Whether or not it is NP-complete has no answer in the literature.
In this paper, we design dynamic programming for the TSPP-PC, which is the first polynomial-time exact algorithm when the number of precedence constraints is a constant.
For the problem with number of precedence constraints, part of the input can be arbitrarily large, so we provide an efficient heuristic based on the exact algorithm.
American Psychological Association (APA)
Xu, Liang& Wang, Yao& Liu, Lin& Wang, Jiaxing. 2016. Exact and Heuristic Algorithms for Routing AGV on Path with Precedence Constraints. Mathematical Problems in Engineering،Vol. 2016, no. 2016, pp.1-8.
https://search.emarefa.net/detail/BIM-1112260
Modern Language Association (MLA)
Xu, Liang…[et al.]. Exact and Heuristic Algorithms for Routing AGV on Path with Precedence Constraints. Mathematical Problems in Engineering No. 2016 (2016), pp.1-8.
https://search.emarefa.net/detail/BIM-1112260
American Medical Association (AMA)
Xu, Liang& Wang, Yao& Liu, Lin& Wang, Jiaxing. Exact and Heuristic Algorithms for Routing AGV on Path with Precedence Constraints. Mathematical Problems in Engineering. 2016. Vol. 2016, no. 2016, pp.1-8.
https://search.emarefa.net/detail/BIM-1112260
Data Type
Journal Articles
Language
English
Notes
Includes bibliographical references
Record ID
BIM-1112260