The traveling purchaser problem with stochastic prices: Exact and approximate algorithms

The paper formulates an extension of the traveling purchaser problem where multiple types of commodities are sold at spatially distributed locations with stochastic prices (each following a known probability distribution). A purchaser’s goal is to find the optimal routing and purchasing strategies that minimize the expected total travel and purchasing costs needed to purchase one unit of each commodity. The purchaser reveals the actual commodity price at a seller upon arrival, and then either purchases the commodity at the offered price, or rejects the price and visits a next seller. In this paper, we propose an exact solution algorithm based on dynamic programming, an iterative approximate algorithm that yields bounds for the minimum total expected cost, and a greedy heuristic for fast solutions to large-scale applications. We analyze the characteristics of the problem and test the computational performance of the proposed algorithms. The numerical results show that the approximate and heuristic algorithms yield near-optimum strategies and very good estimates of the minimum total cost.     

Exploring greedy criteria for the dynamic traveling purchaser problem

Given a set of products and a set of markets, the traveling purchaser problem looks for a tour visiting a subset of the markets to satisfy products demand at the minimum purchasing and traveling costs. In this paper, we analyze the dynamic variant of the problem (D-TPP) where the quantity made available in each market for each product may decrease over time. We introduce and compare several greedy strategies and test their impact on the solution in terms of feasibility and costs. In particular, we study an incremental approach where an initial naive strategy is improved and refined by a number of variants. Some of the proposed heuristics take into account either one of the two objective costs, while others are based on both traveling and purchasing costs. Extensive computational results are also provided on randomly generated instances.     

A Numerical Study of Traveling Wave Fronts for a Reaction-Diffusion-Advection Model

This paper concerns with the traveling wave solutions of a nonlinear reaction-diffusion-advection model for describing the spatiotemporal evolution of bacterial colony pattern. We use different methods for computing the traveling wave fronts of the model equations. One of the methods involves the traveling wave equations. Numerical solutions of these equations as an initial-value problem lead to accurate computations of the wave profiles and speeds. The second method is to construct the time-dependent solutions by solving an initial-moving boundary-value problem for the PDE system, showing an approximation for such wave fronts, in particular, the minimum speed traveling wave.     

Combining simulated annealing with local search heuristics

We introduce a meta-heuristic to combine simulated annealing with local search methods for CO problems. This new class of Markov chains leads to significantly more powerful optimization methods than either simulated annealing or local search. The main idea is to embed deterministic local search techniques into simulated annealing so that the chain explores only local optima. It makes large, global changes, even at low temperatures, thus overcoming large barriers in configuration space. We have tested this meta-heuristic for the traveling salesman and graph partitioning problems. Tests on instances from public libraries and random ensembles quantify the power of the method. Our algorithm is able to solve large instances to optimality, improving upon local search methods very significantly. For the traveling salesman problem with randomly distributed cities, in a square, the procedure improves on 3-opt by 1.6%, and on Lin-Kernighan local search by 1.3%. For the partitioning of sparse random graphs of average degree equal to 5, the improvement over Kernighan-Lin local search is 8.9%. For both CO problems, we obtain new best heuristics.     

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.     

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.     

Optimal search strategies using simultaneous generalized hill climbing algorithms

Optimal search strategies for conducting reconnaissance, surveillance or search and rescue operations with limited assets are of significant interest to military decision makers. Multiple search platforms with varying capabilities can be deployed individually or simultaneously for these operations (e.g., helicopters, fixed wing or satellite). Due to the timeliness required in these operations, efficient use of available search platforms is critical to the success of such missions. Designing optimal search strategies over multiple search platforms can be modeled and solved as a multiple traveling salesman problem (MTSP). This paper demonstrates how simultaneous generalized hill climbing algorithms (SGHC) can be used to determine optimal search strategies over multiple search platforms for the MTSP. Computational results with SGHC algorithms applied to the MTSP are reported. These results demonstrate that when limited computing budgets are available, optimal/near-optimal search strategies over multiple search platforms can be obtained more efficiently using SGHC algorithms compared to other generalized hill climbing algorithms. Applications and extensions of this research to other military applications are also discussed.     

Adaptive sample size and importance sampling in estimation-based local search for the probabilistic traveling salesman problem

