Multiple pickup and delivery traveling salesman problem with last-in-first-out loading and distance constraints

We extend the traveling salesman problem with pickup and delivery and LIFO loading (TSPPDL) by considering two additional factors, namely the use of multiple vehicles and a limitation on the total distance that a vehicle can travel; both of these factors occur commonly in practice. We call the resultant problem the multiple pickup and delivery traveling salesman problem with LIFO loading and distance constraints (MTSPPD-LD). This paper presents a thorough preliminary investigation of the MTSPPD-LD. We propose six new neighborhood operators for the problem that can be used in search heuristics or meta-heuristics. We also devise a two-stage approach for solving the problem, where the first stage focuses on minimizing the number of vehicles required and the second stage minimizes the total travel distance. We consider two possible approaches for the first stage (simulated annealing and ejection pool) and two for the second stage (variable neighborhood search and probabilistic tabu search). Our computational results serve as benchmarks for future researchers on the problem.     

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.     

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 composite-neighborhood tabu search approach to the traveling tournament problem

The Traveling Tournament Problem (TTP) is a combinatorial problem that combines features from the traveling salesman problem and the tournament scheduling problem. We propose a family of tabu search solvers for the solution of TTP that make use of complex combination of many neighborhood structures. The different neighborhoods have been thoroughly analyzed and experimentally compared. We evaluate the solvers on three sets of publicly available benchmarks and we show a comparison of their outcomes with previous results presented in the literature. The results show that our algorithm is competitive with those in the literature.     

Further Extension of the TSP Assign Neighborhood

We introduce a new extension of Punnen's exponential neighborhood for the traveling salesman problem (TSP). In contrast to an interesting generalization of Punnen's neighborhood by De Franceschi, Fischetti, and Toth (2005), our neighborhood is searchable in polynomial time, a feature that invites exploitation by heuristic and metaheuristic procedures for the TSP and related problems, including those of De Franceschi, Fischetti, and Toth (2005) for the vehicle routing problem. Research of GG was partially supported by Leverhulme Trust and by the IST Programme of the European Community, under the PASCAL Network of Excellence, IST-2002–506778.     

The tree representation for the pickup and delivery traveling salesman problem with LIFO loading

The feasible solutions of the traveling salesman problem with pickup and delivery (TSPPD) are commonly represented by vertex lists. However, when the TSPPD is required to follow a policy that loading and unloading operations must be performed in a last-in-first-out (LIFO) manner, we show that its feasible solutions can be represented by trees. Consequently, we develop a novel variable neighborhood search (VNS) heuristic for the TSPPD with last-in-first-out loading (TSPPDL) involving several search operators based on the tree data structure. Extensive experiments suggest that our VNS heuristic is superior to the current best heuristics for the TSPPDL in terms of solution quality, while requiring no more computing time as the size of the problem increases.     

General variable neighborhood search for the uncapacitated single allocation <Emphasis Type="Italic">p</Emphasis>-hub center problem

In this paper we propose a general variable neighborhood search heuristic for solving the uncapacitated single allocation p-hub center problem (USApHCP). For the local search step we develop a nested variable neighborhood descent strategy. The proposed approach is tested on benchmark instances from the literature and found to outperform the state-of-the-art heuristic based on ant colony optimization. We also test our heuristic on large scale instances that were not previously considered as test instances for the USApHCP. Moreover, exact solutions were reached by our GVNS for all instances where optimal solutions are known.     

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.     

On dominance-based multiobjective local search: design, implementation and experimental analysis on scheduling and traveling salesman problems

This paper discusses simple local search approaches for approximating the efficient set of multiobjective combinatorial optimization problems. We focus on algorithms defined by a neighborhood structure and a dominance relation that iteratively improve an archive of nondominated solutions. Such methods are referred to as dominance-based multiobjective local search. We first provide a concise overview of existing algorithms, and we propose a model trying to unify them through a fine-grained decomposition. The main problem-independent search components of dominance relation, solution selection, neighborhood exploration and archiving are largely discussed. Then, a number of state-of-the-art and original strategies are experimented on solving a permutation flowshop scheduling problem and a traveling salesman problem, both on a two- and a three-objective formulation. Experimental results and a statistical comparison are reported in the paper, and some directions for future research are highlighted.     

Quality inspection scheduling for multi-unit service enterprises

