トラック物流における配送日最適化問題と動的計画法に基づく近似最適化

摘要

We propose a novel optimization problem for a vehicle delivery planning and its effective heuristics based on dynamic programming (DP). Novelty of the problem is that each delivery item has a designated delivery date with a certain relaxation window. Then, the minimum delivery cost can be decreased compared with the rigorous delivery date problem. The optimization of the actual delivery dates is formalized as 0-1 integer programming, which can be reduced to a resource allocation problem. DP is then applicable for the rigorous optimization, though the computational cost is large. Here we proposed a heuristic approach based on DP. First, the value function, which is obtained through recursive steps in DP, is approximated by a linear programming relaxation based on the method proposed by Bertsimas et al. Next, a search of the optimal solution at each recursive step is bounded by setting a threshold. Furthermore, the number of recursive steps can be shortened according to a characteristic time scale of a target problem. The proposed heuristics are applied to the target delivery problem, and detailed numerical calculations on various size problems with various parameter settings show the effectiveness with a largely reduced computational time.%物流業界では近年，新規参入業者による価格競争や，原油価格の高騰に伴う燃料費の上昇，また環境対策のために，さらなる物流の効率化が求められている.一方で，情報システムの高度化に伴い，顧客の配送要求に柔軟に対応しながら，大規模かつ高精度な物流計画を作成することが可能になりつつある.