pith. sign in

arxiv: 2604.15754 · v1 · submitted 2026-04-17 · 🧮 math.OC

Urban transit network design using spanning tree: A case study of Canberra transit network

Satoshi Suguira , Kam-Fung Cheung , Michael G. H. Bell , Hitomi Nakanishi , Fumitaka Kurauchi , Supun Perera , Yogi Vidyattama This is my paper

Pith reviewed 2026-05-10 08:36 UTC · model grok-4.3

classification 🧮 math.OC
keywords networktransitspanningtreedesigncanberraheuristicpublic
0
0 comments X

The pith

A tabu search heuristic finds spanning trees minimizing passenger-kilometers in transit networks, with a greedy extension to add links, demonstrated on Canberra bus data.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

Transit networks connect stops so passengers can travel between them. The authors treat the network as a spanning tree, which connects every stop with the fewest possible links and no loops. They set up an optimization problem to choose the tree that makes the sum of all passenger trips as short as possible. Because solving this exactly is too slow for real cities, they use a tabu search method that tries many possible trees and avoids repeating bad choices. They also add a simple greedy step to include a few extra links beyond the tree if those links cut passenger travel even more. The whole method is checked against real bus stop and demand data from Canberra.

Core claim

The proposed tabu search based heuristic is verified using the Canberra bus network data to quickly output a promising spanning tree that addresses passenger utility by minimizing the total passenger-kilometers.

Load-bearing premise

That a spanning tree structure (with optional added links) sufficiently captures the essential features of an effective transit network for minimizing passenger-kilometers, without needing to model transfers, frequencies, or capacity explicitly.

Figures

Figures reproduced from arXiv: 2604.15754 by Fumitaka Kurauchi, Hitomi Nakanishi, Kam-Fung Cheung, Michael G. H. Bell, Satoshi Suguira, Supun Perera, Yogi Vidyattama.

Figure 1
Figure 1. Figure 1: Example of removing a link in a spanning tree and listing all candidate links that can reconnect [PITH_FULL_IMAGE:figures/full_fig_p007_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: The pseudo code of the proposed method improvement at the current iteration, the proposed algorithm proceeds to Lines 26 – 34 examines the tabu list using the strategy mentioned in Section 2.4. The proposed algorithm repeats procedures in Lines 7 -37 until the While-loop counter n exceeds the maximum number of iterations ϕ. 3 Simulation using Canberra bus network data The efficacy of our proposed Link Swap… view at source ↗
Figure 3
Figure 3. Figure 3: Convergence analysis of Link Swapping heuristic algorithm (Heuristic 1), Link Deletion heuristic [PITH_FULL_IMAGE:figures/full_fig_p010_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Performance analysis of Link Swapping heuristic algorithm (Heuristic 1), Link Deletion heuristic [PITH_FULL_IMAGE:figures/full_fig_p010_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Topologies of the three spanning trees: MST, MDST and MPKST. [PITH_FULL_IMAGE:figures/full_fig_p013_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Map of Canberra rapid public transport network. [PITH_FULL_IMAGE:figures/full_fig_p014_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: Relationship between cumulative frequency distribution and ratio of link distance to path travel [PITH_FULL_IMAGE:figures/full_fig_p015_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: Topology of Canberra public transport network topology. [PITH_FULL_IMAGE:figures/full_fig_p015_8.png] view at source ↗
Figure 9
Figure 9. Figure 9: Transition of the ratio of the lower bound to the passenger-kilometers obtained using the greedy [PITH_FULL_IMAGE:figures/full_fig_p016_9.png] view at source ↗
Figure 10
Figure 10. Figure 10: Relationship between cumulative frequency distribution of the demand and ratio of link [PITH_FULL_IMAGE:figures/full_fig_p017_10.png] view at source ↗
read the original abstract

Transit network design plays an important role in public transport. With the simplicity of spanning tree, this paper adopts the concept of spanning tree to help (re-)design a public transit network that addresses passenger utility by minimizing the total passenger-kilometers, which can be formulated as a mixed-integer optimization model. However, searching for an optimal minimum passenger-kilometer spanning tree is intractable for a large network. This paper proposes a tabu search based heuristic to quickly output a promising spanning tree. The efficacy of the proposed tabu search based heuristic is verified using the Canberra bus network data. With the flexibility of the proposed tabu search heuristic and the efficiency of the transit system, this paper proposes a greedy algorithm to relax the number of links constraint to add more links that can further minimize the total passenger-kilometers. With the case study of Canberra transit network, this paper provides implications to policy makers to further improve the design of a public transit network.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Only the abstract is available, so the ledger is limited to elements explicitly named. The mixed-integer formulation implicitly treats passenger demand as fixed input data and assumes the spanning-tree topology is an adequate proxy for network utility.

axioms (1)
  • domain assumption Passenger demand and origin-destination distances are known and fixed inputs that can be used to compute total passenger-kilometers.
    Abstract states the model minimizes total passenger-kilometers using network data.

pith-pipeline@v0.9.0 · 5488 in / 1179 out tokens · 26929 ms · 2026-05-10T08:36:54.878010+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

4 extracted references · 4 canonical work pages

  1. [1]

    doi: 10.1016/j.trb.2012.02.010. A. Haghani and M. Banihashemi. Heuristic approaches for solving large-scale bus transit vehicle schedul- ing problem with route time constraints.Transportation Research Part A: Policy and Practice, 36(4): 309–333, 2002. doi: 10.1016/S0965-8564(01)00004-0. Q. Hu, F. Corman, B. Wiegmans, and G. Lodewijks. A tabu search algori...

    work page doi:10.1016/j.trb.2012.02.010 2012

  2. [2]

    doi: 10.1016/j.tre.2023.103212. O. J. Ibarra-Rojas, F. Delgado, R. Giesen, and J. C. Mu˜ noz. Planning, operation, and control of bus transport systems: A literature review.Transportation Research Part B: Methodological, 77:38–75,

    work page doi:10.1016/j.tre.2023.103212 2023

  3. [3]

    doi: 10.1016/j.trb.2015.03.002. B. Kayı¸ so˘ glu and˙I. Akg¨ un. Multiple allocation tree of hubs location problem for non-complete networks. Computers & Operations Research, 136:105478, 2021. doi: 10.1016/j.cor.2021.105478. K. Kepaptsoglou and M. Karlaftis. Transit route network design problem.Journal of Transportation Engineering, 135(8):491–505, 2009. ...

    work page doi:10.1016/j.trb.2015.03.002 2015

  4. [4]

    doi: 10.1016/j.trpro.2017.03.029

    work page doi:10.1016/j.trpro.2017.03.029 2017