Petrică Pop
ABSTRACT
In this paper, we consider the Family Traveling Salesman Problem (FTSP), which is a variant of the classical Traveling Salesman Problem (TSP). Given a partition of the nodes into a predefined number of clusters, called families, the aim of the FTSP is to find a minimum cost tour visiting a given number of nodes from each family. We describe a novel solution approach for solving the FTSP obtained by decomposing the problem into two smaller subproblems: a macro-level subproblem and a micro-level subproblem, and solving them separately. The goal of the first subproblem is to provide tours visiting the families using a classical genetic algorithm and a diploid genetic algorithm, while the aim of the second subproblem is to find the minimum-cost tour, corresponding to the above mentioned tours, visiting a given number of nodes from each family. The second subproblem is solved by transforming each global tour into a traveling salesman problem (TSP) which then is optimally computed using the Concorde TSP solver. The preliminary computational results on a usually used set of benchmark instances prove that our solution approach provides competitive solutions in comparison to the existing methods for solving the FTSP.
- R. Bernardino and A. Paias. 2017. Solving the family traveling salesman problem. European Journal of Operational Research (2017).Google Scholar
- J. A, Chisman. 1975. The clustered traveling salesman problem. Computers & Operations Research 2, 2 (1975), 115--119.Google ScholarCross Ref
- C. Expósito-Izquierdo, A. Rossi, and M. Sevaux. 2016. A Two-Level solution approach to solve the Clustered Capacitated Vehicle Routing Problem. Computers & Industrial Engineering 91 (2016), 274--289. Google ScholarDigital Library
- C. Feremans, M. Labbé, and G. Laporte. 2003. Generalized network design problems. European Journal of Operational Research 148, 1 (July 2003), 1--13.Google ScholarCross Ref
- D.E. Goldberg and R.E. Smith. 1987. Nonstationary Function Optimization Using Genetic Algorithms with Dominance and Diploidy. In Proc. of Second International Conference on Genetic Algorithms and their application. 59--68. Google ScholarDigital Library
- B. Golden, Z. Naji-Azimi, S. Raghavan, M. Salari, and P. Toth. 2012. The Generalized Covering Salesman Problem. INFORMS Journal on Computing 24, 4 (2012), 534--553. Google ScholarDigital Library
- A.L. Henry-Labordere. 1969. The record balancing problem: A dynamic programming solution of a generalized travelling salesman problem. RIRO (1969).Google Scholar
- M. Mitchell. 1998. An introduction to genetic algorithms. MIT Press. Google Scholar
- L.F. Morán-Mirabal, J.L. González-Velarde, and M.G.C. Resende. 2014. Randomized heuristics for the family traveling salesperson problem. International Transactions in Operational Research 21, 1 (2014), 41--57.Google ScholarCross Ref
- Camelia-M. Pintea, Petrică C. Pop, and Camelia Chira. 2017. The generalized traveling salesman problem solved with ant algorithms. Complex Adaptive Systems Modeling 5, 1 (07 Aug 2017), 8.Google Scholar
- P.C. Pop, L. Fuksz, A. Horvat-Marc, and C. Sabo. 2018. A novel two-level optimization approach for clustered vehicle routing problem. Computers & Industrial Engineering 115 (2018), 304 -- 318.Google ScholarCross Ref
- P.C. Pop, O. Matei, and C. Sabo. 2017. A hybrid diploid genetic based algorithm for solving the generalized traveling salesman problem. In Lecture Notes in Computer Science, Vol. 10334. 149--160.Google ScholarCross Ref
- P.C. Pop, O. Matei, C. Sabo, and A. Petrovan. 2018. A two-level solution approach for solving the generalized minimum spanning tree problem. European Journal of Operational Research 265, 2 (2018), 478--487.Google ScholarCross Ref
- P. C. Pop. 2002. The Generalized Minimum Spanning Tree Problem. Twente University Press, the Netherlands.Google Scholar
- P. C. Pop. 2012. Generalized Network Design Problems. Modeling and Optimization. De Gruyter, Germany.Google Scholar
- Petrica C. Pop and Serban Iordache. 2011. A Hybrid Heuristic Approach for Solving the Generalized Traveling Salesman Problem. In Proceedings of the 13th Annual Conference on Genetic and Evolutionary Computation (GECCO '11). ACM, New York, NY, USA, 481--488. Google ScholarDigital Library
- P. C. Pop, O. Matei, and C. Sabo. 2010. A New Approach for Solving the Generalized Traveling Salesman Problem. In Hybrid Metaheuristics, María J. Blesa, Christian Blum, Günther Raidl, Andrea Roli, and Michael Sampels (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 62--72. Google ScholarDigital Library
- Jean-Yves Potvin and François Guertin. 1996. The Clustered Traveling Salesman Problem: A Genetic Approach. Springer US, Boston, MA, 619--631.Google Scholar
- Mohammad H. Shaelaie, Majid Salari, and Zahra Naji-Azimi. 2014. The generalized covering traveling salesman problem. Applied Soft Computing 24 (2014), 867 -- 878. Google ScholarDigital Library
- S.S. Srivastava, S. Kumar, R.C. Garg, and P. Sen. 1969. Generalized travelling salesman problem through n sets of nodes. CORS.Google Scholar
Index Terms
- A two-level diploid genetic based algorithm for solving the family traveling salesman problem
Recommendations
New formulations for the generalized traveling salesman problem
ASM'12: Proceedings of the 6th international conference on Applied Mathematics, Simulation, ModellingThe Generalized Traveling Salesman Problem (GTSP) is an extension of the well known Traveling Salesman Problem (TSP). The GTSP is defined on a graph in which the nodes (customers or vertices) are grouped into a given number of clusters (node sets). ...
On Semidefinite Programming Relaxations of the Traveling Salesman Problem
We consider a new semidefinite programming (SDP) relaxation of the symmetric traveling salesman problem (TSP) that may be obtained via an SDP relaxation of the more general quadratic assignment problem (QAP). We show that the new relaxation dominates ...
An Effective Hybrid Genetic Algorithm for Solving the Generalized Traveling Salesman Problem
Hybrid Artificial Intelligent SystemsAbstractThe Generalized Traveling Salesman Problem (GTSP) looks for an optimal cycle in a clustered graph, such that every cluster is visited exactly once. In this paper, we describe a novel Hybrid Genetic Algorithm (HGA) for solving the GTSP. At the core ...
Comments