A New Mathematical Model for the Green Vehicle Routing Problem by Considering a Bi-Fuel Mixed Vehicle Fleet

Document Type : Original Manuscript


1 Khatam University

2 School of Industrial Engineering, Iran university of Science & Technology, Tehran, Iran

3 Institute for Manufacturing, University of Cambridge, Cambridge, United Kingdom



This paper formulates a mathematical model for the Green Vehicle Routing Problem (GVRP), incorporating bi-fuel (natural gas and gasoline) pickup trucks in a mixed vehicle fleet. The objective is to minimize overall costs relating to service (earliness and tardiness), transportation (fixed, variable and fuel), and carbon emissions. To reflect a real-world situation, the study considers: (1) a comprehensive fuel consumption function with a soft time window, and (2) an en-route fuel refueling option to eliminate the constraint of driving range. A linear set of valid inequalities for computing fuel consumption were introduced. In order to validate the presented model, first, the model is solved for an illustrative example. Then each component of cost objective function is considered separately so as to investigate the effects of each part on the obtained solutions and the importance of vehicles speed on transportation strategies. Computational analysis shows that, despite the limitation of an appropriate service infrastructure, the proposed model demonstrated an average reduction of 44%, 6% and 5% in carbon emission costs, total distribution costs, and transportation costs respectively. Moreover, the study found paradoxical effects of average speed, suggesting the need to manage trade-offs: while higher speeds reduced service costs, they increased carbon emission costs. In the next stage, some experiments modified from the literature are solved. According to these experiments, in all instances greater objective function values for Gasoline vehicles are gained. The difference in the carbon emission objective is also significant, with an average of 44.23% increase. Finally, managerial and institutional implications are discussed.


