Abstract.
This paper deals with the bi-criteria travelling salesman subtour problem with time threshold (BTSSP-T), which comes from the family of the travelling salesman problem (TSP) and is NP-hard in the strong sense. The problem arises in several application domains, mainly in routing and scheduling contexts. Here, the model focuses on two criteria: total travel distance and gains attained. The BTSSP-T aims to determine a subtour that starts and ends at the same city and visits a subset of cities at a minimum travel distance with maximum gains, such that the time spent on the tour does not exceed the predefined time threshold. A zero-one integer-programming problem is adopted to formulate this model with all practical constraints, and it includes a finite set of feasible solutions (one for each tour). Two algorithms, namely, the Lexi-Search Algorithm (LSA) and the Tabu Search (TS) algorithm have been developed to solve the BTSSP-T problem. The proposed LSA implicitly enumerates the feasible patterns and provides an efficient solution with backtracking, whereas the TS, which is metaheuristic, will give the better approximate solution. A numerical example is demonstrated in order to understand the search mechanism of the LSA. Numerical experiments are carried out in the MATLAB environment, on the different benchmark instances available in the TSPLIB domain as well as on randomly generated test instances. The experimental results show that the proposed LSA works better than the TS algorithm in terms of solution quality and, computationally, both LSA and TS are competitive.
Similar content being viewed by others
References
W. Krauth, M. Mezard, Europhys. Lett. 8, 3 (1989)
R. Matai, S. Singh, M.L. Mittal, in Traveling Salesman Problem, Theory and Applications, edited by D. Davendra (InTech, 2010)
S.N. Daoud, Eur. Phys. J. Plus 129, 7 (2014)
H.E. Stanley, S.V. Buldyrev, Nature 413, 6854 (2001)
Y. Usami, M. Kitaoka, Int. J. Mod. Phys. B. 11, 13 (1997)
R. Durbin, R. Szeliski, A. Yuille, Neural Comput. 1, 3 (1989)
E.L. Ulungu, J. Teghem, J. Multi-Crit. Decis. Anal. 3, 2 (1994)
M.M. Ehrgott, M. Wiecek, Multiple Criteria Decision Analysis: State of the Art Surveys (Kluwer Academic Publishers, 2005)
J. Riera-Ledesma, J.J. Salazar-Gonzalez, Eur. J. Oper. Res. 160, 3 (2005)
J.F. Berube, M. Gendreau, J.Y. Potvin, Eur. J. Oper. Res. 194, 1 (2009)
D. Alexiou, S. Katsavounis, Oper. Res. Int. J. 15, 2 (2015)
J.P. Saksena, S. Kumar, Oper. Res. 14, 5 (1966)
D.H. Gensch, AIIE T. 10, 4 (1978)
G. Laporte, H. Mercure, Y. Norbert, RAIRO-Oper. Res. 18, 3 (1984)
D. Feillet, P. Dejax, M. Gendreau, Transp. Sci. 39, 2 (2005)
P.I. Stetsyuk, Cybern. Syst. Anal. 52, 1 (2016)
K. Mathur, S. Bansal, M.C. Puri, Optimization 28, 2 (1993)
J.R. Current, D.A. Schilling, Eur. J. Oper. Res. 73, 1 (1994)
M. Gen, K. Ida, Y. Li, E. Kubota, Comput. Ind. Eng. 29, 1 (1995)
V.R. Neppalli, C.L. Chen, J.N. Gupta, Eur. J. Oper. Res. 95, 2 (1996)
S.C. Hong, Y.B. Park, Int. J. Prod. Econ. 62, 3 (1999)
W. Li, Finding Pareto-optimal set by merging attractors for a bi-objective traveling salesmen problem, in Evolutionary Multi-Criterion Optimization: EMO 2005, edited by (Springer, Berlin, Heidelberg, 2005)
Y.L. Chen, H.H. Yang, Eur. J. Oper. Res. 144, 3 (2003)
T. Tyni, J. Ylinen, Eur. J. Oper. Res. 169, 3 (2006)
N. Jozefowiez, F. Semet, E.G. Talbi, Comput. Oper. Res. 34, 7 (2007)
F. Tricoire, A. Graf, W.J. Gutjahr, Comput. Oper. Res. 39, 7 (2012)
R. Mansini, B. Tocchella, Comput. Oper. Res. 36, 7 (2009)
M.S. Pishvaee, R.Z. Farahani, W. Dullaert, Comput. Oper. Res. 37, 6 (2010)
K. Ghoseiri, B. Nadjari, Appl. Soft Comput. 10, 4 (2010)
R. Fischer, K. Richter, in Mathematische Operations for schung und Statistik, Series Optimization 13, 2 (1982)
I. Sigal, Comput. Math. Math. Phys. 34, 1 (1994)
I.I. Melamed, I.K. Sigal, Comput. Math. Math. Phys. 37, 8 (1997)
M.P. Hansen, J. Heuristics 6, 3 (2000)
L. Paquete, T. Stutzle, in International Conference on Evolutionary Multi-Criterion Optimization (Springer, Berlin, Heidelberg, 2003) pp. 479--493
E. Angel, E. Bampis, L. Gourves, in Metaheuristics for Multiobjective Optimization (Springer, Berlin, Heidelberg, 2004) pp. 153--176
C. Garcia-Martinez, O. Cordon, F. Herrera, Eur. J. Oper. Res. 180, 1 (2007)
M. Köksalan, D.T. Öztürk, Comput. Oper. Res. 79, 304 (2017)
U. Pferschy, R. Stanek, Cent. Eur. J. Oper. Res. 25, 1 (2017)
S.N.N. Pandit, Oper. Res. 10, 5 (1962)
M. Sundara Murthy, Opsearch 13, 3 (1976)
F. Glover, ORSA J. Comput. 1, 3 (1989)
J. Knox, Comput. Oper. Res. 21, 8 (1994)
C. Changdar, G.S. Mahapatra, R.K. Pal, Swarm Evol. Comput. 15, 27 (2014)
S. Sorlin, C. Solnon, in International Workshop on Graph-Based Representations in Pattern Recognition (Springer, Berlin, Heidelberg, 2005) pp. 172--182
S. Basu, Am. J. Oper. Res. 2, 2 (2012)
C.R. Reeves, Modern heuristic techniques for combinatorial problems (John Wiley & Sons, 1993)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Kumar Thenepalle, J., Singamsetty, P. Bi-criteria travelling salesman subtour problem with time threshold. Eur. Phys. J. Plus 133, 128 (2018). https://doi.org/10.1140/epjp/i2018-11940-1
Received:
Accepted:
Published:
DOI: https://doi.org/10.1140/epjp/i2018-11940-1