Mathematical programming-based heuristic for highway patrol drone scheduling problem

Shinwon Choi, Minseo Lee, Hyejin Park and Jinil Han

Socio-Economic Planning Sciences, 2024, vol. 93, issue C

Abstract: Recently, highway drone patrols have been introduced in several countries to improve the efficiency of continuous patrols to enforce traffic laws and respond to accidents on highways. Since highways stretch over a vast area, a large number of drones are needed to patrol simultaneously, so it is necessary to develop an optimized flight plan to make them operate efficiently. This paper addresses the problem of determining an operational schedule for multiple highway patrol drones in order to satisfy varying patrol demands on different highway sections and at different times. Two integer programming formulations, namely the basic formulation and the path-based formulation, are proposed for the problem. However, these formulations have limitations in generating high quality solutions within a reasonable time frame. To overcome these limitations and find high quality solutions in a short time, we propose a column generation-based heuristic algorithm that combines the advantages of both formulations. Computational experiments were conducted on two real-world Korean highway instances to verify the effectiveness of the proposed heuristic algorithm. The results show that the proposed heuristic is highly effective and can be successfully applied to repetitive scheduling environments in real-world highway drone patrol systems.

Keywords: Drone scheduling; Highway patrol drones; Heuristic; Column generation (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S003801212400106X
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:soceps:v:93:y:2024:i:c:s003801212400106x

DOI: 10.1016/j.seps.2024.101907

Access Statistics for this article

Socio-Economic Planning Sciences is currently edited by Barnett R. Parker

More articles in Socio-Economic Planning Sciences from Elsevier
Bibliographic data for series maintained by Catherine Liu ().