Estimation-based metaheuristics for the probabilistic traveling salesman problem
Introduction
Designing effective algorithms for stochastic routing problems is a difficult task. This is due to the element of uncertainty in the data, which increases the difficulty of finding an optimal solution in a large search space. Exact techniques can solve only small instances to optimality. This motivated researchers and practitioners to focus on metaheuristics, an important class of stochastic local search (SLS) methods [1]. Unfortunately, the literature on metaheuristics for tackling stochastic routing problems is rather underdeveloped when compared to the deterministic case, even if it is receiving increasing attention.
The probabilistic traveling salesman problem (PTSP) [2] is a central problem in stochastic routing. It is an -hard problem that has a number of practical applications not only in transportation but also in strategic planning and scheduling [3]. The PTSP is similar to the TSP, the main difference being that each node has a probability of requiring a visit. The goal is to find a TSP tour that minimizes the expected cost of the pruned tour: this pruned tour is obtained only after knowing the nodes that require being visited by skipping the nodes that do not require being visited according to some predefined rules.
Based on the way in which the expected cost is determined, optimization algorithms for the PTSP can be grouped into two classes: analytical computation algorithms, which use closed form expressions for computing the expected cost, and estimation-based algorithms, which use Monte Carlo simulation for estimating the expected cost. In this paper, we tackle the PTSP by using estimation-based metaheuristics, a goal which is a natural extension of two of our earlier research efforts. First, we developed 2.5-opt-EEais [4], [5], a new state-of-the-art iterative improvement algorithm for the PTSP that uses an estimation-based approach to compute the cost difference between two solutions. Second, we showed that the integration of two PTSP-specific algorithmic components, 2.5-opt-EEais as local search and an estimation-based approach to evaluate the solution cost of artificial ants, into an ant colony optimization (ACO) algorithm [6] is highly beneficial in terms of computation time and solution quality [7]. Here, we extend our work to metaheuristics that are known to have high performance on the related traveling salesman problem(TSP). In particular, we integrate the two PTSP-specific components into iterated local search (ILS) [8] and memetic algorithms (MAs) [9], [10]. We present an experimental study to compare the two algorithms to the recently developed estimation-based ACO algorithm and we show that for various instance classes they can improve upon it. As a control algorithm, we consider a random restart local search (RRLS) algorithm. In fact, the results show that all metaheuristics significantly outperform RRLS. A further comparison to the so far best performing analytical computation metaheuristics for the PTSP clearly establishes the estimation-based algorithms as the new state-of-the-art for the PTSP.
The paper is organized as follows. In Section 2, we describe the PTSP and its solution approaches. In Section 3, we discuss the proposed estimation-based metaheuristics. In Section 4, we evaluate their performances. In Section 5, we conclude the paper.
Section snippets
The probabilistic traveling salesman problem
An instance of the PTSP is defined on a graph G with the following elements:
- •
a set of nodes;
- •
a set of edges, where an edge connects the nodes i and j;
- •
a set of travel costs, where is the cost of traversing an edge ; the costs are assumed to be symmetric, that is, for all pairs of nodes we have ;
- •
a set of probabilities, where specifies the probability that a node i requires being visited. The events that two
Estimation-based approach
In this section, first we summarize the 2.5-opt-EEais algorithm, which is used as the underlying local search heuristic for all metaheuristics. Then, we briefly describe the implemented metaheuristics and we highlight the customizations performed to tackle the PTSP.
Experimental analysis
In this section, we present the experimental setting and the empirical results. The goal of the experiments is to assess the performance of the proposed metaheuristics and to compare them to the state-of-the-art analytical computation algorithms for the PTSP.
Conclusions
In this paper, we customized iterated local search and memetic algorithms to tackle the PTSP. The proposed customization consists in adopting an estimation-based approach to evaluate the solution cost and a state-of-the-art iterative improvement algorithm, 2.5-opt-EEais, as local search. We presented an experimental comparison of the estimation-based algorithms, in which we also included a recently developed estimation-based ant colony system. We used short and long computation times as
Acknowledgements
The authors thank Dr. Leonora Bianchi and Prof. Ann Melissa Campbell for providing the source code of pACS+1-shift and the aggregation approach, respectively. This research has been supported by , an Early Stage Training project funded by the European Commission within the Marie Curie Actions program (MEST-CT-2004-505079), and by ANTS and META-X, which are ARC projects funded by the French Community of Belgium. The authors acknowledge support from the fund for scientific research
References (49)
- et al.
Adaptive sample size and importance sampling in estimation-based local search for the probabilistic traveling salesman problem
European Journal of Operational Research
(2009) A hybrid scatter search for the probabilistic traveling salesman problem
Computers & Operations Research
(2007)Diversified local search strategy under scatter search framework for the probabilistic traveling salesman problem
European Journal of Operational Research
(2008)- et al.
A hybrid multi-swarm particle swarm optimization algorithm for the probabilistic traveling salesman problem
Computers & Operations Research
(2010) - et al.
Local search for the probabilistic traveling salesman problem: correction to the 2-p-opt and 1-shift algorithms
European Journal of Operational Research
(2005) - et al.
Extension of the 2-p-opt and 1-shift algorithms to the heterogeneous probabilistic traveling salesman problem
European Journal of Operational Research
(2007) Aggregation for the probabilistic traveling salesman problem
Computers & Operations Research
(2006)- et al.
Stochastic local search: foundations and applications
(2005) A priori solution of a travelling salesman problem in which a random subset of the customers are visited
Operations Research
(1988)- Bertsimas D. Probabilistic combinatorial optimization problems. PhD thesis, Massachusetts Institute of Technology,...