Real-life scheduling problems are often very large-scale, so that the cost reduction effect by scheduling solvers is also very large. Thus, how closer the solver obtains to optimal solutions or conventional manmade solutions, is important. Also, from user's perspective, it is important to deal with variety of constraints flexibly. In this paper, we focus on variable depth search (VDS) which realizes intensive search by its larger search space represented by the long chain of simple neighborhood operations.

First, we provide a novel VDS algorithm for the multiple depot vehicle scheduling problem (MDVSP) which is a scheduling problem in which all the timetabled trips are assigned compatibly to any vehicle and are covered just once by any vehicle at minimum cost. In our algorithm, we utilize a basic neighborhood operation called ``swap'' which interchanges the latter part of the trip sequence for one vehicle and that for another vehicle. To realize VDS, we propose an algorithm called swap-path multiple backtracking algorithm (SMB) utilizing the fact that we can obtain a new assignment by a path. As a result, SMB traverses a larger search space strategically by regarding consecutive swap operations as a neighborhood.

Second, we introduce some theoretical results with detailed proofs. To begin with, we prove the fact that any assignment can be obtained from another assignment by a finite number of swaps. From the viewpoint of the search tree induced by this fact, we can show that SMB is much faster than that for simple brute-force strategies. Then, we can show the case that n-1 swaps are required at most to obtain the nearest improved solution, where n is the number of trips. This result justifies our VDS approach which considers a larger search space. Moreover, we show a sufficient condition that SMB at threshold k can obtain an improved solution which is obtained by k swaps from the initial solution.

Third, we show an application of SMB algorithm into one of the most famous benchmark problems. To begin with, we show how to take SMB into a conventional framework for MDVSP with some enhancement techniques using pruning and tabu search heuristics. Computational results show that our method achieves an average of at least 20 % better results than other local search based methods, and that it exhibits the best early-time local search performance among state-of-the-art methods.

Fourth, we show another application of SMB algorithm into real-life railway rolling stock allocation problems (RSAP) at a railway company. First, we formulate RSAP as MDVSP with side constraints, and then propose a framework using iterative deepening and two-step backtracking approach to solve the problem. Computational results based on real constraints show that our approach can obtain an approximate solution near the optimum in shorter time than CPLEX.

Fifth, we propose a semiautomatic planning framework for creating the rolling stock allocation schedules using the SMB based engine. Our framework has two main features. First, users can easily register and adjust constraints flexibly through three kinds of constraint expressions. Second, users can obtain failure messages which identify the site of constraint violation accurately in failure cases. Our real-life trials show that our scheduler can provide results that are almost comparable to those obtained by experts faster than before.

The above-mentioned contributions show that the proposed approach is effective for large-scale real-life problems, and that it is independent of the particular choice of constraints. Therefore, it is possibly applicable for wide applications of other real-life problems based on MDVSP.

スケジューリング等に代表される組合せ最適化問題の実問題は、大規模なことが多いため、計画を自動化することによるコスト削減効果が大きい。一方、計画ソルバーを利用するユーザーの見地からは、日々変化する制約条件をいかに上手く扱えるか、また、実際に使える解を得られるかが重要である。

これに対し、局所探索法(local search)は、多様な制約条件に柔軟に対応可能な性質をもつことから、有力な解法であると考えられる。局所探索法は、初期解生成、近傍探索、擾乱の3つの基本処理からなり、これらの基本処理を工夫することにより、様々なバリエーションが提案されている。たとえば、GRASP(Greedy Randomized Adaptive Search Procedure)法は初期解生成を工夫したものであり、遺伝的アルゴリズム(Genetic Algorithm)やシミュレーティッド・アニーリング(Simulated Annealing)は擾乱を工夫した手法である。これに対し、近年、可変深度局所探索法(Variable Depth local Search: VDS)と呼ばれる手法が注目されている。これは近傍探索を工夫した局所探索法の一種であり、巡回セールスマン問題(Traveling Salesman Problem)の有力な解法の一つともなっている。VDSは、単純な近傍操作を複数回反復したものを改めて近傍と定義する手法であり、大規模な近傍を探索できるメリットがあるが、逆に、単純な実装では組合せ爆発が生じるため、適切な枝刈り手法を組み合わせることが重要である。