The probabilistic traveling salesman problem is a paradigmatic example of a stochastic combinatorial optimization problem. For this problem, recently an estimation-based local search algorithm using delta evaluation has been proposed. In this paper, we adopt two well-known variance reduction procedures in the estimation-based local search algorithm: the first is an adaptive sampling procedure that selects the appropriate size of the sample to be used in Monte Carlo evaluation; the second is a procedure that adopts importance sampling to reduce the variance involved in the cost estimation. We investigate several possible strategies for applying these procedures to the given problem and we identify the most effective one. Experimental results show that a particular heuristic customization of the two procedures increases significantly the effectiveness of the estimation-based local search.     

A general variable neighborhood search variants for the travelling salesman problem with draft limits

In this paper, we present two general variable neighborhood search (GVNS) based variants for solving the traveling salesman problem with draft limits (TSPDL), a recent extension of the traveling salesman problem. TSPDL arises in the context of maritime transportation. It consists of finding optimal Hamiltonian tour for a given ship which has to visit and deliver products to a set of ports while respecting the draft limit constraints. The proposed methods combine ideas in sequential variable neighborhood descent within GVNS. They are tested on a set of benchmarks from the literature as well as on a new one generated by us. Computational experiments show remarkable efficiency and effectiveness of our new approach. Moreover, new set of benchmarks instances is generated.     

An iterated local search algorithm for the time-dependent vehicle routing problem with time windows

We generalize the standard vehicle routing problem with time windows by allowing both traveling times and traveling costs to be time-dependent functions. In our algorithm, we use a local search to determine routes of the vehicles. When we evaluate a neighborhood solution, we must compute an optimal time schedule for each route. We show that this subproblem can be efficiently solved by dynamic programming, which is incorporated in the local search algorithm. The neighborhood of our local search consists of slight modifications of the standard neighborhoods called 2- opt^*, cross exchange and Or-opt. We propose an algorithm that evaluates solutions in these neighborhoods more efficiently than the ones computing the dynamic programming from scratch by utilizing the information from the past dynamic programming recursion used to evaluate the current solution. We further propose a filtering method that restricts the search space in the neighborhoods to avoid many solutions having no prospect of improvement. We then develop an iterated local search algorithm that incorporates all the above ingredients. Finally we report computational results of our iterated local search algorithm compared against existing methods, and confirm the effectiveness of the restriction of the neighborhoods and the benefits of the proposed generalization.     

A controlled search simulated annealing method for the single machine weighted tardiness problem

In this paper, a new controlled search simulated annealing method is developed for addressing the single machine weighted tardiness problem. The proposed method is experimentally shown to solve optimally 99% of fifteen job problems with less than 0.2 CPU seconds, and to solve one hundred job problems as accurately as any existing methods, but with far less computational effort. This superior performance is achieved by using controlled search strategies that employ a good initial solution, a small neighborhood for local search, and acceptance probabilities of inferior solutions that are independent of the change in the objective function value.     

A combined local search and integer programming approach to the traveling tournament problem

The traveling tournament problem is a well-known combinatorial optimization problem with direct applications to sport leagues scheduling, that sparked intensive algorithmic research over the last decade. With the Challenge Traveling Tournament Instances as an established benchmark, the most successful approaches to the problem use meta-heuristics like tabu search or simulated annealing, partially heavily parallelized. Integer programming based methods on the other hand are hardly able to tackle larger benchmark instances. In this work we present a hybrid approach that draws on the power of commercial integer programming solvers as well as the speed of local search heuristics. Our proposed method feeds the solution of one algorithm phase to the other one, until no further improvements can be made. The applicability of this method is demonstrated experimentally on the galaxy instance set, resulting in currently best known solutions for most of the considered instances.     

Solving TSP by considering processing time: Meta-heuristics and fuzzy approaches

In this paper, general properties of traveling salesman problem has been illustrated, then a model has been introduced to minimize Make-span (time interval which all of jobs will be done) with considering sequence-dependence setup times and processing time. Furthermore, fuzzy sets and its characteristics are applied to a Hard-solvable traveling salesman problem with considering processing times. As it can be seen, traveling salesman problems are NP-hard, so solving problem in huge dimensions is uncontrollably manageable and in other side these kinds of problems in real-world are unavoidable, so a local search can prove their importance. (However this Meta-heuristic methods may not reveal exact optimal solution, but they yield a near-exact optimal solution in undeniable reduced computational time). Here, some of most famous local searches have been explained in their common and normal form, which are Genetic Algorithm (GA), Tabu Search (TS), Simulated Annealing (SA), Ant Colony System (ACO). In rest, a comprehensive comparison through these methods has been shown. This normality in methods structure could help the article to hold no-side-taken and acceptable judgments. In final, point methods analysis and parameter tuning are held.     

