# Path Planning of Rail-Mounted Logistics Robots Based on the Improved Dijkstra Algorithm
## 1 Introduction  
Rail-mounted logistics robots are suitable for complex material distributions in large production workshops with fixed routes and long distances. The goal of robot path planning is to find the shortest path from the starting point to the target point without conflict. The application scenario of this paper is for large-scale workshop material distribution, especially in ultra-clean semiconductor chip production workshops. The walkable track of the logistics robot is laid on the top of the workshop, and the robot can reach all the cargo stations and workstations in the workshop along the track. When each workstation needs a certain material, it passes the out-of-stock information to the system. After receiving multiple out-of-stock notifications, the system starts the robot from the material station, distributes the goods to the corresponding workstation along the track, and then returns to the goods station. There may be one or more cargo stations inside the workshop. Basedon the calculation of the optimization algorithm, multiple logistics robots cooperate to complete all the material delivery tasks, which can reduce labor costs and improve the efficiency of material delivery to a large extent. However, overlapping path regions occur when multiple robots perform distribution tasks along the track. Therefore, to avoid robot on-orbit conflicts and invalid waiting, we need to consider the coordination method for robot on-orbit conflicts. In the field of computer science, according to the definition of the deterministic Turing machine model and non-deterministic Turing machine model, the traveling salesman problem (TSP), graph coloring problem (GCP), vertex cover, and other classical problems are defined as non-deterministic polynomial problems (NP), NP-hard (NPH), and NP-complete (NPC) [1,2]. A problem is said to be NP-hard if all the NP-class problems are reduced to a single problem. NP-hard problems are more general than NP-complete problems, and it is difficult to find exact solutions in polynomial time. The resources in this paper include the number of parallel tracks, payloads, and robots. The MD-MTSP problem dealt with by the algorithm proposed in this paper has discrete time, and it is relatively easy to find a feasible solution within the resource condition, but the optimal solution is almost impossible to find within an acceptable time. However, beyond the resource conditions, it is an NP-hard problem, which cannot be solved in polynomial time. In this paper, the path-planning problem of the rail-mounted logistics robot is modeled as a multi-depot multiple traveling salesman problem (MD-MTSP); that is, the robot is abstracted as a traveling salesman, and the material station and work station are abstracted as a city. A number of traveling salesmen depart from many different cities, each of which must be visited by at least one salesman, and only once, except for the origin and destination cities. Under this condition, the shortest path traversing all the cities is found. The multi-depot multiple traveling salesman problem is a kind of multiple traveling salesman problem. The multiple traveling salesman problem is an extension of the famous traveling salesman problem (TSP). It is an NP-hard problem and has a strong engineering background and application value. The commonly used path planning algorithms include the A* algorithm [3,4], [PERSON] algorithm [5,6], particle swarm optimization (PSO) [7], [PERSON] algorithm [6], PRM algorithm [7], RRT algorithm [8], genetic algorithm (GA) [8, 9, 10], and ant colony optimization (ACO) [11,12]. These methods should be further improved when considering the path allocation, energy allocation, and global shortest path, thereby ensuring the robustness and fault tolerance of the multi-machine system. PSO, GA, and ACO are heuristic algorithms, which generally have shortcomings, including susceptibility to falling into a local optimum, premature convergence, and limited scope of application.