pith. sign in

arxiv: 2411.17510 · v2 · submitted 2024-11-26 · 🧮 math.OC

An Adaptive Variable Neighborhood Search for a Family of Set Covering Routing Problems with an Application in Disaster Relief Operations

Andreas Hagn , Jan Krause , Moritz Stargalla , Lorenza Moreno This is my paper

Pith reviewed 2026-05-23 16:33 UTC · model grok-4.3

classification 🧮 math.OC
keywords set covering routing problemadaptive variable neighborhood searchdisaster relief operationshumanitarian logisticscovering tour problemmulti-depot vehicle routinghelicopter distribution
0
0 comments X

The pith

An adaptive variable neighborhood search solves integrated landing site, routing, and covering decisions in multi-depot disaster relief logistics.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper develops an adaptive variable neighborhood search for a variant of the set covering routing problem that integrates helicopter landing site location, vehicle routing, and demand covering under facility capacities and multiple depots. This hybrid distribution model addresses post-disaster accessibility by using air transport for most movement and ground transport only for the last mile. The method is evaluated on benchmark instances of the related multi-vehicle covering tour problem and vehicle routing with demand allocation problem, where it produces solution quality competitive with specialized state-of-the-art approaches. The approach is further demonstrated on a case study of the 2024 Afghanistan flash floods to generate practical distribution plans.

Core claim

The adaptive variable neighborhood search combines established routing operators with novel mechanisms for covering decisions to solve the facility-capacitated multi-depot set covering routing problem, achieving competitive solution quality on m-CTP and VRDAP benchmark instances while supporting real-world application to disaster response operations.

What carries the argument

The Adaptive Variable Neighborhood Search (AVNS) that integrates routing operators with novel covering decision mechanisms.

If this is right

  • The AVNS produces solutions of quality comparable to problem-specific methods on m-CTP and VRDAP benchmarks.
  • The approach yields managerial insights into effective distribution strategies for disaster response operations.
  • The integrated model supports simultaneous decisions on landing sites, routes, and covering in capacitated multi-depot settings.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same search framework could be adapted to other hybrid transport problems that mix air and ground modes under coverage requirements.
  • Adding dynamic updates to the covering decisions might allow the method to respond to changing accessibility conditions during an ongoing disaster.
  • Exact solvers on small instances could be used to quantify the optimality gap of the AVNS solutions.

Load-bearing premise

The hybrid helicopter-ground distribution model with limited last-mile ground transport accurately represents real post-disaster accessibility constraints.

What would settle it

Running the AVNS on the Afghanistan case study instances and comparing its generated coverage times and routes against observed actual aid delivery records from the 2024 floods to check for systematic mismatches in accessibility predictions.

Figures

Figures reproduced from arXiv: 2411.17510 by Andreas Hagn, Jan Krause, Lorenza Moreno, Moritz Stargalla.

