Adaptive optimization by dynamic programming heuristics for logistics planning in dynamic environments

This paper considers a novel optimization problem for a vehicle delivery planning and proposes its effective heuristics based on dynamic programming techniques. Each delivery item has a designated delivery date with a certain relaxation window. The minimum delivery cost can be decreased compared to the rigorous delivery date problem. Namely, the relaxing due constraints enable to reduce delivery costs by increasing the load efficiency. The problem is formulated as a dynamic programming model. I approximate the value function of this model using linear programming relaxation in order to reduce a computation time. Through some computational experiments the potential of the proposed algorithm is examined especially for the problem in the dynamic situation.