Diversified local search strategy under scatter search framework for the probabilistic traveling salesman problem

This paper focuses on introducing a concept of diversified local search strategy under the scatter search framework for the probabilistic traveling salesman problem (PTSP). Different combinations of three commonly used local search methods in the PTSP, i.e., 1-shift, 2-opt, and 3-opt, were used to investigate its effects. A set of numerical experiments were conducted to test the validity of the proposed strategy based on randomly generated test instances. The numerical results and the permutation test showed that the diversified local search strategy, especially by combining 1-shift and 2-opt algorithms, can most effectively solve the homogeneous and heterogeneous PTSP in most of the tested instances in comparison with the single local search strategy under scatter search framework.     

Expanding neighborhood search–GRASP for the probabilistic traveling salesman problem

The Probabilistic Traveling Salesman Problem is a variation of the classic traveling salesman problem and one of the most significant stochastic routing problems. In probabilistic traveling salesman problem only a subset of potential customers need to be visited on any given instance of the problem. The number of customers to be visited each time is a random variable. In this paper, a variant of the well-known Greedy Randomized Adaptive Search Procedure (GRASP), the Expanding Neighborhood Search–GRASP, is proposed for the solution of the probabilistic traveling salesman problem. expanding neighborhood search–GRASP has been proved to be a very efficient algorithm for the solution of the traveling salesman problem. The proposed algorithm is tested on a numerous benchmark problems from TSPLIB with very satisfactory results. Comparisons with the classic GRASP algorithm and with a Tabu Search algorithm are also presented. Also, a comparison is performed with the results of a number of implementations of the Ant Colony Optimization algorithm from the literature and in six out of ten cases the proposed algorithm gives a new best solution.     

Efficient local search algorithms for known and new neighborhoods for the generalized traveling salesman problem

The generalized traveling salesman problem (GTSP) is a well-known combinatorial optimization problem with a host of applications. It is an extension of the Traveling Salesman Problem (TSP) where the set of cities is partitioned into so-called clusters, and the salesman has to visit every cluster exactly once.     

Extension of the 2-p-opt and 1-shift algorithms to the heterogeneous probabilistic traveling salesman problem

The probabilistic traveling salesman problem is a well known problem that is quite challenging to solve. It involves finding the tour with the lowest expected cost for customers that will require a visit with a given probability. There are several proposed algorithms for the homogeneous version of the problem, where all customers have identical probability of being realized. From the literature, the most successful approaches involve local search procedures, with the most famous being the 2-p-opt and 1-shift procedures proposed by Bertsimas [D.J. Bertsimas, L. Howell, Further results on the probabilistic traveling salesman problem, European Journal of Operational Research 65 (1) (1993) 68–95]. Recently, however, evidence has emerged that indicates the equations offered for these procedures are not correct, and even when corrected, the translation to the heterogeneous version of the problem is not simple. In this paper we extend the analysis and correction to the heterogeneous case. We derive new expressions for computing the cost of 2-p-opt and 1-shift local search moves, and we show that the neighborhood of a solution may be explored in O(n²) time, the same as for the homogeneous case, instead of O(n³) as first reported in the literature.     

A threshold accepting heuristic with intense local search for the solution of special instances of the traveling salesman problem

In real life scheduling, variations of the standard traveling salesman problem are very often encountered. The aim of this work is to present a new heuristic method for solving three such special instances with a common approach. The proposed algorithm uses a variant of the threshold accepting method, enhanced with intense local search, while the candidate solutions are produced through an insertion heuristic scheme. The main characteristic of the algorithm is that it does not require modifications and parameter tuning in order to cope with the three different problems. Computational results on a variety of real life and artificial problems are presented at the end of this work and prove the efficiency and the ascendancy of the proposed method over other algorithms found in the literature.     

Different initial solution generators in genetic algorithms for solving the probabilistic traveling salesman problem

