Mixed Integer Programming Formulation for Time-Dependent Petrol Station Replenishment Problem: A Real-Life Case in İstanbul

Abstract

With the increase in the consumption of petroleum and petroleum products, these limited resources must be provided efficiently, accurately, and with minimal damage. Therefore, the accurate and effective distribution of petroleum, and related problems with petroleum distribution have attracted much attention among the practitioners and optimization working researchers over the years. The petroleum distribution problem, as a version of the Vehicle Routing Problem (VRP), deals with the planning of petroleum distribution from the depot(s) to the petrol stations safely and quickly. In this study, the petrol station replenishment problem (PSRP) is handled and a case study is presented for a public company located in İstanbul. The problem is considered as a time-dependent VRP with time windows. A novel mixed integer mathematical model is proposed for the problem. In order to handle the proposed time-dependent problem in a more realistic way, variable tanker speeds are considered based on traffic density. The optimum route is determined in which risks such as environment and marine pollution may occur in case of possible accidents, and these risks are minimized by the proposed mathematical model considering the factors as traffic, vehicle speed, road structure, the road's proximity to the sea and living areas

Keywords

• time dependent VRP
• risk minimization
• marine pollution
• petrol station replenishment problem

Kaynakça

1. [1] X. H. Qiu, Z. Wang, and Q. Xue, “Investment in deepwater oil and gas exploration projects: a multi-factor analysis with a real options model,” Pet. Sci., vol. 12, no. 3, pp. 525–533, Aug. 2015, doi: 10.1007/s12182-015-0039-4.
2. [2] H. Li, R. J. Sun, K. Y. Dong, X. C. Dong, Z. Bin Zhou, and X. Leng, “Selecting China’s strategic petroleum reserve sites by multi-objective programming model,” Pet. Sci., vol. 14, no. 3, pp. 622–635, Aug. 2017, doi: 10.1007/s12182-017-0175-0.
3. [3] X. Pan, F. Teng, Y. Tian, and G. Wang, “Countries’ emission allowances towards the low-carbon world: A consistent study,” Appl. Energy, vol. 155, pp. 218–228, Oct. 2015, doi: 10.1016/j.apenergy.2015.06.011.
4. [4] E. Erkut and A. Ingolfsson, “Catastrophe avoidance models for hazardous materials route planning,” Transp. Sci., vol. 34, no. 2, pp. 165–179, May 2000, doi: 10.1287/trsc.34.2.165.12303.
5. [5] B. Y. Kara and V. Verter, “Designing a road network for hazardous materials transportation,” Transp. Sci., vol. 38, no. 2, pp. 188–196, 2004, doi: 10.1287/trsc.1030.0065.
6. [6] E. Erkut and F. Gzara, “Solving the hazmat transport network design problem,” Comput. Oper. Res., vol. 35, no. 7, pp. 2234–2247, Jul. 2008, doi: 10.1016/j.cor.2006.10.022.
7. [7] K. G. Zografos and K. N. Androutsopoulos, “A decision support system for integrated hazardous materials routing and emergency response decisions,” Transp. Res. Part C Emerg. Technol., vol. 16, no. 6, pp. 684–703, Dec. 2008, doi: 10.1016/j.trc.2008.01.004.
8. [8] P. Leonelli, S. Bonvicini, and G. Spadoni, “Hazardous materials transportation: A risk-analysis-based routing methodology,” J. Hazard. Mater., vol. 71, no. 1–3, pp. 283–300, Jan. 2000, doi: 10.1016/S0304-3894(99)00084-9.

