The Fuel Replenishment Problem:A Split-Delivery Multi-Compartment Vehicle Routing Problem with Multiple Trips
Abstract: In this paper, we formally define and model the Fuel Replenishment Problem (FRP). The FRP is a multi-compartment, multi-trip, split-delivery VRP in which tanker trucks transport different types of petrol, separated over multiple vehicle compartments, from an oil depot to petrol stations. Large customer demands often necessitate multiple deliveries. Throughout a single working day, a tanker truck returns several times to the oil depot to resupply. A solution to the FRP involves computing a delivery schedule of minimum duration, thereby determining for each vehicle (1) the allocation of oil products to vehicle compartments,(2) the delivery routes, and (3) the delivery patterns. To solve FRP efficiently, an Adaptive Large Neighbor-hood Search (ALNS) heuristic is constructed. The heuristic is evaluated on data from a Chinese petroleum transportation company and compared against exact results from a MILP model and lower bounds from a column generation approach. In addition, we perform sensitivity analysis on different problem features, including the number of vehicles, products, vehicle compartments and their capacities. Computational results show that the ALNS heuristic is capable of solving instances with up to 60 customers and 3 different products in less than 25 minutes with an average optimality gap of around 10%. On smaller instances, the heuristic finds optimal solutions in significantly less time than the exact MILP formulation.
Keywords: Fuel Replenishment, Multi-compartment, Multi-trip, Split-delivery, Vehicle Routing,Adaptive Large Neighbourhood Search
Category 1: Applications -- OR and Management Sciences
Category 2: Applications -- OR and Management Sciences (Transportation )
Citation:  Abdelaziz, F. B., Roucairol, C., Bacha, C., 2002. Deliveries of liquid fuels to sndp gas stations using vehicles with multiple compartments. In: IEEE international conference on systems, man and cybernetics. Vol. 1. IEEE, pp. 478–483.  Archetti, C., Bouchard, M., Desaulniers, G., 2011. Enhanced branch and price and cut for vehicle routing with split deliveries and time windows. Transportation Science 45 (3), 285–298.  Archetti, C., Speranza, M. G., Hertz, A., 2006. A tabu search algorithm for the split delivery vehicle routing problem. Transportation science 40 (1), 64–73.  Avella, P., Boccia, M., Sforza, A., 2004. Solving a fuel delivery problem by heuristic and exact approaches. European Journal of Operational Research 152 (1), 170–179.  Benantar, A., Ouafi, R., Boukachour, J., 2016. A petrol station replenishment problem: new variant and formulation. Logistics Research 9 (1), 6.  Coelho, L. C., Laporte, G., 2015. Classification, models and exact algorithms for multi-compartment delivery problems. European Journal of Operational Research 242 (3), 854–864.  Cornillier, F., Boctor, F., Renaud, J., 2012. Heuristics for the multi-depot petrol station replenishment problem with time windows. European Journal of Operational Research 220 (2), 361–369.  Cornillier, F., Boctor, F. F., Laporte, G., Renaud, J., 2008. An exact algorithm for the petrol station replenishment problem. Journal of the Operational Research Society 59 (5), 607–615.  Cornillier, F., Boctor, F. F., Laporte, G., Renaud, J., 2008. A heuristic for the multi-period petrol station replenishment problem. European Journal of Operational Research 191 (2), 295–305.  Cornillier, F., Laporte, G., Boctor, F. F., Renaud, J., 2009. The petrol station replenishment problem with time windows. Computers & Operations Research 36 (3), 919–935.  Derigs, U., Gottlieb, J., Kalkoff, J., Piesche, M., Rothlauf, F., Vogel, U., 2011. Vehicle routing with compartments: applications, modelling and heuristics. OR spectrum 33 (4), 885–914.  Desaulniers, G., 2010. Branch-and-price-and-cut for the split-delivery vehicle routing problem with time windows. Operations research 58 (1), 179–192.  Dror, M., Trudeau, P., 1989. Savings by split delivery routing. Transportation Science 23 (2), 141– 145.  Dror, M., Trudeau, P., 1990. Split delivery routing. Naval Research Logistics (NRL) 37 (3), 383–402.  El Fallahi, A., Prins, C., Calvo, R. W., 2008. A memetic algorithm and a tabu search for the multicompartment vehicle routing problem. Computers & Operations Research 35 (5), 1725–1741.  Feillet, D., Dejax, P., Gendreau, M., Gueguen, C., 2006. Vehicle routing with time windows and split deliveries. Technical Paper 851.  Henke, T., Speranza, M. G., Wäscher, G., 2015. The multi-compartment vehicle routing problem with flexible compartment sizes. European Journal of Operational Research 246 (3), 730–743.  Hübner, A., Ostermeier, M., 2018. A multi-compartment vehicle routing problem with loading and unloading costs. Transportation Science.  Jin, M., Liu, K., Bowden, R. O., 2007. A two-stage algorithm with valid inequalities for the splitdelivery vehicle routing problem. International Journal of Production Economics 105 (1), 228–242. Lahyani, R., Coelho, L. C., Khemakhem, M., Laporte, G., Semet, F., 2015. A multi-compartmentvehicle routing problem arising in the collection of olive oil in tunisia. Omega 51, 1–10. Lee, C.-G., Epelman, M. A., White III, C. C., Bozer, Y. A., 2006. A shortest path approach to themultiple-vehicle routing problem with split pick-ups. Transportation research part B: Methodological40 (4), 265–284. Lihua, S., 2012. Study on the logistics optimization informationization of oil products in petrochem-ical enterprises. Computers and Applied Chemistry 29 (5), 620–624. Luo, Z., Qin, H., Zhu, W., Lim, A., 2016. Branch and price and cut for the split-delivery vehiclerouting problem with time windows and linear weight-related cost. Transportation Science 51 (2),668–687. Melechovsk`y, J., 2013. A variable neighborhood search for the selective multi-compartment vehiclerouting problem with time windows. Lecture Notes in Management Science 5, 159–166. Mendoza, J. E., Castanier, B., Guéret, C., Medaglia, A. L., Velasco, N., 2010. A memetic algorithmfor the multi-compartment vehicle routing problem with stochastic demands. Computers & Opera-tions Research 37 (11), 1886–1898. Mendoza, J. E., Castanier, B., Guéret, C., Medaglia, A. L., Velasco, N., 2011. Constructive heuristicsfor the multicompartment vehicle routing problem with stochastic demands. Transportation Science45 (3), 346–363. Muyldermans, L., Pang, G., 2010. On the benefits of co-collection: Experiments with a multi-compartment vehicle routing algorithm. European Journal of Operational Research 206 (1), 93–103. Ng, W. L., Leung, S., Lam, J., Pan, S., 2008. Petrol delivery tanker assignment and routing: a casestudy in hong kong. Journal of the Operational Research Society 59 (9), 1191–1200. Oppen, J., Løkketangen, A., 2008. A tabu search approach for the livestock collection problem. Com-puters & Operations Research 35 (10), 3213–3229. Pisinger, D., Ropke, S., 2007. A general heuristic for vehicle routing problems. Computers & opera-tions research 34 (8), 2403–2435. Popovi ́c, D., Vidovi ́c, M., Radivojevi ́c, G., 2012. Variable neighborhood search heuristic for theinventory routing problem in fuel delivery. Expert Systems with Applications 39 (18), 13390–13398.  Ropke, S., Pisinger, D., 2006. An adaptive large neighborhood search heuristic for the pickup anddelivery problem with time windows. Transportation science 40 (4), 455–472. Shaw, P., 1998. Using constraint programming and local search methods to solve vehicle routing prob-lems. In: International conference on principles and practice of constraint programming. Springer, pp.417–431. Sierksma, G., Tijssen, G. A., 1998. Routing helicopters for crew exchanges on off-shore locations.Annals of Operations Research 76, 261–286. Vidovi ́c, M., Popovi ́c, D., Ratkovi ́c, B., 2014. Mixed integer and heuristics model for the inventoryrouting problem in fuel delivery. International Journal of Production Economics 147, 593–604.
Entry Submitted: 05/24/2019
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|