New lower bounds for online k-server routing problems

In a k-server routing problem k?1 servers move in a metric space in order to visit specified points or carry objects from sources to destinations. In the online version requests arrive online while the servers are traveling. Two classical objective functions are to minimize the makespan, i.e., the time when the last server has completed its tour (k-Traveling Salesman Problem or k-tsp) and to minimize the sum of completion times (k-Traveling Repairman Problem or k-trp). Both problems, the k-tsp and the k-trp have been studied from a competitive analysis point of view, where the cost of an online algorithm is compared to that of an optimal offline algorithm. However, the gap between the obtained competitive ratios and the corresponding lower bounds have mostly been quite large for k>1, in particular for randomized algorithms against an oblivious adversary.We reduce a number of gaps by providing new lower bounds for randomized algorithms. The most dramatic improvement is in the lower bound for the k-Dial-a-Ride-Problem (the k-trp when objects need to be carried) from to 3 which is currently also the best lower bound for deterministic algorithms.     

Algorithms for the On-Line Quota Traveling Salesman Problem

The Quota Traveling Salesman Problem is a generalization of the well-known Traveling Salesman Problem. The goal of the traveling salesman is, in this case, to reach a given quota of sales, minimizing the amount of time. In this paper we address the on-line version of the problem, where requests are given over time. We present algorithms for various metric spaces, and analyze their performance in the usual framework of competitive analysis. In particular we present a 2-competitive algorithm that matches the lower bound for general metric spaces. In the case of the halfline metric space, we show that it is helpful not to move at full speed, and this approach is also used to derive the best on-line polynomial time algorithm known so far for the On-Line TSP (in the homing version).     

A General Decomposition Theorem for the k-Server Problem

The first general decomposition theorem for the k-server problem is presented. Whereas all previous theorems are for the case of a finite metric with k+1 points, the theorem given here allows an arbitrary number of points in the underlying metric space. This theorem implies O(polylog(k))-competitive randomized algorithms for certain metric spaces consisting of a polylogarithmic number of widely separated subspaces and takes a first step toward a general O(polylog(k))-competitive algorithm. The only other cases for which polylogarithmic competitive randomized algorithms are known are the uniform metric space and the weighted cache metric space with two weights.     

Algorithms for the On-Line Travelling Salesman 1

In this paper the problem of efficiently serving a sequence of requests presented in an on-line fashion located at points of a metric space is considered. We call this problem the On-Line Travelling Salesman Problem (OLTSP). It has a variety of relevant applications in logistics and robotics. We consider two versions of the problem. In the first one the server is not required to return to the departure point after all presented requests have been served. For this problem we derive a lower bound on the competitive ratio of 2 on the real line. Besides, a 2.5 -competitive algorithm for a wide class of metric spaces, and a 7/3 -competitive algorithm for the real line are provided. For the other version of the problem, in which returning to the departure point is required, we present an optimal 2 -competitive algorithm for the above-mentioned general class of metric spaces. If in this case the metric space is the real line we present a 1.75 -competitive algorithm that compares with a \approx 1.64 lower bound. Received November 12, 1997; revised June 8, 1998.     

The traveling purchaser problem,with multiple stacks and deliveries: A branch-and-cut approach

The Double Traveling Salesman Problem with Multiple Stacks is a pickup-and-delivery single-vehicle routing problem which performs all pickup operations before the deliveries. The vehicle has a loading space divided into stacks of a fixed height that follows a Last-In-First-Out policy. It has to collect products following a Hamiltonian tour in a pickup region, and then deliver them following a Hamiltonian tour in a delivery region. The aim is to minimize the total routing cost while satisfying the vehicle loading constraints.     

The online Prize-Collecting Traveling Salesman Problem

We study the online version of the Prize-Collecting Traveling Salesman Problem (PCTSP), a generalization of the Traveling Salesman Problem (TSP). In the TSP, the salesman has to visit a set of cities while minimizing the length of the overall tour. In the PCTSP, each city has a given weight and penalty, and the goal is to collect a given quota of the weights of the cities while minimizing the length of the tour plus the penalties of the cities not in the tour. In the online version, cities are disclosed over time. We give a 7/3-competitive algorithm for the problem, which compares with a lower bound of 2 on the competitive ratio of any deterministic algorithm. We also show how our approach can be combined with an approximation algorithm in order to obtain an O(1)-competitive algorithm that runs in polynomial time.     

A traveling salesman problem with pickups and deliveries,time windows and draft limits: Case study from chemical shipping

This paper introduces and studies a real in-port ship routing and scheduling problem faced by chemical shipping companies. We show that this problem can be modeled as a Traveling Salesman Problem with Pickups and Deliveries, Time Windows and Draft Limits (TSPPD-TWDL). We propose a mathematical formulation for the TSPPD-TWDL and suggest a solution method based on forward dynamic programming (DP) to solve the problem. A set of label extension rules are also proposed to accelerate and enhance the performance of the algorithm. Computational studies show that the label extension rules are essential to the DP-algorithm, and the proposed solution method is able to solve real-sized in-port routing and scheduling problems in chemical shipping efficiently.     

