×

A mixed-integer linear programming model for optimal vessel scheduling in offshore oil and gas operations. (English) Zbl 1373.90020

Summary: This paper introduces a non-standard vehicle routing problem (VRP) arising in the oil and gas industry. The problem involves multiple offshore production facilities, each of which requires regular servicing by support vessels to replenish essential commodities such as food, water, fuel, and chemicals. The support vessels are also required to assist with oil off-takes, in which oil stored at a production facility is transported via hose to a waiting tanker. The problem is to schedule a series of round trips for the support vessels so that all servicing and off-take requirements are fulfilled, and total cost is minimized. Other constraints that must be considered include vessel suitability constraints (not every vessel is suitable for every facility), depot opening constraints (base servicing can only occur during specified opening periods), and off-take equipment constraints (the equipment needed for off-take support can only be deployed after certain commodities have been offloaded). Because of these additional constraints, the scheduling problem under consideration is far more difficult than the standard VRP. We formulate a mixed-integer linear programming (MILP) model for determining the optimal vessel schedule. We then verify the model theoretically and show how to compute the vessel utilization ratios for any feasible schedule. Finally, simulation results are reported for a real case study commissioned by Woodside Energy Ltd, Australia’s largest dedicated oil and gas company.

MSC:

90B06 Transportation, logistics and supply chain management
90B10 Deterministic network models in operations research
90C11 Mixed integer programming
90C27 Combinatorial optimization

Software:

VRP; CPLEX; Gurobi; AIMMS
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] AIMMS Modelling Platform, AIMMS B. V.,, Haarlem (2016)
[2] F. Alonso, A tabu search algorithm for the periodic vehicle routing problem with multiple vehicle trips and accessibility restrictions,, Journal of the Operational Research Society, 59, 963 (2008) · Zbl 1144.90312
[3] N. Azi, An exact algorithm for a single-vehicle routing problem with time windows and multiple routes,, European Journal of Operational Research, 178, 755 (2007) · Zbl 1159.90306 · doi:10.1016/j.ejor.2006.02.019
[4] N. Azi, An exact algorithm for a vehicle routing problem with time windows and multiple use of vehicles,, European Journal of Operational Research, 202, 756 (2010) · Zbl 1176.90047
[5] M. Battarra, An adaptive guidance approach for the heuristic solution of a minimum multiple trip vehicle routing problem,, Computers and Operations Research, 36, 3041 (2009) · Zbl 1162.90538
[6] J. Bisschop, <em>AIMMS Optimization Modelling,</em>, Haarlem: AIMMS B.V. (2016)
[7] J. C. S. Brandão, The multi-trip vehicle routing problem,, Journal of the Operational Research Society, 49, 799 (1998) · Zbl 1140.90329
[8] D. Feillet, An exact algorithm for the elementary shortest path problem with resource constraints: Application to some vehicle routing problems,, Networks, 44, 216 (2004) · Zbl 1056.90014 · doi:10.1002/net.20033
[9] B. Fleischmann, The vehicle routing problem with multiple use of vehicles (technical report),, Hamburg: Universität Hamburg (1990)
[10] Gurobi, <em>Optimizer Reference Manual,</em>, Houston: Gurobi Optimization Inc. (2016)
[11] F. Hernandez, A new exact algorithm to solve the multi-trip vehicle routing problem with time windows and limited duration,, 4OR, 12, 235 (2014) · Zbl 1307.90022 · doi:10.1007/s10288-013-0238-z
[12] IBM ILOG CPLEX Optimizer, IBM Corporation,, New York (2016)
[13] IBM ILOG CPLEX Optimization Studio CPLEX User’s Manual, New York,, IBM Corporation (2014)
[14] R. Macedo, Solving the vehicle routing problem with time windows and multiple routes exactly using a pseudo-polynomial model,, European Journal of Operational Research, 214, 536 (2011) · Zbl 1219.90022 · doi:10.1016/j.ejor.2011.04.037
[15] A. Olivera, Adaptive memory programming for the vehicle routing problem with multiple trips,, Computers and Operations Research, 34, 28 (2007) · Zbl 1110.90014 · doi:10.1016/j.cor.2005.02.044
[16] R. J. Petch, A multi-phase constructive heuristic for the vehicle routing problem with multiple trips,, Discrete Applied Mathematics, 133, 69 (2003) · Zbl 1053.90026 · doi:10.1016/S0166-218X(03)00434-7
[17] E. D. Taillard, Vehicle routeing with multiple use of vehicles,, Journal of the Operational Research Society, 47, 1065 (1996) · Zbl 0864.90045
[18] P. Toth, <em>The Vehicle Routing Problem</em>,, Philadelphia: SIAM (2002) · Zbl 0979.00026 · doi:10.1137/1.9780898718515
[19] S. Salhi, A GA based heuristic for the vehicle routing problem with multiple trips,, Journal of Mathematical Modelling and Algorithms, 6, 591 (2007) · Zbl 1140.90333 · doi:10.1007/s10852-007-9069-2
[20] A. Şen, A survey on multi trip vehicle routing problem,, In: Proceedings of the International Logistics and Supply Chain Congress 2008 (2008)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.