An Optimization Framework for Combining the Petroleum Replenishment Problem with the Optimal Bidding in Combinatorial Auctions

Document Type : ICIE 2016


1 Department of Mechanical and Industrial Engineering,Sultan Qaboos University, Muscat, Oman

2 LARODEC Laboratory, Institut Superieur de Gestion, University of Tunis, Tunisia


We address in this paper a periodic petroleum station replenishment problem (PPSRP) that aims to plan the delivery of petroleum products to a set of geographically dispatched stations. It is assumed that each station is characterized by its weekly demand and by its frequency of service. The main objective of the delivery process is to minimize the total travelled distance by the vailable trucks over an extended planning horizon. The problem configuration is described through a set of trucks with several compartments each and a set of stations with demands and prefixed delivery frequencies. Given such input data, the minimization of the total distance is subject to assignment and routing constraints that express the capacity limitations of each truck's compartment in terms of the frequency and the pathways' restrictions. In this paper, we develop and solve the full space mathematical formulation for the PPSRP with application to the Omani context. Our ultimate aim is to include such a model into an integrated framework having the objective of advising petroleum distribution companies on how to prepare bids in case of participation in combinatorial auctions of the transportation procurement.


Main Subjects

An N., Elmaghraby W. and Keskinocak P. (2005). Bidding strategies and their impact on revenues in combinatorial auctions. Journal of Revenue and Pricing Management, Vol. 3(4), pp. 337–357.
Ben Abdelaziz F., Roucairol C. and Bacha C. (2002). Deliveries of liquid fuels to SNDP gas stations using vehicles with multiple compartments. In: Systems Man and Cybernetics IEEE International Conference. Hammamet, Tunisia.
Boctor F., Renaud J. and Cornillier F. (2011). Trip packing in petrol stations replenishment. Omega, Vol.  39, pp. 86-98.
Brown G. G. and Graves G. W. (1981), Real-time dispatch of petroleum tank trucks. Management Science, Vol. 27, pp. 19-32.
Brown G., Ellis C. J., Graves G. W. and Ronen D. (1987). Real-time wide area dispatch of Mobil tank trucks. Interfaces, Vol. 17(1), pp. 107-120.
Cornillier F., Boctor F. and Renaud J. (2012). Heuristics for the multi-depot petrol station replenishment problem with time windows. European J. of Operational Research, Vol. 220, pp. 361-369. 
Cornillier F., Boctor F., Laporte G. and Renaud J. (2008b). A heuristic for the multi-period petrol station replenishment problem. European J. of Operational Research, Vol. 191, pp. 295-305. 
Cornillier F., Boctor F., Laporte G. and Renaud J. (2008a). An Exact Algorithm for the Petrol Station Replenishment Problem, J. of the Operational Research Society, Vol. 59, pp. 607-615.
Cornillier F., Laporte G., Boctor F. and Renaud J. (2009). The petrol station replenishment problem with time windows. Computers and Operations Research, vol. 36, pp. 919-935.
Elmaghraby W. and Keskinocak P. (2003). Combinatorial auctions in procurement. In T. P. Harrison, H. L. Lee and J. J. Neale (Eds.), The practice of supply chain management, pp. 45–258.
Norwell, MA: Kluwer Academic Publishers.
Kuyzu G., Akyol Ç. G., Ergun Ö. and Savelsbergh M. (2015) Bid price optimization for truckload carriers in simultaneous transportation procurement auctions. Transportation Research Part B: Methodological, Vol. 73, pp. 34-58.
Lee C.-G., Kwon R. H. and Ma Z. (2007). A carrier’s optimal bid generation problem in combinatorial auctions for transportation procurement. Transportation Research, Part E, Vol. 43, pp. 173–191.
Malpart V., Boctor F., Renaud J. and Labilois S. (2003). Nouvelles approches pour l'approvisionnement des stations d'essence. Revue Franaise de Gestion Industrielle, Vol. 22, pp. 15-31.
Ma Z., Kwon R. and Lee C.-G. (2010). A stochastic programming winner determination model for truckload procurement under shipment uncertainty, Transportation Research Part E: Logistics and Transportation Review, Vol. 46(1), pp. 49-60.
Ng W. L., Leung S. H., Lam J. P. and Pan S. W. (2008). Petrol delivery tanker assignment and routing: a case study in Hong Kong. J. of the Operational Research Society, Vol. 59, pp. 1191-1200.
Remli N. and Rekik M. (2013). A robust determination problem for the transportation auctions under uncertain shipment volumes. Transportation Research Part C: Emerging Technologies, Vol. 35, pp. 204–217.
Rizzoli A., Casagrande N., Donati A., Gambardella L., Lepori D., Montemanni R., Pina P. and Zaffalon M. (2003). Planning and optimisation of vehicle routes for fuel oil distribution. In: MODSIM International Congress on Modelling and Simulation. Townsville, Australia.
Sheffi Y. (2004). Combinatorial auction in the procurement of transportation service. Interfaces, Vol. 34(4), pp. 245–252.
Surjandari I., Rachman A., Dianawati F. and Wibowo R. P. (2011). Petrol delivery assignment with multi-product, multi-depot, split deliveries and time windows. International J. of Modeling and Optimization, Vol. 1(5), pp. 375-379.
Taqa Allah D., Renaud J., Boctor F.F. (2000). Le problme d'approvisionnement des stations d'essence. APII-JESA J. Europen des Systmes Automatiss, Vol. 34, pp. 11-33.
Triki C. (2013). Solution methods for the periodic petrol replenishment problem. The Journal of Engineering Research, Vol. 10(2), pp. 69-77.
Triki C., Oprea S., Beraldi P. and Crainic T. (2014). The stochastic bid generation problem in combinatorial transportation auctions, European J. of Operational Research, Vol. 236, pp. 991—999.
Triki C. and Al-Hinai N. (2016). Optimisation techniques for planning the petrol replenishment to retail stations over a multi-period horizon. To appear on International Journal of Operations Research.
Triki, C. (2016). Location-based techniques for the synergy approximation in combinatorial transportation auctions. Optimization Letters, Vol. 10(5), pp. 1125-1139.