理工学部

理工学部

在学生向け

関連情報

名物研究室紹介

巡回セールスマン問題の世界記録 【玉木研究室】

玉木研究室

計算理論研究室では、組み合わせ最適化問題を中心としたさまざまな問題に対するアルゴリズムの開発を行っています。組み合わせ最適化というのは、「与えられた部品の要求条件を満たす組み合わせのうち、与えられた評価尺度で最もよい組み合わせをみつけよ」というタイプの問題の一般名称です。VLSIの配置設計や、物流における車両の配送計画、工場における作業行程作成など、実にさまざまな問題が組み合わせ最適化問題と考えることができます。ここでは、例として有名な巡回セールスマン問題を取上げます。たくさんの都市を、順番にひとつずつ訪ねて出発点の都市に戻ってくる道順(巡回路)のうちもっとも総距離の短いものを求めよという問題です。
上で述べた配送計画の他にプリント基板などの穴あけの順番決めなどで実際に起きてくる問題です。組み合わせ最適化問題のよい例題でもあるため、世界中でたくさんの研究者が研究し、TSPLIBという例題集の実例に対して良い解(巡回路)を競い合っています。当研究室で開発したアルゴリズムは、このTSPLIBで大きい方から数えて3番目と5番目の例題に対して、これまででみつかったなかで最短の巡回路をみつけました。右の図は、18512都市の例題d18512に対する、我々の解です。(都市を表示するとつぶれてしまうので、巡回路だけ表示しています。)このアルゴリズムはデンマークのヘルスガウンの開発したプログラムで得た複数の巡回路に、アメリカのクックらが提唱した巡回路併合法を適用するものですが、この併合法の部分に独自のアイディアを盛りこんでいます。

上へ戻る

明治大学 MEIJIUNIVERSITY

© Meiji University,All rights reserved.