Estimation-based metaheuristics for the probabilistic traveling salesman problem

https://doi.org/10.1016/j.cor.2009.12.005Get rights and content

Abstract

The probabilistic traveling salesman problem (PTSP) is a central problem in stochastic routing. Recently, we have shown that empirical estimation is a promising approach to devise highly effective local search algorithms for the PTSP. In this paper, we customize two metaheuristics, an iterated local search algorithm and a memetic algorithm, to solve the PTSP. This customization consists in adopting the estimation approach to evaluate the solution cost, exploiting a recently developed estimation-based local search algorithm, and tuning the metaheuristics parameters. We present an experimental study of the estimation-based metaheuristic algorithms on a number of instance classes. The results show that the proposed algorithms are highly effective and that they define a new state-of-the-art for the PTSP.

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 NP-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 V={1,2,,n} of nodes;

  • a set A={i,j:i,jV,ij} of edges, where an edge i,j connects the nodes i and j;

  • a set C={cij:i,jA} of travel costs, where cij is the cost of traversing an edge i,j; the costs are assumed to be symmetric, that is, for all pairs of nodes i,j we have cij=cji;

  • a set P={pi:iV} of probabilities, where pi 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 COMP2SYS, 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)

  • M. Birattari et al.

    Estimation-based local search for stochastic combinatorial optimization using delta evaluations: a case study in the probabilistic traveling salesman problem

    INFORMS Journal on Computing

    (2008)
  • M. Dorigo et al.

    Ant colony optimization

    (2004)
  • P. Balaprakash et al.

    Estimation-based ant colony optimization and local search for the probabilistic traveling salesman problem

    Swarm Intelligence

    (2009)
  • H.R. Lourenço et al.

    Iterated local search

  • Moscato P. On evolution, search, optimization, genetic algorithms and martial arts: towards memetic algorithms. C3P...
  • P. Moscato

    Memetic algorithms: a short introduction

  • D. Bertsimas et al.

    A priori optimization

    Operations Research

    (1990)
  • A.J. Kleywegt et al.

    The sample average approximation method for stochastic discrete optimization

    SIAM Journal on Optimization

    (2002)
  • G. Laporte et al.

    A priori optimization of the probabilistic traveling salesman problem

    Operations Research

    (1994)
  • L. Bianchi et al.

    Solving the homogeneous probabilistic travelling salesman problem by the ACO metaheuristic

  • L. Bianchi et al.

    An ant colony optimization approach to the probabilistic traveling salesman problem

  • M. Dorigo et al.

    Ant colony system: a cooperative learning approach to the traveling salesman problem

    IEEE Transactions on Evolutionary Computation

    (1997)
  • J. Branke et al.

    New ideas for applying ant colony optimization to the probabilistic TSP

  • J. Branke et al.

    Solving the probabilistic TSP with ant colony optimization

    Journal of Mathematical Modelling and Algorithms

    (2004)
  • Cited by (0)

    View full text