We consider a logistic planning problem for simultaneous optimization of the storage and the delivery. This problem arises in the consolidate shipment using an intermediate storage in a supply chain, which is typically found in the automobile industry. The vehicles deliver the items from the origin to the destination, while the items can be stored at some warehousing facilities as the intermediate storage during the delivery. The delivery plan is made for each day separately, but the storage at a warehouse may last for more than one day. Therefore, the entire logistic plan should be considered over a certain period for the total optimization. We formulate the storage and delivery problem as a mixed integer programming. Then, we propose a relax-and-fix type heuristic method, which incrementally fixes decision variables until all the variables are fixed to obtain a complete solution. Moreover, a semiapproximate model is introduced to effectively fix the variables. Based on the formulation, the delivery plan can be solved for each day separately. This has the advantage especially in the dynamic situation, where the delivery request is modified from the original request before the actual delivery day. Numerical experiments show that the simultaneous optimization gives the effective storage plan to reduce the total logistic cost, and the proposed heuristics efficiently reduce the computational time and are robust against the dynamic situation.