×

zbMATH — the first resource for mathematics

Exact and heuristic algorithms for routing AGV on path with precedence constraints. (English) Zbl 1400.90313
Summary: 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.
MSC:
90C59 Approximation methods and heuristics in mathematical programming
90B10 Deterministic network models in operations research
90C27 Combinatorial optimization
Software:
TSPTW
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Vis, I. F. A., Survey of research in the design and control of automated guided vehicle systems, European Journal of Operational Research, 170, 3, 677-709, (2006) · Zbl 1091.90505
[2] Garey, M. R.; Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness, (1979), New York, NY, USA: WH Freeman and Company, New York, NY, USA · Zbl 0411.68039
[3] Lin, S.; Kernighan, B. W., An effective heuristic algorithm for the traveling-salesman problem, Operations Research, 21, 2, 498-516, (1973) · Zbl 0256.90038
[4] Focacci, F.; Lodi, A.; Milano, M., A hybrid exact algorithm for the TSPTW, INFORMS Journal on Computing, 14, 4, 403-417, (2002) · Zbl 1238.90054
[5] Mingozzi, A.; Bianco, L.; Ricciardelli, S., Dynamic programming strategies for the traveling salesman problem with time window and precedence constraints, Operations Research, 45, 3, 365-377, (1997) · Zbl 0893.90167
[6] Lawler, E. L.; Lenstra, J. K.; Rinnooy Kan, A. H. G.; Shmoys, D. B., The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization, (1985), Chichester, UK: John Wiley & Sons, Chichester, UK · Zbl 0562.00014
[7] Burkard, R. E.; Deineko, V. G.; van Dal, R.; van der Veen, J. A.; Woeginger, G., Well-solvable special cases of the traveling salesman problem: a survey, SIAM Review, 40, 3, 496-546, (1998) · Zbl 1052.90597
[8] Sanjeev, A., Polynomial time approximation schemes for Euclidean TSP and other geometric problems, Proceedings of the 37th Annual Symposium on Foundations of Computer Science
[9] Deń≠neko, V. G.; Woeginger, G. J., The convex-hull-and-k-line travelling salesman problem, Information Processing Letters, 59, 6, 295-301, (1996) · Zbl 0900.68326
[10] Burkard, R. E.; Deineko, V. G.; Woeginger, G. J., The travelling salesman problem on permuted Monge matrices, Journal of Combinatorial Optimization, 2, 4, 333-350, (1998) · Zbl 0955.90113
[11] Rathinam, S.; Sengupta, R.; Darbha, S., A resource allocation algorithm for multivehicle systems with nonholonomic constraints, IEEE Transactions on Automation Science and Engineering, 4, 1, 98-104, (2007)
[12] Xu, Z.; Xu, L.; Rodrigues, B., An analysis of the extended Christofides heuristic for the k-depot TSP, Operations Research Letters, 39, 3, 218-223, (2011) · Zbl 1219.90149
[13] Xu, Z.; Rodrigues, B., A 3/2-approximation algorithm for the multiple TSP with a fixed number of depots, INFORMS Journal on Computing, 27, 4, 636-645, (2015) · Zbl 1338.90358
[14] Moon, C.; Kim, J.; Choi, G.; Seo, Y., An efficient genetic algorithm for the traveling salesman problem with precedence constraints, European Journal of Operational Research, 140, 3, 606-617, (2002) · Zbl 0998.90066
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.