Ramsey-type theorems for metric spaces with applications to online problems

A nearly logarithmic lower bound on the randomized competitive ratio for the metrical task systems problem is presented. This implies a similar lower bound for the extensively studied K-server problem. The proof is based on Ramsey-type theorems for metric spaces, that state that every metric space contains a large subspace which is approximately a hierarchically well-separated tree (and in particular an ultrametric). These Ramsey-type theorems may be of independent interest.     

Improving the space cost of <Emphasis Type="Italic">k</Emphasis>-NN search in metric spaces by using distance estimators

Similarity searching in metric spaces has a vast number of applications in several fields like multimedia databases, text retrieval, computational biology, and pattern recognition. In this context, one of the most important similarity queries is the k nearest neighbor (k-NN) search. The standard best-first k-NN algorithm uses a lower bound on the distance to prune objects during the search. Although optimal in several aspects, the disadvantage of this method is that its space requirements for the priority queue that stores unprocessed clusters can be linear in the database size. Most of the optimizations used in spatial access methods (for example, pruning using MinMaxDist) cannot be applied in metric spaces, due to the lack of geometric properties. We propose a new k-NN algorithm that uses distance estimators, aiming to reduce the storage requirements of the search algorithm. The method stays optimal, yet it can significantly prune the priority queue without altering the output of the query. Experimental results with synthetic and real datasets confirm the reduction in storage space of our proposed algorithm, showing savings of up to 80% of the original space requirement.

– Ant System

Ant System, the first Ant Colony Optimization algorithm, showed to be a viable method for attacking hard combinatorial optimization problems. Yet, its performance, when compared to more fine-tuned algorithms, was rather poor for large instances of traditional benchmark problems like the Traveling Salesman Problem. To show that Ant Colony Optimization algorithms could be good alternatives to existing algorithms for hard combinatorial optimization problems, recent research in this area has mainly focused on the development of algorithmic variants which achieve better performance than Ant System.In this paper, we present – Ant System ( ), an Ant Colony Optimization algorithm derived from Ant System. differs from Ant System in several important aspects, whose usefulness we demonstrate by means of an experimental study. Additionally, we relate one of the characteristics specific to — that of using a greedier search than Ant System — to results from the search space analysis of the combinatorial optimization problems attacked in this paper. Our computational results on the Traveling Salesman Problem and the Quadratic Assignment Problem show that is currently among the best performing algorithms for these problems.     

“The big sweep”: On the power of the wavefront approach to Voronoi diagrams

We show that the wavefront approach to Voronoi diagrams (a deterministic line-sweep algorithm that does not use geometric transform) can be generalized to distance measures more general than the Euclidean metric. In fact, we provide the first worst-case optimal (O (n logn) time,O(n) space) algorithm that is valid for the full class of what has been callednice metrics in the plane. This also solves the previously open problem of providing anO (nlogn)-time plane-sweep algorithm for arbitraryL _k -metrics. Nice metrics include all convex distance functions but also distance measures like the Moscow metric, and composed metrics. The algorithm is conceptually simple, but it copes with all possible deformations of the diagram. Research partially supported by the Natural Sciences and Engineering Research Council of Canada. Research partially supported by the Deutsche Forschungsgemeinschaft, Grant No. Kl 655/2-1.     

<Emphasis Type="Italic">k</Emphasis>-Nearest-Neighbor Clustering and Percolation Theory

Let P be a realization of a homogeneous Poisson point process in ℝ ^d with density 1. We prove that there exists a constant k _d , 1<k _d <∞, such that the k-nearest neighborhood graph of P has an infinite connected component with probability 1 when k≥k _d . In particular, we prove that k ₂≤213. Our analysis establishes and exploits a close connection between the k-nearest neighborhood graphs of a Poisson point set and classical percolation theory. We give simulation results which suggest k ₂=3. We also obtain similar results for finite random point sets. Part of the work was done while S.-H. Teng was at Xerox Palo Alto Research Center and MIT. The work of F.F. Yao was supported in part by a grant from the Research Grants Council of the Hong Kong Special Administrative Region, China [Project No. CityU 1165/04E].     

A Memetic Algorithm with a large neighborhood crossover operator for the Generalized Traveling Salesman Problem

The Generalized Traveling Salesman Problem (GTSP) is a generalization of the well-known Traveling Salesman Problem (TSP), in which the set of cities is divided into mutually exclusive clusters. The objective of the GTSP consists in visiting each cluster exactly once in a tour, while minimizing the sum of the routing costs. This paper addresses the solution of the GTSP using a Memetic Algorithm. The originality of our approach rests on the crossover procedure that uses a large neighborhood search. This algorithm is compared with other algorithms on a set of 54 standard test problems with up to 217 clusters and 1084 cities. Results demonstrate the efficiency of our algorithm in both solution quality and computation time.     

