運搬経路問題の接続に基づく整数線形定式化モデルにおける強欲的制約の定式化

カテゴリ: 部門大会

論文No: TC13-4

グループ名: 【C】平成29年電気学会電子・情報・システム部門大会講演論文集

発行日: 2017/09/06

タイトル(英語): Formulation of Greedy-like Constraints in Connection-based Integer Linear Programming Model for Vehicle Routing Problem

著者名: 稲元 勉(愛媛大学),樋上 喜信(愛媛大学)

著者名(英語): Tsutomu Inamoto|Yoshinobu Higami

キーワード: 運搬経路問題|巡回セールスマン問題|整数線形計画法|強欲法|vehicle routing problem|traveling salesman problem|integer linear programming|greedy algorithm

要約(日本語): 本稿では，整数線形計画法に基づく運搬経路問題のための近似解法の開発を目指す研究の端緒として，強欲的に顧客訪問順序を定める規則の整数線形計画法における制約式としての定式化を提案する．著者らの目指す近似解法は，顧客を部分に分割し，部分集合内での訪問順序を短時間で定められることを前提としている．このようにして定められた訪問順序は最適でなくてもよい．予備調査では，顧客訪問順序を高速に定めるための規則として強欲法を取り上げ，ある顧客のつぎにどの顧客を訪れるかを定めるという一般的定式化モデルの上で，強欲法の定式化を試みた．予備調査の結果，強欲法を厳密に整数線形計画法の制約式として表現した場合の求解時間が非実用的に長いことが分かった．本稿では，強欲法と似た基準で訪問順序を定める規則を考え，この規則を表現する整数線形計画法における制約式を提案する．計算例では，TSPLIB の例題を対象とした計算結果を示す．

PDFファイルサイズ: 251 Kバイト