t学生論文賞受賞論文

駅構内入れ換え計画問題に関する研究
坂口 隆（電気通信大学大学院電気通信学研究科情報工学専攻 現所属：㈲鉄道総合技術研究所）

指導教官 田村明久助教授

1． はじめに

3．1 SDPP

駅構内入れ換え計画とは，ターミナル駅などでの複項点集合Ⅴ，辺集合且にリンク集合エを伴ったグ

数車両の移動手順を決める計画である．ひとつの駅のラフG＝（Ⅴ，且，エ），⊥＝（（5J，わ）1ノ＝1，2，…，々，む∈Ⅴ，計画に数百時間を費やすこともあることから自動化がわ∈Ⅴ）をリンク付きグラフと呼び，リンク（む，わ）望まれている作業の一つであり，近似解法の研究が現の項点を結ぶ点本の頂点非共有パス月，昂，…，f㌔を在行われているところである．本論文では入挽回数を求める問題を頂点非共有パス問題という．頂点非共有最小化する最適化問題に関するアルゴリズムとその理パスとは項点が互いに素なパスの集■合である．さらに論計算量について述べ，実問題へ適用した結果につい辺の長さの和を最小化する問題を最短項点非共有パスて考察する．

問題（ShortestDi房oint PathProblem）といい，ここではSDPPと略す．

2．駅構内入れ換え計画問題

これらの問題について，これまでの研究から一般の

図1は車両入換の例である．XやYの車両は到着有向，無向グラフの場合の計算量はNP−完全であると出発の番線が異なるので入換が必要であり，またZことが知られているが，非巡回有向グラフに限定すれのように到着から出発の間に同じ番線を他が使用する

ばC．L．Li等が0（点】Ⅴ】烏￣1l且】）時間解法を示してい場合も入換が必要となる．列車の着発時刻・番線など

る［1】．これをLiのアルゴリズムと呼ぶ．

が与えられてこの図のような入換手順を求める計画を，

3．2 SDPPへの定式化

駅構内入れ換え計画という．

計画上の時刻をあ秒間隔とし，車両が時刻fに番入換計画では，複数の車両が一度に同じ番線を使用線ゐにいる状態を（∂，〜）と表す．入換車両がとることしないことや，入換する線路上で車両同士が競合しなのできる状態（∂，f）の集合を頂点集合Ⅴ，可能な状いように多くの制約がある．実際には多くの目的，評態遷移（（∂，f），（∂′，f′））の集合を有向辺集合且，入換価基準が存在するが，本研究では必要な制約を満たし車両ノが駅に到着した状態をむ＝（みノ，わ），駅を出発す入挽回数を最小化する問題を扱うこととし，これを駅るときの状態をめ＝（∂ニ，霞），エ＝（（む，め）lノ＝1，2，…，点）

構内入れ換え計画問題と呼ぶ．とすることによって得られる有向グラフC＝（Ⅴ，且，エ）上でむからぁまでのパス昂は車両ノの人換手順

3．定式化を表す．したがって端点の番線が同じ辺の長さを0，

本研究では，駅構内入れ換え計画問題をSDPPとそれ以外を1としこれに対するSDPPを解けば，同して定式化して解く方法を提案する．

時に複数の車両が同一番線を使用しないという条件の上で入挽回数が最小の入換手順が得られる．他の制約

10：00

10：1010：20

はGの変形，リンクの追加によってSDPPに取り込むことができる．

4．SDPPの解法
4．1Liのアルゴリズムとその改善
Liのアルゴリズムでは与えられたグラフG＝（Ⅴ，且，エ），l上】＝烏に対して，頂点のトポロジカルオーダ
図1車両入換の例
1999年12月号の一つガを用いて々次元グラフ百を構成する．百の© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

（31）6Tl項点は，く〃1，〃2，…，〃烏〉のようなゑ個のGの項点の組から訂までの最短距離d（首，汐）と打からデまでのであり，第ノ要素はノ番目のリンクを構成するパス上最短距離♂（訂，㌻）の推定値ゐ（訂）の和が小さな項点訂の項点に対応する．

