Facets and valid inequalities for the time-dependent travelling salesman problem

The Time-Dependent Travelling Salesman Problem (TDTSP) is a generalization of the traditional TSP where the travel cost between two cities depends on the moment of the day the arc is travelled. In this paper, we focus on the case where the travel time between two cities depends not only on the distance between them, but also on the position of the arc in the tour. We consider two formulations proposed in the literature, we analyze the relationship between them and derive several families of valid inequalities and facets. In addition to their theoretical properties, they prove to be very effective in the context of a Branch and Cut algorithm.     

Equivalent cyclic polygon of a euclidean travelling salesman problem tour and modified formulation

Central European Journal of Operations Research - We define a geometric transformation of Euclidean Travelling Salesman Problem (TSP) tours that leads to a new formulation of the TSP. For every...     

A self-organising model for the travelling salesman problem

This work describes a new algorithm, based on a self-organising neural network approach, to solve the Travelling Salesman Problem (TSP). Firstly, various features of the available adaptive neural network algorithms for TSP are reviewed and a new algorithm is proposed. In order to investigate the performance of the algorithms, a comprehensive empirical study has been provided. The simulations, which are conducted on a series of standard data, evaluate the overall performance of this approach by comparing the results with the best known or the optimal solutions of the problems. The proposed algorithm shows significant advances in both the quality of the solution and computational effort for most of the experimental data. The deviation from the optimal solution of this algorithm was, in the worst case, around 2%. This fact indicates that the self-organising neural network may be regarded as a promising heuristic approach for optimisation problems.     

Generalized travelling salesman problem through n sets of nodes: the asymmetrical case

This paper presents an exact algorithm for a generalized version of the Travelling Salesman Problem which consists of finding the shortest Hamiltonian circuit through n clusters of nodes, in the case where the distance matrix is asymmetrical. The problem is formulated as an integer linear program. The program is then relaxed and solved by a branch and bound algorithm. computational results are reported for problems involving up to 100 nodes and 8 clusters.     

POPMUSIC for the travelling salesman problem

POPMUSIC— Partial OPtimization Metaheuristic Under Special Intensification Conditions — is a template for tackling large problem instances. This metaheuristic has been shown to be very efficient for various hard combinatorial problems such as p-median, sum of squares clustering, vehicle routing, map labelling and location routing. A key point for treating large Travelling Salesman Problem (TSP) instances is to consider only a subset of edges connecting the cities. The main goal of this article is to present how to build a list of good candidate edges with a complexity lower than quadratic in the context of TSP instances given by a general function. The candidate edges are found with a technique exploiting tour merging and the POPMUSIC metaheuristic. When these candidate edges are provided to a good local search engine, high quality solutions can be found quite efficiently. The method is tested on TSP instances of up to several million cities with different structures (Euclidean uniform, clustered, 2D to 5D, grids, toroidal distances). Numerical results show that solutions of excellent quality can be obtained with an empirical complexity lower than quadratic without exploiting the geometrical properties of the instances.     

Maximum travelling salesman problem

We present different types of techniques for designing algorithms with worst-case performances for the Maximum Travelling Salesman Problem. Supported by Byelarussian Fundamental Science Found and DAAD     

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.     

Guaranteed performance heuristics for the bottleneck travelling salesman problem

We consider constant-performance, polynomial-time, nonexact algorithms for the minimax or bottleneck version of the Travelling Salesman Problem. It is first shown that no such algorithm can exist for problems with arbitrary costs unless P = NP. However, when costs are positive and satisfy the triangle inequality, we use results pertaining to the squares of biconnected graphs to produce a polynomial-time algorithm with worst-case bound 2 and show further that, unless P = NP, no polynomial alternative can improve on this value.     

A variable neighbourhood search algorithm for the open vehicle routing problem

In the open vehicle routing problem (OVRP), the objective is to minimise the number of vehicles and then minimise the total distance (or time) travelled. Each route starts at the depot and ends at a customer, visiting a number of customers, each once, en route, without returning to the depot. The demand of each customer must be completely fulfilled by a single vehicle. The total demand serviced by each vehicle must not exceed vehicle capacity. Additionally, in one variant of the problem, the travel time of each vehicle should not exceed an upper limit.     

An Insert/Delete Heuristic for the Travelling Salesman Subset-Tour Problem with One Additional Constraint

