eISSN: 2574-8092

International Robotics & Automation Journal

Correspondence:

Received: January 01, 1970 | Published: ,

Citation: DOI:

Download PDF

Abstract

Routing problems is used to find an optimal path from the starting point to the target point. There are some problems with traditional path planning problem. For example, before the path planning, path planning personnel cannot fully grasp all the relevant information about path planning; some information may be unknown, vague or uncertain. After the path planning, partial information may change in the process of actual transportation (such as vehicle traffic time, customer demand, etc.). So, uncertain path problem is more meaningful in practical application. In this paper, different path planning algorithm with uncertain factors was summarized by Probabilistic Travelling Salesman Problem (PTSP) and Selective Traveling Salesman Problem (STSP) and their advantages were analyzed and compared.

Keywords: routing problems, uncertain factor, PTSP, STSP

Overview

Compared with traditional path planning, uncertain path problem contains two kinds of important uncertainties in real application information: information evolution and information quality. Information evolution refers to certain information changes in the actual process of transportation. For example, vehicle travel time can be influenced by real-time traffic conditions, which will change at any time. In the distribution service, there may be new customers to create new demand, etc. Information quality is to point to some of the information uncertainty, such as path planner can only be learned that the customer's actual demand is according to some probability distribution.

The problem of uncertain path planning

The probabilistic traveling salesman problem

The Probabilistic traveling Salesman Problem (PTSP) is an uncertain form of TSP problem. In the Problem of PTSP, the customer demand is random. So, PTSP is also a NP-hard Problem. Campbell & Thomas¹ introduce the PTSP time constraint for the first time. In the article, each customer must be served within the stipulated time. The author build two stochastic models and a chance constrained programming model, the author also discusses the special situation of each model. Campbell & Thomas² then put forward the approximate method to solve the problem. Voccia et al.,³ put forward the probabilistic traveling salesman problem with time Windows for the first time and constructed a model with fixed the problem, and then designed a mutable field search algorithm to solve the model. Liu⁴ study the PTSP solved with genetic algorithm, which focus on the influence of different initial solution on the quality of the solution. Other PTSP mainly focused on the heuristic algorithms.^5–7

Selective traveling salesman problem

Selective Traveling Salesman Problem (STSP) is an extended method of the Traveling Salesman Problem (TSP). In STSP, traveling salesman can obtain certain profit by visiting the customer. Is usually is described as a vehicle starts from the distribution center, in the case of satisfying certain conditions (vehicle mileage limit, time limit, etc.), visits some given customers, maximizes the total profit, and eventually returns to distribution center. Erdogan & Laporte⁸ proposed an extension of STSP problem. There is certain profit on the node. The profit and length of stay in the node were positively correlated. The target of the algorithm is to find a path with maximizing profit under the limit of travel time. In order to solve the path optimization problem which contains random travel time and service time, Papapanagiotou et al.,⁹ put forward a evaluation method about objective function. Pietz & Royset¹⁰ studied the generalized OP problem, with a reward on the issue. The vehicles running on different paths will consume random number of limited resources, and the amount of rewards is determined according to the size of the consumption of resources. The goal is to visit some customers and maximize collected reward within the given time. Zhang et al.,¹¹ researched problems in the pharmaceutical industry. Sales representatives need to have an appointment with the doctor when they promote new relevant drugs. Because there may be multiple sales representatives visiting the same doctor, the sales representatives have to wait random time. The author constructed an OP problem with random wait time and time windows to this situation. His aim is to maximize the expected sales, solve the problem with variable domain search algorithm. Evers et al.,¹² considered the OP problem with capacity constraints and random weight. Vehicles will collect goods with random weight to find out a most profitable path under the capacity constraints. The author proposed a two-stage modified stochastic model and designed the heuristic algorithm to solve the model. Allahviranloo et al.,¹³ put forward three kinds of uncertain selective traveling salesman problem, according to different levels of demand uncertainty, and presented a parallel genetic algorithm to solve these problems. Research has shown that parallel genetic algorithm has higher efficiency. Papapanagiotou et al.,¹⁴ studied the OP with stochastic travel time and service time.

Conclusion

The paper studies the current path planning algorithms with uncertain factors, the application scope of them, and the classification of the path planning.