本論文は「Variable Depth Local Search for Multiple Depot Vehicle Scheduling Problems」(複数デポ運搬車スケジューリング問題に対する可変深度局所探索法)と題し、7章からなる。

第1章「Introduction」(序論)では、本研究の背景を述べ、局所探索法およびVDSの定義、および関連する概念を説明している。また本研究においてモチーフとして用いる、複数デポ運搬車スケジューリング問題(Multiple Depot Vehicle Scheduling Problems: MDVSP)の定義を述べている。ここではMDVSPを、出発時刻・場所、到着時刻・場所が予め定まった複数の運行を、いずれかの編成(運搬車)に最小コストで割当てる最適化問題として定義している。

第2章「Variable depth search algorithm for MDVSP」(MDVSPに対する可変深度局所探索アルゴリズム)では、MDVSPに対する新しい解法であるSMB (Swap-path Multiple Backtracking)アルゴリズムについて述べている。SMBでは、一台の基点編成を選択し、その基点編成の割当変更に相当するパスを探索することで、改善解を探索する。この際、基本的な近傍である「交換」演算を複数回反復したものを改めて近傍と定義するため、VDSと位置づけられる。

第3章「Theoretical analysis for the proposed algorithm」(提案手法の理論解析)では、SMBとMDVSPに関する以下の3つの理論解析に関して述べている。(1)任意の割当は、有限回の交換演算により別の任意の割当から到達することができる。(2)改善解を得るために、運行の総数に相当する回数の交換回数が必要な事例が存在する。(3)ある十分条件の下で、探索深さkのSMBは必ずk回交換の範囲の改善解を発見できる。また以上の解析に基づいて、しらみつぶし探索と比較したSMBの効率性と複数回の交換演算の範囲を探索するMDVSPの有効性に関して議論を展開している。

第4章「Evaluation on benchmark problems」(ベンチマーク問題による評価)では、よく知られたベンチマーク問題に基づくSMBの評価結果について述べている。計画のコストの比較により、SMBはこれまで知られている局所探索ベースの手法に対し平均20%以上低コストの解を得られること、また短時間の性能では、全ての手法の中で最良の解を得られることについて述べている。

第5章「Evaluation on real-life railway rolling stock allocation problems」(車両運用計画実問題による評価)では、ある鉄道事業者における車両運用計画の実問題に基づき、SMBの評価実験について述べている。実際の制約条件に基づく実験の結果として、SMBが、混合整数計画として定式化して汎用ソルバーであるCPLEXを適用して解く手法よりも、短時間で準最適解を得られることを示している。

第6章「Interactive solution framework for railway rolling stock allocation scheduler」(車両運用計画スケジュラーに対するインタラクティブ解法の枠組み)では、SMBに基づくエンジンを用いたインタラクティブなスケジューリングの枠組みについて述べている。この枠組みには、柔軟に制約条件を入力できる点と、計画失敗時にユーザーに分かりやすい理由を提示できる点に特徴がある。また、鉄道事業者の現場に導入したトライアル実験について述べており、従来の人手による作成よりも高速に、エキスパートに匹敵する車両運用計画を得られることを示している。

第7章「Conclusion」(結論)では、以上の結果に対するまとめと議論および今後の課題について述べている。

以上を要するに、本論文は、複数デポ運搬車スケジューリング問題をモチーフとして、新たな可変深度局所探索法の枠組みを提案している。また、これまで人手で実施されていた車両運用計画作成問題においても、実際に使えるレベルの解を高速に得られることを確認している。これは数理情報学および最適化の実適用に関する研究に貢献するところが大きい。

よって本論文は博士(情報理工学)の学位請求論文として合格と認められる。