Competitive travelling salesmen problem: A hyper-heuristic approach

We introduce a novel variant of the travelling salesmen problem and propose a hyper-heuristic methodology in order to solve it. In a competitive travelling salesmen problem (CTSP), m travelling salesmen are to visit n cities and the relationship between the travelling salesmen is non-cooperative. The salesmen will receive a payoff if they are the first one to visit a city and they pay a cost for any distance travelled. The objective of each salesman is to visit as many unvisited cities as possible, with a minimum travelling distance. Due to the competitive element, each salesman needs to consider the tours of other salesman when planning their own tour. Since equilibrium analysis is difficult in the CTSP, a hyper-heuristic methodology is developed. The model assumes that each agent adopts a heuristic (or set of heuristics) to choose their moves (or tour) and each agent knows that the moves/tours of all agents are not necessarily optimal. The hyper-heuristic consists of a number of low-level heuristics, each of which can be used to create a move/tour given the heuristics of the other agents, together with a high-level heuristic that is used to select from the low-level heuristics at each decision point. Several computational examples are given to illustrate the effectiveness of the proposed approach.     

Submodularity and the traveling salesman problem

In this paper we investigate the relationship between traveling salesman tour lengths and submodular functions. This work is motivated by the one warehouse multi-retailer inventory/distribution problem with traveling salesman tour vehicle routing costs. Our goal is to find a submodular function whose values are close to those of optimal tour lengths through a central warehouse and a group of retailers. Our work shows that a submodular approximation to traveling salesman tour lengths whose error is bounded by a constant does not exist. However, we present heuristics that have errors which grow slowly with the number of retailers for the traveling salesman problem in the Euclidean plane. Furthermore, we perform computational tests that show that our submodular approximations of traveling salesman tour lengths have smaller errors than our theoretical worst case analysis would lead us to believe.     

Heuristic for the Asymmetric Travelling Salesman Problem

The paper describes a heuristic algorithm for the asymmetric travelling salesman problem. The procedure is a generalization of Webb's Simple Loss 1 Method and is of the sequential type, i.e. in each step one link of the tour is fixed. The method proved to produce "high quality" near optimal solutions in a computing time, which only grows proportional to n^1.82.     

Minmax earliness–tardiness costs with unit processing time jobs

The problem addressed in this paper is defined by M parallel identical machines, N jobs with identical (unit) processing time, job-dependent weights, and a common due-date for all jobs. The objective is of a minmax type, i.e. we are interested in minimizing the cost of the worst scheduled job. In the case of a non-restrictive (i.e., sufficiently large) common due-date, the problem is shown to have a solution that is polynomial in the number of jobs. The solution in the case of a restrictive due-date remains polynomial in the number of jobs, but is exponential in the number of machines. We introduce a lower bound on the optimal cost and an efficient heuristic. We show that the worst case relative error of the heuristic is bounded by 2 and that this bound is tight. We also prove that the heuristic is asymptotically optimal under very general assumptions. Finally, we provide an extensive numerical study demonstrating that in most cases the heuristic performs extremely well.     

Minisum location of a travelling salesman on simple networks

In this paper, we study the travelling salesman location problem on simple networks. The problem is to find the optimal home location of the salesman (e.g., a repair unit) that in each working day, must visit all the customers that require service. The number of customers as well as their location can change from day to day. In simple networks, each link belongs to at most one cycle. The paper includes O(n) algorithms for several types of simple networks and thus, avoids the calculation of 2ⁿ − 1 probabilities for each possible tour that may occur (customers are located at n nodesof the network).     

Rotation cycle schedulings for multi-item production systems

Consider the production planning and scheduling on a single machine with finite constant production rate over a planning horizon N. For single-item production problem, we have characterised the structure of the optimal solution when N approaches to infinity. This result suggests a near optimal solution when the planning horizon N is large. For multi-item production problem, we restrict our analysis on the Rotation Cycle policies. Under the assumptions of the policy, we convert the problem into a generalised travelling salesman problem and hence a branch and bound algorithm is proposed to solve the problem. For a given error bound of the solution, the algorithm can be further simplified to determine a near-optimal rotation cycle.     

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.     