The probabilistic traveling salesman problem (PTSP) is a topic of theoretical and practical importance in the study of stochastic network problems. It provides researchers with a modeling framework for exploring the stochastic effects in routing problems. This paper proposed three initial solution generators (NN1, NN2, RAN) under a genetic algorithm (GA) framework for solving the PTSP. A set of numerical experiments based on heterogeneous and homogeneous PTSP instances were conducted to test the effectiveness and efficiency of the proposed algorithms. The results from the heterogeneous PTSP show that the average E[τ] values obtained by the three generators under a GA framework are similar to those obtained by the “Previous Best,” but with an average computation time saving of 50.2%. As for the homogeneous PTSP instances, NN1 is a relatively better generator among the three examined, while RAN consistently performs worse than the other two generators in terms of average E[τ] values. Additionally, as compared to previously reported studies, no one single algorithm consistently outperformed the others across all homogeneous PTSP instances in terms of the best E[τ] values. The fact that no one initial solution generator consistently performs best in terms of the E[τ] value obtained across all instances in heterogeneous cases, and that the performance of each examined algorithm is dependent on the number of nodes (n) and probability (p) for homogeneous cases, suggest the possibility of context-dependent phenomenon. Finally, to obtain valid results, researchers are advised to include at least a certain amount of test instances with the same combination of n and p when conducting PTSP experiments.     

Genetic algorithm for asymmetric traveling salesman problem with imprecise travel times

This paper presents a variant of the asymmetric traveling salesman problem (ATSP) in which the traveling time between each pair of cities is represented by an interval of values (wherein the actual travel time is expected to lie) instead of a fixed (deterministic) value as in the classical ATSP. Here the ATSP (with interval objective) is formulated using the usual interval arithmetic. To solve the interval ATSP (I-ATSP), a genetic algorithm with interval valued fitness function is proposed. For this purpose, the existing revised definition of order relations between interval numbers for the case of pessimistic decision making is used. The proposed algorithm is based on a previously published work and includes some new features of the basic genetic operators. To analyze the performance and effectiveness of the proposed algorithm and different genetic operators, computational studies of the proposed algorithm on some randomly generated test problems are reported.     

A general variable neighborhood search for the one-commodity pickup-and-delivery travelling salesman problem

We present a variable neighborhood search approach for solving the one-commodity pickup-and-delivery travelling salesman problem. It is characterized by a set of customers such that each of the customers either supplies (pickup customers) or demands (delivery customers) a given amount of a single product, and by a vehicle, whose given capacity must not be exceeded, that starts at the depot and must visit each customer only once. The objective is to minimize the total length of the tour. Thus, the considered problem includes checking the existence of a feasible travelling salesman’s tour and designing the optimal travelling salesman’s tour, which are both NP-hard problems. We adapt a collection of neighborhood structures, k-opt, double-bridge and insertion operators mainly used for solving the classical travelling salesman problem. A binary indexed tree data structure is used, which enables efficient feasibility checking and updating of solutions in these neighborhoods. Our extensive computational analysis shows that the proposed variable neighborhood search based heuristics outperforms the best-known algorithms in terms of both the solution quality and computational efforts. Moreover, we improve the best-known solutions of all benchmark instances from the literature (with 200 to 500 customers). We are also able to solve instances with up to 1000 customers.     

A tabu search heuristic using genetic diversification for the clustered traveling salesman problem

The clustered traveling salesman problem is an extension of the classical traveling salesman problem where the set of vertices is partitioned into clusters. The objective is to find a least cost Hamiltonian cycle such that the vertices of each cluster are visited contiguously and the clusters are visited in a prespecified order. A tabu search heuristic is proposed to solve this problem. This algorithm periodically restarts its search by merging two elite solutions to form a new starting solution (in a manner reminiscent of genetic algorithms). Computational results are reported on sets of Euclidean problems with different characteristics.     

Iterative patching and the asymmetric traveling salesman problem

