An Impact of Improvement-Exchange Heuristics to Quality of Probabilistic TSP Solution
An Impact of Improvement-Exchange Heuristics to Quality of Probabilistic TSP Solution

Summary/Abstract: 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.

• Details
• Contents