Maximizing the profit per unit of time for the TSP with convex resource-dependent travelling times

This paper introduces a new problem that is an extension of the travelling salesman problem (TSP) in which the travelling times are resource dependent and the objective is to maximize the profit per unit of time. We present an optimal solution approach comprised of three main steps: (1) calculating the optimal amount of total resource required (regardless of the selected tour); (2) constructing the tour; and (3) assigning the optimal resource to each connection between vertices using the equivalent load method. This solution approach finds the optimal solution with the same computational complexity for solving the classic TSP.     

Tabu search for solving the black-and-white travelling salesman problem

The black-and-white travelling salesman problem (BWTSP) is an extension to the well-known TSP by partitioning the set of vertices into black and white vertices, and imposing cardinality and length constraints between two consecutive black vertices in a Hamiltonian tour. BWTSP has various applications in aircraft routing, telecommunication network design and logistics. In this paper, we develop several tabu search (TS) heuristics for solving the BWTSP. Our TS is built upon a new efficient neighbourhood structure, which exploits both the permutation and knapsack features of BWTSP. We also embed our TS as a heuristic procedure to improve the upper bound in a mixed-integer linear programming method. Extensive computational experiment on both benchmark and randomly generated instances shows effectiveness and efficiency of our algorithms. Our algorithms are able to obtain optimal and near optimal solutions to small instances in seconds, and find feasible solutions to large instances that have not been solved by the existing methods in the literature.     

A heuristic for vehicle fleet mix problem using tabu search and set partitioning

The vehicle fleet mix problem is a special case of the vehicle routing problem where customers are served by a heterogeneous fleet of vehicles with various capacities. An efficient heuristic for determining the composition of a vehicle fleet and travelling routes was developed using tabu search and by solving set partitioning problems. Two kinds of problems have appeared in the literature, concerning fixed cost and variable cost, and these were tested for evaluation. Initial solutions were found using the modified sweeping method. Whenever a new solution in an iteration of the tabu search was obtained, optimal vehicle allocation was performed for the set of routes, which are constructed from the current solution by making a giant tour. Experiments were performed for the benchmark problems that appeared in the literature and new best-known solutions were found.     

Total flowtime and makespan for a no-wait <Emphasis Type="Italic">m</Emphasis>-machine flowshop with set-up times separated

This paper addresses the m-machine no-wait flowshop problem where the set-up time of a job is separated from its processing time. The performance measures considered are the total flowtime and makespan. The scheduling problem for makespan reduces to the travelling salesman problem (TSP), and the scheduling problem for total flowtime reduces to the time-dependent travelling salesman problem (TDTSP). Non-polynomial time solution methods are presented, along with a polynomial heuristic.     

Variable neighborhood search for the travelling deliveryman problem

A travelling deliveryman needs to find a tour such that the total waiting time of all the customers he has to visit is minimum. The deliveryman starts his tour at a depot, travelling at constant velocity. In this paper we suggest a general variable neighborhood search based heuristic to solve this NP-hard combinatorial optimization problem. We combine several classical neighborhood structures and design data structure to store and update the incumbent solution efficiently. In this way, we are able to explore neighborhoods as efficiently as when solving the travelling salesman problem. Computational results obtained on usual test instances show that our approach outperforms recent heuristics from the literature.     

An iterated local search heuristic for the capacitated prize-collecting travelling salesman problem

This paper considers a variant of the travelling salesman problem named the capacitated prize-collecting travelling salesman problem (CPCTSP), which is derived from the colour-coating production scheduling in a cold rolling mill. The objective of the CPCTSP is to minimize the travel cost and the penalties paid for unvisited customers in such a way that a sufficiently large prize is collected and the demand of the visited customers does not exceed the salesman's capacity. For this problem, we propose an iterated local search (ILS) heuristic adopting guided kick and enhanced dynasearch. The experimental results on randomly generated instances show that the proposed heuristic outperforms the improved tabu search algorithm using frequency-based memory, and the further experimental results on instances collected from real colour-coating production also show that the proposed ILS algorithm is more effective and efficient than the currently adopted manual scheduling method.     