The Travelling Salesman Subset-tour Problem (TSSP) differs from the well-known Travelling Salesman Problem (TSP) in that the salesman is not required to visit every city. Many problems, such as the prize collecting TSP, the orienteering problem, and the time constrained TSP, can be viewed as TSSPs with one additional constraint (TSSP + 1). In this paper, we present a heuristic approach for the TSSP + I class of problems. The general philosophy of our approach is to maintain tour feasibility with respect to the TSSP subproblem. This allows us to begin our approach with any TSSP tour. In each step, the insertion or deletion of a city is performed either to reduce infeasibility in the additional constraint or to improve upon the minimization objective. We present computational results that show our approach is superior to approaches using just insertion, and thus demonstrate the importance of considering the possible deletion of cities.     

Solving the discrete lotsizing and scheduling problem with sequence dependent set-up costs and set-up times using the Travelling Salesman Problem with time windows

In this paper we consider the Discrete Lotsizing and Scheduling Problem with sequence dependent set-up costs and set-up times (DLSPSD). DLSPSD contains elements from lotsizing and from job scheduling, and is known to be NP-Hard. An exact solution procedure for DLSPSD is developed, based on a transformation of DLSPSD into a Travelling Salesman Problem with Time Windows (TSPTW). TSPTW is solved by a novel dynamic programming approach due to Dumas et al. (1993). The results of a computational study show that the algorithm is the first one capable of solving DLSPSD problems of moderate size to optimality with a reasonable computational effort.     

Exact and heuristic algorithms for the Travelling Salesman Problem with Multiple Time Windows and Hotel Selection

We introduce and study the Travelling Salesman Problem with Multiple Time Windows and Hotel Selection (TSP-MTWHS), which generalises the well-known Travelling Salesman Problem with Time Windows and the recently introduced Travelling Salesman Problem with Hotel Selection. The TSP-MTWHS consists in determining a route for a salesman (eg, an employee of a services company) who visits various customers at different locations and different time windows. The salesman may require a several-day tour during which he may need to stay in hotels. The goal is to minimise the tour costs consisting of wage, hotel costs, travelling expenses and penalty fees for possibly omitted customers. We present a mixed integer linear programming (MILP) model for this practical problem and a heuristic combining cheapest insert, 2-OPT and randomised restarting. We show on random instances and on real world instances from industry that the MILP model can be solved to optimality in reasonable time with a standard MILP solver for several small instances. We also show that the heuristic gives the same solutions for most of the small instances, and is also fast, efficient and practical for large instances.     

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.     

Index policies for the maintenance of a collection of machines by a set of repairmen

A collection of M machines which deteriorate under usage is maintained by a set of R repairmen who may have other tasks to perform. Maintenance interventions will improve a machine's condition and may preempt costly breakdowns. The problem of scheduling such interventions to minimise the total expected discounted cost incurred in operating the machines over an infinite horizon is formulated as a Markov Decision Process which has the form of a restless bandit problem. We outline an approach to the development of maintenance policies based on simple machine indices in the form of a fair charge for a maintenance intervention in the machine's current state. Closed form indices are derived for two particular models. Numerical investigations demonstrate the strong performance of the derived index heuristics.     

The biobjective travelling purchaser problem

The purpose of this article is to present and solve the Biobjective Travelling Purchaser Problem, which consists in determining a route through a subset of markets in order to collect a set of products, minimizing the travel distance and the purchasing cost simultaneously. The most convenient purchase of the product in the visited markets is easily computed once the route has been determined. Therefore, this problem contains a finite set of solutions (one for each route) and the problem belongs to the field of the Biobjective Combinatorial Optimization. It is here formulated as a Biobjective Mixed Integer Linear Programming model with an exponential number of valid inequalities, and this model is used within a cutting plane algorithm to generate the set of all supported and non-supported efficient points in the objective space. A variant of the algorithm computes only supported efficient points. For each efficient point in the objective space exactly one Pareto optimal solution in the decision space is computed by solving a single-objective problem. Each of these single-objective problems, in turn, is solved by a specific branch-and-cut approach. A heuristic improvement based on saving previously generated cuts in a common cut-pool structure has also been developed with the aim of speeding up the algorithm performance. Results based on benchmark instances from literature show that the common cut-pool heuristic is very useful, and that the proposed algorithm manages to solve instances containing up to 100 markets and 200 different products. The general procedure can be extended to address other biobjective combinatorial optimization problems whenever a branch-and-cut algorithm is available to solve a single-objective linear combination of these criteria.     

