IDEAS home Printed from https://ideas.repec.org/a/gam/jmathe/v10y2022i21p3969-d953173.html
   My bibliography  Save this article

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

Author

Listed:
  • 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)

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.

Suggested Citation

  • Jinming Liu & Guoting Zhang & Lining Xing & Weihua Qi & Yingwu Chen, 2022. "An Exact Algorithm for Multi-Task Large-Scale Inter-Satellite Routing Problem with Time Windows and Capacity Constraints," Mathematics, MDPI, vol. 10(21), pages 1-24, October.
    • Handle: RePEc:gam:jmathe:v:10:y:2022:i:21:p:3969-:d:953173
    as

    Download full text from publisher

    File URL: https://www.mdpi.com/2227-7390/10/21/3969/pdf
    Download Restriction: no
    File URL: https://www.mdpi.com/2227-7390/10/21/3969/
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Wang, Xiubin & Regan, Amelia C., 2002. "Local truckload pickup and delivery with hard time window constraints," Transportation Research Part B: Methodological, Elsevier, vol. 36(2), pages 97-112, February.
    2. Marius Solomon & Alain Chalifour & Jacques Desrosiers & Jacques Boisvert, 1992. "An Application of Vehicle-Routing Methodology to Large-Scale Larvicide Control Programs," Interfaces, INFORMS, vol. 22(3), pages 88-99, June.
    3. Marshall L. Fisher & Moshe B. Rosenwein, 1989. "An interactive optimization system for bulk‐cargo ship scheduling," Naval Research Logistics (NRL), John Wiley & Sons, vol. 36(1), pages 27-42, February.
    4. Thomas R. Sexton & Lawrence D. Bodin, 1985. "Optimizing Single Vehicle Many-to-Many Operations with Desired Delivery Times: I. Scheduling," Transportation Science, INFORMS, vol. 19(4), pages 378-410, November.
    5. Natashia Boland & Mike Hewitt & Luke Marshall & Martin Savelsbergh, 2017. "The Continuous-Time Service Network Design Problem," Operations Research, INFORMS, vol. 65(5), pages 1303-1321, October.
    6. del Portillo, Inigo & Eiskowitz, Skylar & Crawley, Edward F. & Cameron, Bruce G., 2021. "Connecting the other half: Exploring options for the 50% of the population unconnected to the internet," Telecommunications Policy, Elsevier, vol. 45(3).
    7. Stefan Ropke & Jean-François Cordeau, 2009. "Branch and Cut and Price for the Pickup and Delivery Problem with Time Windows," Transportation Science, INFORMS, vol. 43(3), pages 267-286, August.
    8. Quan Lu & Maged Dessouky, 2004. "An Exact Algorithm for the Multiple Vehicle Pickup and Delivery Problem," Transportation Science, INFORMS, vol. 38(4), pages 503-514, November.
    9. Martin Savelsbergh & Marc Sol, 1998. "Drive: Dynamic Routing of Independent Vehicles," Operations Research, INFORMS, vol. 46(4), pages 474-490, August.
    10. Harilaos N. Psaraftis, 1983. "An Exact Algorithm for the Single Vehicle Many-to-Many Dial-A-Ride Problem with Time Windows," Transportation Science, INFORMS, vol. 17(3), pages 351-357, August.
    11. Mahmoudi, Monirehalsadat & Zhou, Xuesong, 2016. "Finding optimal solutions for vehicle routing problem with pickup and delivery services with time windows: A dynamic programming approach based on state–space–time network representations," Transportation Research Part B: Methodological, Elsevier, vol. 89(C), pages 19-42.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Mahmoudi, Monirehalsadat & Zhou, Xuesong, 2016. "Finding optimal solutions for vehicle routing problem with pickup and delivery services with time windows: A dynamic programming approach based on state–space–time network representations," Transportation Research Part B: Methodological, Elsevier, vol. 89(C), pages 19-42.
    2. Mahmoudi, Monirehalsadat & Chen, Junhua & Shi, Tie & Zhang, Yongxiang & Zhou, Xuesong, 2019. "A cumulative service state representation for the pickup and delivery problem with transfers," Transportation Research Part B: Methodological, Elsevier, vol. 129(C), pages 351-380.
    3. Hou, Liwen & Li, Dong & Zhang, Dali, 2018. "Ride-matching and routing optimisation: Models and a large neighbourhood search heuristic," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 118(C), pages 143-162.
    4. Dimitris Bertsimas & Allison Chang & Velibor V. Mišić & Nishanth Mundru, 2019. "The Airlift Planning Problem," Transportation Science, INFORMS, vol. 53(3), pages 773-773, May.
    5. Cortés, Cristián E. & Matamala, Martín & Contardo, Claudio, 2010. "The pickup and delivery problem with transfers: Formulation and a branch-and-cut solution method," European Journal of Operational Research, Elsevier, vol. 200(3), pages 711-724, February.
    6. Roberto Baldacci & Enrico Bartolini & Aristide Mingozzi, 2011. "An Exact Algorithm for the Pickup and Delivery Problem with Time Windows," Operations Research, INFORMS, vol. 59(2), pages 414-426, April.
    7. Diana, Marco & Dessouky, Maged M., 2004. "A new regret insertion heuristic for solving large-scale dial-a-ride problems with time windows," Transportation Research Part B: Methodological, Elsevier, vol. 38(6), pages 539-557, July.
    8. Zheng, Jianfeng & Meng, Qiang & Sun, Zhuo, 2014. "Impact analysis of maritime cabotage legislations on liner hub-and-spoke shipping network design," European Journal of Operational Research, Elsevier, vol. 234(3), pages 874-884.
    9. Liu, Mengyang & Luo, Zhixing & Lim, Andrew, 2015. "A branch-and-cut algorithm for a realistic dial-a-ride problem," Transportation Research Part B: Methodological, Elsevier, vol. 81(P1), pages 267-288.
    10. Sun, Yanshuo & Chen, Zhi-Long & Zhang, Lei, 2020. "Nonprofit peer-to-peer ridesharing optimization," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 142(C).
    11. Natashia L. Boland & Martin W. P. Savelsbergh, 2019. "Perspectives on integer programming for time-dependent models," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 27(2), pages 147-173, July.
    12. Wang, Yong & Peng, Shouguo & Zhou, Xuesong & Mahmoudi, Monirehalsadat & Zhen, Lu, 2020. "Green logistics location-routing problem with eco-packages," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 143(C).
    13. Ali Mehsin Alyasiry & Michael Forbes & Michael Bulmer, 2019. "An Exact Algorithm for the Pickup and Delivery Problem with Time Windows and Last-in-First-out Loading," Transportation Science, INFORMS, vol. 53(6), pages 1695-1705, November.
    14. Schaumann, Sarah K. & Bergmann, Felix M. & Wagner, Stephan M. & Winkenbach, Matthias, 2023. "Route efficiency implications of time windows and vehicle capacities in first- and last-mile logistics," European Journal of Operational Research, Elsevier, vol. 311(1), pages 88-111.
    15. Hua, Shijia & Zeng, Wenjia & Liu, Xinglu & Qi, Mingyao, 2022. "Optimality-guaranteed algorithms on the dynamic shared-taxi problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 164(C).
    16. Roberto Baldacci & Enrico Bartolini & Aristide Mingozzi & Roberto Roberti, 2010. "An exact solution framework for a broad class of vehicle routing problems," Computational Management Science, Springer, vol. 7(3), pages 229-268, July.
    17. Garaix, Thierry & Artigues, Christian & Feillet, Dominique & Josselin, Didier, 2010. "Vehicle routing problems with alternative paths: An application to on-demand transportation," European Journal of Operational Research, Elsevier, vol. 204(1), pages 62-75, July.
    18. Timothy Curtois & Dario Landa-Silva & Yi Qu & Wasakorn Laesanklang, 2018. "Large neighbourhood search with adaptive guided ejection search for the pickup and delivery problem with time windows," EURO Journal on Transportation and Logistics, Springer;EURO - The Association of European Operational Research Societies, vol. 7(2), pages 151-192, June.
    19. Detti, Paolo & Papalini, Francesco & Lara, Garazi Zabalo Manrique de, 2017. "A multi-depot dial-a-ride problem with heterogeneous vehicles and compatibility constraints in healthcare," Omega, Elsevier, vol. 70(C), pages 1-14.
    20. Lu, Quan & Dessouky, Maged M., 2006. "A new insertion-based construction heuristic for solving the pickup and delivery problem with time windows," European Journal of Operational Research, Elsevier, vol. 175(2), pages 672-687, December.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:gam:jmathe:v:10:y:2022:i:21:p:3969-:d:953173. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: MDPI Indexing Manager (email available below). General contact details of provider: https://www.mdpi.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.