A tour construction heuristic for the travelling salesman problem

The tour construction heuristic that generates initial tours for the tour improvement heuristics plays an important role in solving the travelling salesman problem (TSP). With the help of an effective tour construction heuristic, the performance of a heuristic can be improved. In this study we present a new tour construction algorithm, the construction priority (CP). We incorporate the performance of the CP into metaheuristics such as tabu search, genetic algorithm, space smoothing, and noising methods. The performance of the CP is empirically compared with the nearest neighbour (NN) approach. Extensive computational comparison shows that the CP is considerably more effective compared to NN.     

The fleet size and mix problem for capacitated arc routing

There have been several attempts to solve the capacitated arc routing problem with m vehicles starting their tours from a central node. The objective has been to minimize the total distance travelled. In the problem treated here we also have the fixed costs of the vehicles included in the objective function. A set of vehicle capacities with their respective costs are used. Thus the objective function becomes a combination of fixed and variable costs. The solution procedure consists of four phases. In the first phase, a Chinese or rural postman problem is solved depending on whether all or some of the arcs in the network demand service with the objective of minimizing the total distance travelled. It results in a tour called the giant tour. In the second phase, the giant tour is partitioned into single vehicle subtours feasible with respect to the constraints. A new network is constructed with the node set corresponding to the arcs of the giant tour and with the arc set consisting of the subtours of the giant tour. The arc costs include both the fixed and variable costs of the subtours. The third phase consists of solving the shortest path problem on this new network to result in the least cost set of subtours represented on the new network. In the last phase a postprocessor is applied to the solution to improve it. The procedure is repeated for different giant tours to improve the final solution. The problem is extended to the case where there can be upper bounds on the number of vehicles with given capacities using a branch and bound method. Extension to directed networks is given. Some computational results are reported.     

Multicriteria tour planning for mobile healthcare facilities in a developing country

A multiobjective combinatorial optimization (MOCO) formulation for the following location-routing problem in healthcare management is given: For a mobile healthcare facility, a closed tour with stops selected from a given set of population nodes has to be found. Tours are evaluated according to three criteria: (i) An economic efficiency criterion related to the tour length, (ii) the criterion of average distances to the nearest tour stops corresponding to p-median location problem formulations, and (iii) a coverage criterion measuring the percentage of the population unable to reach a tour stop within a predefined maximum distance. Three algorithms to compute approximations to the set of Pareto-efficient solutions of the described MOCO problem are developed. The first uses the P-ACO technique, and the second and the third use the VEGA and the MOGA variant of multiobjective genetic algorithms, respectively. Computational experiments for the Thiès region in Senegal were carried out to evaluate the three approaches on real-world problem instances.     

Survey, Categorization, and Comparison of Recent Tour Scheduling Literature

The employee tour scheduling problem involves the determination of both work hours of the day and workdays of the week for each employee. This problem has proven difficult to solve optimally due to its large size and pure integer nature. During the last decade, numerous approaches for modeling and solving this problem have been proposed. In this paper, employee tour scheduling literature published since 1990 is reviewed and classified. Solution techniques are classified into ten categories: (1) manual solution, (2) integer programming, (3) implicit modeling, (4) decomposition, (5) goal programming, (6) working set generation, (7) LP-based solution, (8) construction and improvement, (9) metaheuristics, and (10) other methods. The objective is to identify broad classifications, present typical mathematical models, compare the different methods, and identify future research directions.     

A backbone based TSP heuristic for large instances

We introduce a reduction technique for large instances of the traveling salesman problem (TSP). This approach is based on the observation that tours with good quality are likely to share many edges. We exploit this observation by neglecting the less important tour space defined by the shared edges, and searching the important tour subspace in more depth. More precisely, by using a basic TSP heuristic, we obtain a set of starting tours. We call the set of edges which are contained in each of these starting tours as pseudo-backbone edges. Then we compute the maximal paths consisting only of pseudo-backbone edges, and transform the TSP instance to another one with smaller size by contracting each such path to a single edge. This reduced TSP instance can be investigated more intensively, and each tour of the reduced instance can be expanded to a tour of the original instance. Combining our reduction technique with the currently leading TSP heuristic of Helsgaun, we experimentally investigate 32 difficult VLSI instances from the well-known TSP homepage. In our experimental results we set world records for seven VLSI instances, i.e., find better tours than the best tours known so far (two of these world records have since been improved upon by Keld Helsgaun and Yuichi Nagata, respectively). For the remaining instances we find tours that are equally good or only slightly worse than the world record tours.     

Validating vehicle routing zone construction using Monte Carlo simulation

