Abstract
In this paper, a hybrid genetic algorithm (GA) is proposed for the traveling salesman problem (TSP) with pickup and delivery (TSPPD). In our algorithm, a novel pheromone-based crossover operator is advanced that utilizes both local and global information to construct offspring. In addition, a local search procedure is integrated into the GA to accelerate convergence. The proposed GA has been tested on benchmark instances, and the computational results show that it gives better convergence than existing heuristics.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
G. Mosheiov. The Travelling Salesman Problem with Pickup and Delivery. European Journal of Operational Research, vol. 79, no. 2, pp. 299–310, 1994.
S. Anily, G. Mosheiov. The Traveling Salesman Problem with Delivery and Backhauls. Operations Research Letters, vol. 16, no. 1, pp. 11–18, 1994.
M. Gendreau, G. Laporte, D. Vigo. Heuristics for the Traveling Salesman Problem with Pickup and Delivery. Computer and Operations Research, vol. 26, no. 7, pp. 699–714, 1999.
R. Baldacci, E. Hadjiconstantinou, A. Mingozzi. An Exact Algorithm for the Traveling Salesman Problem with Deliveries and Collections. Networks, vol. 42, no. 1, pp. 26–41, 2003.
H. Hernández-Pérez, J. J. Salazar González. Heuristics for the One-commodity Pickup-and-delivery Traveling Salesman Problem. Transportation Science, vol. 38, no. 2, pp. 245–255, 2004.
M. Gendreau, A. Hertz, G. Laporte. The Traveling Salesman Problem with Backhauls. Computer and Operations Research, vol. 23, no. 5, pp. 501–508, 1996.
F. A. Tang, R. D. Galväo. A Tabu Search Algorithm for the Vehicle Routing Problem with Simultaneous Pick-up and Delivery Service. Computer and Operations Research, vol. 33, no. 3, pp. 595–619, 2006.
P. Chen, H. K. Huang, X. Y. Dong. An Ant Colony System Based Heuristic Algorithm for the Vehicle Routing Problem with Simultaneous Delivery and Pickup. In Proceedings of the 2nd IEEE Conference on Industrial Electronics and Applications, IEEE Press, Harbin, China, pp. 136–141, 2007.
H. D. Nguyen, I. Yoshihara, K. Yamamori, M. Yasunaga. Implementation of an Effective Hybrid GA for Large-scale Traveling Salesman Problems. IEEE Transactions on Systems, Man, and Cybernetics — Part B: Cybernetics, vol. 37, no. 1, pp. 92–99, 2007.
J. H. Holland. Adaptation in Natural and Artificial Systems, University of Michigan Press, Ann Arbour, USA, 1975.
A. Misevicius. An Improved Hybrid Genetic Algorithm: New Results for the Quadratic Assignment Problem. Knowledge-Based Systems, vol. 17, no. 2–4, pp. 65–73, 2004.
C. Prins. A Simple and Effective Evolutionary Algorithm for the Vehicle Routing Problem. Computer and Operations Research, vol. 31, no. 12, pp. 1985–2002, 2004.
B. J. Park, H. R. Choi, H. S. Kim. A Hybrid Genetic Algorithm for the Job Shop Scheduling Problems. Computer & Industrial Engineering, vol. 45, no. 4, pp. 597–613, 2003.
G. Reinelt. The Traveling Salesman: Computational Solutions for TSP Applications, Springer-Verlag, Berlin, Germany, 1994.
D. Whitley, H. K. Huang, X. Y. Dong. The Genitor Algorithm and Selection Pressure: Why Rank-based Allocation of Reproductive Trials is Best. In Proceedings of the 3rd International Conference on Genetic Algorithms, Morgan Kaufmann Publishers, San Francisco, USA, pp. 116–121, 1989.
D. E. Goldberg, R. Lingle. Alleles, loci, and the traveling salesman problem. In Proceedings of the 1st International Conference on Genetic Algorithms and their Applications, Lawrence Erlbaum Associates, Pittsburgh, USA, pp. 154–159, 1985.
G. Syswerda. Handbook of Genetic Algorithms, Van Nostrand Reinhold, New York, USA, pp. 332–349, 1991.
I.M. Oliver, D. J. Smith, J. R. C. Holland. A Study of Permutation Crossover Operators on the Traveling Salesman Problem. In Proceedings of 2nd International Conference on Genetic Algorithms and their Application, Lawrence Erlbaum Associates, Mahwah, USA, pp. 224–230, 1987.
H. D. Nguyen. Hybrid Genetic Algorithms for Combinatorial Optimization Problems, Ph.D. dissertation, University of Miyazaki, Miyazaki, Japan, 2004.
P. Merz, B. Freisleben. Genetic Local Search for the TSP: New Results. In Proceedings of IEEE International Conference on Evolutionary Computation, IEEE Press, Indianapolis, USA, pp. 159–164, 1997.
S. D. Shtovba. Ant Algorithms: Theory and Applications. Programming and Computer Software, vol. 31, no. 4, pp. 167–178, 2005.
S. Lin. Computer Solutions of the Traveling Salesman Problem. Bell Labs Technical Journal, vol. 44, no. 10, pp. 2245–2269, 1965.
T. Stützle, H. H. Hoos. MAX-MIN Ant System. Future Generation Computer Systems, vol. 16, no. 8, pp. 889–914, 2000.
J. J. Dongarra. Performance of Various Computers Using Standard Linear Equations Software, Technical Report CS-89-85, Department of Computer Science Department, University of Tennessee, TN, USA, 2007.
Author information
Authors and Affiliations
Corresponding author
Additional information
Fang-Geng Zhao graduated from Vehicle Management Institute, PRC, in 1999, and received the M. Sc. degree from Military Traffic Institute, PRC, in 2003. He is currently a Ph. D. candidate in University of Science and Technology Beijing, PRC.
His research interests include logistics management and optimization.
Jiang-Sheng Sun graduated from Ordnance Engineering Institute (OEI), PRC, in 1998, and received the M. Sc. degree from OEI, PRC, in 2001. He is currently a Ph.D. candidate in University of Science and Technology Beijing, PRC, and an engineer in Ordnance Technology Research Institute, Shijiazhuang, PRC.
His research interests include logistics management and optimization.
Su-Jian Li graduated from University of Science & Technology Taiyuan, PRC, in 1984, and received the Ph.D. degree from University of Science & Technology Beijing, PRC, in 1993. He is currently a professor in University of Science and Technology Beijing, PRC.
His research interests include logistics management, optimization, and information system.
Wei-Min Liu graduated from Northeastern University, PRC, in 1996. He is currently a Ph. D. candidate in University of Science and Technology Beijing, PRC.
His research interests include logistics management and optimization.
Rights and permissions
About this article
Cite this article
Zhao, FG., Sun, JS., Li, SJ. et al. A hybrid genetic algorithm for the traveling salesman problem with pickup and delivery. Int. J. Autom. Comput. 6, 97–102 (2009). https://doi.org/10.1007/s11633-009-0097-4
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11633-009-0097-4