An efficient genetic algorithm for solving open multiple travelling salesman problem with load balancing constraint

Singamsetty, P.; Thenepalle, J.

Growing Science » Decision Science Letters » An efficient genetic algorithm for solving open multiple travelling salesman problem with load balancing constraint

Journals

DSL Volumes

Volume 1 (10)
- Issue 1 (5)
- Issue 2 (5)

Volume 2 (30)
- Issue 1 (5)
- Issue 2 (6)
- Issue 3 (9)
- Issue 4 (10)

Volume 3 (53)
- Issue 1 (15)
- Issue 2 (10)
- Issue 3 (19)
- Issue 4 (9)

Volume 4 (48)
- Issue 1 (10)
- Issue 2 (12)
- Issue 3 (14)
- Issue 4 (12)

Volume 5 (39)
- Issue 1 (12)
- Issue 2 (10)
- Issue 3 (8)
- Issue 4 (9)

Volume 6 (30)
- Issue 1 (8)
- Issue 2 (6)
- Issue 3 (9)
- Issue 4 (7)

Volume 7 (41)
- Issue 1 (8)
- Issue 2 (8)
- Issue 3 (8)
- Issue 4 (17)

Volume 8 (38)
- Issue 1 (8)
- Issue 2 (6)
- Issue 3 (14)
- Issue 4 (10)

Volume 9 (39)
- Issue 1 (8)
- Issue 2 (9)
- Issue 3 (14)
- Issue 4 (8)

Volume 10 (43)
- Issue 1 (7)
- Issue 2 (8)
- Issue 3 (20)
- Issue 4 (8)

Volume 11 (49)
- Issue 1 (9)
- Issue 2 (9)
- Issue 3 (14)
- Issue 4 (17)

Volume 12 (64)
- Issue 1 (12)
- Issue 2 (24)
- Issue 3 (13)
- Issue 4 (15)

Volume 13 (78)
- Issue 1 (21)
- Issue 2 (18)
- Issue 3 (19)
- Issue 4 (20)

Volume 14 (87)
- Issue 1 (21)
- Issue 2 (23)
- Issue 3 (25)
- Issue 4 (18)

Volume 15 (19)
- Issue 1 (19)

Countries

Decision Science Letters

ISSN 1929-5812 (Online) - ISSN 1929-5804 (Print) Quarterly Publication Volume 10 Issue 4 pp. 525-534 , 2021

An efficient genetic algorithm for solving open multiple travelling salesman problem with load balancing constraint Pages 525-534 Download PDF

Authors: Purusotham Singamsetty, Jayanth Kumar Thenepalle

DOI: 10.5267/j.dsl.2021.5.003

Keywords: Zero-one integer linear programming, Open multiple travelling salesman problem, Genetic algorithm, Load balancing constraint

Abstract: The multiple travelling salesman problem (MTSP) is one of the widely studied combinatorial optimization problems with various theoretical and practical applications. However, most of the studies intended to deal with classical MTSP, very limited attention has been given to an open multiple travelling salesman problem and its variants. In this paper, an open multiple travelling salesman problem with load balancing constraint (OMTSPLB) is addressed. The OMTSPLB differs from the conventional MTSP, in which all the salesmen start from the central depot and need not come back to it after visiting the given number of cities by accomplishing the load balance constraint, which helps in fairly distributing the task among all salesmen. The problem aims to minimize the overall traversal distance/cost for operating open tours subject to the load balancing constraint. A zero-one integer linear programming (0-1 ILP) model and an efficient metaheuristic genetic algorithm (GA), is established for the OMTSPLB. Since no existing study on OMTSPLB, the proposed GA is tested on the relaxed version of the present model, comparative results are reported. The comparative results show that the proposed GA is competent over the existing algorithms. Furthermore, extensive experiments are carried out on OMTSPLB and the results show that proposed GA can find the global solution effectively.

How to cite this paper

 Singamsetty, P & Thenepalle, J. (2021). An efficient genetic algorithm for solving open multiple travelling salesman problem with load balancing constraint.Decision Science Letters , 10(4), 525-534.

Refrences