Association NGS. (2004). Natural Gas and the Environment Online: http://www.naturalgas.org/environment/naturalgas asp# greenhouse/ [Accessed on: 12/03/08].
Azadeh, A., Ghaderi, S. F., Pashapour, S., Keramati, A., Malek, M. R., & Esmizadeh, M. (2017). A unique fuzzy multivariate modeling approach for performance optimization of maintenance workshops with cognitive factors. The International Journal of Advanced Manufacturing Technology90(1-4), 499-525.
Azadeh, A., & Farrokhi-Asl, H. (2019). The close–open mixed multi depot vehicle routing problem considering internal and external fleet of vehicles. Transportation Letters11(2), 78-92.
Barth, M., and Boriboonsomsin, K. (2009). Energy and emissions impacts of a freeway-based dynamic eco-driving system. Transportation Research Part D: Transport and Environment14(6), 400-410.
Barth, M., Younglove, T., and Scora, G. (2005). Development of a heavy-duty diesel modal emissions and fuel consumption model. California Partners for Advanced Transit and Highways (PATH).
Bektaş, T., and Laporte, G. (2011). The pollution-routing problem. Transportation Research Part B: Methodological45(8), 1232-1250.
Bynum, C., Sze, C., Kearns, D., Polovick, B., & Simon, K. (2018). An examination of a voluntary policy model to effect behavioral change and influence interactions and decision making in the freight sector. Transportation Research Part D: Transport and Environment61, 19-32.
Christopher, M. (2005). Logistics and supply chain management: creating value-adding networks. Pearson education.
CO2 Calculator for Fosil Fuels. http://www.environment-watch.co.uk/co2.cgi.
Daneshzand, F. (2011). The vehicle-routing problem. Logistics Operations and Management8, 127-153.
Dantzig, G. B., and Ramser, J. H. (1959). The truck dispatching problem. Management science6(1), 80-91.
De Grancy, G. S., and Reimann, M. (2015). Evaluating two new heuristics for constructing customer clusters in a VRPTW with multiple service workers.Central European Journal of Operations Research23(2), 479-500.
DEFRA (2012) 2012 Guidelines to Defra / DECC's GHG Conversion Factors for Company Reporting.https://www.gov.uk/government/uploads/system/uploads/attachment_data/file/69554/pb13773-ghg-conversion-factors-2012.pdf
Dell'Amico, M., Monaci, M., Pagani, C., and Vigo, D. (2007). Heuristic approaches for the fleet size and mix vehicle routing problem with time windows. Transportation Science41(4), 516-526.
Demir, E., Bektaş, T., and Laporte, G. (2012). An adaptive large neighborhood search heuristic for the pollution-routing problem. European Journal of Operational Research223(2), 346-359.
Demir, E., Bektaş, T., and Laporte, G. (2014). The bi-objective pollution-routing problem. European Journal of Operational Research232(3), 464-478.
Erdoğan, S., and Miller-Hooks, E. (2012). A green vehicle routing problem. Transportation Research Part E: Logistics and Transportation Review48(1), 100-114.
Farrokhi-Asl, H., Makui, A., Jabbarzadeh, A., & Barzinpour, F. (2018). Solving a multi-objective sustainable waste collection problem considering a new collection network. Operational Research, 1-39.
Fuchs, E. F., and Masoum, M. A. (2011). Power conversion of renewable energy systems. Springer Science and Business Media.  
Golden B., Assad A., Levy L., Gheysens F. (1984). The fleet size and mix vehicle routing problem. Computers and Operations Research, 11:49-66
Guerriero, F., Surace, R., Loscri, V., and Natalizio, E. (2014). A multi-objective approach for unmanned aerial vehicle routing problem with soft time windows constraints. Applied Mathematical Modelling38(3), 839-852.
Huang, X., Wang, Y., Xing, Z., and Du, K. (2016). Emission factors of air pollutants from CNG-gasoline bi-fuel vehicles: Part II. CO, HC and NO x. Science of the Total Environment565, 698-705.
Jabali, O., Woensel, T., and de Kok, A. G. (2012). Analysis of travel times and CO2 emissions in time‐dependent vehicle routing. Production and Operations Management21(6), 1060-1074.
Kara, I., Kara, B. Y., and Yetis, M. K. (2007, August). Energy minimizing vehicle routing problem. In International Conference on Combinatorial Optimization and Applications (pp. 62-71). Springer Berlin Heidelberg.
Knörr, W. (2011). EcoTransIT: Ecological transport information tool for worldwide transports - Methodology and data update. Heidelberg, Germany: Institut für Energie (ifeu) und Umweldforschung Heidelberg GmbH.
Koç, Ç., and Karaoglan, I. (2016). The green vehicle routing problem: A heuristic based exact solution approach. Applied Soft Computing39, 154-164.
Lin, C., Choy, K. L., Ho, G. T., Chung, S. H., and Lam, H. Y. (2014). Survey of green vehicle routing problem: past and future trends. Expert Systems with Applications41(4), 1118-1138.
Lim, S.F.W.T., Rabinovich, E., Rogers, D.S. and Laseter, T.M. (2016). Last-mile supply network distribution in omni-channel retailing: A configuration-based typology. Foundations and Trends in Technology, Information and Operations Management, 10(1), 1-87.
Lowe, I. (2016). The electric vehicle challenge. Australasian Science37(4), 49.
Maden, W., Eglese, R., and Black, D. (2010). Vehicle routing and scheduling with time-varying data: A case study. Journal of the Operational Research Society61(3), 515-522.
Min, H. (1991). A multiobjective vehicle routing problem with soft time windows: the case of a public library distribution system. Socio-Economic Planning Sciences25(3), 179-188.
Omidvar, A., and Tavakkoli-Moghaddam, R. (2012, September). Sustainable vehicle routing: Strategies for congestion management and refueling scheduling. In Energy Conference and Exhibition (ENERGYCON), 2012 IEEE International (pp. 1089-1094). IEEE.
Palmer, A. (2007). The development of an integrated routing and carbon dioxide emissions model for goods vehicles. Bedford: Cranfield University, Available from: http://hdl.handle.net/1826/2547.
Pradenas, L., Oportus, B., and Parada, V. (2013). Mitigation of greenhouse gas emissions in vehicle routing problems with backhauling. Expert Systems with Applications40(8), 2985-2991.
Qureshi, A. G., Taniguchi, E., and Yamada, T. (2009). An exact solution approach for vehicle routing and scheduling problems with soft time windows. Transportation Research Part E: Logistics and Transportation Review45(6), 960-977.
Quak, H., and Dekoster, M. (2007). Exploring retailers’ sensitivity to local sustainability policies. Journal of Operations Management, 25, 1103-1122.
Rabbani, M., Ramezankhani, M. J., Farrokhi-Asl, H., and Farshbaf-Geranmayeh, A. (2015). Vehicle Routing with Time Windows and Customer Selection for Perishable Goods. International Journal of Supply and Operations Management2(2), 700-719.
Rabbani, M., Farrokhi-asl, H., and Rafiei, H. (2016). A hybrid genetic algorithm for waste collection problem by heterogeneous fleet of vehicles with multiple separated compartments. Journal of Intelligent and Fuzzy Systems30(3), 1817-1830.
Rabbani, M., Heidari, R., Farrokhi-Asl, H., & Rahimi, N. (2018). Using metaheuristic algorithms to solve a multi-objective industrial hazardous waste location-routing problem considering incompatible waste types. Journal of Cleaner Production170, 227-241.
Russell, R. A. (1977). Technical Note—An Effective Heuristic for the M-Tour Traveling Salesman Problem with Some Side Conditions. Operations Research25(3), 517-524.
Salimifard, K., and Raeesi, R. (2014). A green routing problem: optimising CO2 emissions and costs from a bi-fuel vehicle fleet. International Journal of Advanced Operations Management6(1), 27-57.
Salhi, S., Sari, M., Saidi, D., and Touati, N. A. C. (1992). Adaptation of some vehicle fleet mix heuristics. Omega20(5-6), 653-660.
Schneider, M., Stenger, A., and Goeke, D. (2014). The electric vehicle-routing problem with time windows and recharging stations. Transportation Science48(4), 500-520.
Sexton, T. R., and Choi, Y. M. (1986). Pickup and delivery of partial loads with “soft” time windows. American Journal of Mathematical and Management Sciences6(3-4), 369-398.
 Shahraeeni, M., Ahmed, S., Malek, K., Van Drimmelen, B., and Kjeang, E. (2015). Life cycle emissions and cost of transportation systems: Case study on diesel and natural gas for light duty trucks in municipal fleet operations.Journal of Natural Gas Science and Engineering24, 26-34.
