3D荷物の配置を考慮した配送計画問題に対する研究とその応用

点击翻译按钮获取中文摘要

本研究では荷物を配送する際に車両内での荷物配置を考慮する配送計画問題と取り出し順序を考慮する配置問題に対する発見的解法を開発する．今年度は取り出す順序を考慮する長方形配置問題に対する構築型解法を提案した．取り出す順序を考慮する長方形配置問題は，長方形の集合とその取り出す順序を与えられる時に，高さが可変で幅が固定される長方形の容器にできるだけ効率よく配置する問題である．本研究はこの問題に対して，長方形を取り出す順の逆順で容器に一つずつ詰め込む方法を考えた．長方形を配置する場所について，bottom-left, bottom-right, longest-skylineと呼ばれる三つの配置戦略を提案した．長方形を詰め込んだ後に，より下の位置の空きスペースを埋めることにより，取り出す順序を守るようにした．ランダムに作成した大規模な問題例に対し計算実験を行い，平均充填率が90%以上となることを確認した．また，通勤バスルーティング問題について探索型解法を提案した．通勤バスルーティング問題とはバス停の候補と希望到着時間と目的地をカバーできるバス停の候補の集合を持つ社員が与えれるとき，すべての社員を希望到着時間内に目的地をカバーできるバス停に送るようなバスルート組を求める問題である．この問題に対して反復局所探索法を提案した．提案手法では2種類の近傍操作に基づく局所探索法を用いた．解に多様性を持たせるため，重みを適応的に変化できるペナルティ付き評価関数も設計した．