A Constraint Programming Framework for Local Search Methods

We propose in this paper a novel integration of local search algorithms within a constraint programming framework for combinatorial optimization problems, in an attempt to gain both the efficiency of local search methods and the flexibility of constraint programming while maintaining a clear separation between the constraints of the problem and the actual search procedure. Each neighborhood exploration is performed by branch-and-bound search, whose potential pruning capabilities open the door to more elaborate local moves, which could lead to even better approximate results. Two illustrations of this framework are provided, including computational results for the traveling salesman problem with time windows. These results indicate that it is one order of magnitude faster than the customary constraint programming approach to local search and that it is competitive with a specialized local search algorithm.     

Dual approaches to finite element model updating

The problem of finding the least change adjustment to a stiffness matrix modeled by finite element method is considered in this paper. Desired stiffness matrix properties such as symmetry, sparsity, positive semidefiniteness, and satisfaction of the characteristic equation are imposed as side constraints of the constructed optimal matrix approximation for updating the stiffness matrix, which matches measured data better. The dual problems of the original constrained minimization are presented and solved by subgradient algorithms with different line search strategies. Some numerical results are included to illustrate the performance and application of the proposed methods.     

A dual local search framework for combinatorial optimization problems with TSP application

In practice, solving realistically sized combinatorial optimization problems to optimality is often too time-consuming to be affordable; therefore, heuristics are typically implemented within most applications software. A specific category of heuristics has attracted considerable attention, namely local search methods. Most local search methods are primal in nature; that is, they start the search with a feasible solution and explore the feasible space for better feasible solutions. In this research, we propose a dual local search method and customize it to solve the traveling salesman problem (TSP); that is, a search method that starts with an infeasible solution, explores the dual space—each time reducing infeasibility, and lands in the primal space to deliver a feasible solution. The proposed design aims to replicate the designs of optimal solution methodologies in a heuristic way. To be more specific, we solve a combinatorial relaxation of a TSP formulation, design a neighborhood structure to repair such an infeasible starting solution, and improve components of intermediate dual solutions locally. Sample-based evidence along with statistically significant t-tests support the superiority of this dual design compared to its primal design counterpart.     

Complete Local Search with Memory

Neighborhood search heuristics like local search and its variants are some of the most popular approaches to solve discrete optimization problems of moderate to large size. Apart from tabu search, most of these heuristics are memoryless. In this paper we introduce a new neighborhood search heuristic that makes effective use of memory structures in a way that is different from that in common implementations of tabu search. We report computational experiments with this heuristic on the traveling salesperson problem and the subset sum problem.     

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.     

A threshold accepting heuristic with intense local search for the solution of special instances of the traveling salesman problem

In real life scheduling, variations of the standard traveling salesman problem are very often encountered. The aim of this work is to present a new heuristic method for solving three such special instances with a common approach. The proposed algorithm uses a variant of the threshold accepting method, enhanced with intense local search, while the candidate solutions are produced through an insertion heuristic scheme. The main characteristic of the algorithm is that it does not require modifications and parameter tuning in order to cope with the three different problems. Computational results on a variety of real life and artificial problems are presented at the end of this work and prove the efficiency and the ascendancy of the proposed method over other algorithms found in the literature.     

Adaptive memory programming for matrix bandwidth minimization

In this paper we explore the influence of adaptive memory in the performance of heuristic methods when solving a hard combinatorial optimization problem. Specifically, we tackle the adaptation of tabu search and scatter search to the bandwidth minimization problem. It consists of finding a permutation of the rows and columns of a given matrix which keeps the non-zero elements in a band that is as close as possible to the main diagonal. This is a classic problem, introduced in the late sixties, that also has a well-known formulation in terms of graphs. Different exact and heuristic approaches have been proposed for the bandwidth problem. Our contribution consists of two new algorithms, one based on the tabu search methodology and the other based on the scatter search framework. We also present a hybrid method combining both for improved outcomes. Extensive computational testing shows the influence of the different elements in heuristic search, such as neighborhood definition, local search, combination methods and the use of memory. We compare our proposals with the most recent and advanced methods for this problem, concluding that our new methods can compete with them in speed and running time.