Communications - Scientific Letters of the University of Zilina 2003, 5(4):27-35 | DOI: 10.26552/com.C.2003.4.27-35
An Impact of Improvement-Exchange Heuristics to Quality of Probabilistic TSP Solution
- 1 University of Zilina, Faculty of Management Science and Informatics, Slovakia
This paper deals with a probabilistic travelling salesman problem (PTSP), which differs from a travelling salesman problem (TSP) [6] in the demand for a customer visit. In PTSP is each customer visited with a given probability only. An objective function for PTSP is in general hard to enumerate and it is even harder to estimate an influence of a local change of a PTSP solution on the final value of the objective function of the resulting solution. This hardiness complicates construction of an efficient heuristic for this problem. In this contribution we have focused on research of a relation between type of local change operation and the resulting objective function improvement. We have constrained here ourselves to improvement-exchange heuristics only, whereas inserting heuristics were broadly studied in the previous works [3], [5]. In this work we have tried to suggest several types of feasible solution changes (operations) including estimation of their impact on the objective function value. These operations have been embedded into the best admissible strategy and implemented as a part of software system, which enables exact or approximate evaluation of a PTSP route depending on the problem size. Using this system we have performed a sequence of numerical experiments to reveal relation between complexity of the used heuristics operations and final improvement of the resulting objective function value. This numerical result and associated conclusions are reported in the concluding part of this contribution.
Keywords: no keywords
Published: December 31, 2003 Show citation
| ACS | AIP | APA | ASA | Harvard | Chicago | Chicago Notes | IEEE | ISO690 | MLA | NLM | Turabian | Vancouver |
References
- ftp://ftp.zib.de/pub/Packages/mp-testdata/tsp/tsplib/., internet server with TSP benchmarks
- JAILLET, P.: A priori solution of the traveling salesman problem in which a random subset of customers are visited., Operation Research 36, 1988
Go to original source... - JANÁČEK, J., HURTÍK, J.: Heuristics algorithm and evaluation of probabilistic traveling salesman problem solution. Journal of Information, Control and Management Systems, ®U ®ilina, 2003, to appear
- JANÁČEK, J., HURTÍK, J.: Simulation and evaluation of a probabilistic traveling salesman problem. In: Proceedings of the conference Transcom 2003, ®ilina
- PELIKÁN, J.: A modified insert algorithm for the probabilistic traveling salesman problem. In: Proceedings of the 8th International Scientific Conference Quantitative Methods in Economy and Business-Methodology and Practice in the New Millenium, Bratislava September 18-20, 2002, pp.634-638
- PE©KO, ©., HURTÍK, J.: Solving TSP via SQL queries. In: Proceedings of the conference Quantitative Methods in Economics (Multiple Criteria Decision Making XI), Nitra December 5-6, 2002, pp.194-197
- PE©KO, ©.: The pyramid method for traveling salesman problem (in slovak). Communications, 2000, No. 4, pp. 29-34 Go to original source...
This is an open access article distributed under the terms of the Creative Commons Attribution 4.0 International License (CC BY 4.0), which permits use, distribution, and reproduction in any medium, provided the original publication is properly cited. No use, distribution or reproduction is permitted which does not comply with these terms.