Featured Story December 2017 - February 2018
A Real-Life Fuel Delivery Problem with Safety Considerations

By Dr. Konstantinos N. Androutsopoulos, Assistant Professor, Athens University of Economics and Business.

Fuel delivery problems involve routing and scheduling a heterogeneous fleet of multi-compartment vehicles for replenishing a set of customers (petrol stations). Depending on whether the orders are specified by the customer or the supplier, the fuel delivery problems are modelled as: i) multi-compartment vehicle routing problems (MC-VRPs) [2,3,4,9,10] or ii) multi-compartment inventory routing problems (MC-IRPs) [5,6,7,8], respectively. Both categories of fuel delivery models can be further classified by enforcing or disregarding the following constraints: i) each compartment is not allowed to host more than one order (i.e., no compartment split is allowed), and ii) each order is serviced by a single vehicle through a single visit (i.e., i.e., order split is not allowed). Recently, Androutsopoulos and Kamaras (2017)[11] have addressed a fuel distribution problem in which safety considerations in the sequence of unloading orders are taken into account.

It is assumed that a fuel distribution company offers a variety of products (fuel). Each customer places multiple orders, each one involving a single (different) product. The company serves the customers' orders through a heterogeneous fleet of multi-compartment vehicles. The emerging problem aims to assign customers' orders to vehicle compartments and determine routes for serving all customers under the following criteria: i) minimum number of vehicles used and ii) minimum total travelled distance. A significant feature of the proposed problem relates to the rules that dominate the assignment of customers' orders to vehicle compartments:
  • Each compartment can be allocated up to one order.
  • The orders of a customer must be assigned to the compartments of a single vehicle.
  • If the volume capacity of a compartment exceeds 7,500 lt, then the quantity of an order assigned to it must be either above 80% or below 20% of the compartment's capacity.
  • The load of a vehicle throughout a delivery route must be distributed on the axles of the truck in way that it does not affect the (en-route) stability of the vehicle.

In practice, the last constraint is implemented by applying the following loading/un-loading rule (that prevails in the Greek fuel distribution industry): sorting the compartments of a vehicle to three groups depending on their physical ranking, i.e. front, middle, tail, and then unload them in the following order: middle, tail, front. It is evident that this unloading constraint affects severely the routing decision.

A GRASP heuristic algorithm was developed for solving the proposed fuel delivery problem. The performance of the proposed algorithm in terms of computational time was assessed on set of real life test problems. The average computational time (per iteration) for solving test problems of 50,100 and 150 customers was 1.26, 7.26 and 16.61 seconds, respectively. All computational tests were performed on an Intel Core 3.60 GHz computer with 64-bit Windows operating system and 16GB RAM. In addition, preliminary tests were performed on large-sized real life problems (involving 300-600 customers) of a Greek fuel distribution company. The emerging solutions were compared with the ones determined by the existing route planning system of the company. The comparative assessment was based on the following performance measures: i) the travelled distance of the vehicles and ii) the total number of used vehicles. In summary, the preliminary tests indicate that the travelled distance of the solutions determined by the proposed solution approach was 41 % lower than those determined by the existing system. Moreover, the number of vehicles used were reduced by 26%.


. El Fallahi, C. Prins, R. Woler Calvo, "A memetic algorithm and a tabu search for the multi-compartment vehicle routing problem", Computers & Operations Research 35, 1725 - 1741 (2008).

J.E. Mendoza, B. Castanier, C.  Gu?ret, A.L. Medaglia, N.  Velasco,  "A memetic algorithm for the multi-compartment vehicle routing problem with stochastic demands", Computers and Operations Research 37 (11), pp. 1886-1898 (2010).

U. Derigs, J. Gottlieb, J. Kalkoff, M. Piesche, F. Rothlauf, U. Vogel, "Vehicle Routing with compartments: applications, modeling and heuristics." OR Spectrum (33) 885-914 (2011).

P. Avella , M. Boccia, A. Sforza, "Solving a fuel delivery problem by heuristic and exact approaches", European Journal of Operational Research 152, 170 - 179 (2004).

F. Cornillier, F.F. Boctor, G. Laporte, J. Renaud , "A heuristic for the multi-period petrol station replenishment problem" ,European Journal of Operational Research 191, 295-305 (2008)

F. Cornillier, F.F. Boctor, G. Laporte, J. Renaud , "An exact algorithm for the Petrol Station Replenishment Problem" ,The Journal of the Operational Research Society Vol.59 No.5, 607-615 (2008).

F. Cornillier, G. Laporte, F.F. Boctor, J.  Renaud, "The petrol station replenishment problem with time windows", Computers & Operations Research, 36 919-935(2009). 

L.C. Coelho, G. Laporte, "Classification, models and exact algorithms for multi-compartment delivery problems" ,European Journal of Operational Research 242, 854-864 (2015)

G. G. Brown, W.G. Glenn, "Real Time Dispatch Of Petroleum Tank Trucks", Management Science Vol.27 No.1 (1981).

G. G. Brown , J.E. Carol, W.G. Glenn, D. Ronnen, "Real-Time Wide Area Dispatch of Mobil Tank Trucks", Interfaces Vo.17 No.1, 107-120 (1987).

K.N., Androutsopoulos, N.K., Kamaras. Modelling And Solving A Real-Life Fuel Distribution Problem. 6th International Symposium and 28th National Conference on Operational Research, June 08-10 (2017), Thessaloniki, Greece.

M A N A G E M E N T    S C I E N C E    L A B O R A T O R Y   








Copyright 2013 Website Management Science Laboratory. All rights reserved.