Computing the variance of tour costs over the solution space of the TSP in polynomial time

We give an O(n ²) time algorithm to find the population variance of tour costs over the solution space of the n city symmetric Traveling Salesman Problem (TSP). The algorithm has application in both the stochastic case, where the problem is specified in terms of edge costs which are pairwise independently distributed random variables with known mean and variance, and the numeric edge cost case. We apply this result to provide empirical evidence that, in a range of real world problem sets, the optimal tour cost correlates with a simple function of the mean and variance of tour costs.     

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.     

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.     

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.     

An asymmetric analog of van der Veen conditions and the traveling salesman problem (II)

J.A.A. van der Veen [A new class of pyramidally solvable symmetric traveling salesman problems, SIAM J. Discrete Math. 7 (1994) 585–592] proved that for the traveling salesman problem (TSP) which satisfies some symmetric conditions (called van der Veen conditions), a shortest pyramidal tour is optimal, that is, an optimal tour can be computed in polynomial time. In this paper, we prove that a class satisfying an asymmetric analog of van der Veen conditions is polynomially solvable. An optimal tour of the instance in this class forms a tour which is an extension of pyramidal ones. Moreover, this class properly includes some known polynomially solvable classes.     

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.     

Stochastic center of systems of stochastic differential equations on the plane

We study a stochastic analogy of the famous center problem of Dulac for quadratic differential equations in the plane. We introduce the concept of center for systems of stochastic differential equations of It\^o''s type on the plane, called stochastic center. We derive a criterion for the existence of such a center. We apply it to obtain necessary and sufficient conditions for quadratic stochastic differential equations in dimension 2.     

Martingale problems for some degenerate Kolmogorov equations

We obtain Calderón–Zygmund estimates for some degenerate equations of Kolmogorov type with inhomogeneous nonlinear coefficients. We then derive the well-posedness of the martingale problem associated with related degenerate operators, and therefore uniqueness in law for the corresponding stochastic differential equations. Some density estimates are established as well.     

Distributions for the risk process with a stochastic return on investments

In this paper, we consider a risk model with stochastic return on investments. We mainly discuss the ruin probability, the surplus distribution at the time of ruin and the supremum distribution of the surplus before ruin. We prove some properties for these distributions and derive the integro-differential equations satisfied by them. We present the relation between the ruin probability and the supremum distribution before ruin.     

Comparison theorems for stochastic evolution equations

This paper establishes an anticipating stochastic differential equation of parabolic type for the expectation of the solution of a stochastic differential equation conditioned on complete knowledge of the path of one of its components. Conversely, it is shown that any appropriately regular solution of this stochastic p.d.e. must be given by the conditional expectation. These results generalize the connection, known as the Feynman-Kac formula, between parabolic equations and expectations of functions of a diffusion. As an application, we derive an equation for the unnormalized smoothing law of a filtering problem with observation feedback.     

Implicit Milstein method for stochastic differential equations via the Wong-Zakai approximation

The aim of this paper is to derive a numerical scheme for solving stochastic differential equations (SDEs) via Wong-Zakai approximation. One of the most important methods for solving SDEs is Milstein method, but this method is not so popular because the cost of simulating the double stochastic integrals is high. For overcoming this complexity, we present an implicit Milstein scheme based on Wong-Zakai approximation by approximating the Brownian motion with its truncated Haar expansion. The main advantages of this method lie in the fact that it preserves the convergence order and also stability region of the Milstein method while its simulation is much easier than Milstein scheme. We show the convergence rate of the method by some numerical examples.     

The Perturbed Compound Poisson Risk Process with Investment and Debit Interest

In this paper, we study absolute ruin questions for the perturbed compound Poisson risk process with investment and debit interests by the expected discounted penalty function at absolute ruin, which provides a unified means of studying the joint distribution of the absolute ruin time, the surplus immediately prior to absolute ruin time and the deficit at absolute ruin time. We first consider the stochastic Dirichlet problem and from which we derive a system of integro-differential equations and the boundary conditions satisfied by the function. Second, we derive the integral equations and a defective renewal equation under some special cases, then based on the defective renewal equation we give two asymptotic results for the expected discounted penalty function when the initial surplus tends to infinity for the light-tailed claims and heavy-tailed claims, respectively. Finally, we investigate some explicit solutions and numerical results when claim sizes are exponentially distributed.     

