文献类型：期刊文献

英文题名：Exact and approximation algorithms for the multi-depot data mule scheduling with handling time and time span constraints

作者：Liu, Minqin[1];Yu, Wei[1];Liu, Zhaohui[1];Guo, Xinmeng[1]

机构：[1]East China Univ Sci & Technol, Sch Math, 130 Meilong Rd, Shanghai 200237, Peoples R China

年份：2025

卷号：49

期号：3

外文期刊名：JOURNAL OF COMBINATORIAL OPTIMIZATION

收录：;EI(收录号：20251318113588);WOS:【SCI-EXPANDED(收录号:WOS:001450010000001)】；

基金：We are very grateful to the anonymous reviewers for their valuable comments and suggestions, which greatly improve the presentation of this paper. This research is supported by the National Natural Science Foundation of China under grant number 12371317.

语种：英文

外文关键词：Data mule scheduling; Multi-depot; Handling time; Time span constraint; Approximation algorithm

摘要：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\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$D$$\end{document}. We also study a variant of the DMSTC, denoted by DMSTCl\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$_l$$\end{document} 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/DMSTCl\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$_l$$\end{document} on a path and their multi-depot version. For the DMSTC, we show an O(n4)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(n<^>4)$$\end{document} 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\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$n$$\end{document} 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 DMSTCl\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$_l$$\end{document}, we derive an O((n+k)2)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O((n+k)<^>{2})$$\end{document}-time algorithm for the uniform multi-depot DMSTCl\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$_l$$\end{document} on a path, where k\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k$$\end{document} is the number of depots. For the non-uniform multi-depot DMSTCl\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$_l$$\end{document} on a path or cycle, we give a 2-approximation algorithm.