Desigining algorithms for commodities transportation on a planar graph modeling a map

点击翻译按钮获取中文摘要

本研究では輸送問題の計算困難性問題を扱った．アルゴリズムの分野では，入力のサイズに対して多項式で表される時間内に問題が解けるとき，その問題は効率よく解けるという．これに対して問題解決までの時間が入力のサイズの指数関数的に増大する問題は計算困難な問題という．本研究では輸送問題を扱うが，従来からの輸送問題では１台の車両を用いて需要を満たす輸送を行うのに対して，各節点に用意された車両を用いる点が異なる．また，単方向と双方向の輸送を考えている点も従来と異なる点である．単方向の輸送では一つの方向にしか荷物を運ぶことができないのに対して，双方向の輸送では荷物を送った後，そこから別の荷物を積んで元の場所に戻ることができる．入力としては，節点ごとに荷物の種類ごとに，貯蓄量または需要量を指定する．その上で各節点に用意された車両を用いて，隣との輸送によりすべての需要を満たすことができるかどうかを問う問題（充足可能性問題）と最大の需要を最小にする輸送を求める問題（最適化問題）を考える．グラフに制限がなければどちらの問題もNP完全（効率よく問題を解くことができない問題のクラス）であるが，サイクルを含まない木（または，木の集合としての森）であれば充足可能性問題を解く効率の良いアルゴリズムが存在することをこれまでの研究で明らかにした．また，各節点に１台の車両ではなく，各辺に１台の車両を用意する場合にはより能力が高くなることが予想されるが，実は能力に差がないことも従来の研究で示した．さらに，単方向の輸送問題に対しても，節点の場合分けを利用して多項式時間で充足可能性問題を解く効率の良いアルゴリズムを提案することができた．また，整数線形計画法を用いると，何回の輸送で充足することができるかという一般の問題も定式化できることを示したが，最悪の場合は指数時間がかかるので，近似アルゴリズムが必要である．