DMS*: Minimizing Makespan for Multi-Agent Combinatorial Path Finding
1
Citation
0
Reference
10
Related Paper
Citation Trend
Abstract:
Multi-Agent Combinatorial Path Finding (MCPF) seeks collision-free paths for multiple agents from their initial to goal locations, while visiting a set of intermediate target locations in the middle of the paths. MCPF is challenging as it involves both planning collision-free paths for multiple agents and target sequencing, i.e., solving traveling salesman problems to assign targets to and find the visiting order for the agents. Recent work develops methods to address MCPF while minimizing the sum of individual arrival times at goals. Such a problem formulation may result in paths with different arrival times and lead to a long makespan, the maximum arrival time, among the agents. This paper proposes a min-max variant of MCPF, denoted as MCPF-max, that minimizes the makespan of the agents. While the existing methods (such as MS*) for MCPF can be adapted to solve MCPF-max, we further develop two new techniques based on MS* to defer the expensive target sequencing during planning to expedite the overall computation. We analyze the properties of the resulting algorithm Deferred MS* (DMS*), and test DMS* with up to 20 agents and 80 targets. We demonstrate the use of DMS* on differential-drive robots.Keywords:
Arrival time
The Generalized Traveling Salesman Problem (GTSP) is an extension of the classical traveling salesman problem and has many interesting applications. In this paper we present a New Generalized Traveling Salesman Problem (NGTSP), and the current GTSP is only a special case of the NGTSP. To solve effectively the NGTSP, we extend the ant colony system method from TSP to NGTSP. Meanwhile, to improve the quality of solution, a local searching technique is introduced into this method to speed up the convergence, and a novel parameter adaptive technique is also introduced into this method to avoid locking into local minima. Experimental results on numerous TSPlib instances show that the proposed method can deal with the NGTSP problems fairly well, and the developed improvement techniques is significantly effective.
Maxima and minima
Ant colony
Extremal optimization
Cite
Citations (14)
Traveling purchaser problem
Lin–Kernighan heuristic
Cite
Citations (1)
Christofides algorithm
Extremal optimization
Cite
Citations (1)
Traveling salesman problem is one of the classical problems in Combinatorial Optimization, and the multiple traveling salesman problem(MTSP) is a generalization of the well-known traveling salesman problem(TSP), where more than one salesman is allowed to be used in the solution.Moreover, the characteristics of the MTSP seem more appropriate for real-life applications, and it is also possible to extend the problem to a wide variety of vehicle routing problems(VRPs) by incorporating some additional side constraints.Although there exists a wide body of the literature for the TSP and the VRP, the MTSP has not received the same amount of attention.A special case of multiple traveling salesman problem was calculated by adopting Lin-Kernighan algorithm, then a two stage procedure was applied in order to make sure that the number of cities each traveling salesman visited are the same and the total tour length is minimized.The calculation and simulation results are satisfactory.
Traveling purchaser problem
Vehicle Routing Problem
Lin–Kernighan heuristic
Cite
Citations (0)
This paper presents solutions to symmetric, asymmetric, and multiple traveling salesman problems. In the symmetric traveling salesman problem, one salesperson must go to five cities, making precisely one stop at each location. A matrix with the distances between each city is provided. Using the branch and bound algorithm and expressing it in Python, the final result is obtained. The formulations of the asymmetric traveling salesman problem and the multiple traveling salesman problem are demonstrated in the paper. The asymmetric problem in the paper is solved by transforming the asymmetric traveling salesman problem into a symmetric traveling salesman problem; then, the branch and bound algorithm has been applied to solve the problem. In the multiple traveling salesman problem, three salesmen are required to visit seven cities in total, each of which is only visited by one salesperson once. Each city is a point in an x-y plane, and the coordinates of all points are given in a graph. By formulating the MTSP problem with an assignment-based double-index integer programming and applying the constraints, the outcome is derived from Python code within a few seconds.
Traveling purchaser problem
Nearest neighbour algorithm
Lin–Kernighan heuristic
Christofides algorithm
Branch and bound
Python
Cite
Citations (1)
Introduction. The traveling salesman problem is a transport-type problem. It is natural to use a method based on the technology for solving transport problems to solve it. The cyclicity and degeneracy of the solution to the traveling salesman problem requires significant modification of the corresponding stages of solving the transport problem (drawing up an initial feasible solution; checking the plan for optimality; obtaining a new feasible solution). Purpose. Development of a natural approach to solving the traveling salesman problem. Description of the structure of a set of traveling salesman problems that have a predetermined optimal solution. Algorithmic formation of such problems for the purpose of conducting mass computing experiments. Results. The paper presents new results and computational experiments with a developed natural algorithm for solving the traveling salesman problem, based on the technology for solving transport problems, including a new effective method for generating an initial cyclic solution, an algorithm for transitioning from the initial cyclic to another, also cyclic, solution. An algorithm has been developed for constructing the traveling salesman problem with an optimal solution given in advance, which allows for a better understanding of the structure of traveling salesman problems. Conclusions. The results of computational experiments show that the use of potentials method technology for solving the traveling salesman problem, as a special transport problem, is a promising direction for searching for a high-quality solution. The developed algorithms and programs expand the possibilities of solving the traveling salesman problem. The time it takes to solve a problem depends significantly on the size of the problem. In this regard, it is essential to automatically generate the traveling salesman problem with a given optimal solution, which allows you to conduct mass experiments and draw conclusions. Keywords: travelling salesman problem, method of potentials, optimality criterion, cyclic substitution, route, algorithm.
Traveling purchaser problem
Lin–Kernighan heuristic
Christofides algorithm
Cite
Citations (1)
We present a genetic algorithm for solving the traveling salesman problem by genetic algorithms to optimality for traveling salesman problems with up to 442 cities. Mühlenbein et al. [MGK 88], [MK 89] have proposed a genetic algorithm for the traveling salesman problem, which generates very good but not optimal solutions for traveling salesman problems with 442 and 531 cities. We have improved this approach by improving all basic components of that genetic algorithm. For our experimental investigations we used the traveling salesman problems TSP (i) with i cities for i=137, 202, 229, 318, 431, 442, 666 which were solved to optimality in [CP 80], [GH 89]. We could solve medium sized traveling salesman problems with up to 229 cities in < 3 minutes average runtime on a SUN workstation. Furthermore we could solve traveling salesman problems with up to 442 cities optimally in an acceptable time limit (e.g. the average runtime on a SUN workstation for the TSP (431) is about 30 minutes). The greatest examined problem with 666 cities could be approximately solved by constructing a tour with length 0,04% over the optimum.
Christofides algorithm
Nearest neighbour algorithm
Traveling purchaser problem
Lin–Kernighan heuristic
Workstation
Cite
Citations (142)
Travelling Salesman Problem is a well known problem in operations research. TSP is short for The Travelling Salesman Problem. The general idea is that a peddler travels from one town, through many towns once, only once, and then returns to the original town, asking how to choose the route that will make the journey the shortest. In daily life, many problems can be reduced to this kind of problem. In fact, due to some conditions, the exact distance between the two towns can not be determined. By introducing the theory and concept of Grey for TSP, the grey TSP problem is produced. In this paper, the grey element is introduced into the Travelling Salesman Problem, and based on the grey traveling salesman model, a method of calculating the approximate lower limit of the Travelling Salesman Problem is given by reasoning proof.
Christofides algorithm
Traveling purchaser problem
Lin–Kernighan heuristic
Nearest neighbour algorithm
Cite
Citations (1)
This note proposes a new traveling-salesman problem, which is called Real-Life Traveling-Salesman Problem (RLTSP). RLTSP is quite close to the traveling-salesman problem in real life, and it is between the traditional traveling-salesman problem (TSP) and the graphical traveling-salesman problem (GTSP). An incomplete mathematics modeling of RLTSP is given in the note.
Traveling purchaser problem
Christofides algorithm
Nearest neighbour algorithm
Lin–Kernighan heuristic
Cite
Citations (0)
The Generalized Traveling Salesman Problem (GTSP) extends the classical Traveling Salesman Problem (TSP) and has many interesting applications. In this paper we propose a Continuous Selective Generalized Traveling Salesman Problem (CSGTSP), and the existing GTSP is only a special case of the CSGTSP. To solving it effectively, we extend the ant colony system method from TSP to CSGTSP. Meanwhile, to speed up the convergence and improve the quality of solution, a constrained local searching technique is introduced into this method according to the characteristic of the CSGTSP. Experimental results on numerous TSPLIB instances show that the proposed method can deal with the CSGTSP fairly well, and the developed local searching technique is significantly effective.
Ant colony
Extremal optimization
Cite
Citations (3)