2-opt法とOr-opt法を用いた容量制約付き配送計画問題の局所探索法に関する一考察

摘要

配送計画問題（Vehicle Routing Problem，以下，VRP）は，宅配便や郵便，商品輸送，などの配送サービスにおいて，各運搬車の最適経路を求める組合せ最適化問題である．VRPは，使用する運搬車の台数を最小限に抑え，かつ運搬車の総移動距離と移動時間の短い，最適な配送計画を求めることを目的とする．また，VRPは，NP困難な組合せ最適化問題の一種である．VRPには，各顧客に訪問する時間が設定された時間枠制約付き配送計画問題や各運搬車に積載量の制約を加えた容量制約付き配送計画問題などがある．本研究では，容量制約付き配送計画問題における局所探索法の性能について考察する．CVRPは，運搬車に最大積載量が設定されており，従って，設定された運搬車の最大積載量を超えずに多くの顧客を訪問することが求められる．CVRPの局所探索法として，2-opt法とOr-opt 法がある．本研究では，この2つの手法を組み合わせた新たな局所探索法を提案する．計算機実験の結果から，提案手法を用いることにより，初期解と比較して，最大積載量の制約を守りつつ，運搬車の台数，移動距離が減少することを確認した．