Main Article Content
Abstract
In this paper we introduce the Periodic Petrol Station Replenishment Problem (PPSRP) over a T-day planning horizon and describe four heuristic methods for its solution. Even though all the proposed heuristics belong to the common partitioning-then-routing paradigm, they differ in assigning the stations to each day of the horizon. The resulting daily routing problems are then solved exactly until achieving optimalization. Moreover, an improvement procedure is also developed with the aim of ensuring a better quality solution. Our heuristics are tested and compared in two real-life cases, and our computational results show encouraging improvements with respect to a human planning solution
Keywords
Article Details
References
- Ben Abdelaziz F, Roucairol C, Bacha C (2002), Deliveries of liquid fuels to SNDP gas stations using vehicles with multiple compartments. In: Systems Managment and Cybernetics IEEE International Conference. Hammamet, Tunisia.
- Boctor F, Renaud J, Cornillier F (2011), Trip packing in petrol stations replenishment. Omega 39:86-98.
- Brown GG, Ellis CJ, Graves GW, Ronen D (1987), Real-time wide area dispatch of mobil tank trucks. Interfaces 17:107-120.
- Brown GG, Graves GW (1981), Real-time dispatch of petroleum tank trucks. Management Science 27:19-32.
- Chao IM, Golden BL, Wasil E (1995), An improved heuristic for the period vehicle routing problem. Networks 26:25-44.
- Christofides N, Beasley JE (1984), The period routing problem. Networks 14:237-256.
- Cordeau JF, Gendreau M, Laporte G (1997), A tabu search heuristic for periodic and multi-depot vehicle routing problems. Networks 30:105-119.
- Cornillier F, Boctor F, Laporte G, Renaud J (2008a), An exact algorithm for the petrol station replenishment problem. Journal of the Operational Research Society 59:607-615.
- Cornillier F, Boctor F, Laporte G, Renaud J (2008b), A heuristic for the multi-period petrol station replenishment problem. European Journal of Operational Research 191:295-305.
- Cornillier F, Laporte G, Boctor F, Renaud J (2009), The petrol station replenishment problem with time windows. Computers and Operations Research 36:919-935.
- 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:361-369.
- Gaudioso M, Paletta G (1992), A heuristic for the periodic vehicle routing problem. Transportation Science 26:86-92.
- IBM ILOG Cplex Optimizer. (2011), Available at: 01.ibm.com/software/integration/optimization/cpl ex-optimizer/. Accessed May 2012.
- Lindo Systems Inc. (2006), Optimization Modeling with Lingo. Available at: www.lindo.com. Accessed May 2012.
- Malépart V, Boctor F, Renaud J, Labilois S (2003), Nouvelles approches pour l'approvisionnement des stations d'essence. Revue Française de Gestion Industrielle 22:15-31.
- Ng WL, Leung SH, Lam JP, Pan SW (2008), Petrol delivery tanker assignment and routing: a case study in Hong Kong. Journal of the Operational Research Society 59:1191-1200.
- Paletta G, Triki C (2004), Solving the asymmetric traveling salesman problem with periodic constraints. Networks 44:31-37.
- Rizzoli A, Casagrande N, Donati A, Gambardella L, Lepori D, Montemanni R, Pina P, Zaffalon M (2003), Planning and optimisation of vehicle routes for fuel oil distribution. In: MODSIM International Congress on Modelling and Simulation. Townsville, Australia.
- Surjandari I, Rachman A, Dianawati F, Wibowo RP (2011), Petrol delivery assignment with multiproduct, multi-depot, split deliveries and time windows. International Journal of Modeling and Optimisation 1:375-379.
- Taqa Allah D, Renaud J, Boctor FF (2000), Le problème d'approvisionnement des stations d'essence. APII-JESA Journal Européen des Systèmes Automatisés 34:11-33.
References
Ben Abdelaziz F, Roucairol C, Bacha C (2002), Deliveries of liquid fuels to SNDP gas stations using vehicles with multiple compartments. In: Systems Managment and Cybernetics IEEE International Conference. Hammamet, Tunisia.
Boctor F, Renaud J, Cornillier F (2011), Trip packing in petrol stations replenishment. Omega 39:86-98.
Brown GG, Ellis CJ, Graves GW, Ronen D (1987), Real-time wide area dispatch of mobil tank trucks. Interfaces 17:107-120.
Brown GG, Graves GW (1981), Real-time dispatch of petroleum tank trucks. Management Science 27:19-32.
Chao IM, Golden BL, Wasil E (1995), An improved heuristic for the period vehicle routing problem. Networks 26:25-44.
Christofides N, Beasley JE (1984), The period routing problem. Networks 14:237-256.
Cordeau JF, Gendreau M, Laporte G (1997), A tabu search heuristic for periodic and multi-depot vehicle routing problems. Networks 30:105-119.
Cornillier F, Boctor F, Laporte G, Renaud J (2008a), An exact algorithm for the petrol station replenishment problem. Journal of the Operational Research Society 59:607-615.
Cornillier F, Boctor F, Laporte G, Renaud J (2008b), A heuristic for the multi-period petrol station replenishment problem. European Journal of Operational Research 191:295-305.
Cornillier F, Laporte G, Boctor F, Renaud J (2009), The petrol station replenishment problem with time windows. Computers and Operations Research 36:919-935.
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:361-369.
Gaudioso M, Paletta G (1992), A heuristic for the periodic vehicle routing problem. Transportation Science 26:86-92.
IBM ILOG Cplex Optimizer. (2011), Available at: 01.ibm.com/software/integration/optimization/cpl ex-optimizer/. Accessed May 2012.
Lindo Systems Inc. (2006), Optimization Modeling with Lingo. Available at: www.lindo.com. Accessed May 2012.
Malépart V, Boctor F, Renaud J, Labilois S (2003), Nouvelles approches pour l'approvisionnement des stations d'essence. Revue Française de Gestion Industrielle 22:15-31.
Ng WL, Leung SH, Lam JP, Pan SW (2008), Petrol delivery tanker assignment and routing: a case study in Hong Kong. Journal of the Operational Research Society 59:1191-1200.
Paletta G, Triki C (2004), Solving the asymmetric traveling salesman problem with periodic constraints. Networks 44:31-37.
Rizzoli A, Casagrande N, Donati A, Gambardella L, Lepori D, Montemanni R, Pina P, Zaffalon M (2003), Planning and optimisation of vehicle routes for fuel oil distribution. In: MODSIM International Congress on Modelling and Simulation. Townsville, Australia.
Surjandari I, Rachman A, Dianawati F, Wibowo RP (2011), Petrol delivery assignment with multiproduct, multi-depot, split deliveries and time windows. International Journal of Modeling and Optimisation 1:375-379.
Taqa Allah D, Renaud J, Boctor FF (2000), Le problème d'approvisionnement des stations d'essence. APII-JESA Journal Européen des Systèmes Automatisés 34:11-33.