9. [9] F. Samanlioglu, “A multi-objective mathematical model for the industrial hazardous waste location-routing problem,” Eur. J. Oper. Res., vol. 226, no. 2, pp. 332–340, Apr. 2013, doi: 10.1016/j.ejor.2012.11.019.
10. [10] M. R. Saat, C. J. Werth, D. Schaeffer, H. Yoon, and C. P. L. Barkan, “Environmental risk analysis of hazardous material rail transportation,” J. Hazard. Mater., vol. 264, pp. 560–569, Jan. 2014, doi: 10.1016/j.jhazmat.2013.10.051.
11. [11] S. Bonvicini, G. Antonioni, P. Morra, and V. Cozzani, “Quantitative assessment of environmental risk due to accidental spills from onshore pipelines,” Process Saf. Environ. Prot., vol. 93, pp. 31–49, Jan. 2015, doi: 10.1016/j.psep.2014.04.007.
12. [12] C. Lam and W. Zhou, “Statistical analyses of incidents on onshore gas transmission pipelines based on PHMSA database,” Int. J. Press. Vessel. Pip., vol. 145, pp. 29–40, Sep. 2016, doi: 10.1016/j.ijpvp.2016.06.003.
13. [13] E. Zarei, A. Azadeh, N. Khakzad, M. M. Aliabadi, and I. Mohammadfam, “Dynamic safety assessment of natural gas stations using Bayesian network,” J. Hazard. Mater., vol. 321, pp. 830–840, Jan. 2017, doi: 10.1016/j.jhazmat.2016.09.074.
14. [14] C. Ma, “Network optimisation design of Hazmat based on multi-objective genetic algorithm under the uncertain environment,” Int. J. Bio-Inspired Comput., vol. 12, no. 4, pp. 236–244, 2018, doi: 10.1504/IJBIC.2018.096482.
15. [15] Q. Yang, K. S. Chin, and Y. L. Li, “A quality function deployment-based framework for the risk management of hazardous material transportation process,” J. Loss Prev. Process Ind., vol. 52, pp. 81–92, Mar. 2018, doi: 10.1016/j.jlp.2018.02.001.
16. [16] H. Hu, J. Li, and X. Li, “A credibilistic goal programming model for inventory routing problem with hazardous materials,” Soft Comput., vol. 22, no. 17, pp. 5803–5816, Sep. 2018, doi: 10.1007/s00500-017-2663-y.
17. [17] H. Hu, X. Li, Y. Zhang, C. Shang, and S. Zhang, “Multi-objective location-routing model for hazardous material logistics with traffic restriction constraint in inter-city roads,” Comput. Ind. Eng., vol. 128, pp. 861–876, Feb. 2019, doi: 10.1016/j.cie.2018.10.044.
18. [18] A. Ghaderi and R. L. Burdett, “An integrated location and routing approach for transporting hazardous materials in a bi-modal transportation network,” Transp. Res. Part E Logist. Transp. Rev., vol. 127, pp. 49–65, Jul. 2019, doi: 10.1016/j.tre.2019.04.011.
19. [19] Y. L. Li, Q. Yang, and K. S. Chin, “A decision support model for risk management of hazardous materials road transportation based on quality function deployment,” Transp. Res. Part D Transp. Environ., vol. 74, pp. 154–173, Sep. 2019, doi: 10.1016/j.trd.2019.07.026.
20. [20] S. W. Chiou, “A resilience-based signal control for a time-dependent road network with hazmat transportation,” Reliab. Eng. Syst. Saf., vol. 193, p. 106570, Jan. 2020, doi: 10.1016/j.ress.2019.106570.
21. [21] H. Hu, J. Li, X. Li, and C. Shang, “Modeling and Solving a Multi-Period Inventory Fulfilling and Routing Problem for Hazardous Materials,” J. Syst. Sci. Complex., pp. 1–23, Jan. 2020, doi: 10.1007/s11424-019-8176-2.
22. [22] Z. Ziaei and A. Jabbarzadeh, “A multi-objective robust optimization approach for green location-routing planning of multi-modal transportation systems under uncertainty,” J. Clean. Prod., vol. 291, Apr. 2021, doi: 10.1016/J.JCLEPRO.2020.125293.
23. [23] Z. Zhou, M. Ha, H. Hu, and H. Ma, “Half open multi-depot heterogeneous vehicle routing problem for hazardous materials transportation,” Sustain., vol. 13, no. 3, pp. 1–17, Feb. 2021, doi: 10.3390/su13031262.
24. [24] E. Ayyildiz and A. Taskin Gumus, “Pythagorean fuzzy AHP based risk assessment methodology for hazardous material transportation: an application in Istanbul,” Environ. Sci. Pollut. Res., pp. 1–13, Mar. 2021, doi: 10.1007/s11356-021-13223-y.
25. [25] J. Men, G. Chen, L. Zhou, and P. Chen, “A pareto-based multi-objective network design approach for mitigating the risk of hazardous materials transportation,” Process Saf. Environ. Prot., vol. 161, pp. 860–875, May 2022, doi: 10.1016/j.psep.2022.03.048.
26. [26] E. Erkut and A. Ingolfsson, “Transport risk models for hazardous materials: Revisited,” Oper. Res. Lett., vol. 33, no. 1, pp. 81–89, Jan. 2005, doi: 10.1016/j.orl.2004.02.006.
27. [27] T. S. Chang, L. K. Nozick, and M. A. Turnquist, “Multiobjective path finding in stochastic dynamic networks, with application to routing hazardous materials shipments,” Transp. Sci., vol. 39, no. 3, pp. 383–399, 2005, doi: 10.1287/trsc.1040.0094.
28. [28] B. Zheng, “Multi-Objective Vehicle Routing Problem in Hazardous Material Transportation,” in ICLEM 2010, Sep. 2010, vol. 387, pp. 3136–3142. doi: 10.1061/41139(387)438.
29. [29] J. Tang, Y. Ma, J. Guan, and C. Yan, “A Max-Min Ant System for the split delivery weighted vehicle routing problem,” Expert Syst. Appl., vol. 40, no. 18, pp. 7468–7477, Dec. 2013, doi: 10.1016/j.eswa.2013.06.068.
30. [30] J. M. V. Cantú, A. B. Solano, E. A. L. Leyva, and M. L. Acosta, “Optimization of territories and transport routes for hazardous materials in a distribution network,” J. Ind. Eng. Manag., vol. 10, no. 4 Special Issue, pp. 604–622, Oct. 2017, doi: 10.3926/jiem.2107.
31. [31] M. Zhang, N. Wang, Z. He, Z. Yang, and Y. Guan, “Bi-Objective Vehicle Routing for Hazardous Materials Transportation with Actual Load Dependent Risks and Considering the Risk of Each Vehicle,” IEEE Trans. Eng. Manag., vol. 66, no. 3, pp. 429–442, Aug. 2019, doi: 10.1109/TEM.2018.2832049.
32. [32] N. Wichapa and P. Khokhajaikiat, “Solving a multi-objective location routing problem for infectious waste disposal using hybrid goal programming and hybrid genetic algorithm,” Int. J. Ind. Eng. Comput., vol. 9, pp. 75–98, 2018, doi: 10.5267/j.ijiec.2017.4.003.
33. [33] J. Caceres-Cruz, P. Arias, D. Guimarans, D. Riera, and A. A. Juan, “Rich vehicle routing problem: Survey,” ACM Comput. Surv., vol. 47, no. 2, pp. 1–28, Dec. 2014, doi: 10.1145/2666003.
34. [34] F. Cornillier, F. F. Boctor, G. Laporte, and J. Renaud, “An exact algorithm for the petrol station replenishment problem,” J. Oper. Res. Soc., vol. 59, no. 5, pp. 607–615, May 2008, doi: 10.1057/palgrave.jors.2602374.
35. [35] F. Cornillier, F. F. Boctor, G. Laporte, and J. Renaud, “A heuristic for the multi-period petrol station replenishment problem,” Eur. J. Oper. Res., vol. 191, no. 2, pp. 295–305, Dec. 2008, doi: 10.1016/j.ejor.2007.08.016.
36. [36] W. L. Ng, S. C. H. Leung, J. K. P. Lam, and S. W. Pan, “Petrol delivery tanker assignment and routing: A case study in Hong Kong,” J. Oper. Res. Soc., vol. 59, no. 9, pp. 1191–1200, Jul. 2008, doi: 10.1057/palgrave.jors.2602464.
37. [37] F. Cornillier, G. Laporte, F. F. Boctor, and J. Renaud, “The petrol station replenishment problem with time windows,” Comput. Oper. Res., vol. 36, no. 3, pp. 919–935, Mar. 2009, doi: 10.1016/j.cor.2007.11.007.
38. [38] I. Surjandari, A. Rachman, F. Dianawati, and R. P. Wibowo, “Oil fuel delivery optimization for multi product and multi depot: the case of petrol station replenishment problem (PSRP),” in International Conference on Graphic and Image Processing (ICGIP 2011), Oct. 2011, vol. 8285, p. 82853Q. doi: 10.1117/12.914444.
39. [39] F. F. Boctor, J. Renaud, and F. Cornillier, “Trip packing in petrol stations replenishment,” Omega, vol. 39, no. 1, pp. 86–98, Jan. 2011, doi: 10.1016/j.omega.2010.03.003.
40. [40] F. Cornillier, F. Boctor, and J. Renaud, “Heuristics for the multi-depot petrol station replenishment problem with time windows,” Eur. J. Oper. Res., vol. 220, no. 2, pp. 361–369, Jul. 2012, doi: 10.1016/j.ejor.2012.02.007.
41. [41] C. Triki, “Solution methods for the periodic petrol station replenishment problem,” J. Eng. Res., vol. 10, no. 2, pp. 69–77, Dec. 2013, doi: 10.24200/tjer.vol10iss2pp69-77.
42. [42] P. Carotenuto, S. Giordani, S. Massari, and F. Vagaggini, “Periodic capacitated vehicle routing for retail distribution of fuel oils,” in Transportation Research Procedia, Jan. 2015, vol. 10, pp. 735–744. doi: 10.1016/j.trpro.2015.09.027.
43. [43] A. Benantar, R. Ouafi, and J. Boukachour, “A petrol station replenishment problem: new variant and formulation,” Logist. Res., vol. 9, no. 1, pp. 1–18, Dec. 2016, doi: 10.1007/s12159-016-0133-z.
44. [44] P. Carotenuto, S. Giordani, S. Massari, and F. Vagaggini, “A multi-depot periodic vehicle routing model for petrol station replenishment,” in Advances in Intelligent Systems and Computing, vol. 572, Springer Verlag, 2018, pp. 421–437. doi: 10.1007/978-3-319-57105-8_21.
45. [45] P. Carotenuto, S. Giordani, and D. Celani, “Planning Retail Distribution of Fuel Oils,” in Transportation Research Procedia, Jan. 2017, vol. 27, pp. 484–491. doi: 10.1016/j.trpro.2017.12.017.
46. [46] N. Al-Hinai and C. Triki, “A two-level evolutionary algorithm for solving the petrol station replenishment problem with periodicity constraints and service choice,” Ann. Oper. Res., vol. 286, no. 1–2, pp. 325–350, Mar. 2020, doi: 10.1007/s10479-018-3117-3.
47. [47] H. Yahyaoui, I. Kaabachi, S. Krichen, and A. Dekdouk, “Two metaheuristic approaches for solving the multi-compartment vehicle routing problem,” Oper. Res., pp. 1–24, Jun. 2018, doi: 10.1007/s12351-018-0403-4.
48. [48] V. A. Gromov, K. A. Kuznietzov, and T. Pigden, “Decision support system for light petroleum products supply chain,” Oper. Res., vol. 19, no. 1, pp. 219–236, Mar. 2019, doi: 10.1007/s12351-016-0290-5.
49. [49] X. T. Wei et al., “MILP formulations for highway petrol station replenishment in initiative distribution mode,” Pet. Sci., vol. 18, no. 3, pp. 994–1010, Jun. 2021, doi: 10.1007/S12182-021-00551-4.
50. [50] A. Benantar, R. Ouafi, and J. Boukachour, “An improved tabu search algorithm for the petrol-station replenishment problem with adjustable demands,” INFOR Inf. Syst. Oper. Res., vol. 58, no. 1, pp. 17–37, Jan. 2020, doi: 10.1080/03155986.2019.1607806.
51. [51] L. Wang, J. Kinable, and T. van Woensel, “The fuel replenishment problem: A split-delivery multi-compartment vehicle routing problem with multiple trips,” Comput. Oper. Res., vol. 118, p. 104904, Jun. 2020, doi: 10.1016/j.cor.2020.104904.
52. [52] X. Pan, F. Teng, and G. Wang, “Sharing emission space at an equitable basis: Allocation scheme based on the equal cumulative emission per capita principle,” Appl. Energy, vol. 113, pp. 1810–1818, Jan. 2014, doi: 10.1016/j.apenergy.2013.07.021.
53. [53] X. Huang, X. Wang, J. Pei, M. Xu, X. Huang, and Y. Luo, “Risk assessment of the areas along the highway due to hazardous material transportation accidents,” Nat. Hazards, vol. 93, no. 3, pp. 1181–1202, Sep. 2018, doi: 10.1007/s11069-018-3346-4.
54. [54] Y. Xing, S. Chen, S. Zhu, Y. Zhang, and J. Lu, “Exploring risk factors contributing to the severity of hazardous material transportation accidents in China,” Int. J. Environ. Res. Public Health, vol. 17, no. 4, Feb. 2020, doi: 10.3390/ijerph17041344.
55. [55] Yandex, “Veriler ve Raporlar — Yandex İstanbul için 3 Yıllık Trafik Analizi,” 2018. https://yandex.com.tr/company/press_center/infographics/istanbul_traffic (accessed Jul. 16, 2020).
56. [56] Republic of Turkey-General Directorarate of Highways, “Hız Sınırları,” 2020. https://www.kgm.gov.tr/Sayfalar/KGM/SiteTr/Trafik/HizSinirlari.aspx (accessed Jul. 27, 2020).