運搬経路問題のパラメータ付けられた整数線形計画問題としての定式化に向けた検討

カテゴリ: 部門大会

論文No: TC1-4

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

発行日: 2016/08/31

タイトル(英語): Consideration on Modeling Vehicle Routing Problems as Parameterized Integer Linear Programming Problems

著者名: 稲元 勉(愛媛大学),遠藤 慶一(愛媛大学),樋上 喜信(愛媛大学),小林 真也(愛媛大学)

著者名(英語): Tsutomu Inamoto|Keiichi Endo|Yoshinobu Higami|Shinya Kobayashi

キーワード: 運搬経路問題|整数線形計画法|パラメータ化|近似|vehicle routing problem|integer linear programming|parametrize|approximation

要約(日本語): 本稿では，運搬経路問題の求解時間の短縮を目指し，当該問題をパラメータ付けられた整数線形計画問題として定式化する試みの現況を報告する．運搬経路問題の最適解を求めることは，小規模のベンチマーク問題に対してのみ可能であるとしても，ヒューリスティクスの試金石などとして一定の有用性を持つ．一方，著者らは，エレベータ運行計画問題の求解に際して，解の粒度を徐々に微細化できるようパラメータ付けられた整数線形計画モデルを用いる近似解法を提案している．同様の解法を運搬経路問題へ適用することで，求解時間の削減を期待できる．そのためには，運搬経路問題を，解の微細度を規定できるようパラメータ付けて定式化する必要がある．そのような定式化の1候補として，経路をトリップへと分割し，各トリップをスロットへと分割する定式化を提案し，その実現の取り組みについて報告することを，本稿の目的とする．

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