An optimal algorithm for the on-line closest-pair problem

We give an algorithm that computes the closest pair in a set ofn points ink-dimensional space on-line, inO(n logn) time. The algorithm only uses algebraic functions and, therefore, is optimal. The algorithm maintains a hierarchical subdivision ofk-space into hyperrectangles, which is stored in a binary tree. Centroids are used to maintain a balanced decomposition of this tree.These authors were supported by the ESPRIT II Basic Research Actions Program, under Contract No. 3075 (project ALCOM).This author was supported in part by the National Science and Engineering Research Council of Canada.     

A k-server problem with parallel requests and unit distances

In this paper we consider k-server problems with parallel requests where several servers can also be located on one point. We will distinguish the surplus-situation where the request can be completely fulfilled by means of the k servers and the scarcity-situation where the request cannot be completely met. We use the method of the potential function by Bartal and Grove [2] in order to prove that a corresponding Harmonic algorithm is competitive for the more general k-server problem in the case of unit distances. For this purpose we partition the set of points in relation to the online and offline servers? positions and then use detailed considerations related to sets of certain partitions.     

GRASP with path relinking for the symmetric Euclidean clustered traveling salesman problem

In this paper, we propose new heuristics using several path-relinking strategies to solve the Clustered Traveling Salesman Problem (CTSP). The CTSP is a generalization of the Traveling Salesman Problem (TSP) in which the set of vertices is partitioned into clusters and the objective is to find a minimum cost Hamiltonian cycle such that the vertices of each cluster are visited continuously. A comparison among the performance of the several different adopted path-relinking strategies is presented using instances with up to 2000 vertices and clusters varying between 4 and 150 vertices. Also computational experiments were performed to compare the performance of the proposed heuristics with an exact algorithm and a Genetic Algorithm. The obtained computational results showed that the proposed heuristics were able to obtain competitive results related to the quality of the solutions and computational execution time.     

The Traveling Salesman Problem with Draft Limits

In maritime transportation, routing decisions are sometimes affected by draft limits in ports. The draft of a ship is the distance between the waterline and the bottom of the ship and is a function of the load onboard. Draft limits in ports can thus prevent ships to enter these ports fully loaded and may impose a constraint on the sequence of visits made by a ship. This paper introduces the Traveling Salesman Problem with Draft Limits (TSPDL), which is to determine an optimal sequence of port visits under draft limit constraints. We present two mathematical formulations for the TSPDL, and suggest valid inequalities and strengthened bounds. We also introduce a set of instances based on TSPLIB. A branch-and-cut algorithm is applied on both formulations for all these instances. Computational results show that introducing draft limits make the problem much harder to solve. They also indicate that the proposed valid inequalities and strengthened bounds significantly reduce both the number of branch-and-bound nodes and the solution times.     

On Constructing Minimum Spanning Trees in R k 1

We give an algorithm to find a minimum spanning tree in the k-dimensional space under rectilinear metric. The running time is for k≥ 3. This improves the previous bound by a factor . Received January 10, 1995; revised December 21, 1995.     

On the performance of self-organizing maps for the non-Euclidean Traveling Salesman Problem in the polygonal domain

In this paper, two state-of-the-art algorithms for the Traveling Salesman Problem (TSP) are examined in the multi-goal path planning problem motivated by inspection planning in the polygonal domain W. Both algorithms are based on the self-organizing map (SOM) for which an application in W is not typical. The first is Somhom’s algorithm, and the second is the Co-adaptive net. These algorithms are augmented by a simple approximation of the shortest path among obstacles in W. Moreover, the competitive and cooperative rules are modified by recent adaptation rules for the Euclidean TSP, and by proposed enhancements to improve the algorithms’ performance in the non-Euclidean TSP. Based on the modifications, two new variants of the algorithms are proposed that reduce the required computational time of their predecessors by an order of magnitude, therefore making SOM more competitive with combinatorial heuristics. The results show how SOM approaches can be used in the polygonal domain so they can provide additional features over the classical combinatorial approaches based on the complete visibility graph.     

A Randomized O(log2 k)-Competitive Algorithm for Metric Bipartite Matching

We consider the online metric matching problem in which we are given a metric space, k of whose points are designated as servers. Over time, up to k requests arrive at an arbitrary subset of points in the metric space, and each request must be matched to a server immediately upon arrival, subject to the constraint that at most one request is matched to any particular server. Matching decisions are irrevocable and the goal is to minimize the sum of distances between the requests and their matched servers. We give an O(log² k)-competitive randomized algorithm for the online metric matching problem. This improves upon the best known guarantee of O(log³ k) on the competitive factor due to Meyerson, Nanavati and Poplawski (SODA ’06, pp. 954–959, 2006). It is known that for this problem no deterministic algorithm can have a competitive better than 2k?1, and that no randomized algorithm can have a competitive ratio better than lnk.