時間枠つき配送計画問題に対するパス再結合と適応的パラメータ調整

• Item type: SIG Technical Reports(1)
• 公開日: 2008-05-20
• タイトル: 時間枠つき配送計画問題に対するパス再結合と適応的パラメータ調整
• タイトル / 言語: en
• タイトル: Path Relinking and Adaptive Parameter Control for the Vehicle Routing Problem with Time Windows
• 言語: eng
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 京都大学
• 著者所属: 名古屋大学
• 著者所属(英): en
• 著者所属(英): Kyoto University
• 著者所属(英): en
• 著者所属(英): Nagoya University
• 著者名: 橋本, 英樹; 柳浦睦憲
• 著者名(英): Hideki, Hashimoto; Mutsunori, Yagiura
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 時間枠つき配送計画問題に対してパス再結合アプローチを提案する．本解法は主にパス再結合，局所探索法，適応的パラメータ調整の３つから構成される．パス再結合では，これまでの探索中に見つけた良い解を組み合わせて新しい有望な解集合の生成法を提案する．生成された解は局所探索法により改善を行う．局所探索法の近傍としては 2-opt*，cross exchange，Or-opt を用い，さらに効率的に近傍探索を行うために近傍リストを定義し，それを利用して近傍のサイズを制限する．本解法は実行不可能解も探索の対象とし，制約違反度をペナルティとして評価関数に重み付きで足し合わせることで解を評価する．アルゴリズムの性能はその重みに大きく依存するため，探索状況をフィードバックしつつ重みを適応的に調整する方法を提案する．最後に，ベンチマーク問題に対して計算実験を行い，本解法の効果を確認する．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: We propose a path relinking approach for the vehicle routing problem with time windows. In our algorithm, solutions generated by path relinking operations are improved by a local search whose neighborhood consists of the representative neighborhoods called 2-opt*, cross exchange and Or-opt. To make the search more efficient, we propose a neighbor list that prunes the neighborhood search heuristically. Infeasible solutions are allowed to be visited during the search, while the amount of violation is penalized. As the performance of the algorithm crucially depends on penalty weights that specify how such penalty is emphasized, we propose an adaptive mechanism to control the penalty weights. The computational results on well-studied benchmark instances with up to 1000 customers revealed that our algorithm is highly efficient especially for large instances. Moreover, it updated 41 best known solutions among 356 instances.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 2008, 号 49(2008-AL-118), p. 57-64, 発行日 2008-05-20
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会