IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v292y2021i1p73-94.html
   My bibliography  Save this article

Simultaneous node and link districting in transportation networks: Model, algorithms and railway application

Author

Listed:
  • Wang, Dian
  • Zhao, Jun
  • D’Ariano, Andrea
  • Peng, Qiyuan

Abstract

Partitioning a large network into multiple subnetworks is adopted extensively in various practical applications involving the architecture of distributed management. In this study, we consider strategic simultaneous node and link districting to partition the nodes and links of a given transportation network into a fixed number of mutually disjoint districts, based on the districting criteria of integrity, contiguity, balance, and independence. We first formulate the resulting problem as a mixed integer linear programming model to minimize the weighted sum of the total size deviation of districts and total cooperation between districts. An improved network flow-based technique is proposed to incorporate the complicated contiguity criterion by using a polynomial number of constraints. Valid inequalities, which break the symmetry within and between districts, are designed to strengthen the model. To solve this challenge problem, we reformulate it as a binary linear programming model, and develop a column generation-based algorithm to find tight lower bounds and good-quality solutions. Then, an iterative search algorithm is designed to obtain good-quality solutions rapidly. Furthermore, a more efficient hybrid algorithm is proposed by using the results of the iterative search algorithm to initialize the column generation-based algorithm. We assess the proposed model and algorithms by using various scales of instances derived from the train dispatcher desk districting problem, which is a practical application of the investigated problem in the context of railway. The computational results reveal that our approaches outperform existing approaches and a commercial solver, and our best algorithm can solve almost all the investigated instances to optimality within a considerably short average computation time. The districting solutions of our approaches are also better than the empirical solutions designed by railway managers mainly based on experience.

Suggested Citation

  • Wang, Dian & Zhao, Jun & D’Ariano, Andrea & Peng, Qiyuan, 2021. "Simultaneous node and link districting in transportation networks: Model, algorithms and railway application," European Journal of Operational Research, Elsevier, vol. 292(1), pages 73-94.
    • Handle: RePEc:eee:ejores:v:292:y:2021:i:1:p:73-94
    DOI: 10.1016/j.ejor.2020.10.013
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221720308894
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2020.10.013?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Luis Henrique Pauleti Mendes & Fábio Luiz Usberti & Celso Cavellucci, 2022. "The Capacitated and Economic Districting Problem," INFORMS Journal on Computing, INFORMS, vol. 34(4), pages 2003-2016, July.
    2. Hao, Yuchen & Liu, Chuang & Zhao, Lugang & Liu, Weibo, 2023. "A dual-clustering algorithm for a robust medical grid partition problem considering patient referral," Socio-Economic Planning Sciences, Elsevier, vol. 88(C).
    3. Wang, Dian & Zhao, Jun & Peng, Qiyuan, 2022. "Optimizing the loaded train combination problem at a heavy-haul marshalling station," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 162(C).

    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:eee:ejores:v:292:y:2021:i:1:p:73-94. 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.

    We have no bibliographic references for this item. You can help adding them by using 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    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.