The primary purpose of this paper is to validate a clustering procedure used to construct contiguous vehicle routing zones (VRZs) in metropolitan regions. Given a set of customers with random demand for pickups and deliveries over the day, the goal of the design problem is to cluster the customers into zones that can be serviced by a single vehicle. Monte Carlo simulation is used to determine the feasibility of the zones with respect to package count and tour time. For each replication, a separate probabilistic traveling salesman problem (TSP) is solved for each zone. For the case where deliveries must precede pickups, a heuristic approach to the TSP is developed and evaluated, also using Monte Carlo simulation. In the testing, performance is measured by overall travel costs and the probability of constraint violations. Gaps in tour length, tour time and tour cost are the measure used when comparing exact and heuristic TSP solutions.     

混合图上最小-最大圈覆盖问题的近似算法

考虑一个混合图上的最小-最大圈覆盖问题.给定一个正整数k和一个混合加权图G=(V E,A),这里V表示顶点集,E表示边集,A表示弧集.E中的每条边和A中的每条弧关联一个权重.问题的要求是确定k个环游,使得这k个环游能够经过A中的所有弧.目标是极小化最大环游的权重.该问题是运筹学和计算机科学中一个重要的组合优化问题,它和...     

New TSP Construction Heuristics and Their Relationships to the 2-Opt

Correction heuristics for the traveling salesman problem (TSP), with the 2-Opt applied as a postprocess, are studied with respect to their tour lengths and computation times. This study analyzes the 2-Opt dependency, which indicates how the performance of the 2-Opt depends on the initial tours built by the construction heuristics. In accordance with the analysis, we devise a new construction heuristic, the recursive-selection with long-edge preference (RSL) method, which runs faster than the multiple-fragment method and produces a comparable tour when they are combined with the 2-Opt.     

On the one-commodity pickup-and-delivery traveling salesman problem with stochastic demands

This paper studies how to set the vehicle capacity for traveling Salesman Problems where some of the customer demands are stochastic. The analyses are done for the one-commodity pickup-and-delivery TSP, as this problem also includes the setting of the initial load. The paper first considers feasibility issues. This includes finding the smallest vehicle capacity and some initial load such that a given tour is feasible for all scenarios. Different variants are considered as a function of the time when information becomes available. The paper then analyzes the case where some penalties are paid for routing a tour unable to handle customer demands. Various types of penalties are considered. The paper studies properties of the minimal expected penalty of a given tour, which are then used to provide approaches to find near-optimal tours. Computational results are presented.     

Heuristics for the Stochastic Eulerian Tour Problem

The Stochastic Eulerian Tour Problem (SETP) seeks the Eulerian tour of minimum expected length on an undirected Eulerian graph, when demand on the arcs that have to be serviced is probabilistic. The SETP is NP-hard and in this paper, we develop three constructive heuristics for this problem. The first two are greedy tour construction heuristics while the third is a sub-tour concatenation heuristic. Our experimental results show that for grid networks, the sub-tour concatenation heuristic performs well when the probability of service of each edge is greater than 0.1. For Euclidean networks, as the number of edges increases, the second heuristic performs the best among the three. Also, the expected length of our overall best solution is lower than the expected length of a random tour by up to 10% on average for grid networks and up to 2% for Euclidean networks.     

Selective generalized travelling salesman problem

ABSTRACT

This paper introduces the Selective Generalized Traveling Salesman Problem (SGTSP). In SGTSP, the goal is to determine the maximum profitable tour within the given threshold of the tour’s duration, which consists of a subset of clusters and a subset of nodes in each cluster visited on the tour. This problem is a combination of cluster and node selection and determining the shortest path between the selected nodes. We propose eight mixed integer programming (MIP) formulations for SGTSP. All of the given MIP formulations are completely new, which is one of the major novelties of the study. The performance of the proposed formulations is evaluated on a set of test instances by conducting 4608 experimental runs. Overall, 4138 out of 4608 (~90%) test instances were solved optimally by using all formulations.     

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.     

A time-based formulation and upper bounding scheme for the selective travelling salesperson problem

The selective travelling salesperson problem (STSP) involves determining a tour of maximal value over a set of cities subject to a tour length constraint. The problem has the characteristic that not all cities have to be visited. An integer formulation which combines permutation variables with flow variables is presented. An upper bounding scheme for the number of nodes visited in the final solution is used to reduce the size of the integer programme. The problem is solved using an off-the-shelf mixed-integer solver called CPLEX. Results demonstrating the usefulness of the bound are presented. The methodology is also applied to solve a 15-zone fisheries surveillance problem.     

Facets of the polytope of the asymmetric travelling salesman problem with replenishment arcs

