Multi-mode transportation planning of crude oil via Greedy Randomized Adaptive Search and Path Relinking

Abstract

The transportation of crude oil from production fields to refineries is a very important operation in the oil industry. In this paper, an inventory routing problem for crude oil transportation is studied, where the crude oil is transported from a central depot to a set of customers with dynamic demand using multiple transportation modes. Oil can be transported through marine routes, pipelines or a combination of the two modes. The marine transportation of crude oil is performed by a heterogeneous fleet of tankers with limited capacity owned by an oil distributor itself and/or the tankers of different types rented from a third party. Each transportation operation has a lead time and the storage capacity of oil at each customer is limited. The problem is to determine over a given planning horizon an optimal oil transportation plan that minimizes the total transportation and inventory costs subject to various constraints. The plan defines the number of tankers of each type to rent and the number of tankers of each type to dispatch on each route in each period. A mixed-integer programming model is established for the problem. Because of the high complexity and large size of the problem, the model is too complicated to be solved exactly. A metaheuristic method, the Greedy Randomized Adaptive Search Procedure (GRASP) enhanced by an intensification strategy based on Path Relinking is developed to find its near-optimal solutions. Numerical test results of the method demonstrate the effectiveness of the method.

Keywords

crude oil transportation inventory routing metaheuristics modeling planning.

Get full access to this article

View all access options for this article.

References

Bard, J.

Huang, L.

Jaillet, P.

and

Dror, M.

1998: A decomposition approach to the inventory routing problem with satellite facilities. Transportation Science 32, 189-203.

Bell, W.

Dalberto, L.

Fisher, M.

Greenfield, A.

Jaikumar, R.

Kedia, P.

Mack, R.

and

Prutzman, P.

1983: Improving the distribution of industrial gases with an on-line computerized routing and scheduling optimizer. Interfaces 13, 4-23.

Brown, G.G.

Graves, G.W.

and

Ronen, D.

1987: Scheduling ocean transportation of crude oil. Management Science 33, 335-46.

Campbell, A.M.

and

Savelsbergh, M.W.P.

2004: A decomposition approach for the inventory-routing problem . Transportation Science 38, 488-502.

Campbell, A.M.

Clarke, L.W.

Kleywegt, A.J.

and

Savelsbergh, M.W.P.

1998: The inventory routing problem. In Fleet Management and Logistics. Kluwer Academic Publishers, 95-113.

Cheng, L.

and

Duran, M.A.

2004: Logistics for world-wide crude oil transportation using discrete event simulation and optimal control. Computers and Chemical Engineering 28, 897-911.

Chien, T.

Balakrishnan, A.

and

Wong, R.

1989: An integrated inventory allocation and vehicle routing problem. Transportation Science 23, 67-76.

Chu, F.

Chu, C.

Shen, Q.

and

Chen, H.

2008: An O(T3) polynomial algorithm for crude oil transportation . The 4th IEEE Conference on Automation Science and Engineering, Washington DC, August 23-26, 2008 (IEEE CASE 2008), Proceedings.

Federgruen, A.

and

Zipkin, P.

1984: A combined vehicle routing and inventory allocation problem . Operations Research 32, 1019-36.

10.

Festa, P.

and

Resende, M.G.C.

2002: GRASP: an annotated bibliography. Essays and surveys in metaheuristics. Kluwer Academic, 325-1367.

11.

Fisher, M.

Greenfield, A.

Jaikumar, R.

and

Kedia, P.

1982: Real-time scheduling of a bulk delivery fleet: practical application of Lagrangean relaxation. Technical report, The Wharton School, University of Pennsylvania.

12.

Glover, F.

1998: A template for scatter search and path relinking. Lecture Notes in Computer Science. Springer-Verlag, 10-13.

13.

Glover, F.

and

Laguna, M.

1997: Tabu search. Kluwer Academic.

14.

Iakovou, E.T.

2001: An interactive multiobjective model for the strategic maritime transportation of petroleum products: risk analysis and routing. Safety Science 39, 19-29.

15.

Laguna, M.

and

Mart, R.

1999: GRASP and path relinking for 2-layer straight line crossing minimization. Journal on Computing 11, 44-52.

16.

Larson, R.

1988: Transporting sludge to the 106 mile site: an inventory/routing model for fleet sizing and logistics system design. Transportation Science 22, 186-98.

17.

Pardalos, P.M.

and

Resende, M.G.C.

2002: Handbook of applied optimization. Oxford University Press, 126.

18.

Resende, M.G.C.

and

Ribeiro, C.C.

2003: Greedy randomized adaptive search procedures. Handbook of metaheuristics. Kluwer, 219-49.

19.

Sherali, H.D.

Al-Yakoob, S.M.

and

Hassan, M.M.

1999: Fleet management models and algorithms for an oil-tanker routing and scheduling problem. IIE Transactions 31, 395-406.

20.

Webb, R.

and

Larson, R.

1995: Period and phase of customer replenishment: a new approach to the strategic inventory/routing problem. European Journal of Operations Research 85, 132-48.

21.

Wu, N.

Zhou, M.C.

and

Chu, F.

2008a: A Petri net based heuristic algorithm for realizability of target refining schedules in oil refinery. IEEE Transactions on Automation Science and Engineering 5, 661-76.

22.

Wu, N.

Chu, F.

Chu, C.

and

Zhou, M.

2008b: Short-term schedulability analysis of crude oil operations in refinery with residency time constraint using Petri nets. IEEE Transactions on Systems, Man, and Cybernetics, Part C 38, 765-78.

23.

Wu, N.

Chu, F.

Chu, C.

and

Zhou, M.

2009: Short-term schedulability analysis of multiple distiller crude oil operations in refinery with oil residency time constraint. IEEE Transactions on Systems, Man and Cybernetics, Part C 39, 1-16.

24.

Yu, Y.

Chen, H.

and

Chu, F.

2008: A new model and hybrid approach for large scale inventory routing problems. European Journal of Operations Research 189, 1022-40.

25.

Yu, Y.

Chu, F.

and

Chen, H.

2007: A note on coordination of production and distribution planning. European Journal of Operations Research 177, 626-29.