\`x^2+y_1+z_12^34\`
Advanced Search
Advanced Search
Advanced Search
This issue Previous Article Next Article
Article Contents
Article Contents
2024, Volume 20, Issue 5: 1951-1966. Doi: 10.3934/jimo.2023150
This issue Previous Article Convergence properties of stochastic proximal subgradient method in solving a class of composite optimization problems with cardinality regularizer Next Article Insolvency prediction of Australian construction companies using deep learning with bidirectional LSTM autoencoder

A heuristic algorithm for the drone rural postman problem

  • 1.

    Nagoya University, Japan

  • 2.

    Shizuoka University, Japan

  • *Corresponding author: Ailing Xie

    *Corresponding author: Ailing Xie 
Received:  November 2022
Revised:  October 2023
Early access:  November 2023
Published:  May 2024

The first author is supported by [Graduate Program for Lifestyle Revolution based on Transdisciplinary Mobility Innovation].

Abstract / Introduction Full Text(HTML) Figure(5) / Table(4) Related Papers Cited by
    Abstract

  • 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.

    Mathematics Subject Classification: Primary: 90C27, 90C10; Secondary: 90B06.

    Citation:
    shu

    \begin{equation} \\ \end{equation}
    • FullText(HTML)
  • 加载中

  • Figure 1.  Required edges of instance DroneRPP66

    Download: Full-size image PowerPoint slide

    Figure 2.  Approximation by polygonal chains

    Download: Full-size image PowerPoint slide

    Figure 3.  An optimal route for instance DroneRPP66

    Download: Full-size image PowerPoint slide

    Figure 4.  Two graphs $ G_1 $ and $ G_2 $ with edge sets $ E_1 $ and $ E_2 $, respectively, and the graph $ G_3 $ having edges $ E_1 \uplus E_2 $

    Download: Full-size image PowerPoint slide

    Figure 5.  A tight example

    Download: Full-size image PowerPoint slide

    Table 1.  Results for $\mathtt{random}$ instances

    existing heuristic existing exact proposed Gurobi
    instance LB %gap time$ ^\dagger $ %gap time$ ^\dagger $ %gap time$ ^\ddagger $ %gap time$ ^\ddagger $
    DroneRPP561 4347.09 0.00 0.30 0.00 8.17 0.00 0.29 0.00 18.53
    DroneRPP562 5123.62 0.00 0.22 0.00 3.26 0.00 0.27 0.00 51.01
    DroneRPP581 5929.64 0.00 0.37 0.00 9.62 0.00 0.65 0.00 45.26
    DroneRPP582 7274.21 0.00 0.94 0.00 14.75 0.00 0.56 0.00 57.76
    DroneRPP5101 6592.95 0.02 0.35 0.00 36.53 0.00 1.07 0.00 72.45
    DroneRPP5102 10259.65 0.00 0.83 0.00 19.98 0.00 1.11 0.00 367.57
    DroneRPP661 4684.62 0.00 0.34 0.00 4.06 0.00 0.34 0.00 16.02
    DroneRPP662 5298.72 0.00 0.30 0.00 13.44 0.00 0.41 0.00 15.80
    DroneRPP681 6391.92 0.00 1.00 0.00 117.08 0.00 0.76 0.00 97.65
    DroneRPP682 8797.11 0.00 0.81 0.00 20.50 0.00 0.91 0.00 245.50
    DroneRPP6101 9258.50 0.01 0.53 0.00 23.68 0.00 9.63 0.00 320.32
    DroneRPP6102 12271.33 0.00 1.81 0.00 163.56 0.00 3.00 0.00 2830.16
    DroneRPP771 6654.00 0.00 1.25 0.00 744.85 0.00 5.07 0.00 450.74
    DroneRPP772 10441.46 0.00 0.94 0.00 5.75 0.00 0.88 0.00 185.02
    DroneRPP791 10039.18 0.00 1.78 t.l. t.l. 0.00 8.35 0.00 1461.35
    DroneRPP792 11946.27 0.01 0.97 0.00 55.77 0.00 3.13 0.00 888.95
    DroneRPP7101 11019.16 0.01 1.78 0.00 177.04 0.00 4.95 0.04 567.25
    DroneRPP7102 13425.04 0.00 0.72 0.00 27.05 0.00 1.85 0.00 480.76
    DroneRPP881 10263.85 0.00 0.88 0.00 41.93 0.00 3.88 0.00 631.35
    DroneRPP882 12538.78 0.00 11.30 0.00 217.18 0.00 2.61 0.00 744.61
    DroneRPP891 10911.38 0.01 2.41 0.00 3266.83 0.00 6.20 0.00 1590.72
    DroneRPP892 12519.73 0.00 0.53 0.00 28.43 0.00 2.28 0.00 534.00
    DroneRPP8101 12414.48 0.66 5.36 t.l. t.l. 0.66 33.68 0.91 2925.44
    DroneRPP8102 16020.01 0.00 1.95 0.00 49.41 0.00 3.27 0.01 2233.96
    DroneRPP991 12118.63 0.00 0.96 0.00 528.07 0.00 6.05 0.00 1977.60
    DroneRPP992 16365.53 0.00 2.66 0.00 159.89 0.00 3.81 0.07 2977.23
    DroneRPP9101 13282.73 0.00 3.53 0.00 46.13 0.00 6.04 0.00 1204.49
    DroneRPP9102 16636.71 0.01 4.20 0.00 830.98 0.00 16.59 0.58 1545.82
    DroneRPP10101 14997.03 0.00 1.28 0.00 129.41 0.00 6.18 0.64 1493.77
    DroneRPP10102 17532.11 0.01 13.13 0.00 1284.55 0.00 5.34 0.28 2926.56
    $^\dagger$ The CPU time on a PC with an Intel Core i7 running at 3.4 GHz with 32 GB memory.
    $^\ddagger$ The CPU time on a PC with Xeon E-2286G CPU running at 4.00~GHz, with 64~GB memory, with computations always conducted on a single thread.
     | Show Table
    DownLoad: CSV

    Table 2.  Results for $\mathtt{even}$ instances

    existing heuristic existing exact proposed Gurobi
    instance LB %gap time$ ^\dagger $ %gap time$ ^\dagger $ %gap time$ ^\ddagger $ %gap time$ ^\ddagger $
    DroneRPP56 5431.55 0.01 0.17 0.00 4.54 0.00 0.31 0.00 7.74
    DroneRPP58 6602.73 0.04 1.02 0.00 730.97 0.00 11.17 0.00 2340.35
    DroneRPP510 9608.49 0.03 1.05 0.00 73.30 0.00 3.12 0.00 3047.43
    DroneRPP66 4861.05 0.04 1.25 0.00 661.78 0.00 1.87 0.00 1026.47
    DroneRPP68 6899.64 0.15 3.55 0.00 2164.14 0.00 13.92 0.39 2041.82
    DroneRPP610 9436.44 1.08 9.19 t.l. t.l. 1.04 45.12 1.25 1645.07
    DroneRPP77 9656.78 0.10 1.92 t.l. t.l. 0.05 1.60 0.05 3267.05
    DroneRPP79 12076.52 0.02 2.14 0.00 1907.81 0.00 14.92 0.56 3552.19
    DroneRPP710 11416.28 0.06 2.86 0.00 929.52 0.00 8.60 0.03 2553.69
    DroneRPP88 10068.64 0.02 2.55 t.l. t.l. 0.00 21.56 0.00 667.88
    DroneRPP89 11236.67 t.l. t.l. t.l. t.l. 0.82 2432.04 0.95 3318.21
    DroneRPP810 13681.12 0.76 4.91 t.l. t.l. 0.68 64.71 0.74 3536.96
    DroneRPP99 12852.00 0.54 7.46 t.l. t.l. 0.51 17.09 0.66 3342.83
    DroneRPP910 17156.69 t.l. t.l. t.l. t.l. 1.35 630.82 2.45 2864.88
    DroneRPP1010 18157.81 0.85 336.21 t.l. t.l. 0.81 58.11 2.16 2069.51
    †The CPU time on a PC with an Intel Core i7 running at 3.4 GHz with 32 GB memory.
    ‡The CPU time on a PC with Xeon E-2286G CPU running at 4.00 GHz, with 64 GB memory, with computations always conducted on a single thread.
     | Show Table
    DownLoad: CSV

    Table 3.  Comparison between the existing heuristic algorithm and the proposed algorithm under the same environment for $\mathtt{random}$ instances

    existing heuristic proposed
    instance #vertices %gap time #vertices %gap time
    DroneRPP561 76 0.00 0.67 33 0.00 0.29
    DroneRPP562 89 0.00 0.36 30 0.00 0.27
    DroneRPP581 109 0.00 0.94 89 0.00 0.65
    DroneRPP582 139 0.00 1.08 24 0.00 0.56
    DroneRPP5101 127 0.02 1.27 78 0.00 1.07
    DroneRPP5102 191 0.00 0.92 40 0.00 1.11
    DroneRPP661 89 0.00 0.60 35 0.00 0.34
    DroneRPP662 107 0.00 0.28 30 0.00 0.40
    DroneRPP681 118 0.00 1.32 53 0.00 0.76
    DroneRPP682 177 0.00 2.77 33 0.00 0.91
    DroneRPP6101 169 0.01 1.91 135 0.00 9.63
    DroneRPP6102 226 0.00 6.19 80 0.00 3.00
    DroneRPP771 128 0.00 3.60 94 0.00 5.07
    DroneRPP772 186 0.00 2.45 22 0.00 0.88
    DroneRPP791 170 0.00 8.25 125 0.00 8.35
    DroneRPP792 232 0.01 5.56 93 0.00 3.13
    DroneRPP7101 211 0.01 10.26 126 0.00 4.95
    DroneRPP7102 254 0.00 1.86 51 0.00 1.85
    DroneRPP881 193 0.00 3.39 149 0.00 3.88
    DroneRPP882 242 0.00 2.68 78 0.00 2.61
    DroneRPP891 220 0.01 7.59 142 0.00 6.20
    DroneRPP892 242 0.00 3.29 59 0.00 2.28
    DroneRPP8101 237 0.66 18.39 169 0.66 33.68
    DroneRPP8102 302 0.00 14.77 71 0.00 3.27
    DroneRPP991 232 0.00 8.40 109 0.00 6.05
    DroneRPP992 308 0.00 11.60 87 0.00 3.81
    DroneRPP9101 254 0.00 4.08 193 0.00 6.04
    DroneRPP9102 315 0.01 36.21 192 0.00 16.59
    DroneRPP10101 281 0.00 6.29 185 0.00 6.18
    DroneRPP10102 335 0.01 20.89 111 0.00 16.59
     | Show Table
    DownLoad: CSV

    Table 4.  Comparison between the existing heuristic algorithm and the proposed algorithm under the same environment for $\mathtt{even}$ instances

    existing heuristic proposed
    instance #vertices %gap time #vertices %gap time
    DroneRPP56 94 0.01 0.27 22 0.00 0.31
    DroneRPP58 121 0.04 9.96 75 0.00 11.17
    DroneRPP510 185 0.03 16.40 72 0.00 3.12
    DroneRPP66 95 0.04 4.86 39 0.00 1.87
    DroneRPP68 130 0.15 65.52 51 0.00 13.92
    DroneRPP610 175 1.08 78.64 108 1.04 45.12
    DroneRPP77 177 0.10 9.09 38 0.05 1.60
    DroneRPP79 232 0.02 19.60 112 0.00 14.92
    DroneRPP710 220 0.06 14.86 134 0.00 8.60
    DroneRPP88 193 0.02 19.60 169 0.00 21.56
    DroneRPP89 226 0.95 1266.41 144 0.82 2432.04
    DroneRPP810 270 0.76 78.21 132 0.68 64.71
    DroneRPP99 247 0.54 23.17 138 0.51 17.09
    DroneRPP910 339 1.38 3571.23 152 1.35 630.82
    DroneRPP1010 359 0.85 128.94 155 0.81 58.11
     | Show Table
    DownLoad: CSV
    • Related Papers
  • Cited by
  • References
  • [1] J. F. Campbell, Á. Corberán, I. Plana and J. M. Sanchis, Drone arc routing problems, Networks, 72 (2018), 543-559.  doi: 10.1002/net.21858.
    [2] J. F. Campbell, Á. Corberán, I. Plana, J. M. Sanchis and P. Segura, Solving the length constrained $K$-drones rural postman problem, European Journal of Operational Research, 292 (2021), 60-72.  doi: 10.1016/j.ejor.2020.10.035.
    [3] A. Corberán, I. Plana and J. M. Sanchis, A branch & cut algorithm for the windy general routing problem and special cases, Networks, 49 (2007), 245-257.  doi: 10.1002/net.20176.
    [4] H. A. Eiselt, M. Gendreau and G. Laporte, Arc routing problems, part Ⅰ : The Chinese postman problem, Operations Research, 43 (1995), 231-242.  doi: 10.1287/opre.43.2.231.
    [5] H. A. Eiselt, M. Gendreau and G. Laporte, Arc routing problems, part Ⅱ: The rural postman problem, Operations Research, 43 (1995), 399-414.  doi: 10.1287/opre.43.3.399.
    [6] M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, 1979.
    [7] S. Poikonen and J. F. Campbell, Future directions in drone routing research, Networks, 77 (2021), 116-126.  doi: 10.1002/net.21982.
    • Access History
  • 加载中

Figures(5)

Tables(4)

PDF
XML
Export Citation
SHARE
Email to a Friend

Article Metrics

HTML views(3808) PDF downloads(276) Cited by(0)

Access History

Other Articles By Authors

Catalog

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return
    Site map Copyright © 2025 American Institute of Mathematical Sciences