95. The Attractor-Based Search Algorithm for Probabilistic Traveling Salesman Problem (PTSP)
Invited abstract in session WA-15: Discrete, continuous or stochastic optimization and control in networks, transportation and design 1, stream Combinatorial Optimization.
Wednesday, 8:30-10:00Room: Esther Simpson 1.08
Authors (first author is the speaker)
| 1. | Weiqi Li
|
| School of Management, University of Michigan-Flint |
Abstract
PTSP is one of the most significant stochastic networks. In PTSP, the number of cities is treated as a random variable. We wish to find an a priori tour through all cities with minimum expected cost. Designing effective and efficient algorithms for solving PTSP is challenging, since the computational complexity associated with the TSP is exacerbated by the stochastic element in data. People usually use two types of techniques for PTSP: analytical computation and empirical estimation. The analytical approach computes the cost of an a priori tour using a closed-form expression. Empirical estimation estimates the cost through Monte Carlo simulation. Our presentation introduces the attractor-based search algorithm (ABSA) to solve the PTSP, which combines local search and exhaustive search to find the best a priori tour. In the local search, all search trajectories converge to a small set of suboptimal points, called attractor. The attractor is exponentially smaller than the solution space and thus makes exhaustive search feasible. ABSA first uses a simple multi-start local search to find a set of locally optimal a priori tours through Monte Carlo simulation, and stores their edge configurations in the edge matrix – a data structure for tracking the search trajectories and for reducing the computational complexity of the search space. Then ABSA uses an exhausted search process to find the globally optimal a priori tour in the attractor again through Monte Carlo simulation.
Keywords
- Algorithms
- Combinatorial Optimization
- Global Optimization
Status: accepted
Back to the list of papers