大規模Vehicle Routing Problemに対するエリア分割と段階的統合に基づく新たな探索アプローチの提案

摘要

Vehicle Routing Problems（VRPs）は，配送計画問題または運搬経路問題と呼ばれ，配送センター（Depot）から複数の需要地への配送を効率的に行おうとする配送ルート決定問題であり，実務的な問題として1950年代より数多くの研究がなされてきた．VRPsは，制約として与えられた各ビークルの積載量制約を満たした上で複数のビークルを用いてすべてのカスクマを訪れる経路決定問題であり，ビークルに対するカスクマの割り当て，および各ビークルでのカスクマの訪問順序を決定する問題である．これまでVRPs に対しては，様々な発見的解法が適用されており，数多くの適用例が報告されている．また，VRPsは総移動距離だけでなくビークルの台数，各経路間の移動距離の分散度合いなど本質的に多目的の要素を内包していることから，進化型多目的最適化（Evolutionary Multi-criterion Optimization，EMO）をVRPsへ応用した研究も数多く報告されている．