| Autor: |
Xie, Ailing, Miyagawa, Keigo, Wu, Wei, Yagiura, Mutsunori |
| Předmět: |
|
| Zdroj: |
Journal of Industrial & Management Optimization; May2024, Vol. 20 Issue 5, p1-16, 16p |
| Abstrakt: |
In this paper, we consider the drone rural postman problem (DRPP). Unlike a vehicle in the traditional rural postman problem, a drone can travel directly between any two points without following the edges of the graph. Thus, a drone can start (or restart) and end (or pause) the service of an edge at any two points of it, and an edge can be serviced separately (e.g., from an end point to the middle point in the first visit and the remaining half in the second visit). This property implies that a lower cost solution may be obtained by using a drone. In DRPP instances, the input data are represented by approximating each edge that have to be traversed by a polygonal chain with a finite number of vertices, allowing the drone to enter and exit each edge at these vertices. For this problem, we propose a heuristic algorithm consisting of two phases. In the first phase, we reduce the size of the original graph by considering the degree of each vertex and the cheapest travel costs between connected components. In the second phase, we solve the rural postman problem on the resulting graph. We show that the proposed two-phase heuristic has a performance guarantee of ratio 2. The experimental results on benchmark instances show that the proposed algorithm outperforms other existing algorithms. [ABSTRACT FROM AUTHOR] |
| Databáze: |
Complementary Index |
| Externí odkaz: |
|
