An open close multiple travelling salesman problem with single depot

Abstract: This paper introduces a novel practical variant, namely an open close multiple travelling salesmen problem with single depot (OCMTSP) that concerns the generalization of classical travelling salesman problem (TSP). In OCMTSP, the overall salesmen can be categorized into internal/permanent and external/outsourcing ones, where all the salesmen are positioned at the depot city. The primary objective of this problem is to design the optimal route such that all salesmen start from the depot/base city, and then visit a given set of cities. Each city is to be visited precisely once by exactly one salesman, and only the internal salesmen have to return to the depot city whereas the external ones need not return. To find optimal solutions, an exact pattern recognition technique based Lexi-search algorithm (LSA) is developed which has been subjected in Matlab. Comparative computational results of the LSA have been made with the existing methods for general multiple travelling salesman problem (MTSP). Further, to test the performance of LSA, computational experiments have been carried out on some benchmark as well as randomly generated test instances for OCMTSP, and results are reported. The overall computational results demonstrate that the proposed LSA is efficient in providing optimal and sub-optimal solutions within the considerable CPU times.

How to cite this paper

 Thenepalle, J & Singamsetty, P. (2019). An open close multiple travelling salesman problem with single depot.Decision Science Letters , 8(2), 121-136.

Refrences

Ali, A. I., & Kennington, J. L. (1986). The asymmetric M-travelling salesmen problem: A duality based branch-and-bound algorithm. Discrete Applied Mathematics, 13(2-3), 259-276.
Bektas, T. (2006). The multiple traveling salesman problem: an overview of formulations and solution procedures. Omega, 34(3), 209-219.
Berenguer, X. (1979). A characterization of linear admissible transformations for the m-travelling salesmen problem. European Journal of Operational Research, 3(3), 232-238.
Bhavani, V., & Murthy, M. S. (2006). Truncated M-travelling salesmen problem. Opsearch, 43(2), 152-177.
Bolaños, R., Echeverry, M., & Escobar, J. (2015). A multiobjective non-dominated sorting genetic algorithm (NSGA-II) for the Multiple Traveling Salesman Problem. Decision Science Letters, 4(4), 559-568.
Bolanos, R. (2016). A population-based algorithm for the multi travelling salesman problem. International Journal of Industrial Engineering Computations, 7(2), 245-256.
Carter, A. E., & Ragsdale, C. T. (2006). A new approach to solving the multiple traveling salesperson problem using genetic algorithms. European Journal of Operational Research, 175(1), 246-257.
Changdar, C., Pal, R. K., & Mahapatra, G. S. (2017). A genetic ant colony optimization based algorithm for solid multiple travelling salesmen problem in fuzzy rough environment. Soft Computing, 21(16), 4661-4675.
França, P. M., Gendreau, M., Laporte, G., & Müller, F. M. (1995). The m-traveling salesman problem with minmax objective. Transportation Science, 29(3), 267-275.
Gavish, B., & Srikanth, K. (1986). An optimal solution method for large-scale multiple traveling salesmen problems. Operations Research, 34(5), 698-717.
Kara, I., & Bektas, T. (2006). Integer linear programming formulations of multiple salesman problems and its variations. European Journal of Operational Research, 174(3), 1449-1458.
Király, A., & Abonyi, J. (2010). A novel approach to solve multiple traveling salesmen problem by genetic algorithm. Computational Intelligence in Engineering, 141-151.
Király, A., Christidou, M., Chován, T., Karlopoulos, E., & Abonyi, J. (2016). Minimization of off-grade production in multi-site multi-product plants by solving multiple traveling salesman problem. Journal of Cleaner Production, 111, 253-261.
Larki, H., & Yousefikhoshbakht, M. (2014). Solving the multiple traveling salesman problem by a novel meta-heuristic algorithm. Journal of Optimization in Industrial Engineering, 7(16), 55-63.
Lenstra, J. K., & Kan, A. R. (1979). A characterization of linear admissible transformations for the m-travelling salesmen problem: A result of Berenguer. European Journal of Operational Research, 3(3), 250-252.
Little, J. D., Murty, K. G., Sweeney, D. W., & Karel, C. (1963). An algorithm for the traveling salesman problem. Operations Research, 11(6), 972-989.
Murthy, M. S. (1976). A bulk transportation problem. Opsearch, 13(3–4), 143-155.
Na, B. (2007). Heuristic approaches for no-depot k-traveling salesmen problem with a minmax objective (Doctoral dissertation, Texas A&M University).
Pandit, S. N. (1962). The loading problem. Operations Research, 10(5), 639-646.
Russell, R. A. (1977). An effective heuristic for the m-tour traveling salesman problem with some side conditions. Operations Research, 25(3), 517-524.
Reinhelt, G. (2014). {TSPLIB}: a library of sample instances for the TSP (and related problems) from various sources and of various types. URL: http://comopt. ifi. uniheidelberg. de/software/TSPLIB95.
Sarin, S. C., Sherali, H. D., Judd, J. D., & Tsai, P. F. J. (2014). Multiple asymmetric traveling salesmen problem with and without precedence constraints: Performance comparison of alternative formulations. Computers & Operations Research, 51, 64-89.
Singh, A., & Baghel, A. S. (2009). A new grouping genetic algorithm approach to the multiple traveling salesperson problem. Soft Computing-A Fusion of Foundations, Methodologies and Applications, 13(1), 95-101.
Somhom, S., Modares, A., & Enkawa, T. (1999). Competition-based neural network for the multiple travelling salesmen problem with minmax objective. Computers & Operations Research, 26(4), 395-407.
Soylu, B. (2015). A general variable neighborhood search heuristic for multiple traveling salesmen problem. Computers & Industrial Engineering, 90, 390-401.
Venkatesh, P., & Singh, A. (2015). Two metaheuristic approaches for the multiple traveling salesperson problem. Applied Soft Computing, 26, 74-89.
Wacholder, E., Han, J., & Mann, R. C. (1989). A neural network algorithm for the multiple traveling salesmen problem. Biological Cybernetics, 61(1), 11-19.
Wang, P., Sanin, C., & Szczerbicki, E. (2015). Evolutionary algorithm and decisional DNA for multiple travelling salesman problem. Neurocomputing, 150, 50-57.
Yousefikhoshbakht, M., Didehvar, F., & Rahmati, F. (2013). Modification of the ant colony optimization for solving the multiple traveling salesman problem. Romanian Journal of Information Science and Technology, 16(1), 65-80.
Yuan, S., Skinner, B., Huang, S., & Liu, D. (2013). A new crossover approach for solving the multiple travelling salesmen problem using genetic algorithms. European Journal of Operational Research, 228(1), 72-82.

Journals

DSL Volumes

Keywords

Authors

Countries

Decision Science Letters

An open close multiple travelling salesman problem with single depot Pages 121-136 Download PDF

Add Reviews