A random-key genetic algorithm for the generalized traveling salesman problem

The generalized traveling salesman problem is a variation of the well-known traveling salesman problem in which the set of nodes is divided into clusters; the objective is to find a minimum-cost tour passing through one node from each cluster. We present an effective heuristic for this problem. The method combines a genetic algorithm (GA) with a local tour improvement heuristic. Solutions are encoded using random keys, which circumvent the feasibility problems encountered when using traditional GA encodings. On a set of 41 standard test problems with symmetric distances and up to 442 nodes, the heuristic found solutions that were optimal in most cases and were within 1% of optimality in all but the largest problems, with computation times generally within 10 seconds. The heuristic is competitive with other heuristics published to date in both solution quality and computation time.     

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.     

Solving TSP by considering processing time: Meta-heuristics and fuzzy approaches

In this paper, general properties of traveling salesman problem has been illustrated, then a model has been introduced to minimize Make-span (time interval which all of jobs will be done) with considering sequence-dependence setup times and processing time. Furthermore, fuzzy sets and its characteristics are applied to a Hard-solvable traveling salesman problem with considering processing times. As it can be seen, traveling salesman problems are NP-hard, so solving problem in huge dimensions is uncontrollably manageable and in other side these kinds of problems in real-world are unavoidable, so a local search can prove their importance. (However this Meta-heuristic methods may not reveal exact optimal solution, but they yield a near-exact optimal solution in undeniable reduced computational time). Here, some of most famous local searches have been explained in their common and normal form, which are Genetic Algorithm (GA), Tabu Search (TS), Simulated Annealing (SA), Ant Colony System (ACO). In rest, a comprehensive comparison through these methods has been shown. This normality in methods structure could help the article to hold no-side-taken and acceptable judgments. In final, point methods analysis and parameter tuning are held.     

Traveling salesman games

In this paper we discuss the problem of how to divide the total cost of a round trip along several institutes among the institutes visited. We introduce two types of cooperative games—fixed-route traveling salesman games and traveling salesman games—as a tool to attack this problem. Under very mild conditions we prove that fixed-route traveling salesman games have non-empty cores if the fixed route is a solution of the classical traveling salesman problem. Core elements provide us with fair cost allocations. A traveling salesman game may have an empty core, even if the cost matrix satisfies the triangle inequality. In this paper we introduce a class of matrices defining TS-games with non-empty cores.     

The adjacency relation on the traveling salesman polytope is NP-Complete

We consider the problem of determining whether two traveling salesman tours correspond to non-adjacent vertices of the convex polytope associated with the traveling salesman problem. This problem is shown to be NP-Complete for both the symmetric and nonsymmetric traveling salesman problem. Several implications are discussed.This Research was supported by NSF Grant GK-420488, the U.S. Army Research Office-Durham under Grant DAHC04-75-G0192, and an IBM Fellowship.     

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.     

Lower Bounds for Scheduling a Single Robot in a Job-Shop Environment

We consider a single-machine scheduling problem which arises as a subproblem in a job-shop environment where the jobs have to be transported between the machines by a single transport robot. The robot scheduling problem may be regarded as a generalization of the traveling salesman problem with time windows, where additionally generalized precedence constraints (minimal time-lags) have to be respected. The objective is to determine a sequence of all nodes and corresponding starting times in the given time windows in such a way that all generalized precedence relations are respected and the sum of all traveling and waiting times is minimized.We calculate lower bounds for this problem using constraint propagation techniques and a linear programming formulation which is solved by a column generation procedure. Computational results are presented for test data arising from job-shop instances with a single transport robot and some modified traveling salesman instances.     

The time dependent traveling salesman problem: polyhedra and algorithm

The time dependent traveling salesman problem (TDTSP) is a generalization of the classical traveling salesman problem (TSP), where arc costs depend on their position in the tour with respect to the source node. While TSP instances with thousands of vertices can be solved routinely, there are very challenging TDTSP instances with less than 100 vertices. In this work, we study the polytope associated to the TDTSP formulation by Picard and Queyranne, which can be viewed as an extended formulation of the TSP. We determine the dimension of the TDTSP polytope and identify several families of facet-defining cuts. We obtain good computational results with a branch-cut-and-price algorithm using the new cuts, solving almost all instances from the TSPLIB with up to 107 vertices.     

Genetic algorithms and traveling salesman problems

A genetic algorithm (GA) with an asexual reproduction plan through a generalized mutation for an evolutionary operator is developed that can be directly applied to a permutation of n numbers for an approximate global optimal solution of a traveling salesman problem (TSP). Schema analysis of the algorithm shows that a sexual reproduction with the generalized mutation operator preserves the global convergence property of a genetic algorithm thus establishing the fundamental theorem of the GA for the algorithm. Avoiding an intermediate step of encoding through random keys to preserve crossover or permuting n and using “fixing” states for legal crossover are the chief benefits of the innovations reported in this paper. The algorithm has been applied to a number of natural and artificial problems and the results are encouraging.     

Integer programming models and linearizations for the traveling car renter problem

