A heuristic approach for green vehicle routing
RAIRO. Operations Research, Tome 55 (2021), pp. S2543-S2560

This paper addresses a green capacitated vehicle routing problem that accounts for transportation emissions. A Dynamic Programming approach has been used to formulate the problem. Although small-sized problems can be solved by Dynamic Programming, this approach is infeasible for larger problems due to the curse of dimensionality. Therefore, we propose a Dynamic Programming based solution approach that involves the ideas of restriction, simulation and online control of parameters to solve large-sized problems. The added values of the proposed decision support tool have been shown on a small-sized base case and relatively larger problems. Performance comparisons of the proposed heuristic against other existing Dynamic Programming based solution approaches reveal its effectiveness, as in most of the instance-setting pairs, the proposed heuristic outperforms the existing ones. Accordingly, the proposed heuristic can be used as an alternative decision support tool to tackle real routing problems confronted in sustainable logistics management.

DOI : 10.1051/ro/2020109
Classification : 90-08, 90B06, 90C59, 90C90
Keywords: Routing, Dynamic Programming, Online control, Greenhouse Gas emissions 
@article{RO_2021__55_S1_S2543_0,
     author = {Soysal, Mehmet and \c{C}imen, Mustafa and Sel, \c{C}a\u{g}r{\i} and Belba\u{g}, Sedat},
     title = {A heuristic approach for green vehicle routing},
     journal = {RAIRO. Operations Research},
     pages = {S2543--S2560},
     year = {2021},
     publisher = {EDP-Sciences},
     volume = {55},
     doi = {10.1051/ro/2020109},
     mrnumber = {4223100},
     language = {en},
     url = {https://www.numdam.org/articles/10.1051/ro/2020109/}
}
TY  - JOUR
AU  - Soysal, Mehmet
AU  - Çimen, Mustafa
AU  - Sel, Çağrı
AU  - Belbağ, Sedat
TI  - A heuristic approach for green vehicle routing
JO  - RAIRO. Operations Research
PY  - 2021
SP  - S2543
EP  - S2560
VL  - 55
PB  - EDP-Sciences
UR  - https://www.numdam.org/articles/10.1051/ro/2020109/
DO  - 10.1051/ro/2020109
LA  - en
ID  - RO_2021__55_S1_S2543_0
ER  - 
%0 Journal Article
%A Soysal, Mehmet
%A Çimen, Mustafa
%A Sel, Çağrı
%A Belbağ, Sedat
%T A heuristic approach for green vehicle routing
%J RAIRO. Operations Research
%D 2021
%P S2543-S2560
%V 55
%I EDP-Sciences
%U https://www.numdam.org/articles/10.1051/ro/2020109/
%R 10.1051/ro/2020109
%G en
%F RO_2021__55_S1_S2543_0
Soysal, Mehmet; Çimen, Mustafa; Sel, Çağrı; Belbağ, Sedat. A heuristic approach for green vehicle routing. RAIRO. Operations Research, Tome 55 (2021), pp. S2543-S2560. doi: 10.1051/ro/2020109

[1] P. Ahi and C. Searcy, A comparative literature analysis of definitions for green and sustainable supply chain management. J. Cleaner Prod. 52 (2013) 329–341. | DOI

[2] P. Alvarez, I. Lerga, A. Serrano-Hernandez and J. Faulin, The impact of traffic congestion when optimising delivery routes in real time. A case study in spain. Int. J. Logistics Res. App. 21 (2018) 529–541. | DOI

[3] A. Bastaş and K. Liyanage, Sustainable supply chain quality management: a systematic review. J. Cleaner Prod. 181 (2018) 726–744. | DOI

[4] T. Bektaş and G. Laporte, The pollution-routing problem. Transp. Res. Part B Methodological 45 (2011) 1232–1250. | DOI

[5] T. Bektaş, E. Demir, G. Laporte, Green vehicle routing. In: Vol. 226 of International Series in Operations Research & Management Science. Springer, Cham (2016) 243–265.

[6] T. Bektaş, J. F. Ehmke, H. N. Psaraftis and J. Puchinger, The role of operational research in green freight transportation. Eur. J. Oper. Res. 274 (2019) 807–823. | MR | DOI

[7] R. Bellman, Dynamic programming treatment of the traveling salesman problem. J. ACM 9 (1962) 61–63. | MR | Zbl | DOI

[8] P. G. Boulter, T. J. Barlow, I. S. Mccrae, Emission factors 2009: report 3 – exhaust emission factors for road vehicles in the United Kingdom. Technical Report. Published project report PPR356 by TRL limited (2009).

[9] M. Bravo, L. P. Rojas and V. Parada, An evolutionary algorithm for the multi-objective pick-up and delivery pollution-routing problem. Int. Trans. Oper. Res. 26 (2019) 302–317. | MR | DOI

[10] W. R. Cherif-Khettaf, M. H. Rachid, C. Bloch and P. Chatonnay, New notation and classification scheme for vehicle routing problems. RAIRO:OR 49 (2015) 161–194. | MR | Zbl | Numdam | DOI

[11] M. Çimen and M. Soysal, Time-dependent green vehicle routing problem with stochastic vehicle speeds: an approximate dynamic programming algorithm. Transp. Res. Part D: Transp. Environ. 54 (2017) 82–98. | DOI

[12] L. C. Coelho, J. Renaud and G. Laporte, Road-based goods transportation: a survey of real-world logistics applications from 2000 to 2015. INFOR: Info. Syst. Oper. Res. 54, 2016 (2015) 79–96.

[13] D. Coley, M. Howard and M. Winter, Local food, food miles and carbon emissions: a comparison of farm shop and mass distribution approaches. Food Policy 34 (2009) 150–155. | DOI

[14] DEFRA, Guidelines to Defra’s GHG conversion factors for company reporting – Annexes updated June 2007. Technical Report. Department for Environment, Food and Rural Affairs (2007).

[15] E. Demir, T. Bektaş and G. Laporte, A review of recent research on green road freight transportation. Eur. J. Oper. Res. 237 (2014) 775–793. | DOI

[16] R. Dubey, A. Gunasekaran, T. Papadopoulos, S. J. Childe, K. Shibin and S. F. Wamba, Sustainable supply chain management: framework and further research directions. J. Cleaner Prod. 142 (2017) 1119–1130. | DOI

[17] R. Eglese and T. Bektaş, Green vehicle routing. Veh. Routing: Prob. Methods App. 18 (2014) 437–458. | DOI

[18] A. Franceschetti, D. Honhon, T. Van Woensel, T. Bektaş and G. Laporte, The time-dependent pollution-routing problem. Transp. Res. Part B: Methodological 56 (2013) 265–293. | DOI

[19] A. Franceschetti, E. Demir, D. Honhon, T. Van Woensel, G. Laporte and M. Stobbe, A metaheuristic for the time-dependent pollution-routing problem. Eur. J. Oper. Res. 259 (2017) 972–991. | MR | DOI

[20] B. Funke, T. Grünert and S. Irnich, Local search for vehicle routing and scheduling problems: review and conceptual integration. J. Heuristics 11 (2005) 267–306. | DOI

[21] M. Gajanand and T. Narendran, Green route planning to reduce the environmental impact of distribution. Int. J. Logistics Res. App. 16 (2013) 410–432. | DOI

[22] M. Gan, X. Liu, S. Chen, Y. Yan and D. Li, The identification of truck-related greenhouse gas emissions and critical impact factors in an urban logistics network. J. Cleaner Prod. 178 (2018) 561–571. | DOI

[23] A. Goel, Vehicle scheduling and routing with drivers’ working hours. Transp. Sci. 43 (2009) 17–26. | DOI

[24] J. Gromicho, J. J. Van Hoorn, A. L. Kok and J. M. J. Schutten, The flexibility of restricted dynamic programming for the VRP. Beta Working Pap. Ser. 266 (2008) 1–20.

[25] J. Gromicho, J. J. Van Hoorn, A. L. Kok and J. M. J. Schutten, Restricted dynamic programming: a flexible framework for solving realistic VRPs. Comput. Oper. Res. 39 (2012) 902–909. | MR | Zbl | DOI

[26] M. Held and R. M. Karp, A dynamic programming approach to sequencing problems. J. SIAM 10 (1962) 196–210. | MR | Zbl

[27] I. Kara, B. Kara and M. Yetis, Energy minimizing vehicle routing problem, edited by A. Dress, Y. Xu, B. Zhu. Vol. 4616 of Lecture Notes in Computer Science Combinatorial Optimization and Applications. Springer, Berlin-Heidelberg (2007) 62–71. | MR | Zbl

[28] A. L. Kok, C. M. Meyer, H. Kopfer and J. M. J. Schutten, A dynamic programming heuristic for the vehicle routing problem with time windows and european community social legislation. Transp. Sci. 44 (2010) 442–454. | DOI

[29] A. L. Kok, E. W. Hans and J. M. J. Schutten, Vehicle routing under time-dependent travel times: the impact of congestion avoidance. Comput. Oper. Res. 39 (2012) 910–918. | Zbl | DOI

[30] G. Laporte, H. Mercure and Y. Nobert, An exact algorithm for the asymmetrical capacitated vehicle-routing problem. NETWORKS 16 (1986) 33–46. | MR | Zbl | DOI

[31] G. Laporte, F. Louveaux and L. Van Hamme, An integer L -shaped algorithm for the capacitated vehicle routing problem with stochastic demands. Oper. Res. 50 (2002) 415–423. | MR | Zbl | DOI

[32] C. Lin, K. L. Choy, G. T. S. Ho, S. H. Chung and H. Y. Lam, Survey of green vehicle routing problem: past and future trends. Expert Syst. App. 41 (2014) 1118–1138. | DOI

[33] S. Majidi, S. M. Hosseini-Motlagh, S. Yaghoubi and A. Jokar, Fuzzy green vehicle routing problem with simultaneous pickup–delivery and time windows. RAIRO:OR 51 (2017) 1151–1176. | MR | Zbl | Numdam | DOI

[34] Y. Niu, Z. Yang, P. Chen and J. Xiao, Optimizing the green open vehicle routing problem with time windows by minimizing comprehensive routing cost. J. Cleaner Prod. 171 (2018) 962–971. | DOI

[35] E. Pérez-Bernabeu, A. A. Juan, J. Faulin and B. B. Barrios, Horizontal cooperation in road transportation: a case illustrating savings in distances and greenhouse gas emissions. Int. Trans. Oper. Res. 22 (2015) 585–606. | MR | DOI

[36] K. N. Reddy, A. Kumar and E. E. Ballantyne, A three-phase heuristic approach for reverse logistics network design incorporating carbon footprint. Int. J. Prod. Res. 57 (2019) 6090–6114. | DOI

[37] S. Rogerson, Influence of freight transport purchasing processes on logistical variables related to CO2 emissions: a case study in Sweden. Int. J. Logistics Res. App. 20 (2017) 604–623. | DOI

[38] M. Salehi, M. Jalalian and M. M. V. Siar, Green transportation scheduling with speed control: trade-off between total transportation cost and carbon emission. Comput. Ind. Eng. 113 (2017) 392–404. | DOI

[39] I. Sbai, S. Krichen and O. Limam, Two meta-heuristics for solving the capacitated vehicle routing problem: the case of the tunisian post office. Oper. Res. 1–43 (2020).

[40] M. M. Solomon, Algorithms for the vehicle routing and scheduling problems with time window constraints. Oper. Res. 35 (1987) 254–265. | MR | Zbl | DOI

[41] M. Soysal, Decision support modeling for sustainable food logistics management, Ph.D. thesis. Wageningen University (2015).

[42] M. Soysal and M. Çimen, A simulation based restricted dynamic programming approach for the green time dependent vehicle routing problem. Comput. Oper. Res. 88 (2017) 297–305. | MR | DOI

[43] M. Soysal, M. Çimen, S. Belbağ and E. Toğrul, A review on sustainable inventory routing. Comput. Ind. Eng. 132 (2019) 395–411. | DOI

[44] M. Soysal, M. Çimen, M. Ömürgönülşen and S. Belbağ, Performance comparison of two recent heuristics for green time dependent vehicle routing problem. Int. J. Bus. Anal. (IJBAN) 6 (2019) 1–11. | DOI

[45] F. Tao, T. Fan and K. K. Lai, Optimal inventory control policy and supply chain coordination problem with carbon footprint constraints. Int. Trans. Oper. Res. 25 (2018) 1831–1853. | MR | DOI

[46] S. Validi, A. Bhattacharya and P. Byrne, Integrated low-carbon distribution system for the demand side of a product distribution supply chain: a doe-guided MOPSO optimiser-based solution approach. Int. J. Prod. Res. 52 (2014) 3074–3096. | DOI

[47] Y. Xiao, X. Zuo, J. Huang, A. Konak and Y. Xu, The continuous pollution routing problem. Appl. Math. Comput. 387 (2020) 125072.

[48] L. Zhu and D. Hu, Study on the vehicle routing problem considering congestion and emission factors. Int. J. Prod. Res. 57 (2019) 6115–6129. | DOI

Cité par Sources :