2025S-Seminar #9 / Methods of Bus Network Design

2025.06.04

最近は雨が多く、ジメジメした日が続きますね。洗濯物も乾きにくくなりました。
さて、今回のゼミでは、M1出本さんが「Ceder, A., & Wilson, N. H. m. (1986). Bus Network Design.」に基づいて、バスネットワークの最適化ついての発表を行いました。また、D1Theethadさんは、「Schuewe et al. (2019) The line planning routing game」に基づいて、路線計画問題にゲーム理論の最適反応アルゴリズムを用いたThe Line Planning Routing Game (LPRG)についての発表を行いました。
In this seminar, M1 student Demoto gave a presentation on bus network optimization based on “Ceder, A., & Wilson, N. H. m. (1986). Bus Network Design.” Additionally, D1 student Theethad presented on the Line Planning Routing Game (LPRG), which applies game theory’s optimal response algorithm to route planning problems, based on “Schuewe et al. (2019) The line planning routing game.”

発表を担当したみなさんに、内容をまとめてもらいました！
We asked everyone who was in charge of the presentations to summarize the content!

出本 (Demoto)：
Ceder, A., & Wilson, N. H. m. (1986). Bus Network Design. について紹介しました。この論文では、バスネットワークの最適化をより実用的にする目的で、ルート探索アルゴリズムと二段階のアプローチが提案されています。前者によって運行可能なルートを生成し、これをもとに後者を用います。可能な限り複雑さを排したこれらの手法では、乗客と運行者両方のコストの最小化を狙い、最短距離での所要時間を一定の割合以上で上回るルートは採用されないことが特徴です。
This paper proposes a route search algorithm and a two-stage approach to make bus network optimization more practical. The former generates feasible routes, which are then used as the basis for the latter. These methods, which eliminate complexity as much as possible, aim to minimize costs for both passengers and operators, and are characterized by the fact that routes that exceed a certain percentage of the shortest distance travel time are not adopted.

Theethad：
The Line Planning Problem with Travel Cost and Quality (LPQC) involves determining pairs of frequencies and routes that achieve the system-optimal point. The Line Planning Routing Game (LPRG) applies Game Theory’s best-response algorithm. In this study, passenger demand from origin-destination (OD) pairs and the designed network were simulated using the best-response algorithms. In each game iteration, each passenger selects the route that minimizes their individual travel cost, considering the routes chosen by others. The game terminates when no passenger can find a better route, indicating that the last strategy is in equilibrium. However, the network structure may not be suitable for finding equilibria; a symmetrical network, for example, may not guarantee the existence of an equilibrium. This paper proposes the auxiliary frequencies and arc weights to ease convergence to a state where each passenger’s individual cost cannot be improved or equilibria point. Results from the study show that solutions from LPRG are 8% more expensive than those from LPQC but consume only 10 minutes, while LPQC consumes 1 hour.

written by Ryusuke Ono (B4)