Title: A modified genetic algorithm-based approach to solve constrained solid TSP with time window using interval valued parameter

Authors: Chiranjit Changdar; G.S. Mahapatra; Rajat Kumar Pal

Addresses: Department of Computer Science, Raja N.L. Khan Women's College, Midnapore, West Bengal, 721102, India ' Department of Mathematics, National Institute of Technology Puducherry Karaikal, 609605, India ' Department of Computer Science and Engineering, University of Calcutta, Calcutta, 700 009, West Bengal, India

Abstract: In this paper, we have presented a solid travelling salesman problem (STSP) with introduction of time-window and constraints. In STSP, a traveller can avail different conveyance for travelling. Also as constraint, a risk factor is there joining a path between two cities. During a tour, the traveller must ensure that the entire risk of the tour is within a prearranged risk level. Costs, time, and risk factor of travel using different conveyances are dissimilar and interval in nature. Finding a complete tour with minimum cost is the goal of the problem, where risk and time-window constraints are also to be satisfied. The standard genetic algorithm (GA) is modified by adding three features, namely refinement, immigration, and refreshing population, and thus a modified GA is devised to solve the intended problem. The efficiency of the algorithm is tested by using some model datasets from TSPLIB and some existing benchmark test functions.

Keywords: solid TSP; constrained TSP; travelling salesman problem; genetic algorithms; time windows; interval numbers; refinement; immigration; population refreshing; constraints.

DOI: 10.1504/IJOR.2016.077688

International Journal of Operational Research, 2016 Vol.26 No.4, pp.398 - 421

Received: 26 Feb 2014
Accepted: 17 Aug 2014
Published online: 13 Jul 2016 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article