スケジューリング問題における相転移理学専攻・情報科学コース

1

はじめにスケジューリングとは作業の順番を計画することであり、それが最も効率よく作業できる順番を求める問題のことをスケジューリング問題という。このスケジューリング問題は、組合せ最適化問題の代表的な 1 つである。最適化問題とは、与えられた制約条件の下で、ある目的関数を最大または最小にする解を求める問題のことをいう。最適化問題には、本論文で扱う勤務スケジューリング問題、巡回セールスマン問題の他に、ナップサック問題、配送計画問題などが例に挙げられる。
本要旨においては、巡回セールスマン問題について述べる。
旅行地やテーマパークを周遊する際、効率の良い周り方を考えることがよくある。効率の良い周り方とは、訪れたい場所の全てを最短路、最短時間で周ることとする。これには巡回セールスマン問題 (TSP) が応用できると考えられる。TSP とは、N 個の都市を一度ずつ訪問して出発地に戻る経路の中で、最短で訪問できる経路を求める問題である。先行研究には、都市数 N を変化させた場合に有限サイズスケーリングを観察することができるもの [1] や、時間の制約を付けたもの [2]、複数の時間枠を付けたもの [3] などがある。本研究では、経路だけでなく時間の制約を付けることによって、旅行地やテーマパークの周遊に応用できる手法を考えたい。大きさ 1×1 の正方形の中に N 個の都市が置かれているとする。全ての都市を巡って戻った時の最短時間が、時間 T 以下である場合を成功とする。これに時間の制約を加えたときの成功率の変化を調べる。

2

図 1: 時間制約. 時間枠の設定.

3.1

実行結果 (1)以下の条件で実行した。
• N =5, 10• ∆t=1, 2, ..., 5 (1 刻み)• ti =0, 0.5, 1.0, ..., 5 (0.5 刻み)
ti =0, 1.5, 2.5 のときを図 2 に抜粋して示す。ti =0〜2.0までは N =5 と 10 のときで差が見られるが、これは単純に巡回時間の差であると考えられる。また、ti =0 のとき ∆t が小さいと成功率が最大でも 1 未満となる。これは、tf ＜ ts となることが多くなり成功しにくくなったからである。ti =1.5 のとき、N =10 のグラフで不規則な上昇をしているグラフがあるが、これは ∆t =1 のときである。こちらも、前述したように tf ＜ ts となることが成功率低下の原因である。ti =2.5〜のとき、N による違いが見られないグラフになるが、N =5 の成功率が低下し、N =10 の成功率に近づいたためである。ti が大きいため時間制約がある都市に早く到着することが多くなり、ti まで待ってしまうことで T までに巡回できずに失敗が多くなったと考えられる。

3.2

実行結果 (2)以下の条件で実行した。
• N =5, 10• ∆t=2.0• ti =0, 0.1, 0.2, ...., 1.5 (0.1 刻み)
N =5, 10 それぞれの場合の結果を図 3 に示す。ti に大きな変化は見られないが、グラフの広がりを観察できる。N =5 のとき、下部分の広がっているグラフの右側が ti が大きく、左側が小さいグラフである。このような形になったのは、ti が大きいため、ti まで待機したことで T までに巡回できず成功率が低下したからである。しかし、これは T が小さいときに影響を受けるので、T が大きくなるとグラフの広がりはほとんどなくなる。N =10 のとき、上部分の広がっているグラフの右側が ti が小さく、左側が大きいグラフである。つまり、ti が大きいときの方が成功率が高い。これは、∆t が大きい条件の下、ti が大きい、すなわち tf が大きくなり、T も小さい値ではないことが理由である。

分枝限定法と時間の制約

本研究では、厳密解法である分枝限定法を使用している。分枝限定法は、解の全列挙にかかる膨大な計算時間の無駄をできるだけ省くため、最適解が得られないことがわかったらその計算を無視する。つまり、検索途中の経路と残りの経路の下限の合計がそれ以前に見つかっている最短経路より大きい場合、その探索を打ち切るという方法である。本研究は、これに時間の制約を追加した。
時間の制約として、ある 1 つの都市に時間枠を設定した。時間枠とは、その都市に到着してよい時間枠のことである。その時間枠の始時刻を ti 、時間枠を ∆tとし、時間枠の終時刻を tf とする。また、出発の都市から時間制約をつけた都市までにかかった時間を ts とする。指定した始時刻前に時間制約をつけた都市に到着した場合、始時刻まで待ってから探索を再開する。
しかし、時間枠内に時間制約をつけた都市に到着できなかった場合、その探索は打ち切りとする [図 1]。

3

藪内友紀

3.3

実行結果 (3)以下の条件で実行した。
• N =5, 10• ∆t=0, 0.1, 0.2, ...., 1.5 (0.1 刻み)• ti =0∆t の値が大きくなるにつれて成功率が上がる結果が得られ、∆t に依存していることが観察できた。さらに成功率の関係を観察するために、ti と ∆t を変数とした立体図を作成した。(ここでは図を割愛する。)

実行結果と考察[成功条件]：ts ＜ tf かつ、巡回時間が T 以下であれば成功、そうでないとき失敗とする。
[成功率の計算条件]：ランダムな都市の配置を 1000 通り試した平均をとった。

1

3.4

実行結果 (4)以下の条件で実行した。
• N =5, 10• T =10
N =5 のときの結果を図 4 に示す。データから、成功率が下がり始める部分の ti と ∆t の値は約 1.2〜1.3 程度であり、図4 にある青線部の直線の式は概ね
ti + ∆t =√√tf = 2 と推察できる。つまり、tf ＜ 2 のときに成功率が下がることが観察できた。これは今、都市の位置を 1×1 の正方形の中にランダムに配置しているため、出発した都市から指定された都市までの距離が最√大で 2 になるからであると考えられる。

図 4: (4) の N =5 のときの実行結果. x 軸は ti , y 軸は∆t, z 軸は成功率. 成功率が下がり始める部分と、その部分の x,y の値に補助線を引いた.
図 2: (1) の実行結果. 横軸は T , 縦軸は成功率. 左の曲線の束が N =5 のとき. 右の曲線の束が N =10 のとき.

4

まとめと今後の課題経路に加え、時間の制約をつけた TSP について、成功率を計算し相転移の様子を捉えた。実行結果より、成功率は制限時間 T と時間枠の長さ ∆t に影響を受けることが観察できた。さらに、都市配置の領域の大きさと時間枠の終時刻 tf との関係が成功率を左右することがわかった。今後は、効率をよくするためには待っている時間が無駄であるため、この時間に重みをつけるなどさらに制約を課し、より効率の良いスケジューリングができるようにしたいと考えている。

参考文献[1] I. P. Gent, T. Walsh, “The TPS phase transition”, Artificial Intelligence, Vol. 88, 349-358,(1996).
[2] E. K. Baker, “An Exact Algorithm for the TimeConstrained Traveling Salesman Problem”, Operations Research, Vol. 38, No. 5, 938-945,(1983).
[3] G. Pesant, M. Gendreau, J. Potvin, J. Rousseau,“On the Flexibility of Constraint Programming
Models: From Single to Multiple Time Windowsfor the Traveling Salesman Problem”, European
Journal of Operational Research, Vol.117, 253263, (1999).

図 3: (2) の実行結果. 横軸は T , 縦軸は成功率. グラフの広がりが N によって異なることが観察できる.

2