Exact and approximation algorithms for the multi-depot data mule scheduling with handling time and time span constraints

Minqin Liu (), Wei Yu (), Zhaohui Liu () and Xinmeng Guo ()
Additional contact information
Minqin Liu: East China University of Science and Technology
Wei Yu: East China University of Science and Technology
Zhaohui Liu: East China University of Science and Technology
Xinmeng Guo: East China University of Science and Technology

Journal of Combinatorial Optimization, 2025, vol. 49, issue 3, No 4, 22 pages

Abstract: Abstract In this paper, we investigate the data mule scheduling with handling time and time span constraints (DMSTC) in which the goal is to minimize the number of data mules dispatched from a depot that are used to serve target sensors located on a wireless sensor network. Each target sensor is associated with a handling time and each dispatched data mule must return to the original depot before time span $$D$$ D . We also study a variant of the DMSTC, denoted by DMSTC $$_l$$ l in which the objective is to minimize the total travel distance of the data mules dispatched. We give exact and approximation algorithms for the DMSTC/DMSTC $$_l$$ l on a path and their multi-depot version. For the DMSTC, we show an $$O(n^4)$$ O ( n 4 ) polynomial time algorithm for the uniform 2-depot DMSTC on a path with at least one depot being on the endpoint of the path, where $$n$$ n indicates the number of target sensors and an instance of the DMSTC is called uniform if all the handling times are identical. We present a new 2-approximation algorithm for the non-uniform DMSTC on a path and conduct extensive computational experiments on randomly generated instances to show its good practical performance. For the DMSTC $$_l$$ l , we derive an $$O((n+k)^{2})$$ O ( ( n + k ) 2 ) -time algorithm for the uniform multi-depot DMSTC $$_l$$ l on a path, where $$k$$ k is the number of depots. For the non-uniform multi-depot DMSTC $$_l$$ l on a path or cycle, we give a 2-approximation algorithm.

Keywords: Data mule scheduling; Multi-depot; Handling time; Time span constraint; Approximation algorithm (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-025-01280-9 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

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:spr:jcomop:v:49:y:2025:i:3:d:10.1007_s10878-025-01280-9

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-025-01280-9

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().