In rail freight systems, shipments arriving at a marshalling yard with the same destination are consolidated and travel together for the remainder of the trip, so the flow pattern for each destination forms a tree-shaped path. Lin (2018) modeled this rail freight flow assignment (RFFA) problem as a nonlinear binary program — minimizing total transport cost plus penalties for unmet demand, subject to flow conservation, tree-shaped confluence constraints and link capacities, with the admissible first-front-station choices restricted by a detour-ratio threshold — argued it is NP-complete, and solved it with a simulated annealing heuristic whose parameters were set from computational experience. The direct journal successor (Lin et al., 2022) keeps the simulated annealing approach; exact mixed-integer programming with the same tree-shaped constraint has been demonstrated only at regional scale (139 stations) inside a service-network-design variant (Xin, 2022); and adjacent exact-method work omits the confluence structure. The open core is: an algorithm for RFFA with tree-shaped path constraints that solves national-scale instances (thousands of stations, on the order of 10510^5 origin–destination pairs) to proven optimality or with a guaranteed approximation bound on total cost, together with a principled, economically grounded method for the unmet-demand penalties that determine which demands are abandoned at bottlenecks.

Background

Rail freight flow assignment (RFFA) is the tactical planning problem of routing a given set of origin–destination (O–D) freight demands through a rail network so that total transport cost is minimized while every link's capacity is respected. Unlike road networks, rail freight exhibits the tree-shaped path: at a marshalling (classification) yard, incoming trains are broken up and cars are re-sorted by destination, so any shipments that arrive at a yard with the same destination are treated as a single consolidated flow and run on one common itinerary for the remainder of the trip, regardless of their origins. Lin (2018) derived this confluence mechanism from yard operations and formulated RFFA as a nonlinear program: minimize the sum of arc transport costs plus a penalty term for unmet demand, subject to (i) flow conservation, (ii) tree-shaped path constraints forcing all flow bound for a destination to follow the same subpath once merged, (iii) link capacity constraints, and (iv) a detour-ratio threshold ε\varepsilon limiting how far a shipment's path may exceed its shortest path; in the source ε\varepsilon screens the admissible choices of first front station — a choice of adjacent station kk for flow fijf_{ij} is discarded when the detour ratio ρijk/ρij\rho_{ijk}/\rho_{ij} exceeds ε\varepsilon (set to 1.41.4) — rather than entering models RFFA I–IV as an enumerated constraint. Because the tree-shaped constraints generate a large number of quadratic terms, the model is reformulated with binary variables selecting each flow's first front station (the yard where a flow first merges onto a shared path). Two modeling devices handle infeasibility when bottlenecks prevent full assignment: unmet-demand penalties PijP_{ij} (equivalently, virtual arcs whose cost PijP_{ij} represents the lost income of abandoning one unit of demand from ii to jj), and a penalty-function method with weight λ\lambda. Integer multicommodity flow (IMFP) — the problem of routing integral commodity demands through a capacitated network — is NP-complete (Even, Itai and Shamir, 1975), and Lin observes that RFFA generalizes it, concluding that RFFA is NP-complete. For large instances Lin therefore proposes a simulated annealing (SA) heuristic — a stochastic local search that accepts worsening moves with temperature-dependent probability — with a flexible Markov-chain inner loop, a piecewise cooling schedule, and incremental energy evaluation. All key parameters are set heuristically: λ=600\lambda = 600 and the detour threshold ε=1.4\varepsilon = 1.4 from computational experience, the cooling parameters δ,α,n\delta,\alpha,n and inner-loop factor K∈[3,6]K\in[3,6] by convention; PijP_{ij} only needs to exceed the longest possible path, with a sum-of-all-arc-lengths rule suggested. The SA solver was tested on nine instances against the commercial solver Lingo and applied to a case study on the planned 2020 China rail network. The tree-shaped constraint is the multi-destination capacitated cousin of confluent flow, a structure studied in approximation algorithms, where strong inapproximability is known even for single-sink unsplittable confluent objectives (Shepherd and Vetta, 2015); that theory has not been applied to RFFA.

Problem Statement