Figure 1
Figure 1. Figure 1: Example solution for a CTLRP instance and solution [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: CTLRP and similar problems. Depots, intermediate facilities and customers are represented by pink [PITH_FULL_IMAGE:figures/full_fig_p004_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Elementary and non-elementary path constraints [PITH_FULL_IMAGE:figures/full_fig_p010_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Intra route operators 2opt This operator, as shown in Figure 4a, first removes two disjoint edges (a, b) and (c, d) and then inserts two new edges (a, c) and (b, d). 13 [PITH_FULL_IMAGE:figures/full_fig_p013_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Inter route operators 1point move This operator iterates over facilities from R1 and looks for an improvement while inserting it into R2 (Figure 5a). Note that this operator is sensitive to the input order R1, R2. 2point move 2point iterates over all facility-pairs of R1 and R2 and looks for an improvement while exchang￾ing them (Figure 5b). 2opt* This operator only considers two distinct routes belonging … view at source ↗
Figure 6
Figure 6. Figure 6: Instances of category (1) with the corresponding Gap = 100( [PITH_FULL_IMAGE:figures/full_fig_p025_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: Instances of category (2) with the corresponding Gap = 100( [PITH_FULL_IMAGE:figures/full_fig_p026_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: Instances of category (2) with the corresponding Gap = 100( [PITH_FULL_IMAGE:figures/full_fig_p026_8.png] view at source ↗
Figure 9
Figure 9. Figure 9: Instances of category (3) with corresponding MIP-LB Gap = 100( [PITH_FULL_IMAGE:figures/full_fig_p027_9.png] view at source ↗
Figure 10
Figure 10. Figure 10: Time (s) to attain the heuristic values with the MIP. Instances where [PITH_FULL_IMAGE:figures/full_fig_p027_10.png] view at source ↗
read the original abstract

This paper studies a variant of the Set Covering Routing Problem (SCRP) motivated by post-disaster humanitarian logistics. We consider a hybrid distribution concept in which the majority of transportation is performed by helicopters, while ground transport is limited to the last mile, addressing severe accessibility constraints in disaster-affected regions. The resulting problem integrates landing site location, routing, and covering decisions, incorporating features of the Multi-Vehicle Covering Tour Problem (m-CTP) and the Vehicle Routing with Demand Allocation Problem (VRDAP) in a facility-capacitated, multi-depo setting. Due to the computational complexity of the problem, we develop an Adaptive Variable Neighborhood Search (AVNS) that combines established routing operators with novel mechanisms for covering decisions. The performance of the proposed approach is evaluated on benchmark instances for the related m-CTP and VRDAP problems, demonstrating competitive solution quality compared to problem-specific state-of-the-art approaches. Furthermore, we apply our AVNS to a real-world case study based on the 2024 flash floods in Afghanistan. The results highlight the practical relevance of the proposed framework and provide managerial insights into effective distribution strategies for disaster response operations.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 1 minor

Summary. The manuscript proposes an Adaptive Variable Neighborhood Search (AVNS) metaheuristic for a capacitated multi-depot variant of the Set Covering Routing Problem arising in post-disaster humanitarian logistics. The model integrates helicopter landing-site location, routing, and demand-covering decisions under a hybrid distribution concept that combines the Multi-Vehicle Covering Tour Problem (m-CTP) and Vehicle Routing with Demand Allocation Problem (VRDAP). The AVNS augments standard routing operators with new covering mechanisms; its performance is asserted to be competitive with problem-specific state-of-the-art methods on m-CTP and VRDAP benchmark sets, and the method is demonstrated on a real-world instance drawn from the 2024 Afghanistan floods.

Significance. If the empirical competitiveness claim is substantiated with detailed numerical comparisons, the work supplies a reusable algorithmic template for set-covering routing problems that arise under severe accessibility constraints; the explicit linkage of the hybrid-distribution model to a recent disaster event also supplies a concrete test bed for managerial insights on last-mile relief operations.

major comments (2)
  1. [Abstract] Abstract: the central claim that the AVNS 'demonstrates competitive solution quality compared to problem-specific state-of-the-art approaches' is unsupported by any tabulated objective values, percentage gaps, instance sizes, statistical tests, or runtime figures; without these data the performance assertion cannot be evaluated.
  2. [§4] §4 (Algorithm Description): the novel covering-decision mechanisms are introduced at a conceptual level but lack explicit pseudocode, neighborhood definitions, or acceptance criteria that would allow independent reproduction or verification of the claimed integration advantages over standard VNS.
minor comments (1)
  1. [Introduction] The motivation paragraph on hybrid distribution would benefit from a short table contrasting the new model features with those of m-CTP and VRDAP to clarify the precise extensions.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the constructive feedback. We address each major comment below, indicating whether revisions are planned.

read point-by-point responses

  1. Referee: [Abstract] Abstract: the central claim that the AVNS 'demonstrates competitive solution quality compared to problem-specific state-of-the-art approaches' is unsupported by any tabulated objective values, percentage gaps, instance sizes, statistical tests, or runtime figures; without these data the performance assertion cannot be evaluated.

    Authors: Detailed numerical results supporting the competitiveness claim—including objective values, percentage gaps, instance sizes, runtimes, and statistical comparisons—are provided in Section 5 on the m-CTP and VRDAP benchmark sets. The abstract summarizes these findings at a high level. To improve clarity, we will revise the abstract to explicitly reference Section 5 and highlight key performance metrics. revision: partial

  2. Referee: [§4] §4 (Algorithm Description): the novel covering-decision mechanisms are introduced at a conceptual level but lack explicit pseudocode, neighborhood definitions, or acceptance criteria that would allow independent reproduction or verification of the claimed integration advantages over standard VNS.

    Authors: We agree that explicit pseudocode and precise definitions would enhance reproducibility. In the revised manuscript we will add pseudocode for the novel covering mechanisms, formal neighborhood definitions, and the acceptance criteria used within the AVNS. revision: yes

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper presents an algorithmic heuristic (AVNS) for a set covering routing problem variant and evaluates its performance empirically on existing benchmark sets for related problems (m-CTP, VRDAP) plus a case study. No derivation chain, equations, or first-principles predictions exist that could reduce to fitted inputs or self-citations by construction. The claims rest on standard computational testing of an algorithmic construction, with no load-bearing self-referential steps or renamings of known results.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Review performed on abstract only; no explicit free parameters, axioms or invented entities are stated. Standard combinatorial optimization modeling assumptions are implicit but not enumerated.

pith-pipeline@v0.9.0 · 5744 in / 1112 out tokens · 44260 ms · 2026-05-23T16:33:42.896464+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

46 extracted references · 46 canonical work pages

  1. [1]

    Allahyari, S., Salari, M., and Vigo, D. (2015). A hybrid metaheuristic algorithm for the multi-depot covering tour vehicle routing problem. European Journal of Operational Research, 242:756–768

    work page 2015

  2. [2]

    and Green, W

    Altay, N. and Green, W. G. (2006). Or/ms research in disaster operations management. European Journal of Operational Research, 175:475–493

    work page 2006

  3. [3]

    Baldacci, R., Hadjiconstantinou, E., and Mingozzi, A. (2004). An exact algorithm for the capacitated vehicle routing problem based on a two-commodity network flow formulation. Operations research, 52:723–738

    work page 2004

  4. [4]

    and Nascimento, E

    Beasley, J. and Nascimento, E. (1996). The vehicle routing-allocation problem: A unifying framework. Top, 4:65–86

    work page 1996

  5. [5]

    Belenguer, J.-M., Benavent, E., Prins, C., Prodhon, C., and Wolfler Calvo, R. (2011). A branch-and-cut method for the capacitated location-routing problem. Computers & Operations Research, 38:931–941

    work page 2011

  6. [6]

    and Novellani, S

    Buzzega, G. and Novellani, S. (2023). Last mile deliveries with lockers: Formulations and algorithms. Soft Computing, 27:12843–12861

    work page 2023

  7. [7]

    M., Thompson, R

    Cheng, C., Zhu, R., Costa, A. M., Thompson, R. G., and Huang, X. (2022). Multi-period two-echelon location routing problem for disaster waste clean-up. Transportmetrica A: Transport Science, 18:1053–1083

    work page 2022

  8. [8]

    Conforti, M., Cornu´ ejols, G., and Zambelli, G. (2014). Integer programming models. Springer

    work page 2014

  9. [9]

    Contardo, C., Cordeau, J.-F., and Gendron, B. (2013). A computational comparison of flow formulations for the capacitated location-routing problem. Discrete Optimization, 10:263–295

    work page 2013

  10. [10]

    and Wøhlk, S

    Cubillos, M. and Wøhlk, S. (2021). Solution of the maximal covering tour problem for locating recycling drop-off stations. Journal of the Operational Research Society , 72:1898–1913

    work page 2021

  11. [11]

    Dumez, D., Lehu´ ed´ e, F., and P´ eton, O. (2021). A large neighborhood search approach to the vehicle routing problem with delivery options. Transportation Research Part B: Methodological, 144:103–132

    work page 2021

  12. [12]

    Fischer, V., Legrain, A., and Schindl, D. (2024). A benders decomposition approach for a capacitated multi-vehicle covering tour problem with intermediate facilities. In Dilkina, B., editor, Integration of Con- straint Programming, Artificial Intelligence, and Operations Research, pages 277–292, Cham. Springer Nature Switzerland

    work page 2024

  13. [13]

    Gauthier, J. B. and Irnich, S. (2024). Inter-depot moves and dynamic-radius search for multi-depot vehicle routing problems. Discrete Applied Mathematics, 346:131–153

    work page 2024

  14. [14]

    Gendreau, M., Laporte, G., and Semet, F. (1997). The covering tour problem. Operations Research, 45:568– 576

    work page 1997

  15. [15]

    Glize, E., Roberti, R., Jozefowiez, N., and Ngueveu, S. U. (2020). Exact methods for mono-objective and bi-objective multi-vehicle covering tour problems. European Journal of Operational Research, 283:812–824

    work page 2020

  16. [16]

    and Malmir, B

    Goli, A. and Malmir, B. (2020). A covering tour approach for disaster relief locating and routing with fuzzy demand. International journal of intelligent transportation systems research , 18:140–152

    work page 2020

  17. [17]

    F., and Hartl, R

    Grabenschweiger, J., D¨ orner, K. F., and Hartl, R. F. (2022). The multi-period location routing problem with locker boxes. Logistics Research, 15:1–25

    work page 2022

  18. [18]

    H., Bostel, N., Langevin, A., and Rousseau, L.-M

    Ha, M. H., Bostel, N., Langevin, A., and Rousseau, L.-M. (2013). An exact algorithm and a metaheuristic for the multi-vehicle covering tour problem with a constraint on the number of vertices. European Journal of Operational Research, 226:211–220

    work page 2013

  19. [19]

    J., Laporte, G., and Semet, F

    Hachicha, M., Hodgson, M. J., Laporte, G., and Semet, F. (2000). Heuristics for the multi-vehicle covering tour problem. Computers & Operations Research, 27:29–42

    work page 2000

  20. [20]

    Hu, H., Li, X., Zhang, Y., Shang, C., and Zhang, S. (2019). Multi-objective location-routing model for hazardous material logistics with traffic restriction constraint in inter-city roads. Computers & Industrial Engineering, 128:861–876

    work page 2019

  21. [21]

    Janinhoff, L., Klein, R., Sailer, D., and Schoppa, J. M. (2024). Out-of-home delivery in last-mile logistics: A review. Computers & Operations Research, 168:106686

    work page 2024

  22. [22]

    Kammoun, M., Derbel, H., Ratli, M., and Jarboui, B. (2017). An integration of mixed vnd and vns: the case of the multivehicle covering tour problem. International Transactions in Operational Research, 24:663–679. 29

    work page 2017

  23. [23]

    and Nobert, Y

    Laporte, G. and Nobert, Y. (1981). An exact algorithm for minimizing routing and operating costs in depot location. European Journal of Operational Research, 6:224–226. Location Decisions

    work page 1981

  24. [24]

    H., Mahjoub, A

    Liguori, P. H., Mahjoub, A. R., Marques, G., Sadykov, R., and Uchoa, E. (2023). Nonrobust strong knapsack cuts for capacitated location routing and related problems. Operations Research, 71:1577–1595

    work page 2023

  25. [25]

    A., and Salles da Cunha, A

    Lopes, R., Souza, V. A., and Salles da Cunha, A. (2013). A branch-and-price algorithm for the multi-vehicle covering tour problem. Electronic Notes in Discrete Mathematics , 44:61–66

    work page 2013

  26. [26]

    and Gansterer, M

    Mancini, S. and Gansterer, M. (2021). Vehicle routing with private and shared delivery locations. Computers & Operations Research, 133:105361

    work page 2021

  27. [27]

    Mara, S. T. W., Kuo, R., and Asih, A. M. S. (2021). Location-routing problem: a classification of recent research. International Transactions in Operational Research, 28:2941–2983

    work page 2021

  28. [28]

    Nedjati, A., Izbirak, G., and Arkat, J. (2017). Bi-objective covering tour location routing problem with replenishment at intermediate depots: Formulation and meta-heuristics. Computers & Industrial Engineering , 110:191–206

    work page 2017

  29. [29]

    Oliveira, B., Pessoa, A., and Roboredo, M. (2024). New cuts and a branch-cut-and-price model for the multi-vehicle covering tour problem

    work page 2024

  30. [30]

    and Ropke, S

    Pisinger, D. and Ropke, S. (2018). Large neighborhood search. In Handbook of Metaheuristics, pages 99–127. Springer

    work page 2018

  31. [31]

    Rasku, J., K¨ arkk¨ ainen, T., and Musliu, N. (2019). Meta-survey and implementations of classical capaci- tated vehicle routing heuristics with reproduced results. Toward Automatic Customization of Vehicle Routing Systems, pages 133–260

    work page 2019

  32. [32]

    and Ghoniem, A

    Reihaneh, M. and Ghoniem, A. (2018). A multi-start optimization-based heuristic for a food bank distribu- tion problem. Journal of the Operational Research Society , 69:691–706

    work page 2018

  33. [33]

    and Ghoniem, A

    Reihaneh, M. and Ghoniem, A. (2019). A branch-and-price algorithm for a vehicle routing with demand allocation problem. European Journal of Operational Research, 272:523–538

    work page 2019

  34. [34]

    and Drexl, M

    Schneider, M. and Drexl, M. (2017). A survey of the standard location-routing problem. Annals of Operations Research, 259:389–414

    work page 2017

  35. [35]

    M., Kinable, J., Dellaert, N., and Van Woensel, T

    Sluijk, N., Florio, A. M., Kinable, J., Dellaert, N., and Van Woensel, T. (2023). Two-echelon vehicle routing problems: A literature review. European Journal of Operational Research, 304:865–886

    work page 2023

  36. [36]

    and Yang, C.-L

    Sutrisno, H. and Yang, C.-L. (2023). A two-echelon location routing problem with mobile satellites for last-mile delivery: mathematical formulation and clustering-based heuristic method. Annals of Operations Research, 323:203–228

    work page 2023

  37. [37]

    and Migdalas, A

    Tadaros, M. and Migdalas, A. (2022). Bi-and multi-objective location routing problems: classification and literature review. Operational Research, 22:4641–4683

    work page 2022

  38. [38]

    Tilk, C., Olkis, K., and Irnich, S. (2021). The last-mile vehicle routing problem with delivery options. Or Spectrum, 43:877–904

    work page 2021

  39. [39]

    H., Nguyen, T

    Tran, T. H., Nguyen, T. B. T., Le, H. S. T., and Phung, D. C. (2024). Formulation and solution technique for agricultural waste collection and transport network design. European Journal of Operational Research , 313:1152–1169

    work page 2024

  40. [40]

    A., Schrotenboer, A

    uit het Broek, M. A., Schrotenboer, A. H., Jargalsaikhan, B., Roodbergen, K. J., and Coelho, L. C. (2021). Asymmetric multidepot vehicle routing problems: Valid inequalities and a branch-and-cut algorithm. Opera- tions Research, 69:380–409

    work page 2021

  41. [41]

    J., Coelho, L

    Veenstra, M., Roodbergen, K. J., Coelho, L. C., and Zhu, S. X. (2018). A simultaneous facility location and vehicle routing problem arising in health care logistics in the netherlands. European Journal of Operational Research, 268:703–715

    work page 2018

  42. [42]

    Yu, Shih-Wei Lin, L

    Vincent F. Yu, Shih-Wei Lin, L. Z. and Baldacci, R. (2023). A fast simulated annealing heuristic for the multi-depot two-echelon vehicle routing problem with delivery options. Transportation Letters, 0:1–12

    work page 2023

  43. [43]

    G., and Miao, L

    Wang, M., Zhang, C., Bell, M. G., and Miao, L. (2022). A branch-and-price algorithm for location-routing problems with pick-up stations in the last-mile distribution system. European Journal of Operational Research, 303:1258–1276

    work page 2022

  44. [44]

    Wen, X., Sun, X., Sun, Y., and Yue, X. (2021). Airline crew scheduling: Models and algorithms. Trans- portation Research Part E: logistics and transportation review , 149:102304

    work page 2021

  45. [45]

    Yu, X., Zhou, Y., and Liu, X.-F. (2020). The two-echelon multi-objective location routing problem inspired by realistic waste collection applications: The composable model and a metaheuristic algorithm. Applied Soft 30 Computing, 94:106477

    work page 2020

  46. [46]

    Zhou, L., Baldacci, R., Vigo, D., and Wang, X. (2018). A multi-depot two-echelon vehicle routing problem with delivery options arising in the last mile distribution. European Journal of Operational Research, 265:765– 778. 31 List of Symbols Sets P(·) Power set D Set of depots F Set of facilities W Set of customers ¯D Set of depot copies Fl Set of faciliti...

    work page 2018