A Multi-Start Iterated Local Search Algorithm for the Bottleneck Traveling Salesman Problem
- Resource Type
- Conference
- Authors
- Rajaramon, Viknesh; Pandiri, Venkatesh
- Source
- 2022 IEEE 19th India Council International Conference (INDICON) India Council International Conference (INDICON), 2022 IEEE 19th. :1-7 Nov, 2022
- Subject
- Communication, Networking and Broadcast Technologies
Components, Circuits, Devices and Systems
Computing and Processing
Photonics and Electrooptics
Power, Energy and Industry Applications
Robotics and Control Systems
Signal Processing and Analysis
Costs
Vehicle routing
Metaheuristics
Traveling salesman problems
Benchmark testing
Search problems
Planning
Bottleneck traveling salesman problem
iterated local search
2-opt move
heuristic algorithm
- Language
- ISSN
- 2325-9418
The bottleneck traveling salesman problem (BTSP) is a variation of the well-known traveling salesman problem (TSP) in which the goal is to identify a Hamiltonian circuit with the lowest maximum edge cost among its constituent edges on a complete graph. The BTSP finds application in minimizing make-span in a two-machine flow shop with no-wait-in-process and in the area of workforce planning. A multi-start iterated local search algorithm for the BTSP is proposed in this paper. As part of this approach, two local search algorithms have been developed - one based on modified 2-opt moves and the other based on node insertion. The performance of the proposed approach is investigated by using the standard TSPLIB’s benchmark instances. The effectiveness of the proposed approach is demonstrated through computational results and their interpretation.