Yandong Liu,∗,∗∗ Dong Han,∗,∗∗ Lujia Wang,∗ and Cheng-zhong Xu∗∗∗
Task sequence planning problem, topological relationship, autonomous logistics vehicle
The task sequence planning problem (TSPP) is one of the most significant combinatorial optimization problems. In this paper, we formulate the TSPP and prove that the optimal task se- quence planning problem (OTSPP) is NP-complete based on the graph theory. We incorporate the idea of topological sorting into the solution and propose the exact method, named all topology sort minimum distance (ATS-MD). Given the shortcomings of the ATS-MD, the time complexity is very high. We use the idea of dynamic programming to reduce the search range of the algorithm and propose the dynamic programming based on topological rela- tionship algorithm (DP-TR). However, both ATS-MD and DP-TR are unable to cope with largescale OTSPP. We present a hybrid ge- netic algorithm, genetic algorithm based on topological relationship (GA-TR), which can give an approximate solution to the large-scale OTSPP in a feasible time. The results of numerical experiments prove the validity of the three algorithms.
Important Links:
Go Back
