京都大学教育研究振興財団助成事業
成 果 報 告 書
平成28年8月30日
公益財団法人京都大学教育研究振興財団会 長 辻井 昭 雄 様
所属部局・研究科

工学研究科

職 名・学 年

准教授

氏

Qureshi Ali Gul

名助 成 の 種 類

平成２８年度 ・ 研究者交流支援 ・ 国際研究集会発表助成／一般

研 究 集 会 名

第14回世界交通学会大会

発 表 題 目A new tabu search algorithm for collection and transport of the debris after
disasters

開 催 場 所

中国・上海・同済大学

渡 航 期 間平成28年7月9日

成 果 の 概 要～

平成28年7月13日

タイトルは「成果の概要／報告者名」として、A４版２０００字程度・和文で作成し、添付して下さい。 「成果の概要」以外に添付する資料 ■ 無□ 有()
交付を受けた助成金額

150,000 円

使 用 し た 助 成 金 額

150,000 円

返納すべき助成金額0円
航空費51,890 円

鉄道賃 5,928円
会 計 報 告日当助 成 金 の 使 途 内 訳

25,000円 （1日5,000円×5日）

宿泊費 60,000円 （1日15,000円×4泊）
査証手数料 7,182円（今回の助成に対する感想、今後の助成に望むこと等お書き下さい。助成事業の参考にさせていただきます。）

当財団の助成について成果の概要／Qureshi Ali Gul
中国上海にある同済大学で 7 月 10 日から 7 月 13 日まで第 14 回世界交通学会大会（WCTRS、２０１４）に参加いたしました。今まで研究した成果を発表する機会があり、嬉しく思います。
このレポートは、その際の研究発表についての成果概要です。
発表題目：A new tabu search algorithm for collection and transport of the debris afterdisasters
甚大な災害の後では、災害により発生した災害がれきの処理や管理が問題となる。日本の地震災害にみられるように、がれき除去作業の完了には数カ月を要することが多く、中には数年を要する場合もある。特に、2011年に発生した東日本大震災の場合のがれき除去作業は、災害がれき管理事業として歴史上最も困難で且つ多大な費用を要するものの一つとなっている。地震に伴って発生した津波が、想定を超えた大量の災害廃棄物と津波堆積物を広範囲にわたって生みだした。岩手県石巻市では、津波により推定615万tのがれきが発生した。この量は、通常時に同市で発生する固形廃棄物の103年分に相当する。他の都市でも同様の状況が生じているが、その規模はさまざまである。道路啓開作業では、災害廃棄物に混ざっている個人の所有物を扱っていよいか確認することも必要となる一方、作業の緊急性も要するため、発災直後の道路啓開作業は一層困難を極める。道路啓開作業に必要な費用の主な発生源としては、がれき回収費用と処分施設への輸送費用が挙げられる。また、処分施設への輸送費用は、車両による一時／最終処分施設へのがれきの輸送に際して選択する経路に依存する。そこで本研究では、災害後のがれき管理事業の一つである道路啓開作業の費用の最適化や作業効率の向上に焦点をあてて研究を行うこととする。
Pramudita, Taniguchi, Qureshi（2011）はこの最適化問題に対応する代替解決法としての数学モデルの開発を行い、がれきを撤去するときの道路リンクの訪問順序の最適化および中間的ながれきの仮置き場の最適配置について検討している。災害後のがれき回収事業を誘因とする無向容量制約付きアーク巡回問題（CARP: Capacitated Arc Routing Problem）の一種を採択している。CARPから Capacitated Vehicle Routing Problem（CVRP）の変換については、Longo et al. （2006） が採用したように、各必須アークに2個のノードを作成する方法を用いた。がれき回収事業問題に対する新たなアイデアとして、ノードに輸送能力制限を導入する。この制限は、 で表される。この値は、車両kがノードiからノードjに移動する場合、もしくはノードjで修復作業を行う場合には1に等しくなり、それ以外では0となる。車両が必須ノードの修復作業を完了し、閉鎖していた道路が開通するごとに、輸送能力マトリクスは当初の状況、もしくは以前の状況から常に変化する。したがって、この制限は動的制限に分類することができる。
上記の問題は NP-困難問題に分類されるため、問題に対して近似的最適解を得るために様々なヒューリスティクスの解法が研究されてきた。Pramudita, Taniguchi, Qureshi（2011）はこのような問題に広く使われているメタヒューリスティクスの一種であるタブーサーチを用いている。従来の解法で用いられていたタブーサーチでは、がれき回収輸送事業の特色である車両アクセス制限のために、実行不可能解も含んだ探索を行っていた。しかし、実行不可能解を含めた探索は非合理的であるため、これを防ぐ必要がある。本研究では、グラニュラータブーサーチ（ＧＴＳ）の基本概念を導入し、従来の解法の改善を行う。タブーサーチにおける近傍探索の範囲を狭める手段として、第二章第一節で説明したアクセス制限（Access possibilityconstraint）の活用を考える。従来の解法ではこのアクセス制限が十分に活用されておらず、そのために近傍探索において多くの実行不可能解の探索を許していた。本研究ではアクセス制
限を考慮した新しい解法を以下ＡＰ－ＧＴＳ（Access Possibility-based Granular TabuSearch）法とよぶこととする。本研究のタブーサーチでは、ノードで構成される現在の解から二つのノードを交換することにより近傍解を生成する。ＡＰ－ＧＴＳ法では各試行において、アクセス制限という観点から交換可能なノードを抽出し、それらをリストアップする。こうすることによって、実行不可能な近傍解が生成するのを防ぐことができる。アクセス制限は訪問リンクの組み合わせが変わるたびに変化するので、交換可能なノードのリストアップも毎試行行わなければならない。
ＡＰ－ＧＴＳ法がどれだけ改善したかをテストするために、同じ道路ネットワーク・同じデータセット（岩手県陸前高田市）に対して従来の解法とＡＰ－ＧＴＳ法を用いて比較を行った。
結果は計算時間とそれぞれの解法で導かれた最適解の値を用いて評価され。従来の解法に比べてＡＰ－ＧＴＳ法は計算時間を 85％、コストを 12.2％削減することに成功している。この結果より、ＡＰ－ＧＴＳ法により十分な改善ができたと言える。
参考文献
Longo, H., Poggi de Aragão, M. and Uchoa, E., Solving capacitated arc routing
problems using a transformationthe CVRP, Computers and Operations Research, Vol.33,
1823-1837, 2006.
Pramudita, A, Taniguchi, E, & Qureshi, A.G., Undirected Capacitated Arc Routing
Problem in Debris Collection Operation after Disasters, Journal of Japan Societyof Civil Engineers, Ser. D3 (Infrastructure Planning and Management), Vol.68, No.5,
pp.805-813, 2011.