2024-03-28T23:38:19Zhttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_oaipmhoai:ipsj.ixsq.nii.ac.jp:000808812023-04-27T10:00:04Z01164:02735:06701:06702
移動体の通過順序付けにおけるタブーサーチへの長期記憶の導入結果Introduction of Long Term Memory into Tabu Search for Object Orderingjpnhttp://id.nii.ac.jp/1001/00080881/Technical Reporthttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_action_common_download&item_id=80881&item_no=1&attribute_id=1&file_no=1Copyright (c) 2012 by the Information Processing Society of Japan三菱電機株式会社情報技術総合研究所三菱電機株式会社情報技術総合研究所三菱電機株式会社情報技術総合研究所三菱電機株式会社インフォメーションシステム事業推進本部澤田, めぐみ白石, 將尾崎, 敦夫松村, 寛夫複数の移動体の通過順序付けには,一般に先着順方式が採用されることが多い.しかし,先着順方式を適用する場合,遅延伝搬により,交通全体として大きな遅延が発生する危険性がある.そこで,先着順からの順序入替えを許容し,最適化手法を用いて遅延を抑制する順序入替え方式を提案している.提案方式では,順序付けの決定に,最適化手法の 1 つであるタブーサーチ (TS:Tabu Search) を用いている.本稿では,提案方式で利用するTSに長期記憶を導入した.評価の結果,提案方式で利用する TS の性能向上には,長期記憶を用いるよりも,最良解が一定期間未更新となった場合に探索を初期解 (先着順の順列) へ戻して再スタートする方が良いことが確認された.In a transportation system, Moving objects passing through a common region should be ordered at the entrance. Usually, a first-come-first-served (FCFS) method is applied. However, FCFS could cause delay propagation among these objects, which could result in substantial total delay. To solve this problem, we proposed an ordering method that minimizes the total sum of delays considering fairness. The proposed method determines the order by using a tabu search (TS) that is a optimization algorithm. In this paper, we introduce a long term memory into the TS for the proposed method. Experimental results show that a restart of the search (the search is restarted from the FCFS order when the best solution has not been updated in a given number of iterations) provides better performance than the long term memory for the proposed method.AN10505667研究報告数理モデル化と問題解決(MPS)2012-MPS-8724162012-02-232012-02-21