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

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.