 Drone scheduling to monitor vessels in emission control areasJun Xia, Kai Wang and Shuaian Wang Transportation Research Part B: Methodological, 2019, vol. 119, issue C, 174-196 Abstract: The use of drones to monitor the emissions of vessels has recently attracted wide attention because of its great potentials for enforcing regulations in emission control areas (ECAs). Motivated by this potential application, we study how drones can be scheduled to monitor the sailing vessels in ECAs, which is defined as a drone scheduling problem (DSP) in this paper. The objective of the DSP is to design a group of flight tours for drones, including the inspection sequence and timings for the vessels, such that as many vessels as possible can be inspected during a given time period while prioritizing highly weighted vessels for inspection. We show that the DSP can be regarded as a generalized team orienteering problem, which is known to be NP-hard, and deriving solutions for this problem can be more difficult because additional complicated features, such as time-dependent locations, multiple trips for a drone, and multiple stations (or depots), are addressed simultaneously. To overcome these difficulties, we model the dynamics of each sailing vessel using a real-time location function in a deterministic fashion. This approach allows us to approximately represent the problem on a time-expanded network, based on which a network flow-based formulation can be formally developed. To solve this proposed formulation, we further develop a Lagrangian relaxation-based method that can obtain near-optimal solutions for large-scale instances of the problem. Numerical experiments based on practically generated instances with 300 time points and up to 100 vessels are conducted to validate the effectiveness and efficiency of the proposed method. Results show that our method derives tight upper bounds on optimal solutions, and can quickly return good feasible solutions for the tested instances. We also conduct experiments based on realistic tracking data to demonstrate the usefulness of our solutions, including those for the cases considering the uncertainty of vessel locations. Keywords: Drone scheduling; Emission control area; Time-expanded network; Lagrangian relaxation (search for similar items in EconPapers) Downloads: (external link) Related works: Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text Persistent link: https://EconPapers.repec.org/RePEc:eee:transb:v:119:y:2019:i:c:p:174-196 Ordering information: This journal article can be ordered from DOI: 10.1016/j.trb.2018.10.011 Access Statistics for this article Transportation Research Part B: Methodological is currently edited by Fred Mannering More articles in Transportation Research Part B: Methodological from Elsevier |
Is your work missing from RePEc? Here is how to contribute.
Questions or problems? Check the EconPapers FAQ or send mail to .
EconPapers is hosted by the
School of Business at Örebro University.