Approximate expressions for evaluating a priori solutions to the probabilistic traveling salesperson problem (PTSP) are introduced. The approximate expressions are incorporated in heuristic improvement procedures for PTSP to provide high-quality solutions with significantly reduced computational complexity compared with that for identical improvement procedures with exact solution evaluation. The link between this approximation evaluation scheme and a metaheuristic is discussed. Additionally, a progressive approximation extension is provided. Numerical experiments were conducted to assess the effectiveness of a proposed approximate evaluation expression and the progressive approximation scheme. Experimental results indicate that improvement procedures incorporated with the approximate evaluation expressions can produce solutions comparable to those of improvement procedures with exact solution evaluation with significantly reduced computational complexity. The results also show that the progressive approximation scheme is able to provide consistently improved solutions with a considerably reduced computational effort compared with that required for a similar approach that uses exact calculation of expected length.
Approximate Procedures for Probabilistic Traveling Salesperson Problem
Transportation Research Record: Journal of the Transportation Research Board
Transportation Research Record: Journal of the Transportation Research Board ; 1882 , 1 ; 27-36
2004-01-01
Article (Journal)
Electronic Resource
English
Approximate Procedures for Probabilistic Traveling Salesperson Problem
Online Contents | 2004
|Probabilistic Traveling Salesman Problem with Deadlines
Online Contents | 2008
|Probabilistic Traveling Salesman Problem with Deadlines
British Library Online Contents | 2008
|A Control Theoretic Approach to the Dubins Travelling Salesperson Problem
British Library Conference Proceedings | 2014
|