鉄道とスケジューリング　- 数学の問題として捉えると –

鉄道会社は、持っているたくさんの車両を、時刻表上の複数の列車にどう割り当てるか、車両運用を行いスケジューリングする必要があります。日本で代表的な、ある車両が一日内の全列車を何日かで一回ずつ担当する方法では、それぞれの車両が、1日ごとの仕事を少しずつずらしていきながらローテーションを担当するため、どの車両がどの駅を出発してどこに到着するのかを一日単位で示し、それをどのような順番で行うかを考えます。この車両運用を数学的な問題として捉えてみると、巡回セールスマン問題（TSP）に帰着することが分かります。TSPとは、都市間（枝）の距離が既知の、n個の都市を全部訪問し、元に戻る場合の総距離が最短なのはどの巡回路かという問題です。都市を「列車」に、枝を「異なる二つの列車のつながり」に、枝の長さを「次の列車発時刻－前の列車着時刻」に置き換えて求めますが、nの数が増えると、コンピューターでも全列挙算出するのは無謀です。さらに、点検のための日数を考慮するといった条件を付加する必要があるため、整数計画・組合せ最適化領域から、一番良い組合せ方を見つけたり、「良い」「悪い」を測る目的関数や、組合せの条件の制約条件を用いたりして運用していきます。スケジューリングを数学的な問題として捉えると、このような車両運用だけでなく、さまざまな生産スケジューリングや勤務スケジュール、スポーツの試合日程などにも適用することができるのです。