最長路問題とJR大都市近郊区間大回りへの応用  [in Japanese] The Longest Path Problem and Its Application to the Path Selection in JR Urban Areas  [in Japanese]

最長路問題は、各辺に非負整数の距離が与えられた無向グラフに対し、始点s、終点t間のシンプルなパスで、その上の距離の総和が最大となるものを求める問題である。最長路問題は、効率的な多項式時間アルゴリズムが古くから知られている最短路問題とは異なった性質を持つ。例えば、各辺に関連付けられた距離の正負を反転させた最短路問題を解くことで最長路が得られるように一見思われるが、負の閉路(距離の総和が負となる閉路)が存在するため、最短路問題のアルゴリズムを適用することはできない。本研究では、最長路問題、s-t最長路問題、全点対最長路問題を定式化し、全探索および0-1整数計画法に基づく厳密最適化アルゴリズムを提案する。また、JR大都市近郊区間の大回りをベンチマークとして利用し、各手法の実装および評価を与える。

The longest path problem is, given an undirected graph with non-negative integer weights for the edges, to find the simple path of the largest length. Although the shortest path problem has brilliant algorithms in the literature, the longest path has no efficient algorithms. In this paper, we treat the longest path problem, the s-t longest path problem, and the all pairs longest path problem. For these problems, we propose two types of algorithms based on the exhaustive search and the 0-1 integer programming. We also implement and evaluate the algorithms by the benchmark instances of the path selection in JR Urban areas.