Optimal fleet composition and mix periodic location-routing problem with time windows in an offshore oil and gas industry: A case study of National Iranian Oil Company

Document Type : Article


1 Department of Industrial Engineering, Science and Research Branch, Islamic Azad University, Tehran, Iran

2 School of Industrial Engineering, Iran University of Science and Technology, Tehran, Iran

3 School of Industrial Engineering, College of Engineering, University of Tehran, Tehran, Iran


This paper presents a new Mixed-Integer Non-Linear Programming (MINLP) model for a Supply Vessel Planning (SVP) problem. The traditional SVP, which is a maritime transportation problem, is developed to a Maritime Fleet Sizing Mix Periodic Location-Routing Problem with Time Windows (MFSMPLRPTW) by considering suppliers, location of onshore-base(s) and some real life aspects. The objective of this model is to decide the composition of fleets, optimal voyages, schedules and also the optimal location(s) for onshore-base(s) in such a way that the total cost is minimized and the needs of operation regions are fulfilled. The MFSMPLPRTW model is solved by an exact two-phase solution approach for both small and medium cases. Also, two   meta-heuristic algorithms are used to solve the large-sized instances. In order to justify and show how the model and solution can lead to significant economic improvements for real life instances, a case study by the IOOC is considered, which is the only offshore oil and gas producer in Iran that has lots of installations and operation regions in the Persian Gulf and the Sea of Oman.


Main Subjects

