Tolerance-based algorithms for the traveling salesman problem
2008 (English)In: Mathematical Programming and Game Theory for Decision Making / [ed] S.K. Neogy, R.B. Bapat, A.K. Das, and T. Parthasarathy, New Jersey: World Scientific, 2008, 47-59 p.Chapter in book (Refereed)
Most research on algorithms for combinatorial optimization use the costs of the elements in the ground set for making decisions about the solutions that the algorithms would output. For traveling salesman problems, this implies that algorithms generally use arc lengths to decide on whether an arc is included in a partial solution or not. In this paper we study the eect of using element tolerances for making these decisions. We choose the traveling salesman problem as a model combinatorial optimization problem and propose several greedy algorithms for it based on tolerances. We report extensive computational experiments on benchmark instances that clearly demonstrate that our tolerance-based algorithms outperform their weight-based counterpart. This indicates that the potential for using tolerance-based algorithms for various optimization problems is high and motivates further investigation of the approach.
Place, publisher, year, edition, pages
New Jersey: World Scientific, 2008. 47-59 p.
Traveling salesman problems, greedy algorithms, arc tolerances
IdentifiersURN: urn:nbn:se:umu:diva-83133ISBN: 9812813217OAI: oai:DiVA.org:umu-83133DiVA: diva2:665037