Expected Length of the Shortest Path of the Traveling Salesman Problem in 3D Space
Finding the shortest path of the traveling salesman problem (TSP) is a typical NP-hard problem and one of the basic optimization problems. TSP in three-dimensional space (3D-TSP) is an extension of TSP. It plays an important role in the fields of 3D path planning and UAV inspection, such as forest f...
Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2022-01-01
|
| Series: | Journal of Advanced Transportation |
| Online Access: | http://dx.doi.org/10.1155/2022/4124950 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1849306984329773056 |
|---|---|
| author | Hongtai Yang Xiaoqian Lu Xinan Zhou Rong Zheng Yugang Liu Siyu Tao |
| author_facet | Hongtai Yang Xiaoqian Lu Xinan Zhou Rong Zheng Yugang Liu Siyu Tao |
| author_sort | Hongtai Yang |
| collection | DOAJ |
| description | Finding the shortest path of the traveling salesman problem (TSP) is a typical NP-hard problem and one of the basic optimization problems. TSP in three-dimensional space (3D-TSP) is an extension of TSP. It plays an important role in the fields of 3D path planning and UAV inspection, such as forest fire patrol path planning. Many existing studies have focused on the expected length of the shortest path of TSP in 2D space. The expected length of the shortest path in 3D space has not yet been studied. To fill this gap, this research focuses on developing models to estimate the expected length of the shortest path of 3D-TSP. First, different experimental scenarios are designed by combining different service areas and the number of demand points. Under each scenario, the specified number of demand points is randomly generated, and an improved genetic algorithm and Gurobi are used to find the shortest path. A total of 500 experiments are performed for each scenario, and the average length of the shortest path is calculated. The models to estimate the expected length of the shortest path are proposed. Model parameters are estimated and k-fold cross-validation is used to evaluate the goodness of fit. Results show that all the models fit the data well and the best model is selected. The developed models can be used to estimate the expected length of the shortest path of 3D-TSP and provide important references for many applications. |
| format | Article |
| id | doaj-art-249bdd1ae9294eab8e30a1673c5f85b7 |
| institution | Kabale University |
| issn | 2042-3195 |
| language | English |
| publishDate | 2022-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | Journal of Advanced Transportation |
| spelling | doaj-art-249bdd1ae9294eab8e30a1673c5f85b72025-08-20T03:54:53ZengWileyJournal of Advanced Transportation2042-31952022-01-01202210.1155/2022/4124950Expected Length of the Shortest Path of the Traveling Salesman Problem in 3D SpaceHongtai Yang0Xiaoqian Lu1Xinan Zhou2Rong Zheng3Yugang Liu4Siyu Tao5School of Transportation and LogisticsSchool of Transportation and LogisticsSchool of Transportation and LogisticsSchool of Transportation and LogisticsSchool of Transportation and LogisticsSchool of Transportation and LogisticsFinding the shortest path of the traveling salesman problem (TSP) is a typical NP-hard problem and one of the basic optimization problems. TSP in three-dimensional space (3D-TSP) is an extension of TSP. It plays an important role in the fields of 3D path planning and UAV inspection, such as forest fire patrol path planning. Many existing studies have focused on the expected length of the shortest path of TSP in 2D space. The expected length of the shortest path in 3D space has not yet been studied. To fill this gap, this research focuses on developing models to estimate the expected length of the shortest path of 3D-TSP. First, different experimental scenarios are designed by combining different service areas and the number of demand points. Under each scenario, the specified number of demand points is randomly generated, and an improved genetic algorithm and Gurobi are used to find the shortest path. A total of 500 experiments are performed for each scenario, and the average length of the shortest path is calculated. The models to estimate the expected length of the shortest path are proposed. Model parameters are estimated and k-fold cross-validation is used to evaluate the goodness of fit. Results show that all the models fit the data well and the best model is selected. The developed models can be used to estimate the expected length of the shortest path of 3D-TSP and provide important references for many applications.http://dx.doi.org/10.1155/2022/4124950 |
| spellingShingle | Hongtai Yang Xiaoqian Lu Xinan Zhou Rong Zheng Yugang Liu Siyu Tao Expected Length of the Shortest Path of the Traveling Salesman Problem in 3D Space Journal of Advanced Transportation |
| title | Expected Length of the Shortest Path of the Traveling Salesman Problem in 3D Space |
| title_full | Expected Length of the Shortest Path of the Traveling Salesman Problem in 3D Space |
| title_fullStr | Expected Length of the Shortest Path of the Traveling Salesman Problem in 3D Space |
| title_full_unstemmed | Expected Length of the Shortest Path of the Traveling Salesman Problem in 3D Space |
| title_short | Expected Length of the Shortest Path of the Traveling Salesman Problem in 3D Space |
| title_sort | expected length of the shortest path of the traveling salesman problem in 3d space |
| url | http://dx.doi.org/10.1155/2022/4124950 |
| work_keys_str_mv | AT hongtaiyang expectedlengthoftheshortestpathofthetravelingsalesmanproblemin3dspace AT xiaoqianlu expectedlengthoftheshortestpathofthetravelingsalesmanproblemin3dspace AT xinanzhou expectedlengthoftheshortestpathofthetravelingsalesmanproblemin3dspace AT rongzheng expectedlengthoftheshortestpathofthetravelingsalesmanproblemin3dspace AT yugangliu expectedlengthoftheshortestpathofthetravelingsalesmanproblemin3dspace AT siyutao expectedlengthoftheshortestpathofthetravelingsalesmanproblemin3dspace |