1. Cuesta, E.F., Andersson, H., Fagerholt, K., and Laporte, G. "Vessel routing with pickups and deliveries: an application to the supply of offshore oil platforms", Computer and Operations Research, 79, pp. 140-147 (2017).
2. Halvorsen-Weare, E.E., Fagerholt, K., Nonas, L.M., and Asbjrnslett, B.E. "Optimal  fleet composition and periodic routing of offshore supply vessels", European Journal of Operational Research, 223(2), pp. 508-517 (2012).
3. Pantuso, G., Fagerholt, K., and Hvattum, L.M. "A survey on maritime  fleet size and mix problems", European Journal of Operational Research, 235(2), pp. 341-349 (2014).
4. Christiansen, M., Fageholt, K., Nygreen, B., and Ronen, D. "Maritme transportation", Transportation, 14, pp. 189-284 (2006).
5. Everett, J.I., Hax, A.C., Lewinson, V.A., and Nudds, D. "Optimization of a  fleet of large tankers and bulkers: a linear programming approach", Marine Technology, 9(4), pp. 430-438 (1972).
6. Murotsu, Y. and Taguchi, K. "optimization of ship fleet-size", Bulletin of University of Osaka Prefecture, Series A: Engineering and Natural Science, 23, pp. 171-192 (1975).
7. Larson, R.C. "Transporting sludge to the 106-mile site: an inventory/routing model for fleet sizing and logistics system design", Transportation Science, 22, pp. 186- 198 (1988).
8. Pesenti, R., "Hierarchical resource planning for shipping companies", European Journal of Operational Research, 86(1), pp. 91-102 (1995). 
9. Sigurd, M.M., Ulstein, N.L., Nygreen, B., and Ryan, D.M., "Ship scheduling with recurring visits and visit separation requirements", In Column Generation, Springer, pp. 225-245 (2005).
10. Zeng, Q. and Yang, Z. "Model integrating fleet design and ship routing problems for coal shipping", Lecture Notes in Computer Science, 4489, pp. 1000-1003 (2007).
11. Gogna, A. and Tayal, A. "Meta-heuristics: review and application", Journal of Experimental & Theoretical Artificial Intelligence, 25(4), pp. 503-526 (2013).
12. Fagerholt, K., Christiansen, M., Hvattum, L.M., Johnsen, T.A.V., and Vab, T.J. "A decision support methodology for strategic planning in maritime transportation", Omega, 38(6), pp. 465-474 (2010).
13. Dantzig, G. and Ramser, J. "The truck dispatching problem", Management Science, 6(1), pp. 80-91 (1959).
14. Kocu, C., Bektasu, T., Jabali, O., and Laporte, G. "The  fleet size and mix location-routing problem with time windows: formulations and a heuristic algorithm", European Journal of Operation Research, 248 (1), pp. 33-51 (2016).
15. Fagerholt, K. and Lindstad, H. "Optimal policies for maintaining a supply service in the Norwegian Sea", Omega, 28(3), pp. 269-275 (2000).
16. Aas, B., Gribkovskaia, I., Halskau, ., and Shlopak, A. "Routing of supply vessels to petroleum installations", International Journal of Physical Distribution & Logistics Management, 37(2), pp. 164-179 (2007).
17. Gribkovskaia, I., Laporte, G., and Shlopak, A. "A tabu search heuristic for a routing problem arising in servicing of offshore oil and gas platforms", Journal of the Operational Research Society, 59(11), pp. 1449- 1459 (2007).
18. Iachan, R. "A Brazilian experience: 40 years using operations research at Petrobras", International Transactions in Operational Research, 16(5), pp. 585- 593 (2009).
19. Aas, B., Halskau Sr, ., and Wallace, S.W. "The role of supply vessels in offshore logistics", Maritime Economics and Logistics, 11(3), pp. 302-325 (2009).
20. Shyshou, A., Gribkovskaia, I., and Barcelo, J. "A simulation study of the  fleet sizing problem arising in offshore anchor handling operations", European Journal of Operational Research, 203(1), pp. 230-240 (2010).
21. Halvorsen-Weare, E.E. and Fagerholt, K. "Robust supply vessel planning", Network Optimization, 6701, pp. 559- 573 (2011).
22. Shyshou, A., Gribkovskaia, I., Laporte, G., and Fagerholt, K. "A large neighbourhood search heuristic for a periodic supply vessel planning problem arising in offshore oil and gas operations", Information Systems and Operational Research, 50(4), pp. 195-204 (2012).
23. Norlund, E.K., Gribkovskaia, I., and Laporte, G. "Supply vessel planning under cost, environment and robustness considerations", Omega, 57(B), pp. 271-281 (2015).
24. Christiansen, M., Fagerholt, K., Rachaniotis, N., and Stalhane, M. "Operational planning of routes and schedules for a  fleet of fuel supply vessels", Transportation Research Part E: Logistics and Transportation Review, 105, pp. 163-175 (2017).
25. Prodhon, C. and Prins, C. "A survey of recent research on location-routing problems", European Journal of Operational Research, 238(1), pp. 1-17 (2014).
26. Nagy, G. and Salhi, S. "Location-routing: Issues, models and methods", European Journal of Operational Research, 177(2), pp. 649-672 (2007).
27. Prins, C., Prodhon, C., andWol er-Calvo, R. "Solving the capacitated location routing problem by a GRASP complemented by a learning process and a path relinking", 4OR: A Quarterly Journal of Operations Research, 4(3), pp. 221-238 (2006).
28. Derbel, H., Jarboui, B., Hanafi, S., and Chabchoub, H. "Genetic algorithm with iterated local search for solving a location-routing problem", Expert Systems with Applications, 39(3), pp. 2865-2871 (2012).
29. Yu, V.F., Lin, S.W., Lee, W., and Ting, C.J. "A simulated annealing heuristic for the capacitated location routing problem", Computers and Industrial Engineering, 58(2), pp. 288-299 (2010).
30. Hemmelmayr, V.C., Cordeau, J.-F., and Crainic, T.G. "An adaptive large neighborhood search heuristic for two-echelon vehicle routing problems arising in city logistics", Computers and Operations Research, 39(12), pp. 3215-3228 (2012).
31. Jarboui, B., Derbel, H., Hanafi, S., and Mladenovic, N. "Variable neighborhood search for location routing", Computers and Operations Research, 40(1), pp. 47-57 (2013).
32. Laporte, G. and Nobert, Y. "An exact algorithm for minimizing routing and operating costs in depot location", European Journal of Operational Research, 6(2), pp. 224-226 (1981).
33. Albareda-Sambola, M., Diaz, J.A., and Fernandez, E. "A compact model and tight bounds for a combined location-routing problem", Computers and Operations Research, 32(3), pp. 407-428 (2005).
34. Belenguer, J.M., Benavent, E., Prins, C., Prodhon, C., and Wol er-Calvo, R. "A branch-and-cut method for the capacitated location-routing problem", Computers and Operations Research, 38(6), pp. 931-941 (2011).
35. Kennedy, J. and Eberhart, R. "Particle swarm optimization", Proceedings of the 1995 IEEE International Conference on Neural Networks, pp. 1942-1948 (1995).
36. Mirjalili, S., Lewis, A. "The whale optimazation algorithm", Advances in Engineering Software, 95, pp. 51-67 (2016).
37. Marinakis, Y. and Marinaki, M. "A particle swarm optimization algorithm with path relinking for the location routing problem", Journal of Mathematical Modeling and Algorithms, 7(1), pp. 59-78 (2008).
38. Belmecheri, F., Prins, C. Yalaoui, F., and Amodeo, L. "A particle swarm optimization algorithm for a vehicle routing problem with heterogeneous  fleet, mixed backhauls, and time windows", Journal of Intelligent Manufacturing, 24(4), pp. 775-789 (2013).
39. Onwunalu, J.E. and Durlofsky, L.J. "Application of a particle swarm optimization algorithm for determining optimum well location and type", Computational Geosciences, 14(1), pp. 183-198 (2010).
40. Kaveh, A. and Ghazaan, M.I "Enhanced whale optimization algorithm for sizing optimization of skeletal structures", Mechanics Based Design of Structures and Machines, 45(3), pp. 345-362 (2016).
41. Mafarja, M.M. and Mirjalili, S. "Hybrid whale optimization algorithm with simulated annealing for feature selection", Neurocomputing, 260, pp. 302-312 (2017).
42. Prakash, D.B. and Lakshminarayana, C. "Optimal siting of capacitors in radial distribution network using whale optimization algorithm", Alexandria Engineering Journal, 56(4), pp. 499-509 (2017).
43. Reddy, P.D.P., Reddy, V.C.V., and Manohar, T.G. "Whale optimization algorithm for optimal sizing of renewable resources for loss reduction in distribution systems", Renewables: Wind, Water and Solar, 4(1), 3 (2017).
44. Abd El Aziz, M., Ewees, A.A., and Ella Hassanein, A. "Whale optimization algorithm and moth-flame optimization for multilevel thresholding image segmentation", Expert Systems With Applications, 83(C), pp. 242-256 (2017).
45. Fruggiero, F., Lambiase, A., Macchiaroli, R., and Miranda, S. "The role of uncertainty in supply chains under dynamic modeling", International Journal of Industrial Engineering Computations, 8(1), pp. 119- 140 (2017).
46. Rincon-Garcia, N., Waterson, B.J., and Cherrett, T.J. "A hybrid metaheuristic for the time-dependent vehicle routing problem with hard time windows", International Journal of Industrial Engineering Computations, 8(1), pp. 141-160 (2017).