Worst-case analysis of two travelling salesman heuristics

In this paper we analyze the worst-case performance of some heuristics for the symmetric travelling salesman problem. We show that the worst-case ratios of tour length produced by the savings and greedy heuristics to that of a minimum tour are bounded by [log₂n]+1 and 0.5([log₂n]+1) respectively, where n is the number of cities.     

Worst case analysis of Max-Regret,Greedy and other heuristics for Multidimensional Assignment and Traveling Salesman Problems

Optimization heuristics are often compared with each other to determine which one performs best by means of worst-case performance ratio reflecting the quality of returned solution in the worst case. The domination number is a complement parameter indicating the quality of the heuristic in hand by determining how many feasible solutions are dominated by the heuristic solution. We prove that the Max-Regret heuristic introduced by Balas and Saltzman (Oper. Res. 39:150–161, 1991) finds the unique worst possible solution for some instances of the s-dimensional (s≥3) assignment and asymmetric traveling salesman problems of each possible size. We show that the Triple Interchange heuristic (for s=3) also introduced by Balas and Saltzman and two new heuristics (Part and Recursive Opt Matching) have factorial domination numbers for the s-dimensional (s≥3) assignment problem.     

A multi-space sampling heuristic for the vehicle routing problem with stochastic demands

The vehicle routing problem with stochastic demands consists in designing transportation routes of minimal expected cost to satisfy a set of customers with random demands of known probability distributions. This paper proposes a simple yet effective heuristic approach that uses randomized heuristics for the traveling salesman problem, a tour partitioning procedure, and a set partitioning formulation to sample the solution space and find high-quality solutions for the problem. Computational experiments on benchmark instances from the literature show that the proposed approach is competitive with the state-of-the-art algorithm for the problem in terms of both accuracy and efficiency. In experiments conducted on a set of 40 instances, the proposed approach unveiled four new best-known solutions (BKSs) and matched another 24. For the remaining 12 instances, the heuristic reported average gaps with respect to the BKS ranging from 0.69 to 0.15 % depending on its configuration.     

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.     

On the solutions of stochastic traveling salesman problems

We consider the n-city traveling salesman problem where the distances between the cities are nondeterministic. Our purpose is to estimate the expectation of the length of the optimal tour. This is done by calculating the expectations of a lower bound and an upper bound for the length of the optimal tour. Because the upper bound is formed by the well-known nearest neighbour rule, we can simultaneously find the cases where this rule is effective in the mean. If we let the number of cities grow, we obtain symptotic results that are totally determined by the behaviour of the distribution of the distance between any two points in the neighbourhood of the distance zero.     

Lagrangean relaxation for a lower bound to a set partitioning problem with side constraints: properties and algorithms

The problem (P) addressed here is a special set partitioning problem with two additional non-trivial constraints. A Lagrangean Relaxation (LR_u) is proposed to provide a lower bound to the optimal solution to this problem. This Lagrangean relaxation is accomplished by a subgradient optimization procedure which solves at each iteration a special 0–1 knapsack problem (KP-k). We give two procedures to solve (KP-k), namely an implicity enumeration algorithm and a column generation method. The approach is promising for it provides feasible integer solutions to the side constraints that will hopefully be optimal to most of the instances of the problem (P). Properties of the feasible solutions to (KP-k) are highlighted and it is shown that the linear programming relaxation to this problem has a worst case time bound of order O(n³).     

Allocation of jobs and identical resources with two pooling centers

We examine the resource allocation problem of partitioning identical servers into two parallel pooling centers, and simultaneously assigning job types to pooling centers. Each job type has a distinct Poisson arrival rate and a distinct holding cost per unit time. Each pooling center becomes a queueing system with an exponential service time distribution. The goal is to minimize the total holding cost. The problem is shown to be polynomial if a job type can be divided between the pooling centers, and NP-hard if dividing job types is not possible. When there are two servers and jobs cannot be divided, we demonstrate that the two pooling center configuration is rarely optimal. A heuristic which checks the single pooling center has an upper bound on the relative error of 4/3. The heuristic is extended for the multiple server problem, where relative error is bounded above by the number of servers.