Three New Heuristic Algorithms For The Fleet Size And Mix Green Vehicle Routing Problem

Document Type : Research Paper


Department of Industrial and Systems Engineering, Isfahan University of Technology, Isfahan, Iran


In recent years, great efforts have been made to reduce greenhouse gas emissions by vehicles. Petroleum products produces greenhouse gas emissions, therefore reducing the use of these products can make a major contribution to reducing pollution. The Fleet Size and Mix Vehicle Routing Problem is one of the most widely used routing branches. In this problem, there are vehicle with different capacities and there is the possibility of choosing vehicles of different types. In this paper, Fleet Size and Mix Vehicle Routing Problem is death considering the reduction of fuel consumption. Since this problem is NP-hard, three novel heuristic methods entitled GROS-I,GROS-II, GGT are presented for the problem. In order to evaluate the proposed heuristics a number of small, medium and large problems are solved. The results show that proposed algorithms have good performance.


Main Subjects

Clarke, G.u., and Wright, J.W. (1964). Scheduling of vehicles from a central depot to a number of delivery points. Operations research 12, 568-581.
Dantzig, G.B., and Ramser, J.H. (1959). The truck dispatching problem. Management science 6, 80-91.
Erdoğan, S., and Miller-Hooks, E. (2012). A green vehicle routing problem. Transportation Research Part E: Logistics and Transportation Review 48, 100-114.
Fagerholt, K., Laporte, G., and Norstad, I. (2010). Reducing fuel emissions by optimizing speed on shipping routes. Journal of the Operational Research Society 61, 523-529.
Faulin, J., Juan, A., Lera, F., and Grasman, S. (2011). Solving the capacitated vehicle routing problem with environmental criteria based on real estimations in road transportation: a case study. Procedia-Social and Behavioral Sciences 20, 323-334.
Felipe, Á., Ortuño, M.T., Righini, G., and Tirado, G. (2014). A heuristic approach for the green vehicle routing problem with multiple technologies and partial recharges. Transportation Research Part E: Logistics and Transportation Review 71, 111-128.
Figliozzi, M.A. (2011). The impacts of congestion on time-definitive urban freight distribution networks CO2 emission levels: Results from a case study in Portland, Oregon. Transportation Research Part C: Emerging Technologies 19, 766-778.
Golden, B., Assad, A., Levy, L., and Gheysens, F. (1984). The fleet size and mix vehicle routing problem. Computers & Operations Research 11, 49-66.
Kara, İ., Kara, B., and Yetis, M.K. (2007). Energy Minimizing Vehicle Routing Problem. In Combinatorial Optimization and Applications, A. Dress, Y. Xu, and B. Zhu, eds. (Springer Berlin Heidelberg), pp. 62-71.
Kirby, H.R., Hutton, B., McQuaid, R.W., Raeside, R., and Zhang, X. (2000). Modelling the effects of transport policy levers on fuel efficiency and national fuel consumption. Transportation Research Part D: Transport and Environment 5, 265-282.
Koç, Ç., Bektaş, T., Jabali, O., and Laporte, G. (2014). The fleet size and mix pollution-routing problem. Transportation Research Part B: Methodological 70, 239-254.
Kopfer, H., and Kopfer, H. (2013). Emissions Minimization Vehicle Routing Problem in Dependence of Different Vehicle Classes. In Dynamics in Logistics, H.-J. Kreowski, B. Scholz-Reiter, and K.-D. Thoben, eds. (Springer Berlin Heidelberg), pp. 49-58.
Kucukoglu, I., Ene, S., Aksoy, A., and Ozturk, N. (2013). a green capacitated vehicle routing problem with fuel consumption optimization model International Journal of Computational Engineering Research 3, 16-23.
Kwon, Y.-J., Choi, Y.-J., and Lee, D.-H. (2013). Heterogeneous fixed fleet vehicle routing considering carbon emission. Transportation Research Part D: Transport and Environment 23, 81-89.
Lin, C., Choy, K.L., Ho, G.T., Chung, S., and Lam, H. (2014). Survey of green vehicle routing problem: Past and future trends. Expert Systems with Applications 41, 1118-1138.
Omidvar, A., and Tavakkoli-Moghaddam, R (2012). Sustainable vehicle routing: Strategies forcongestion management and refueling scheduling. In Energy Conference and Exhibition
(ENERGYCON), Florence, Italy, 1089–1094.
Palmer, A. (2007). The development of an integrated routing and carbon dioxide emissions model for goods vehicles.
Saberi, M.a.V., İ. (2012). Continuous Approximation Model for the Vehicle Routing Problem for Emissions Minimization at the Strategic Level. Journal of Transportation Engineering 138, 1368-1376.
Shao, S., and Huang, G.Q. (2014). A SHIP Inventory Routing Problem with Heterogeneous Vehicles under Order-Up-To Level Policies. In IIE Annual Conference. Proceedings (Institute of Industrial Engineers-Publisher), p. 1106.
Ubeda, S., Arcelus, F., and Faulin, J. (2011). Green logistics at Eroski: A case study. International Journal of Production Economics 131, 44-51.
Yong Peng, X.W. (Apr. 11, 2009 to Apr. 12, 2009). “Research on a Vehicle Routing Schedule to Reduce Fuel
Consumption”. 2014 Sixth International Conference on Measuring Technology and Mechatronics Automation 3.
  • Receive Date: 10 October 2015
  • Revise Date: 25 December 2015
  • Accept Date: 08 April 2016
  • First Publish Date: 08 April 2016