For the rail freight flow assignment (RFFA) problem with tree-shaped path constraints as formulated by Lin (2018) — minimize total transport cost plus penalties for unmet demand, subject to flow conservation, tree-shaped confluence constraints (all flow bound for the same destination follows a common subpath once merged at a yard), link capacity constraints, and the restriction of admissible first-front-station choices by the detour-ratio threshold ε\varepsilon — develop a solution methodology with provable performance guarantees at national scale. Concretely, the requested results are: (1) an algorithm that either solves national-scale instances (networks with thousands of stations and on the order of 10510^5 origin–destination pairs) to proven optimality within practical computational resources, or achieves a guaranteed approximation ratio on the total cost objective for the stated model class; and (2) a principled method for selecting the unmet-demand penalties PijP_{ij} (virtual-arc costs) — grounded in the economic or operational value of abandoned demand rather than the current rule of setting them above the longest possible path — since these values determine which demands are abandoned at bottlenecks and hence change the optimum itself. Results (1) and (2) jointly serve one objective: replacing experience-tuned heuristics for tree-shaped RFFA by theoretically grounded methodology. Substantiating such a methodology requires grounding any remaining free parameters and validating beyond the original nine test instances, in addition to the provable-guarantee objective (1)–(2).

References

  1. Lin, Bo-Liang (2018). Large-scale rail freight flow assignment with the tree-shaped path. arXiv:1812.03013. https://arxiv.org/abs/1812.03013
  2. Lin, Boliang; Zhao, Yinan; Lin, Ruixi; Liu, Chang (2022). Shipment Path Planning for Rail Networks Considering Elastic Capacity. IEEE Intelligent Transportation Systems Magazine 14(3), 160–174. DOI: 10.1109/MITS.2020.3014109. https://doi.org/10.1109/MITS.2020.3014109
  3. Xin, Xiaoyu (2022). Service network design for freight railway transportation: The Chinese case. PLOS ONE 17(12): e0276671. DOI: 10.1371/journal.pone.0276671. https://doi.org/10.1371/journal.pone.0276671
  4. Xin, Xiaoyu; Wu, Xu; Wang, Jiaxi (2025). Rail freight transportation service network design with mixed blocking policies: Formulation and solution methods. Journal of Rail Transport Planning & Management 33, 100495. DOI: 10.1016/j.jrtpm.2024.100495. https://doi.org/10.1016/j.jrtpm.2024.100495
  5. Even, S.; Itai, A.; Shamir, A. (1975). On the complexity of time table and multi-commodity flow problems. 16th Annual Symposium on Foundations of Computer Science (SFCS 1975), pp. 184–193. DOI: 10.1109/SFCS.1975.21. https://doi.org/10.1109/SFCS.1975.21
  6. Lan, Zekang; He, Shiwei; Xu, Yan; Wang, Yidong (2019). Optimizing Train Formation Problem With Car Flow Routing and Train Routing by Benders-and-Price Approach. IEEE Access 7, 178496–178510. DOI: 10.1109/ACCESS.2019.2958601. https://doi.org/10.1109/ACCESS.2019.2958601
  7. Lin, Boliang; Wang, Zhenyu; Zhao, Yinan (2021). A Train Formation Plan with Elastic Capacity for Large-Scale Rail Networks. arXiv:2111.03473. https://arxiv.org/abs/2111.03473
  8. Li, Xiang; Lin, Boliang (2025). Rail freight service network design integrating train formation and transit time performance. Transportmetrica A: Transport Science. DOI: 10.1080/23249935.2025.2552983. https://doi.org/10.1080/23249935.2025.2552983
  9. Zhao, Yinan; Jiang, Hanwen; Gong, Shiyi (2026). Robust railway traffic routing problem under uncertain demand: an improved Benders decomposition approach. Computers & Industrial Engineering 214, 111829. DOI: 10.1016/j.cie.2026.111829. https://doi.org/10.1016/j.cie.2026.111829
  10. Shepherd, F. Bruce; Vetta, Adrian (2015). The Inapproximability of Maximum Single-Sink Unsplittable, Priority and Confluent Flow Problems. arXiv:1504.00627. https://arxiv.org/abs/1504.00627