Although Branch-and-Bound (BnB) methods are among the most widely used techniques for solving hard problems, it is still a challenge to make these methods smarter. In this paper, we investigate iterative patching, a technique in which a fixed patching procedure is applied at each node of the BnB search tree for the Asymmetric Traveling Salesman Problem. Computational experiments show that iterative patching results in general in search trees that are smaller than the classical BnB trees, and that solution times are lower for usual random and sparse instances. Furthermore, it turns out that, on average, iterative patching with the Contract-or-Patch procedure of Glover, Gutin, Yeo and Zverovich (2001) and the Karp–Steele procedure are the fastest, and that ‘iterative’ Modified Karp–Steele patching generates the smallest search trees.     

Thermodynamical approach to the traveling salesman problem: An efficient simulation algorithm

We present a Monte Carlo algorithm to find approximate solutions of the traveling salesman problem. The algorithm generates randomly the permutations of the stations of the traveling salesman trip, with probability depending on the length of the corresponding route. Reasoning by analogy with statistical thermodynamics, we use the probability given by the Boltzmann-Gibbs distribution. Surprisingly enough, using this simple algorithm, one can get very close to the optimal solution of the problem or even find the true optimum. We demonstrate this on several examples.We conjecture that the analogy with thermodynamics can offer a new insight into optimization problems and can suggest efficient algorithms for solving them.The author acknowledges stimulating discussions with J. Piút concerning the main ideas of the present paper. The author is also indebted to P. Brunovský, J. erný, M. Hamala, . Peko, . Znám, and R. Zajac for useful comments.     

An ensemble of discrete differential evolution algorithms for solving the generalized traveling salesman problem

In this paper, an ensemble of discrete differential evolution algorithms with parallel populations is presented. In a single populated discrete differential evolution (DDE) algorithm, the destruction and construction (DC) procedure is employed to generate the mutant population whereas the trial population is obtained through a crossover operator. The performance of the DDE algorithm is substantially affected by the parameters of DC procedure as well as the choice of crossover operator. In order to enable the DDE algorithm to make use of different parameter values and crossover operators simultaneously, we propose an ensemble of DDE (eDDE) algorithms where each parameter set and crossover operator is assigned to one of the parallel populations. Each parallel parent population does not only compete with offspring population generated by its own population but also the offspring populations generated by all other parallel populations which use different parameter settings and crossover operators. As an application area, the well-known generalized traveling salesman problem (GTSP) is chosen, where the set of nodes is divided into clusters so that the objective is to find a tour with minimum cost passing through exactly one node from each cluster. The experimental results show that none of the single populated variants was effective in solving all the GTSP instances whereas the eDDE performed substantially better than the single populated variants on a set of problem instances. Furthermore, through the experimental analysis of results, the performance of the eDDE algorithm is also compared against the best performing algorithms from the literature. Ultimately, all of the best known averaged solutions for larger instances are further improved by the eDDE algorithm.     

New tighter polynomial length formulations for the asymmetric traveling salesman problem with and without precedence constraints

We propose a new formulation for the asymmetric traveling salesman problem, with and without precedence relationships, which employs a polynomial number of subtour elimination constraints that imply an exponential subset of certain relaxed Dantzig-Fulkerson-Johnson subtour constraints. Promising computational results are presented, particularly in the presence of precedence constraints.     

Decision diagrams for solving traveling salesman problems with pickup and delivery in real time

The Traveling Salesman Problem with Pickup and Delivery seeks a minimum cost path with pickups preceding deliveries. It is important in on-demand last-mile logistics, such as ride sharing and meal delivery. We examine the use of low-width Decision Diagrams in a branch-and-bound with and without Assignment Problem inference duals as a primal heuristic for finding good solutions within strict time budgets. We show these diagrams can be more effective than similarly structured hybrid Constraint Programming techniques for real-time decision making.     

