Search results for "Travelling salesman problem"
showing 10 items of 32 documents
Automating the Parameter Selection in VRP: An Off-line Parameter Tuning Tool Comparison
2014
Vehicle route optimization is an important application of combinatorial optimization. Therefore, a variety of methods has been proposed to solve different challenging vehicle routing problems. An important step in adopting these methods to solve real-life problems is to find appropriate parameters for the routing algorithms. In this chapter, we show how this task can be automated using parameter tuning by presenting a set of comparative experiments on seven state-of-the-art tuning methods. We analyze the suitability of these methods in configuring routing algorithms, and give the first critical comparison of automated parameter tuners in vehicle routing. Our experimental results show that t…
A branch-and-cut algorithm for the soft-clustered vehicle-routing problem
2021
Abstract The soft-clustered vehicle-routing problem is a variant of the classical capacitated vehicle-routing problem (CVRP) in which customers are partitioned into clusters and all customers of the same cluster must be served by the same vehicle. We introduce a novel symmetric formulation of the problem in which the clustering part is modeled with an asymmetric sub-model. We solve the new model with a branch-and-cut algorithm exploiting some known valid inequalities for the CVRP that can be adapted. In addition, we derive problem-specific cutting planes and new heuristic and exact separation procedures. For square grid instances in the Euclidean plane, we provide lower-bounding techniques …
Cotas inferiores para el QAP-Arbol
1985
The Tree-QAP is a special case of the Quadratic Assignment Problem where the flows not equal zero form a tree. No condition is required for the distance matrix. In this paper we present an integer programming formulation for the Tree-QAP. We use this formulation to construct four Lagrangean relaxations that produce several lower bounds for this problem. To solve one of the relaxed problems we present a Dynamic Programming algorithm which is a generalization of the algorithm of this type that gives a lower bound for the Travelling Salesman Problem. A comparison is given between the lower bounds obtained by each ralaxation for examples with size from 12 to 25.
Influence of rounding errors on the quality of heuristic optimization algorithms
2011
Abstract Search space smoothing and related heuristic optimization algorithms provide an alternative approach to simulated annealing and its variants: while simulated annealing traverses barriers in the energy landscape at finite temperatures, search space smoothing intends to remove these barriers, so that a greedy algorithm is sufficient to find the global minimum. Several formulas for smoothing the energy landscape have already been applied, one of them making use of the finite numerical precision on a computer. In this paper, we thoroughly investigate the effect of finite numerical accuracy on the quality of results achieved with heuristic optimization algorithms. We present computation…
Investigation of acceptance simulated annealing — A simplified approach to adaptive cooling schedules
2010
Abstract Simulated annealing is the classic physical optimization algorithm, which has been applied to a large variety of problems for many years. Over time, several adaptive mechanisms for decreasing the temperature and thus controlling the acceptance of deteriorations have been developed, based on the measurement of the mean value and the variance of the energy. Here we propose a new simplified approach in which we consider the probability of accepting deteriorations as the main control parameter and derive the temperature by averaging over the last few deteriorations stored in a memory. We present results for the traveling salesman problem and demonstrate, how the amount of data retained…
Investigation of Simulated Trading — A multi agent based trading system for optimization purposes
2010
Abstract Some years ago, Bachem, Hochstattler, and Malich proposed a heuristic algorithm called Simulated Trading for the optimization of vehicle routing problems. Computational agents place buy-orders and sell-orders for customers to be handled at a virtual financial market, the prices of the orders depending on the costs of inserting the customer in the tour or for his removal. According to a proposed rule set, the financial market creates a buy-and-sell graph for the various orders in the order book, intending to optimize the overall system. Here I present a thorough investigation for the application of this algorithm to the traveling salesman problem.
Design of Representations and Search Operators
2015
Successful and efficient use of evolutionary algorithms depends on the choice of genotypes and the representation – that is, the mapping from genotype to phenotype – and on the choice of search operators that are applied to the genotypes. These choices cannot be made independently of each other. This chapter gives recommendations on the design of representations and corresponding search operators and discusses how to consider problem-specific knowledge. For most problems in the real world, similar solutions have similar fitness values. This fact can be exploited by evolutionary algorithms if they ensure that the representations and search operators used are defined in such a way that simila…
An Investigation of the Robustness in the Travelling Salesman Problem Routes Using Special Structured Matrices
2020
In this study, the robustness of the Travelling Salesman Problem (TSP) routes is investigated by recognising the special combinatorial structures of Kalmanson matrices. A recognition algorithm encompassing three procedures based on combinatorial and linear programming (LP) is developed and executed on several randomly generated instances. These procedures produce three lower bounds which provide guarantees on the optimality of the solutions. Computational experiments show that the proposed LP-based procedure performs efficiently well across all problem dimensions and provides the best lower bounds to the TSP. This is supported by an average deviation of less than 7% between the TSP tour len…
A Branch-and-Cut Algorithm for the Single Truck and Trailer Routing Problem with Satellite Depots
2016
International audience; In the single truck and trailer routing problem with satellite depots (STTRPSD), a truck with a detachable trailer based at a main depot must serve the demand of a set of customers accessible only by truck. Therefore, before serving the customers, it is necessary to detach the trailer in an appropriate parking place (called either a satellite depot or a trailer point) and transfer goods between the truck and the trailer. This problem has applications in milk collection for farms that cannot be reached using large vehicles. In this work we present an integer programming formulation of the STTRPSD. This formulation is tightened with several families of valid inequaliti…
A Neuro-Ethological Approach for the TSP: Changing Metaphors in Connectionist Models.
1994
Biological systems often offer solutions to difficult problems which are not only original but also efficient. Connectionist models have been inspired by neural systems and successfully applied to the formulation of algorithms for solving complex problems such as the travelling salesman problem. In this paper we extend the connectionist metaphor to include an ethological account of how problems similar to the travelling salesman problem are solved by real living systems. A model is presented in which a population of neural networks with simple sensory-motor systems evolve genetically in simulated environments which represent the problem instances to be solved. Preliminary results are discu…