DocumentCode :
1323074
Title :
A Polynomial Dynamic Programming Algorithm for Crude Oil Transportation Planning
Author :
Chu, Chengbin ; Chu, Feng ; Zhou, MengChu ; Chen, Haoxun ; Shen, Qingning
Author_Institution :
Sch. of Econ. & Manage., Tongji Univ., Shanghai, China
Volume :
9
Issue :
1
fYear :
2012
Firstpage :
42
Lastpage :
55
Abstract :
Crude oil transportation is a central logistics operation in petrochemical industry because its cost represents a significant part in the cost of petrochemical products. In this paper, we consider the transportation by tankers or trucks. We show that under some realistic assumptions, this problem can be transformed into a single item lot sizing problem with limited production and inventory capacities. We develop a strongly polynomial dynamic programming algorithm to solve it. The problem of crude oil transportation is very difficult. There are few efficient methods in this domain. In the model considered in this paper, crude oil is directly shipped from a supplier port to n client ports to satisfy customer demands over T future periods. The supplier port disposes a fleet of identical tankers with limited capacity. The inventory capacities of customers are limited and time-varying. The backlogging is admitted. The objective is to find an optimal shipment plan minimizing the total cost over the T-period horizon. When the number of tankers is unlimited and customer demands are independent, shipment plans of different customers become independent. This problem can be considered as n independent problems. Each of them can be transformed into a single item lot sizing problem with limited production and inventory capacities, where tanker capacity corresponds to production capacity in classical lot sizing models. The main contributions of this paper are: 1) transformation of a transportation planning problem into a lot-sizing problem; 2) an O(T3) algorithm is proposed to solve it; and 3) the results can also be applied to terrestrial transportation with direct deliveries.
Keywords :
capacity planning (manufacturing); cost reduction; crude oil; customer satisfaction; dynamic programming; inventory management; lot sizing; minimisation; petrochemicals; polynomials; road vehicles; transportation; T-period horizon; backlogging; central logistic operation; client ports; cost minimization; crude oil transportation planning; customer demand satisfaction; inventory capacity; optimal shipment plan; petrochemical industry; petrochemical products; polynomial dynamic programming algorithm; production capacity; single item lot sizing problem; supplier port; tanker capacity; terrestrial transportation; trucks; Cost function; Dynamic programming; Lot sizing; Mathematical model; Polynomials; Transportation; Complex system; crude oil transportation; dynamic programming; lot-sizing; scheduling;
fLanguage :
English
Journal_Title :
Automation Science and Engineering, IEEE Transactions on
Publisher :
ieee
ISSN :
1545-5955
Type :
jour
DOI :
10.1109/TASE.2011.2164524
Filename :
6021348
Link To Document :
بازگشت