The traveling salesman problem Applegate, David L; Applegate, David L; Bixby, Robert E ...
2006., 20110919, 2011, 2007, 2007-01-01, Letnik:
17
eBook
This book presents the latest findings on one of the most intensely investigated subjects in computational mathematics--the traveling salesman problem. It sounds simple enough: given a set of cities ...and the cost of travel between each pair of them, the problem challenges you to find the cheapest route by which to visit all the cities and return home to where you began. Though seemingly modest, this exercise has inspired studies by mathematicians, chemists, and physicists. Teachers use it in the classroom. It has practical applications in genetics, telecommunications, and neuroscience.
A traveling salesman problem (TSP) is a well-known NP-complete problem. Traditional TSP presumes that the locations of customers and the traveling time among customers are fixed and constant. In ...real-life cases, however, the traffic conditions and customer requests may change over time. To find the most economic route, the decisions can be made constantly upon the time-point when the salesman completes his service of each customer. This brings in a dynamic version of the traveling salesman problem (DTSP), which takes into account the information of real-time traffic and customer requests. DTSP can be extended to a dynamic pickup and delivery problem (DPDP). In this article, we ameliorate the attention model to make it possible to perceive environmental changes. A deep reinforcement learning algorithm is proposed to solve DTSP and DPDP instances with a size of up to 40 customers in 100 locations. Experiments show that our method can capture the dynamic changes and produce a highly satisfactory solution within a very short time. Compared with other baseline approaches, more than 5% improvements can be observed in many cases.
The fast and cost-efficient home delivery of goods ordered online is logistically challenging. Many companies are looking for new ways to cross the last mile to their customers. One ...technology-enabled opportunity that recently has received much attention is the use of drones to support deliveries. An innovative last-mile delivery concept in which a truck collaborates with a drone to make deliveries gives rise to a new variant of the traveling salesman problem (TSP) that we call the TSP with drone. In this paper, we model this problem as an integer program and develop several fast route-first, cluster-second heuristics based on local search and dynamic programming. We prove worst-case approximation ratios for the heuristics and test their performance by comparing the solutions to the optimal solutions for small instances. In addition, we apply our heuristics to several artificial instances with different characteristics and sizes. Our experiments show that substantial savings are possible with this concept compared to truck-only delivery.
The online appendix is available at
https://doi.org/10.1287/trsc.2017.0791
.
For a dynamic traveling salesman problem (DTSP), the weights (or traveling times) between two cities (or nodes) may be subject to changes. Ant colony optimization (ACO) algorithms have proved to be ...powerful methods to tackle such problems due to their adaptation capabilities. It has been shown that the integration of local search operators can significantly improve the performance of ACO. In this paper, a memetic ACO algorithm, where a local search operator (called unstring and string) is integrated into ACO, is proposed to address DTSPs. The best solution from ACO is passed to the local search operator, which removes and inserts cities in such a way that improves the solution quality. The proposed memetic ACO algorithm is designed to address both symmetric and asymmetric DTSPs. The experimental results show the efficiency of the proposed memetic algorithm for addressing DTSPs in comparison with other state-of-the-art algorithms.
This article proposes an end-to-end framework for solving multiobjective optimization problems (MOPs) using deep reinforcement learning (DRL), that we call DRL-based multiobjective optimization ...algorithm (DRL-MOA). The idea of decomposition is adopted to decompose the MOP into a set of scalar optimization subproblems. Then, each subproblem is modeled as a neural network. Model parameters of all the subproblems are optimized collaboratively according to a neighborhood-based parameter-transfer strategy and the DRL training algorithm. Pareto-optimal solutions can be directly obtained through the trained neural-network models. Specifically, the multiobjective traveling salesman problem (MOTSP) is solved in this article using the DRL-MOA method by modeling the subproblem as a Pointer Network. Extensive experiments have been conducted to study the DRL-MOA and various benchmark methods are compared with it. It is found that once the trained model is available, it can scale to newly encountered problems with no need for retraining the model. The solutions can be directly obtained by a simple forward calculation of the neural network; thereby, no iteration is required and the MOP can be always solved in a reasonable time. The proposed method provides a new way of solving the MOP by means of DRL. It has shown a set of new characteristics, for example, strong generalization ability and fast solving speed in comparison with the existing methods for multiobjective optimizations. The experimental results show the effectiveness and competitiveness of the proposed method in terms of model performance and running time.
This paper addresses the task scheduling and path planning problem for a team of cooperating vehicles performing autonomous deliveries in urban environments. The cooperating team comprises two ...vehicles with complementary capabilities, a truck restricted to travel along a street network, and a quadrotor micro-aerial vehicle of capacity one that can be deployed from the truck to perform deliveries. The problem is formulated as an optimal path planning problem on a graph and the goal is to find the shortest cooperative route enabling the quadrotor to deliver items at all requested locations. The problem is shown to be NP-hard. A solution is then proposed using a novel reduction to the Generalized Traveling Salesman Problem, for which well-established heuristic solvers exist. The heterogeneous delivery problem contains as a special case the problem of scheduling deliveries from multiple static warehouses. We propose two additional algorithms, based on enumeration and a reduction to the traveling salesman problem, for this special case. Simulation results compare the performance of the presented algorithms and demonstrate examples of delivery route computations over real urban street maps.
The paper gives an applicable model called colored balanced traveling salesman problem (CBTSP), it is utilized to model optimization problems with partially overlapped workspace such as the ...scheduling and deploying of the resources and goods. CBTSP is NP-hard problem, the traditional nature-inspired algorithms, such as genetic algorithm (GA), hill-climbing GA and simulated annealing GA, are easy to fall into local optimum. In order to improve it, the paper proposes a novel genetic algorithm (NGA) based on ITÖ process to solve CBTSP. First of all, NGA utilizes the dual-chromosome coding to represent solution of this problem, and then updates the solution by the crossover and mutation operator. During the process of crossover operator, the length of crossover can be affected by activity intensity, which is directly proportional to environmental temperature and inversely proportional to particle radius. The experiments verify that NGA can demonstrate better solution quality than the compared algorithms for large scale CBTSP.
•This paper provides colored balanced traveling salesman problem (CBTSP).•The large scale optimization for CBTSP is studied.•A novel genetic algorithm is proposed for large scale CBTSP.•Experiments show the superiority of the proposed algorithm.
With the advent of e-commerce and its fast-delivery expectations, efficiently routing pickers in warehouses and distribution centers has received renewed interest. The processes and the resulting ...routing problems in this environment are diverse. For instance, not only human pickers have to be routed but also autonomous picking robots or mobile robots that accompany human pickers. Traditional picker routing, in which a single picker has to visit a given set of picking positions in a picker-to-parts process, can be modeled as the classical Traveling Salesman Problem (TSP). The more involved processes of e-commerce fulfillment, however, require solving more complex TSP variants, such as the clustered, generalized, or prize-collecting TSP. In this context, our paper provides two main contributions: We systematically survey the large number of TSP variants that are known in the routing literature and check whether meaningful applications in warehouses exist that correspond to the respective TSP variant. If they do, we survey the existing research and investigate the computational complexity of the TSP variant in the warehousing context. Previous research has shown that the classical TSP is efficiently solvable in the parallel-aisle structure of warehouses. Consequently, some TSP variants also turn out to be efficiently solvable in the warehousing context, whereas others remain NP-hard. We survey existing complexity results, provide new ones, and identify future research needs.
•This paper surveys routing problems in warehouses.•We focus on variants of the TSP in warehouses.•New and old complexity results for the parallel-aisle structure are provided.•We elaborate warehouse use cases and future research needs.
A colored traveling salesman problem (CTSP) is a generalization of the well-known multiple traveling salesman problem. This paper investigate a class of CTSP, called serial CTSP (S-CTSP). Each of its ...salesmen has his exclusive cities and shares some cities with its neighbor(s) in a serial manner. It can be used to model the scheduling problem of multimachine engineering systems with linearly arranged machines. S-CTSP is NP-hard. Developing effective and efficient approaches to S-CTSP is important to enable its industrial applications. This paper presents a population-based incremental learning (PBIL) approach to it. After analyzing its solution space, we set up some probability matrix models to guide the individual search of the algorithm. Then, a distance penalty is introduced into the state transfer function that can select the cities with small penalty values by the Roulette method to form a good route. By adding a powerful local search operation, 2-opt, to the algorithm, we can further enhance its search ability. Extensive simulation is conducted and its results show that the augmented PBIL is effective and well outperforms the genetic algorithms and CPLEX.
Multi-solution problems extensively exist in practice. Particularly, the traveling salesman problem (TSP) may possess multiple shortest tours, from which travelers can choose one according to their ...specific requirements. However, very few efforts have been devoted to the multi-solution problems in the discrete domain. In order to fill this research gap and to effectively tackle the multi-solution TSP, we propose a niching memetic algorithm in this article. The proposed algorithm is characterized by a niche preservation technique to enable the parallel search of multiple optimal solutions; an adaptive neighborhood strategy to balance the exploration and exploitation; a critical edge-aware method to provide effective guidance to the reproduction; and a selective local search strategy to improve the search efficiency. To evaluate the performance of the proposed algorithm, we conduct comprehensive experiments on a recently published multi-solution optimization test suite. The experimental results show that our algorithm outperforms other compared algorithms. Furthermore, the proposed algorithm is adopted to tackle problems from the well-known TSPLIB library to obtain a set of distinct but good solutions.
PDF
