Open Access Open Access  Restricted Access Subscription Access

EFFICIENT METAHEURISTIC ALGORITHMS FOR THE MULTI-STRIPE TRAVELLING SALESMAN PROBLEM

Ban Ha Bang

Abstract


The Multi-stripe Travelling Salesman Problem (Ms-TSP) is an extension of the Travelling Salesman Problem (TSP). In the \textit{q}-stripe TSP with $q \geq 1$, the objective function sums the costs for travelling from one customer to each of the next \textit{q} customers along the tour. The resulting \textit{q}-stripe TSP generalizes the TSP and forms a special case of the Quadratic Assignment Problem. To solve medium and large size instances, a metaheuristic algorithm is proposed. The proposed algorithm has two main components, which are construction and improvement phases. The construction phase generates a solution using Greedy Randomized Adaptive Search Procedure (GRASP) while the optimization phase improves the solution with several variants of Variable Neighborhood Search, both coupled with a technique called Shaking Technique to escape from local optima. In addition, Adaptive Memory is integrated into our algorithms to balance between the diversification and intensification. To show the efficiency of our proposed metaheuristic algorithms, we extensively experiment on benchmark instances. The results indicate that the developed algorithms can produce efficient and effective solutions at a reasonable computation time.


Keywords


\textit{q}-stripe-TSP; Adaptive Memory; VND; VNS; GVNS

Full Text:

PDF

References


bibitem{bib01} R. Bermudez, M. H. Cole, ``A Genetic Algorithm Approach to Door Assignments in Breakbulk Terminals", University of Arkansas, Mack-Blackwell National Rural Transportation, 2001, Study Center, Fayetteville.

bibitem{bib02} E. c{C}ela, V. G. Deineko, and G. J. Woeginger, ``The Multi-stripe Travelling Salesman Problem", J. Annals of Operations Research, Vol. 259, 2017, pp. 21–34.

bibitem{bib03} T. A. Feo and M.G.C. Resende, ``Greedy Randomized Adaptive Search Procedures", J. Global Opt., 1995, pp. 109-133.

bibitem{bib04} G. Finke, E. B. Rainer, F. Rendl, ``Quadratic Assignment Problems", J. North-Holland Mathematics Studies, Vol. 132, 1987, Pages 61-82.

bibitem{bib05} A. M. Geoffrion, G. W. Graves, ``Scheduling Parallel Production Lines with Changeover Costs: Practical Application of A Quadratic Assignment/LP Approach, J. Oper Res, Vol. 24, No. 4, 1976, pp.595–610.

bibitem{bib06} M. Grotschel, ``Discrete Mathematics in Manufacturing", Proc. ICIAM on SIAM, pp. 119–145.

bibitem{bib07} D. S. Johnson, and L. A. McGeoch, ``The traveling salesman problem: A case study in local optimization in Local Search in Combinatorial Optimization", E. Aarts and J. K. Lenstra, eds., pp. 215-310.

bibitem{bib08} A. Mason, M. Ronnqvist, ``Solution Methods for the Balancing of Jet Turbines, J. Comput Oper Res, Vol. 24, No. 2, 1997, pp. 153–167.

bibitem{bib09} O. Martin, S. W. Otto, and E.W. Felten, “Large-Step Markov Chains for The Traveling Salesman Problem", J. Complex Systems, Vol. 5, No. 3, 1991, pp. 299-326

bibitem{bib10} I. Mathlouthi, M. Gendreau, J. Y. Potvin, ``A Metaheuristic Based on Tabu Search for Solving a Technician Routing and Scheduling Problem", 2018.

bibitem{bib11} N. Mladenovic, P. Hansen, ``Variable Neighborhood Search", J. Operations Research, vol.24, No. 11 24, 1997, pp.1097-1100.

bibitem{bib12} I. Ugi, J. Bauer, J. Brandt, J. Friedrich, J. Gasteige, C. Jochum C, W. Schubert, ``New Fields of Application for Computers in Chemistry", J. Angew Chem, Vol. 91, No. 2, 1997, pp. 99–111.

bibitem{bib13} A. T. Phillips, J. B. Rosen, ``A Quadratic Assignment Formulation of the Molecular Conformation Problem. J Glob Optim, Vol. 4, No. 2, 1994, pp. 229–241.

bibitem{bib14} K. Ruland, ``Polyhedral Solution to the Pickup and Delivery Problem”, Ph.D. Thesis, Washington University, Saint Louis, MO, 1995.




DOI: https://doi.org/10.15625/1813-9663/36/3/14770 Display counter: Abstract : 41 views. PDF : 20 views.

Oktrik

Journal of Computer Science and Cybernetics ISSN: 1813-9663

Published by Vietnam Academy of Science and Technology