An Interactive Algorithm for Vehicle Routeing for Winter — Gritting

In winter, when roads may become dangerously slippery due to frost, ice or snow, a de-icing agent (usually salt) is spread on them by a local authority for safety reasons. A gritter only needs to travel once down all those roads requiring treatment, as it can spread the salt onto both sides of the carriageway. The problem studied is how to design routes for gritters which will minimise costs. This problem is a type of Capacitated Arc Routeing Problem including consideration of multiple depot locations, limited vehicle capacities, time constraints on when roads must be gritted, roads with different priorities for gritting, the existence of one-way roads and salt-refilling locations. The objective function to be optimised depends on both the total distance travelled and the number and capacity of the gritters. A heuristic algorithm is devised with a computer program which allows user-interaction, and provides a practical tool for planning gritter routes. The model is linked to a GIS containing information on the road network for the County of Lancashire. Test results from the interactive algorithm are found to outperform another existing approach which solves the same problem.     

Kohonen maps for solving a class of location-allocation problems

Location-Allocation problems occur whenever more than one facility need be located to serve a set of demand centers and it is not known or fixed a priori their allocation to the supply centers. This paper deals with a continuous space problem in which demand centers are independently served from a given number of independent, uncapacitated supply centers. Installation costs are assumed not to depend on neither the actual location nor the actual throughput of the supply centers. Transportation costs are considered to be proportional to the square Euclidean distance travelled and a minisum criterium is adopted. The problem is recognized as identical to certain Cluster Analysis and Vector Quantization problems. Such a relationship leads to applying Kohonen Maps, which are Artificial Neural Networks capable of extracting the main features, i.e. the structure, of the input data through a self-organizing process based on local adaptation rules. This approach has previously been applied to other combinatorial problems such as the Travelling Salesperson Problem.     

Heuristics for the flow line problem with setup costs

This paper presents two new heuristics for the flowshop scheduling problem with sequence-dependent setup times (SDSTs) and makespan minimization objective. The first is an extension of a procedure that has been very successful for the general flowshop scheduling problem. The other is a greedy randomized adaptive search procedure (GRASP) which is a technique that has achieved good results on a variety of combinatorial optimization problems. Both heuristics are compared to a previously proposed algorithm based on the traveling salesman problem (TSP). In addition, local search procedures are developed and adapted to each of the heuristics. A two-phase lower bounding scheme is presented as well. The first phase finds a lower bound based on the assignment relaxation for the asymmetric TSP. In phase two, attempts are made to improve the bound by inserting idle time. All procedures are compared for two different classes of randomly generated instances. In the first case where setup times are an order of magnitude smaller than the processing times, the new approaches prove superior to the TSP-based heuristic; for the case where both processing and setup times are identically distributed, the TSP-based heuristic outperforms the proposed procedures.     

基于遗传算法的固定起讫点危险品配送路线优化

为科学选择危险品配送路线,保障运输安全,将传统TSP(Travelling SalesmanProblem)问题加以推广和延伸,建立以路段交通事故率、路侧人口密度、环境影响因子和路段运输费用为指标的固定起讫点危险品配送路线优化模型.以遗传算法基本框架为基础,引入新的遗传算子,构建了可用于实现模型的多目标遗传算法.实例仿真表明,所建模型和算法在求解固定起讫点危险品配送路线优化问题中有较好的实用性.     

Condition-based maintenance optimization considering improving prediction accuracy

Condition-based maintenance (CBM) aims to reduce maintenance cost and improve equipment reliability by effectively utilizing condition monitoring and prediction information. It is observed that the prediction accuracy often improves with the increase of the age of the component. In this research, we develop a method to quantify the remaining life prediction uncertainty considering the prediction accuracy improvement, and an effective CBM optimization approach to optimize the maintenance schedule. Any type of prognostics methods can be used, including data-driven methods, model-based methods and integrated methods, as long as the prediction method can produce the predicted failure time distribution at any given inspection point. Furthermore, we develop a numerical method to accurately and efficiently evaluate the cost of the CBM policy. The proposed approach is demonstrated using vibration monitoring data collected from pump bearings in the field as well as simulated degradation data. The proposed policy is compared with two benchmark maintenance policies and is found to be more effective.