Some Results for Classical Risk Process with Stochastic Return on Investments

In this paper, we discuss the classical risk process with stochastic return on investment. We prove some properties of the ruin probability, the supremum distribution before ruin and the surplus distribution at the time of ruin and derive the integro-differential equations satisfied by these distributions respectively.     

Hybrid Metaheuristics for the Vehicle Routing Problem with Stochastic Demands

This article analyzes the performance of metaheuristics on the vehicle routing problem with stochastic demands (VRPSD). The problem is known to have a computationally demanding objective function, which could turn to be infeasible when large instances are considered. Fast approximations of the objective function are therefore appealing because they would allow for an extended exploration of the search space. We explore the hybridization of the metaheuristic by means of two objective functions which are surrogate measures of the exact solution quality. Particularly helpful for some metaheuristics is the objective function derived from the traveling salesman problem (TSP), a closely related problem. In the light of this observation, we analyze possible extensions of the metaheuristics which take the hybridized solution approach VRPSD-TSP even further and report about experimental results on different types of instances. We show that, for the instances tested, two hybridized versions of iterated local search and evolutionary algorithm attain better solutions than state-of-the-art algorithms.     

Reconstruction of external actions under incomplete information in a linear stochastic equation

The problem of reconstructing unknown external actions in a linear stochastic differential equation is investigated on the basis of the approach of the theory of dynamic inversion. We consider the statement when the simultaneous reconstruction of disturbances in the deterministic and stochastic terms of the equation is performed with the use of discrete information on a number of realizations of a part of coordinates of the stochastic process. The problem is reduced to an inverse problem for systems of ordinary differential equations describing the mathematical expectation and covariance matrix of the original process. A finite-step software-oriented solution algorithm based on the method of auxiliary controlled models is proposed. We derive an estimate for its convergence rate with respect to the number of measured realizations.     

A formula on the weight distribution of linear codes with applications to AMDS codes

The determination of the weight distribution of linear codes has been a fascinating problem since the very beginning of coding theory. There has been a lot of research on weight enumerators of special cases, such as self-dual codes and codes with small Singleton's defect. We propose a new set of linear relations that must be satisfied by the coefficients of the weight distribution. From these relations we are able to derive known identities (in an easier way) for interesting cases, such as extremal codes, Hermitian codes, MDS and NMDS codes. Moreover, we are able to present for the first time the weight distribution of AMDS codes. We also discuss the link between our results and the Pless equations.     

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.     

k-Interchange procedures for local search in a precedence-constrained routing problem

We develop k-interchange procedures to perform local search in a precedence-constrained routing problem. The problem in question is known in the Transportation literature as the single vehicle many-to-many Dial-A-Ride Problem, or DARP. The DARP is the problem of minimizing the length of the tour traveled by a vehicle to service N customers, each of whom wishes to go from a distinct origin to a distinct destination. The vehicle departs from a specified point and returns to that point upon service of all customers. Precedence constraints in the DARP exist because the origin of each customer must precede his/her destination on the route. As in the interchange procedure of Lin for the Traveling Salesman Problem (TSP), a k-interchange is a substitution of k of the links of an initial feasible DARP tour with k other links, and a DARP tour is k-optimal if it is impossible to obtain a shorter tour by replacing any k of its links by k other links. However, in contrast to the TSP where each individual interchange takes O(1) time, checking whether each individual DARP interchange satisfies the origin-destination precedence constraints normally requires O(N²) time. In this paper we develop a method which still finds the best k-interchange that can be produced from an initial feasible DARP tour in O(N^k) time, the same order of magnitude as in the Lin heuristic for the TSP. This method is then embedded in a breadth-first or a depth-first search procedure to produce a k-optimal DARP tour. The paper focuses on the k = 2 and k = 3 cases. Experience with the procedures is presented. in which k-optimal tours are produced by applying a 2-opt or 3-opt search to initial DARP tours produced either randomly or by a fast O(N²) heuristic. The breadth-first and depth-first search modes are compared. The heuristics are seen to produce very good or near-optimal DARP tours.     

Algorithms for the universal and a priori TSP

We present two simple results for generalizations of the traveling salesman problem (TSP): for the universal TSP, we show that one can compute a tour that is universally optimal whenever the input is a tree metric. A (randomized) O(logn)-approximation algorithm for the a priori TSP follows as a corollary.     

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.