The traveling car renter problem (CaRS) is an extension of the classical traveling salesman problem (TSP) where different cars are available for use during the salesman’s tour. In this study we present three integer programming formulations for CaRS, of which two have quadratic objective functions and the other has quadratic constraints. The first model with a quadratic objective function is grounded on the TSP interpreted as a special case of the quadratic assignment problem in which the assignment variables refer to visitation orders. The second model with a quadratic objective function is based on the Gavish and Grave’s formulation for the TSP. The model with quadratic constraints is based on the Dantzig–Fulkerson–Johnson’s formulation for the TSP. The formulations are linearized and implemented in two solvers. An experiment with 50 instances is reported.     

A note on the prize collecting traveling salesman problem

We study the version of the prize collecting traveling salesman problem, where the objective is to find a tour that visits a subset of vertices such that the length of the tour plus the sum of penalties associated with vertices not in the tour is as small as possible. We present an approximation algorithm with constant bound. The algorithm is based on Christofides' algorithm for the traveling salesman problem as well as a method to round fractional solutions of a linear programming relaxation to integers, feasible for the original problem.Research supported in part by ONR contract N00014-90-J-1649 and NSF contract DDM-8922712.     

A location-routing problem in glass recycling

In this study, a location-routing problem encountered in glass recycling is addressed. We formulate a combined maximal covering location problem in the presence of partial coverage and selective traveling salesman problem to determine the location of bottle banks and the route of a collecting vehicle that will daily visit a number of customers and the bottle banks. We propose a nested heuristic procedure to solve the problem. The outer loop of the heuristic is based on variable neighborhood search while the inner loop solves the traveling salesman problem on the locations defined. The performance of the heuristic procedure is demonstrated with computational experimentation on instances that are both randomly generated and are taken from the literature. An application of the procedure on a case study using a geographical information system is also reported.     

A branch and bound method for the job-shop problem with sequence-dependent setup times

This paper deals with the job-shop scheduling problem with sequence-dependent setup times. We propose a new method to solve the makespan minimization problem to optimality. The method is based on iterative solving via branch and bound decisional versions of the problem. At each node of the branch and bound tree, constraint propagation algorithms adapted to setup times are performed for domain filtering and feasibility check. Relaxations based on the traveling salesman problem with time windows are also solved to perform additional pruning. The traveling salesman problem is formulated as an elementary shortest path problem with resource constraints and solved through dynamic programming. This method allows to close previously unsolved benchmark instances of the literature and also provides new lower and upper bounds.     

The symmetric quadratic traveling salesman problem

In the quadratic traveling salesman problem a cost is associated with any three nodes traversed in succession. This structure arises, e.g., if the succession of two edges represents energetic conformations, a change of direction or a possible change of transportation means. In the symmetric case, costs do not depend on the direction of traversal. We study the polyhedral structure of a linearized integer programming formulation of the symmetric quadratic traveling salesman problem. Our constructive approach for establishing the dimension of the underlying polyhedron is rather involved but offers a generic path towards proving facetness of several classes of valid inequalities. We establish relations to facets of the Boolean quadric polytope, exhibit new classes of polynomial time separable facet defining inequalities that exclude conflicting configurations of edges, and provide a generic strengthening approach for lifting valid inequalities of the usual traveling salesman problem to stronger valid inequalities for the symmetric quadratic traveling salesman problem. Applying this strengthening to subtour elimination constraints gives rise to facet defining inequalities, but finding a maximally violated inequality among these is NP-complete. For the simplest comb inequality with three teeth the strengthening is no longer sufficient to obtain a facet. Preliminary computational results indicate that the new cutting planes may help to considerably improve the quality of the root relaxation in some important applications.     

Solving symmetric vehicle routing problems asymmetrically

The vehicle routing problem can be regarded as a traveling salesman problem with additional constraints. Algorithms based on assignment relaxations provide better solutions for the symmetric traveling salesman problem if they are used on an asymmetric transformed distance matrix, as shown by Jonker et al., in a paper in Operations Research. The generalization of such a transformation to the distance matrix of symmetric vehicle routing problems is described. The approach is illustrated within a heuristic algorithm, although it can also be the basis for an exact algorithm. For a number of standard problems computational results are given, that are competitive to results of other algorithms.     

A restricted dynamic programming heuristic algorithm for the time dependent traveling salesman problem

Dynamic programming (DP) algorithms for the traveling salesman problem (TSP) can easily incorporate time dependent travel times, time windows, and precedence relationships which present difficulties for algorithms based on linear or nonlinear programming formulations and for many TSP heuristics. However, exact DP algorithms for the TSP have exponential storage and computational time requirements and can solve only very small problems. We present a restricted DP heuristic (a generalization of the nearest neighbor heuristic) that can include all the above considerations but solves much larger problems. The heuristic cannot guarantee optimality because only a userspecified specified number of partial tours is retained at each stage. In this paper, the heuristic is implemented for the time dependent traveling salesman problem and is tested on a personal computer on randomly generated problems. The quality of the solution improves, on average, as more computational time is permitted.     

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.     

Routing vehicles to minimize fuel consumption

We consider a generalization of the capacitated vehicle routing problem known as the cumulative vehicle routing problem in the literature. Cumulative VRPs are known to be a simple model for fuel consumption in VRPs. We examine four variants of the problem, and give constant factor approximation algorithms. Our results are based on a well-known heuristic of partitioning the traveling salesman tours and the use of the averaging argument.