Al-Omeer, M. A., & Ahmed, Z. H. (2019, April). Comparative study of crossover operators for the MTSP. In 2019 International Conference on Computer and Information Sciences (ICCIS) (pp. 1-6). IEEE.
Alves, R. M., & Lopes, C. R. (2015, May). Using genetic algorithms to minimize the distance and balance the routes for the multiple traveling salesman problem. In 2015 IEEE Congress on Evolutionary Computation (CEC) (pp. 3171-3178). IEEE.
Bailey, J. D. (1967), The behaviour of adaptive systems which employ genetic and correlation algorithms, Ph.D thesis, University of Michigan.
Benavent, E., & Martínez, A. (2013). Multi-depot Multiple TSP: a polyhedral study and computational results. Annals of Operations Research, 207(1), 7-25.
Bhavani, V., & Murthy, M. S. (2006). Truncated M-travelling salesmen problem. Opsearch, 43(2), 152-177.
Bharath-Kumar, K., & Jaffe, J. (1983). Routing to multiple destinations in computer networks. IEEE Transactions on Communications, 31(3), 343-351.
Brown, E. C., Ragsdale, C. T., & Carter, A. E. (2007). A grouping genetic algorithm for the multiple traveling salesperson problem. International Journal of Information Technology & Decision Making, 6(02), 333-347.
Carter, A. E., & Ragsdale, C. T. (2002). Scheduling pre-printed newspaper advertising inserts using genetic algorithms. Omega, 30(6), 415-421.
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), 245-257.
Garey, M.R., & Johnson DS (1979) Computers and intractability: a guide to the theory of NP-completeness, in computers and intractability, vol. 24, New York, pp 90–91
Ghadiry, W., Habibi, J., & Aghdam, A.G. (2015) Generalized formulation for trajectory optimization in patrolling problems. In: Proceedings Halifax, NS, CCECE, pp 231–236
Gorenstein, S. (1970). Printing press scheduling for multi-edition periodicals. Management Science, 16(6), B-373.
Harrath, Y., Salman, A. F., Alqaddoumi, A., Hasan, H., & Radhi, A. (2019). A novel hybrid approach for solving the multiple traveling salesmen problem. Arab Journal of Basic and Applied Sciences, 26(1), 103-112.
Hong, S., & Padberg, M. W. (1977). A note on the symmetric multiple traveling salesman problem with fixed charges. Operations Research, 25(5), 871-874.
Kaliaperumal, R., Ramalingam, A., & Sripriya, J. (2015, March). A modified Two part chromosome Crossover for solving MTSP using Genetic algorithms. In Proceedings ICARCSET 2015, New York, pp. 1-4.
Kim, K. H., & Park, Y. M. (2004). A crane scheduling method for port container terminals. European Journal of operational research, 156(3), 752-768.
Király, A., & Abonyi, J. (2011). Optimization of multiple traveling salesmen problem by a novel representation based genetic algorithm. In Intelligent Computational Optimization in Engineering Vol. 366, pp. 241-269.
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.
Liu, M, & Zhang, PY (2014) New hybrid genetic algorithm for solving the multiple traveling salesman problem: an example of distribution of emergence materials. J Syst Manag 23(02):247–254.
Lo, K. M., Yi, W. Y., Wong, P. K., Leung, K. S., Leung, Y., & Mak, S. T. (2018). A genetic algorithm with new local operators for multiple traveling salesman problems. International Journal of Computational Intelligence Systems, 11(1), 692-705.
Malmborg, C. J. (1996). A genetic algorithm for service level based vehicle scheduling. European Journal of Operational Research, 93(1), 121-134.
Modares, A., Somhom, S., & Enkawa, T. (1999). A self‐organizing neural network approach for multiple traveling salesman and vehicle routing problems. International Transactions in Operational Research, 6(6), 591-606.
Okonjo-Adigwe, C. (1988). An effective method of balancing the workload amongst salesmen. Omega, 16(2), 159-163.
Saleh, H. A., & Chelouah, R. (2004). The design of the global navigation satellite system surveying networks using genetic algorithms. Engineering Applications of Artificial Intelligence, 17(1), 111-122.
Sedighpour, M., Yousefikhoshbakht, M., & Mahmoodi Darani, N. (2012). An effective genetic algorithm for solving the multiple traveling salesman problem. Journal of Optimization in Industrial Engineering, (8), 73-79.
Shuai, Y., Yunfeng, S., & Kai, Z. (2019). An effective method for solving multiple travelling salesman problem based on NSGA-II. Systems Science & Control Engineering, 7(2), 108-116.
Singh, A., & Baghel, A. S. (2009). A new grouping genetic algorithm approach to the multiple traveling salesperson problem. Soft Computing, 13(1), 95-101.
Singh, D. R., Singh, M. K., Singh, T., & Prasad, R. (2018). Genetic algorithm for solving multiple traveling salesmen problem using a new crossover and population generation. Computación y Sistemas, 22(2).
Sofge, D., Schultz, A., & De Jong, K. (2002, April). Evolutionary computational approaches to solving the multiple traveling salesman problem using a neighborhood attractor schema. In Workshops on Applications of Evolutionary Computation (pp. 153-162). Springer, Berlin, Heidelberg.
Tang, L., Liu, J., Rong, A., & Yang, Z. (2000). A multiple traveling salesman problem model for hot rolling scheduling in Shanghai Baoshan Iron & Steel Complex. European Journal of Operational Research, 124(2), 267-282.
TSPLIB: The Library of TSP Benchmark Instances: http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/
Thenepalle, J., & Singamsetty, P. (2019). An open close multiple travelling salesman problem with single depot. Decision Science Letters, 8(2), 121-136.
Wang, X., & Regan, A. C. (2002). Local truckload pickup and delivery with hard time window constraints. Transportation Research Part B: Methodological, 36(2), 97-112.
Xu, X., Yuan, H., Liptrott, M., & Trovati, M. (2018). Two phase heuristic algorithm for the multiple-travelling salesman problem. Soft Computing, 22(19), 6567-6581.
Yan, X., Zhang, C., Luo, W., Li, W., Chen, W., & Liu, H. (2012). Solve traveling salesman problem using particle swarm optimization algorithm. International Journal of Computer Science Issues (IJCSI), 9(6), 264.
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.