VRP#

読み: ぶいあーるぴー
英名:
別名: 配車計画問題

Vehicle Routing Problem の略．複数のサービス車 (Vehicle) がスタート地点から需要のある地点の巡回を行いゴール地点へ行く．全ての需要を満たし，総経路コストを最小化することを考える問題．数理計画問題として定式化を行い厳密解法で解くことも可能ではあるが，問題が複雑になってしまうため現実的に有効な手法ではない．近似解法によって求めるのが一般的である．問題の構造によって有効なアルゴリズムが大きく変わるため，どのような手法がよいかを一般的に提示することは難しいが，列生成法を用いたアプローチが有名である．