を優先的に探索する方法で，ゐ（訂）に良い下界を与え駅構内入れ換え計画問題では点が非常に大きな値となるので，このアルゴリズムをそのまま通用してもられれば最適性の保証の下で探索空間を効率的に縮小できる［2］

実時間では計算できない．本研究では百の次の条件

d（訂，㌻）は頂点を共有しないパス賞廟（ノ＝1・‥烏）のを満たす項点によって誘導される部分グラフ（適合部長さの和の最小値である．したがって項点非共有の条分グラフ）を考えた．

件を緩和した最短路長の和∑J＝1‥烏d（〃J，わ）はd（訂，デ）（1） 宮から到達可能であること．の下界を与える．ここではこれをゐ（訂）として定義し（2）ノ番目の要素彷は万の並びにおいてsノとわた．の間の項点であること．

6．理論と実用可能性の検証

そして，適ノ合部分グラフ上でLiのアルゴリズムと同様に最短路問題を解くアルゴリズムSDPPlを開発

紺＝一定の条件の下でのリンク数と計算時間の関係を調べる実験を行い，けl，】却，紺が一定ならば計算時した．

4．2 リンク幅と計算量間は点に依らず棚によって決まる上限があることを

SDPPlの計算量を評価するために以下で定義され検証した．

またA＊アルゴリズムなどによる改善の効果を調べるリンク幅Ⅳ（打）という概念を導入した．ここでる実験を行った．eの全探索を基本とするダイクス

打（〃）は打の並びにおける〃の順位である．

ぴ（冗，〃）空（（∫，川（s，′）∈ん方（s）≦方（〃）＜打（≠））Ⅳ（冗）聖maxl紺（冗，〃）】トラ法などのアルゴリズムでは棚の増加に対して理論計算量が示すとおり指数的に計算時間が増加するが，〜一己l■ぴ（打，〃）は万の頂点列における〃をまたぐリンクのこれに対しA＊を適用して改善したアルゴリズムでは集合であり，Ⅳ（冗）はその大きさの最大値である．G

探索頂点数を劇的に削減でき，実験的にはぴの増加に対して万が与えられたとき，Gのリンク幅紺＝に対しても現実的な時間（多項式時間）で計算可能でⅣ（冗）と適合部分グラフeの間に次の二つの定理があることが分かった．

最後にJRのある中規模駅の駅設備，入出車両デー成立する．
定理1∂の頂点の数は，高々悍1∽個である．
定理2 ∂の辺の数は，高々紺昨l∽￣1l且l個である．

SDPPlの計算量は上の定理から0（u）2EvEWTllEl）
時間，0（紺lVlぴ）領域となる．駅構内入れ換え計画問タを使用し，仮想的な入換車両を含む厳しい条件の問題を設定して，実問題への有効性の検証を行った．計
画時間76分，入換車両数6本を対象としたグラフ（lVl＝3，300，l且l＝5，871，烏＝118，紺＝12）に対し，題では紺の上限が駅設備によって定まるので，変数数分で最通解（入挽回数22回）を求めることが出来である々に比べ非常に小さな定数として評価できる．

た．

したがってSDPPlは同問題を多項式時間・領域で計算でき，しかも理論計算量だけでなく絶対的な計算時間，計算領域の面でも有効な解法であると言える．

参考文献［1］C．L．Li，S．T．McCormick，and D．Simchi−Levi，Finding Disjoint Paths with Different PathLCosts：
Complexity and Algorithms．Networks，22，（1992），

5．実問題への適用

pp．653−667．

実問題では紗が10程度となるので，上記の結果に加え探索方法や頂点の記憶方法の改善による実計算時［2］N．J．Nilsson（白井他訳），人工知能の原理，日本コンピュータ協会，1983．

間・領域の縮小が必要である．そこで宮から「への最短路探索にA＊アルゴリズムを適用した．A＊は宮672（32）© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オペレーションズ・リサーチ