A petrol station replenishment problem: new variant and formulation
Tóm tắt
One of the most important problems in the petroleum industry is the well-known petrol station replenishment problem with time windows, which calls for the determination of optimal routes by using a fleet of tank trucks to serve a set of petrol stations over a given planning horizon. In this paper, we introduce a model and solve a specific problem that originates from a real-life application arising in the fuel distribution where specific attention is paid to tank trucks with compartments and customers with different types of products and time windows. Literally, we call the resulting problem the multi-compartment vehicle routing problem with time windows (MCVRPTW). To solve the MCVRPTW, we begin by describing the problem, providing its mathematical formulation and discussing the sense of its constraints. As the problem is NP-hard, we propose an efficient tabu search algorithm for its solution. We introduce the Kolmogorov–Smirnov statistic into the framework of the tabu search to manage the neighbourhood size. We evaluate the performance of the algorithm on a set of vehicle routing problems with time windows instances as well as other realistic instances. Our results are compared to CPLEX, to the heuristics reported in the literature and also to those extracted from the company plans.
Tài liệu tham khảo
Avella P, Boccia M, Sforza A (2004) Solving a fuel delivery problem by heuristic and exact approaches. Eur J Oper Res 152(1):170–179. doi:10.1016/S0377-2217(02)00676-8
Bausch DO, Brown G, Ronen D (1995) Consolidating and dispatching truck shipments of Mobil heavy petroleum products. Interfaces 25:117. doi:10.1287/inte.25.2.1
Ben Abdelaziz F, Roucairol C, Bacha C (2002) Deliveries of liquid fuels to SNDP gas stations using vehicles with multiple compartments. In: International conference on systems man and cybernetics 2002 IEEE, Hammamet, Tunisia. doi:10.1109/ICSMC.2002.1168021
Berger J, Barkaoui M (2004) A parallel hybrid genetic algorithm for the vehicle routing problem with time windows. Comput Oper Res 31(12):2037–2053. doi:10.1016/S0305-0548(03)00163-1
Braysy O, Gendreau M (2002) Tabu search heuristics for the vehicle routing problem with time windows. TOP 10(2):211–237. doi:10.1007/BF02579017
Brown GG, Graves WG (1981) Real-time dispatch of petroleum tank trucks. Manag Sci 27(1):19–31. doi:10.1287/mnsc.27.1.19
Brown GG, Ellis CJ, Graves WG, Ronen D (1987) Real-time, wide area dispatch of mobil tank trucks. Interfaces 17(1):107–120. doi:10.1287/inte.17.1.107
Bullnheimer B, Hartl RF, Strauss C (1999) An improved ant system algorithm for the vehicle routing problem. Ann Oper Res 89:319–328
Chiang WC, Russell RA (1997) A reactive tabu search metaheuristics for the vehicle routing problem with time windows. INFORMS J Comput 9(4):417–430. doi:10.1287/ijoc.9.4.417
Cordeau JF, Laporte G, Mercier A (2001) A unified tabu search heuristic for vehicle routing problems with time windows. J Oper Res Soc 52(8):928–936. doi:10.1057/palgrave.jors.2601163
Cornillier F, Boctor FF, Laporte G, Renaud J (2008a) An exact algorithm for the petrol station replenishment problem. J Oper Res Soc 59(5):607–615. doi:10.1057/palgrave.jors.2602374
Cornillier F, Boctor FF, Laporte G, Renaud J (2008b) A heuristic for the multi-period petrol station replenishment problem. Eur J Oper Res 191(2):295–305. doi:10.1016/j.ejor.2007.08.016
Cornillier F, Boctor FF, Laporte G, Renaud J (2009) The petrol station replenishment problem with time windows. Comput Oper Res 36(3):919–935. doi:10.1016/j.cor.2007.11.007
Cornillier F, Boctor FF, Renaud J (2012) Heuristics for the multi-depot petrol station replenishment problem with time windows. Eur J Oper Res 220:361–369. doi:10.1016/j.ejor.2012.02.007
Day JM, Wright PD, Schoenherr T, Venkataramanan M, Gaudette K (2009) Improving routing and scheduling decisions at a distributor of industrial gasses. Omega 37(1):227–237. doi:10.1016/j.omega.2006.11.007
El Fallahi A, Prins C, Wolfler Calvo R (2008) A memetic algorithm and a tabu search for the multi-compartment vehicle routing problem. Comput Oper Res 35(5):1725–1741. doi:10.1016/j.cor.2006.10.006
Franz LS, Woodmanse J (1990) Computer-aided truck dispatching under conditions of product price variance with limited supply. J Bus Logist 11(1):127–139
Gambardella LM, Taillard E, Agazzi G (1999) MACS-VRPTW: a multiple ant colony system for vehicle routing problems with time windows. In: New ideas in optimization, pp 63-76
Glover F, Laguna M (1997) Tabu search. Kluwer, Boston
Lau HC, Sim M, Teo KM (2003) Vehicle routing problem with time windows and a limited number of vehicles. Eur J Oper Res 148(3):559–569. doi:10.1016/S0377-2217(02)00363-6
Malépart V, Boctor FF, Renaud J, Labilois S (2003) Nouvelles approches pour l’approvisionnement des stations d’essence. Revue Franaise de Gestion Industrielle 22:15–31
Nagata Y, Braysy O, Dullaert W (2010) A penalty-based edge assembly memetic algorithm for the vehicle routing problem with time windows. Comput Oper Res 37(4):724–737. doi:10.1016/j.cor.2009.06.022
Ng WL, Leung S, Lam J, Pan S (2008) Petrol delivery tanker assignment and routing: a case study in Hong Kong. J Oper Res Soc 59:1191–1200. doi:10.1057/palgrave.jors.2602464
Nussbaum M, Sepulveda M (1997) A fuel distribution knowledge-based decision support system. Omega 25(2):225–234. doi:10.1016/S0305-0483(96)00059-X
Popović D, Vidović M, Radivojević G (2012) Variable neighbourhood search heuristic for the inventory routing problem in fuel delivery. Expert Syst Appl 39(18):13390–13398. doi:10.1016/j.eswa.2012.05.064
Renaud J, Bolduc MC, Laporte G, Boctor F (2010) A tabu search heuristic for the split delivery vehicle routing problem with production and demand calendars. Eur J Oper Res 202:122–130
Ronen D (1995) Dispatching petroleum products. Oper Res 43(3):379–387. doi:10.1287/opre.43.3.379
Solomon M (1987) Algorithms for the vehicle routing and scheduling problems with time window constraints. Oper Res 35(2):254–265. doi:10.1287/opre.35.2.254
Taillard E, Badeau P, Gendreau M, Geurtin F, Potvin JY (1997) A tabu search heuristic for the vehicle routing problem with time windows. Transp Sci 31(2):170–186. doi:10.1287/trsc.31.2.170
Tan KC, Lee LH, Ou K (2001a) Artificial intelligence heuristics in solving vehicle routing problems with time window constraints. Eng Appl Artif Intell 14(6):825–837. doi:10.1016/S0952-1976(02)00011-8
Tan KC, Lee LH, Ou K (2001) A messy genetic algorithm for the vehicle routing problem with time window constraints. In: IEEE congress on evolutionary computation, vol. 1, pp 679–686. doi:10.1109/CEC.2001.934457
Tan KC, Chew YH, Lee LH (2006) A hybrid multiobjective evolutionary algorithm for solving vehicle routing problem with time windows. Comput Optim Appl 34(1):115–151. doi:10.1007/s10589-005-3070-3
Taqa allah D, Renaud J, Boctor FF (2000) Le problme d’approvisionnement des stations d’essence. J Eur des Syst Autom 34:11–33
Toth P, Vigo D (2014) Vehicle routing: problems, methods, and application, 2nd edn. Society for Industrial and Applied Mathematics, Philadelphia
Toth P, Vigo D (2003) The granular tabu search and its application to the vehicle routing problem. INFORMS J Comput 15(4):333–348. doi:10.1287/ijoc.15.4.333.24890
Van der Bruggen L, Gruson R, Salomon M (1995) Reconsidering the distribution of gasoline products for a large oil company. Eur J Oper Res 81(3):460–473. doi:10.1016/0377-2217(94)00189-J
Vidal T, Crainic TG, Gendreau M, Prins C (2013) A hybrid genetic algorithm with adaptive diversity management for a large class of vehicle routing problems with time windows. Comput Oper Res 40(1):475–489. doi:10.1016/j.cor.2012.07.018
Vidović M, Popović D, Ratković B (2014) Mixed integer and heuristics model for the inventory routing problem in fuel delivery. Int J Prod Econ 147:593–604. doi:10.1016/j.ijpe.2013.04.034