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

设计平面图上的商品运输算法对地图进行建模

基本信息

批准号：
20K11673
负责人：
浅野哲夫
金额：
$ 2.66万
依托单位：
Kanazawa University
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research (C)
财政年份：
2020
资助国家：
日本
起止时间：
2020-04-01 至 2024-03-31
项目状态：
已结题

项目摘要

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

在这项研究中，我们处理了计算困难的交通问题。在算法领域，如果可以在输入大小的多项式表示的时间内解决问题，则称该问题已得到有效解决。另一方面，解决问题所需的时间随着输入的大小呈指数增长的问题称为计算困难问题。本研究涉及交通问题，但不同的是，传统的交通问题使用单一车辆来满足需求，而使用每个节点准备的车辆。它与传统模型的不同之处还在于它考虑了单向和双向运输。在单向运输中，货物只能在一个方向上运载，而在双向运输中，可以将货物发送出去，然后装载其他货物并返回到原来的地点。作为输入，指定每个节点每种类型货物的存储或需求量。然后，使用每个节点准备的车辆，存在询问是否可以通过与邻近节点的运输来满足所有需求的问题（可满足性问题），以及寻找使最大需求最小化的运输的问题（优化问题）。如果图不受限制，这两个问题都是 NP 完全问题（一类无法有效解决的问题），但如果它们是不包含循环的树（或作为一组树的森林），则它们是可满足的。表明存在解决问题的有效算法。此外，虽然预计如果每侧配备一辆车而不是每个节点配备一辆车，容量会更高，但之前的研究表明，容量实际上没有差异。此外，即使对于单向运输问题，我们也能够提出一种有效的算法，通过使用节点案例分类在多项式时间内解决可满足性问题。我们还表明，使用整数线性规划，可以制定可以满足多少传输的一般问题，但在最坏的情况下需要指数时间，因此需要近似算法。