A Novel Heuristic Algorithm Based on Clark and Wright Algorithm for Green Vehicle Routing Problem

Document Type : Research Paper


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

2 Department of Industrial Engineering at Iran University of Science and Technology, Tehran, Iran


A significant portion of Gross Domestic Production (GDP) in any country belongs to the transportation system. Transportation equipment, in the other hand, is supposed to be great consumer of oil products. Many attempts have been assigned to the vehicles to cut down Greenhouse Gas (GHG). In this paper a novel heuristic algorithm based on Clark and Wright Algorithm called Green Clark and Wright (GCW) for Vehicle Routing Problem regarding to fuel consumption is presented. The objective function is fuel consumption, drivers, and the usage of vehicles. Being compared to exact methods solutions for small-sized problems and to Differential Evolution (DE) algorithm solutions for large-scaled problems, the results show efficient performance of the proposed GCW algorithm.


Main Subjects

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, Vol. 5, pp. 265-282.

Zachariadis, E. E., Tarantilis, C. D., and Kiranoudis, C. T. (2009). An integrated local search method for inventory and routing decisions. Expert Systems with Applications, Vol. 36, pp. 10239-10248.

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, Vol. 41, pp. 1118-1138.

Barbarosoglu,G. Ozgur, D. (1999). A tabu search algorithm for the vehicle routing problem. Computers & Operations Reaserch. Vol 26, pp. 255-270.
Demir, E., Bektaş, T., and Laporte, G. (2014). A review of recent research on green road freight transportation. European Journal of Operational Research. Vol. 237, pp. 775-793.

Xiao, Y., Zhao, Q., Kaku, I., and Xu, Y. (2012). Development of a fuel consumption optimization model for the capacitated vehicle routing problem. Computers & Operations Research Vol. 39, pp. 1419-1431.

Kuo, Y. (2010).Using simulated annealing to minimize fuel consumption for the time-dependent vehicle routing problem. Computers & Industrial Engineering. Vol. 59, pp. 157-165.

Ubeda, S., Arcelus, F., and Faulin, J. (2011). Green logistics at Eroski: A case study. International Journal of Production Economics. Vol. 131, pp. 44-51.

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. Vol. 20, pp. 323-334.

Rakha, H., Ahn, K., and Trani, A. (2003). Comparison of MOBILE5a, MOBILE6, VT-MICRO, and CMEM models for estimating hot-stabilized light-duty gasoline vehicle emissions. Canadian Journal of Civil Engineering. Vol. 30, pp. 1010-1021.

Palmer, A. (2007).The development of an integrated routing and carbon dioxide emissions model for goods vehicles. Lancaster University.

Banderia, J., ALMEIDA, TG., Khattak, AJ., Rouphail, NM. And Coelho, MC. (2013). Generation emissions information for route selection: Experimental monitoring and routes characterization. Journal of Intelligent Transportation Systems. Vol. 17, pp. 3-17.

Bektaş, T. and Laporte, G. (2011). The pollution-routing problem. Transportation Research Part B: Methodological, Vol. 45, pp. 1232-1250.

Demir, E., Bektaş, T., and Laporte, G. (2012). An adaptive large neighborhood search heuristic for the Pollution-Routing Problem. European Journal of Operational Research. Vol. 223, pp. 346-359.

Demir, E., Bektaş, T., and Laporte, G. (2014). The bi-objective pollution routing problem. European Journal of Operational Research. Vol. 232, pp. 464–478.

Franceschetti, A., Honhon, D., VanWoensel, T., Bektas, T. and Laporte, G. (2013). Time-dependent pollution routing problem. Transportation Research Part B. Vol 56, pp 265-293.

Koc,C., Bektas, T., Jabali, O. and Laporte, G. (2014). The fleet size and mix Pollution routing problem. Transportation Research Part B: Methodological, Vol. 70, pp. 239-254.
Jabali, O., Van Woensel, T. and de kok, AG. (2012). Analysis of travel time and CO2 emissions time dependent vehicle routing. Production and Operations Management. Vol. 21(6), pp. 1060-1074.

Omidvar, A., Tavakkoli-moghaddam, R. (2012). Sustainable vehicle routing: strategies for congestion management and refueling scheduling. Energy Conference and Exhibition (ENERGYCON), 2012, IEEE International, pp. 1089-1094.

Maden, W., Eglese, R., and Black, D. (2010). Vehicle routing and scheduling with time-varying data: A case study. Journal of the Operational Research Society, vol. 61, pp. 515-522.

E.Demir. (2012). Models and Algorithms for the Pollution-Routing Problem and Its Variations. Thesis for the degree of Doctor of Philosophy.

J. Lysgaard (1997). Clarke & Wright's Savings Algorithm." Department of Management Science and Logistics. The Aarhus School of Business.
R. Agarwal, R.K. Ahuja, G. Laporte, Z.J. Shen, (2004). Handbook of Scheduling: Algorithms, Models, and Performance Analysis. Chapman and Hall/CRC.
R. Storn (1997). Differential Evolution, a Simple and Efficient Heuristic Strategy for Global Optimization over Continuous Spaces. Journal of Global Optimization Vol.11, pp. 341-359.