The traveling salesman problem is a classic NP-hard problem used to model many production and scheduling problems. The problem becomes even more difficult when additional salesmen are added to create a multiple traveling salesman problem (MTSP). We consider a variation of this problem where one salesman visits a given set of cities in a series of short trips. This variation is faced by numerous franchise companies that use quality control inspectors to ensure properties are maintaining acceptable facility and service levels. We model an actual franchised hotel chain using traveling quality inspectors to demonstrate the technique. The model is solved using a commercially available genetic algorithm (GA) tool as well as a custom GA program. The custom GA is proven to be an effective method of solving the proposed model.     

A new extension principle algorithm for the traveling salesman problem

In this paper, an algorithm for solving the asymmetric traveling salesman problem is developed and tested by computation. This algorithm is based on the extension principle by Schoch and uses the assignment problem relaxation of the traveling salesman problem for computing lower bounds. Computational experience with randomly generated test problems indicate that the present algorithm yields good results in runtime which are comparable with the results of Smith/Srinivasan/Thompson. Computational experience are reported for up to 120-node problems with uniformly distributed and approximately normally distributed cost.     

Discrete particle swarm optimization for the team orienteering problem

Orienteering problem is a well researched routing problem which is a generalization of the traveling salesman problem. Team orienteering problem (TOP) is the extended version of the orienteering problem with more than one member in the team. In this paper the first known discrete particle swarm optimization (DPSO) algorithm has been developed for 2, 3 and 4-member TOP. In the DPSO meta-heuristic novel methods have been introduced for the initial particle generation process. Reduced variable neighborhood search and 2-opt were applied as the local search tools. The efficacy of the algorithm was tested using seven commonly used benchmark problem sets ranging in size from 21 to 102 nodes. The results of the DPSO algorithm were compared against seven other heuristic algorithms that have been developed for TOP. It was concluded that the developed DPSO algorithm for the TOP is competitive and robust across the benchmark problem sets.     

On single courier problem

A new set of NP problems defined as Courier Problems that is motivated from the requirements in railway wagon scheduling is proposed. The general version includes many mobile couriers. The simplest version of this will consider a single courier. An algorithm to transform the single courier problem into a traveling salesman problem is presented.     

An improved approach to attribute reduction with ant colony optimization

Attribute reduction problem (ARP) in rough set theory (RST) is an NPhard one, which is difficult to be solved via traditionally analytical methods. In this paper, we propose an improved approach to ARP based on ant colony optimization (ACO) algorithm, named the improved ant colony optimization (IACO). In IACO, a new state transition probability formula and a new pheromone traps updating formula are developed in view of the differences between a traveling salesman problem and ARP. The experimental results demonstrate that IACO outperforms classical ACO as well as particle swarm optimization used for attribute reduction.     

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.     

The multi-commodity one-to-one pickup-and-delivery traveling salesman problem

This paper concerns a generalization of the traveling salesman problem (TSP) called multi-commodity one-to-one pickup-and-delivery traveling salesman problem (m-PDTSP) in which cities correspond to customers providing or requiring known amounts of m different commodities, and the vehicle has a given upper-limit capacity. Each commodity has exactly one origin and one destination, and the vehicle must visit each customer exactly once. The problem can also be defined as the capacitated version of the classical TSP with precedence constraints. This paper presents two mixed integer linear programming models, and describes a decomposition technique for each model to find the optimal solution. Computational experiments on instances from the literature and randomly generated compare the techniques and show the effectiveness of our implementation.     

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.     

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.     

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.     

A comparison of lower bounds for the symmetric circulant traveling salesman problem

When the matrix of distances between cities is symmetric and circulant, the traveling salesman problem (TSP) reduces to the so-called symmetric circulant traveling salesman problem (SCTSP), that has applications in the design of reconfigurable networks, and in minimizing wallpaper waste. The complexity of the SCTSP is open, but conjectured to be NP-hard, and we compare different lower bounds on the optimal value that may be computed in polynomial time. We derive a new linear programming (LP) relaxation of the SCTSP from the semidefinite programming (SDP) relaxation in [E. de Klerk, D.V. Pasechnik, R. Sotirov, On semidefinite programming relaxation of the traveling salesman problem, SIAM Journal of Optimization 19 (4) (2008) 1559-1573]. Further, we discuss theoretical and empirical comparisons between this new bound and three well-known bounds from the literature, namely the Held-Karp bound [M. Held, R.M. Karp, The traveling salesman problem and minimum spanning trees, Operations Research 18 (1970) 1138-1162], the 1-tree bound, and the closed-form bound for SCTSP proposed in [J.A.A. van der Veen, Solvable cases of TSP with various objective functions, Ph.D. Thesis, Groningen University, The Netherlands, 1992].