EconPapers    
Economics at your fingertips  
 

An Exact Algorithm for Multi-Task Large-Scale Inter-Satellite Routing Problem with Time Windows and Capacity Constraints

Jinming Liu, Guoting Zhang, Lining Xing (), Weihua Qi and Yingwu Chen
Additional contact information
Jinming Liu: College of Systems Engineering, National University of Defense Technology, No. 109 Deya Street, Changsha 410073, China
Guoting Zhang: Beijing Institute of Tracking and Telecommunications Technology, Beijing 100094, China
Lining Xing: College of Electronic Engineering, Xidian University, Xi’an 710071, China
Weihua Qi: College of Systems Engineering, National University of Defense Technology, No. 109 Deya Street, Changsha 410073, China
Yingwu Chen: College of Systems Engineering, National University of Defense Technology, No. 109 Deya Street, Changsha 410073, China

Mathematics, 2022, vol. 10, issue 21, 1-24

Abstract: In the context of a low-orbit mega constellation network, we consider the large-scale inter-satellite routing problem with time windows and capacity constraints (ISRPTWC) with the goal of minimizing the total consumption cost, including transmission, resource consumption, and other environmentally impacted costs. Initially, we develop an integer linear programming model for ISRPTWC. However, a difficult issue when solving ISRPTWC is how to deal with complex time window constraints and how to reduce congestion and meet transmission capacity. Along this line, we construct a three-dimensional time-space state network aiming to comprehensively enumerate the satellite network state at any moment in time and a task transmission route at any given time and further propose a time-discretized multi-commodity network flow model for the ISRPTWC. Then, we adopt a dynamic programming algorithm to solve the single-task ISRPTWC. By utilizing a Lagrangian relaxation algorithm, the primal multi-task routing problem is decomposed into a sequence of single-task routing subproblems, with Lagrangian multipliers for individual task route nodes and links being updated by a subgradient method. Notably, we devise a novel idea for constructing the upper bound of the ISRPTWC. Finally, a case study using illustrative and real-world mega constellation networks is performed to demonstrate the effectiveness of the proposed algorithm.

Keywords: low-orbit mega constellation network; inter-satellite routing problem with time windows and capacity constraints; time-discretized multi-commodity network flow model; Lagrangian relaxation algorithm (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/10/21/3969/pdf (application/pdf)
https://www.mdpi.com/2227-7390/10/21/3969/ (text/html)

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:gam:jmathe:v:10:y:2022:i:21:p:3969-:d:953173

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().

 
Page updated 2025-03-19
Handle: RePEc:gam:jmathe:v:10:y:2022:i:21:p:3969-:d:953173