New integer linear programming formulation for the traveling salesman problem with time windows: minimizing tour duration with waiting times

The travelling salesman problem, being one of the most attractive and well-studied combinatorial optimization problems, has many variants, one of which is called ‘travelling salesman problem with Time Windows (TSPTW)’. In this problem, each city (nodes, customers) must be visited within a time window defined by the earliest and the latest time. In TSPTW, the traveller has to wait at a city if he/she arrives early; thus waiting times directly affect the duration of a tour. It would be useful to develop a new model solvable by any optimizer directly. In this paper, we propose a new integer linear programming formulation having O(n²) binary variables and O(n²) constraints, where (n) equals the number of nodes of the underlying graph. The objective function is stated to minimize the total travel time plus the total waiting time. A computational comparison is made on a suite of test problems with 20 and 40 nodes. The performances of the proposed and existing formulations are analysed with respect to linear programming relaxations and the CPU times. The new formulation considerably outperforms the existing one with respect to both the performance criteria. Adaptation of our formulation to the multi-traveller case and some additional restrictions for special situations are illustrated.     

Decomposition and local search based methods for the traveling umpire problem

The Traveling Umpire Problem (TUP) is a challenging combinatorial optimization problem based on scheduling umpires for Major League Baseball. The TUP aims at assigning umpire crews to the games of a fixed tournament, minimizing the travel distance of the umpires. The present paper introduces two complementary heuristic solution approaches for the TUP. A new method called enhanced iterative deepening search with leaf node improvements (IDLI) generates schedules in several stages by subsequently considering parts of the problem. The second approach is a custom iterated local search algorithm (ILS) with a step counting hill climbing acceptance criterion. IDLI generates new best solutions for many small and medium sized benchmark instances. ILS produces significant improvements for the largest benchmark instances. In addition, the article introduces a new decomposition methodology for generating lower bounds, which improves all known lower bounds for the benchmark instances.     

A dynamic adaptive local search algorithm for the circular packing problem

This paper studies the circular packing problem (CPP) which consists of packing n non-identical circles C_i of known radius r_i, i ∈ N = {1, … , n}, into the smallest containing circle C. The objective is to determine the coordinates (x_i, y_i) of the center of C_i, i ∈ N, as well as the radius r and center (x, y) of C. This problem, which is a variant of the two-dimensional open dimension problem, is solved using a two-step, dynamic, adaptive, local search algorithm. At each iteration, the algorithm identifies the set of potential “best local positions” of a circle C_i, i ∈ N, given the positions of the previously packed circles, and determines for each of these positions the coordinates and radius of the smallest containing circle. The “best local position” minimizes the radius of the current containing circle. That is, every time an additional circle is packed, both the center and the radius of the containing circle are dynamically updated, and the smallest containing circle is known. The experimental results reflect the good performance of the algorithm.     

An efficient genetic algorithm for the traveling salesman problem with precedence constraints

The traveling salesman problem with precedence constraints (TSPPC) is one of the most difficult combinatorial optimization problems. In this paper, an efficient genetic algorithm (GA) to solve the TSPPC is presented. The key concept of the proposed GA is a topological sort (TS), which is defined as an ordering of vertices in a directed graph. Also, a new crossover operation is developed for the proposed GA. The results of numerical experiments show that the proposed GA produces an optimal solution and shows superior performance compared to the traditional algorithms.     

Exploiting planarity in separation routines for the symmetric traveling salesman problem

At present, the most successful approach for solving large-scale instances of the Symmetric Traveling Salesman Problem to optimality is branch-and-cut. The success of branch-and-cut is due in large part to the availability of effective separation procedures; that is, routines for identifying violated linear constraints.

For two particular classes of constraints, known as comb and domino-parity constraints, it has been shown that separation becomes easier when the underlying graph is planar. We continue this line of research by showing how to exploit planarity in the separation of three other classes of constraints: subtour elimination, 2-matching and simple domino-parity constraints.