Solomon, M. M. (1987). Algorithms for the vehicle routing and scheduling problems with time window constraints. Operations research35(2), 254-265.
Taillard, É. D. (1999). A heuristic column generation method for the heterogeneous fleet VRP. RAIRO-Operations Research33(1), 1-14.
Toro, E., Franco, J., Echeverri, M., Guimarães, F., and Rendón, R. (2017). Green open location-routing problem considering economic and environmental costs. International Journal of Industrial Engineering Computations8(2), 203-216.
Wilson, R. M., and Gilligan, C. (2012). Strategic marketing management. Routledge.  
Xiao, Y., Zhao, Q., Kaku, I., and Xu, Y. (2012). Development of a fuel consumption optimization model for the capacitated vehicle routing problem. Computers and Operations Research39(7), 1419-1431.
Yang, C., McCollum, D., McCarthy, R., and Leighty, W. (2009). Meeting an 80% reduction in greenhouse gas emissions from transportation by 2050: A case study in California. Transportation Research Part D: Transport and Environment14(3), 147-156.
Yavuz, M., Oztaysi, B., Onar, S. C., and Kahraman, C. (2015). Multi-criteria evaluation of alternative-fuel vehicles via a hierarchical hesitant fuzzy linguistic model. Expert Systems with Applications42(5), 2835-2848.
Zhang, L. H., and Wang, M. Y. (2013). Study on a Multi-Depot and Heterogeneous-Vehicle Open Vehicle Routing Problem to Reduce Fuel Consumption. In Applied Mechanics and Materials (Vol. 336, pp. 2567-2571). Trans Tech Publication.