The Asymmetric Travelling Salesman Problem with Replenishment Arcs (RATSP) is a new class of problems arising from work related to aircraft routing. Given a digraph with cost on the arcs, a solution of the RATSP, like that of the Asymmetric Travelling Salesman Problem, induces a directed tour in the graph which minimises total cost. However the tour must satisfy additional constraints: the arc set is partitioned into replenishment arcs and ordinary arcs, each node has a non-negative weight associated with it, and the tour cannot accumulate more than some weight limit before a replenishment arc must be used. To enforce this requirement, constraints are needed. We refer to these as replenishment constraints.In this paper, we review previous polyhedral results for the RATSP and related problems, then prove that two classes of constraints developed in V. Mak and N. Boland [Polyhedral results and exact algorithms for the asymmetric travelling salesman problem with replenishment arcs, Technical Report TR M05/03, School of Information Technology, Deakin University, 2005] are, under appropriate conditions, facet-defining for the RATS polytope.     

Mind the gap: a heuristic study of subway tours

What is the minimum tour visiting all lines in a subway network? In this paper we study the problem of constructing the shortest tour visiting all lines of a city railway system. This combinatorial optimization problem has links with the classic graph circuit problems and operations research. A broad set of fast algorithms is proposed and evaluated on simulated networks and example cities of the world. We analyze the trade-off between algorithm runtime and solution quality. Time evolution of the trade-off is also captured. Then, the algorithms are tested on a range of instances with diverse features. On the basis of the algorithm performance, measured with various quality indicators, we draw conclusions on the nature of the above combinatorial problem and the tacit assumptions made while designing the algorithms.     

Using Benders Decomposition to Implicitly Model Tour Scheduling

This paper introduces a new integrated model for the combined days-off and shift scheduling problem (the tour scheduling problem). This model generalizes the forward and backward constraints, previously introduced by Bechtold and Jacobs for the shift scheduling problem, to the tour scheduling problem. This results in a general and compact formulation that can handle several types of scheduling flexibility. We also provide a new proof of the correctness of forward and backward constraints based on Benders decomposition. The latter approach is interesting in itself because it can be used to solve the problem when extraordinary overlap of break windows or start-time bands is present. A discussion of model size for a set of hypothetical test problems is presented to show the merits of the new formulation.     

Solving the Probabilistic TSP with Ant Colony Optimization

In this paper, we describe new ways to apply Ant Colony Optimization (ACO) to the Probabilistic Traveling Salesperson Problem (PTSP). PTSP is a stochastic extension of the well known Traveling Salesperson Problem (TSP), where each customer will require a visit only with a certain probability. The goal is to find an a priori tour visiting all customers with minimum expected length, customers not requiring a visit simply being skipped in the tour.We show that ACO works well even when only an approximative evaluation function is used, which speeds up the algorithm, leaving more time for the actual construction. As we demonstrate, this idea can also be applied successfully to other state-of-the-art heuristics. Furthermore, we present new heuristic guidance schemes for ACO, better adapted to the PTSP than what has been used previously. We show that these modifications lead to significant improvements over the standard ACO algorithm, and that the resulting ACO is at least competitive to other state-of-the-art heuristics.     

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 simulated annealing heuristic for the team orienteering problem with time windows

This paper presents a simulated annealing based heuristic approach for the team orienteering problem with time windows (TOPTW). Given a set of known locations, each with a score, a service time, and a time window, the TOPTW finds a set of vehicle tours that maximizes the total collected scores. Each tour is limited in length and a visit to a location must start within the location’s service time window. The proposed heuristic is applied to benchmark instances. Computational results indicate that the proposed heuristic is competitive with other solution approaches in the literature.     

Local search for the probabilistic traveling salesman problem: Correction to the 2-p-opt and 1-shift algorithms

The probabilistic traveling salesman problem concerns the best way to visit a set of customers located in some metric space, where each customer requires a visit only with some known probability. A solution to this problem is an a priori tour which visits all customers, and the objective is to minimize the expected length of the a priori tour over all customer subsets, assuming that customers in any given subset must be visited in the same order as they appear in the a priori tour. This problem belongs to the class of stochastic vehicle routing problems, a class which has received increasing attention in recent years, and which is of major importance in real world applications.Several heuristics have been proposed and tested for the probabilistic traveling salesman problem, many of which are a straightforward adaptation of heuristics for the classical traveling salesman problem. In particular, two local search algorithms (2-p-opt and 1-shift) were introduced by Bertsimas.In a previous report we have shown that the expressions for the cost evaluation of 2-p-opt and 1-shift moves, as proposed by Bertsimas, are not correct. In this paper we derive the correct versions of these expressions, and we show that the local search algorithms based on these expressions perform significantly better than those exploiting the incorrect expressions.