Beam-ACO for the travelling salesman problem with time windows

Abstract

The travelling salesman problem with time windows is a difficult optimization problem that arises, for example, in logistics. This paper deals with the minimization of the travel-cost. For solving this problem, this paper proposes a Beam-ACO algorithm, which is a hybrid method combining ant colony optimization with beam search. In general, Beam-ACO algorithms heavily rely on accurate and computationally inexpensive bounding information for differentiating between partial solutions. This work uses stochastic sampling as a useful alternative. An extensive experimental evaluation on seven benchmark sets from the literature shows that the proposed Beam-ACO algorithm is currently a state-of-the-art technique for the travelling salesman problem with time windows when travel-cost optimization is concerned.

Introduction

The travelling salesman problem with time windows (TSPTW) is an important problem in logistics. More specifically, it can be used for modelling routing as well as scheduling tasks. Concerning routing, it models the problem of finding an efficient route to visit a number of customers, starting and ending at a depot, with the added difficulty that each customer must be visited within a given time window. The TSPTW can also model the problem of scheduling jobs on a single machine where the setup time of each job depends on the previous job, and each job has a release time and a deadline. In the context of the routing problem the travel cost is the objective most often minimized, whereas in the context of the scheduling problem the makespan is usually subject to optimization. In this work we focus on the routing problem under travel-cost optimization. We will henceforth refer to this problem simply as the TSPTW. The TSPTW is proven to be $\mathcal{NP}\text{-hard}$, and even finding a feasible solution is an $\mathcal{NP}\text{-complete}$ problem [1]. Moreover, the TSPTW is closely related to a number of important problems. For example, while the travelling salesman problem (TSP) is a special case of the TSPTW, the TSPTW itself can be seen as a special case of the vehicle routing problem with time windows (VRPTW) when only one vehicle is concerned.

Early works [2], [3] focused on makespan optimization. The proposed techniques are based on branch-and-bound and solve instances with up to 50 nodes. However, they are not able to handle time windows that are wide or mostly overlapping. Most later works deal with travel-cost optimization. Langevin et al. [4] considered both makespan and travel-cost optimization. They describe a two-commodity flow formulation within a branch-and-bound scheme being able to solve instances with up to 40 nodes. Dumas et al. [5] extended earlier dynamic programming approaches by using state space reduction techniques that enable the solution of instances with up to 200 customers. More recently, Ascheuer et al. [6] considered a branch-and-cut algorithm applying techniques tailored for the asymmetric TSPTW. Balas and Simonetti [7] proposed a linear-time dynamic programming algorithm for various TSP variants with precedence constraints including the TSPTW. Constraint programming has also been applied to develop exact methods [8], [9].

Because of the inherent difficulty of the TSPTW, heuristic techniques have been considered as well. Carlton and Barnes [10] developed a tabu search approach that allows the examination of infeasible neighbors through the implementation of a (static) penalty function. Gendreau et al. [11] presented a construction and post-optimization heuristic. Calvo [12] presented a construction heuristic that starts with a solution to an ad hoc assignment problem, proceeds with a greedy insertion procedure to obtain a complete solution and applies local search to further improve the solution. Recently, Ohlmann and Thomas [13] proposed a compressed annealing (CA) algorithm, a variant of simulated annealing [14] that makes use of a variable penalty method. In their excellent paper they provide an extensive comparison with previous approaches. Their approach can currently be regarded as state of the art.

In this work, we propose a Beam-ACO algorithm [15], [16] for solving the TSPTW. This algorithm results from combining the metaheuristic ant colony optimization [17] with the tree search method beam search [18]. Due to the lack of an efficient and effective lower bound, which is needed by the beam search component, we employ instead stochastic sampling [19], [20] for the evaluation of partial solutions. This paper is a significant extension of previous work [21], [22]. First, we add a sophisticated local search method for improving the solutions constructed by Beam-ACO. Second, we apply our algorithm to all benchmark sets that can be found in the literature. More specifically, we use the five benchmark sets considered by Ohlmann and Thomas [13], and additionally we consider two more benchmark sets. For each benchmark set we compare to the best available algorithms. To the best of our knowledge, this is the most comprehensive comparison of algorithms for the TSPTW to date. Apart from the extensive comparison to existing approaches, we also present a study of the influence of different algorithmic components on the performance of the algorithm. In particular, we examine the influence of the pheromone information, the effect of different degrees of stochastic sampling, and how the algorithm behavior changes when local search is incorporated.

This work is organized as follows. In Section 2 we give a technical description of the TSPTW. Section 3 introduces the Beam-ACO algorithm to tackle the TSPTW. In Section 4 we describe the experimental evaluation, and in Section 5 we offer conclusions and an outlook to future work.