列生成法とヒユーリスティッタスの併用による配送集荷経路問題の解決

摘要

近年,荷主企業にとって輸送コストを削減したいという大きなニーズがある.その中でも,配送集荷経路問題を解決する必要がある.本稿では列生成法にヒューリスティックスである挿入法とtwo-opt法を併用すること巡回距離の短縮を図った.この問題は複数の車両で配送集荷地点を分割する集合分解問題と,分割された各配送集荷地点の巡回距離を同時に最適化するものである.提案手法の有用性を示すためにソロモンのベンチマークテストによる検証実験を行い,従来結果と同等以上の結果を得られた.この結果をうけて配送集荷経路問題への適用を図った.%In recent years there is a great need that want to reduce transportation costs for shippers company. Among them, it is necessary to solve the VRPSDP(Vehicle routing problem simultaneously delivery and pick-up). In this paper we tried to short the distance using column generation method and two-opt method and insertion method that is heuristic. The problem is to optimize the set decomposition problem that split the pick-up and delivery point in multiple vehicles, and cycle distance of divided pick-up and delivery point. We conducted a verification experiment(Solomon's benchmark) to demonstrate the usefulness of the proposed method, and obtained results equal to or better than conventional result. In response to this result, we tried application of the proposed method to VRPSDP.