A PFIH-Based Heuristic for Green Routing Problem with Hard Time Windows

Document Type : Research Paper


Department of Industrial and Systems Engineering, Isfahan University of Technology


Transportation sector generates a considerable part of each nation's gross domestic product and considered among the largest consumers of oil products in the world. This paper proposes a heuristic method for the vehicle routing problem with hard time windows while incorporating the costs of fuel, driver, and vehicle. The proposed heuristic uses a novel speed optimization algorithm to reach its objectives. Performance of the proposed algorithm is validated by comparing its results with the results of the exact method and differential evaluation algorithm for small-scale problems. For large-scale problems, the results of the proposed algorithm are compared with those obtained from the differential evaluation algorithm. Overall, results indicate the good performance of the proposed heuristic algorithm.


Main Subjects

Kirby, H. R., Hutton, B., McQuaid, R. W., Raeside, R., and Zhang, X., "Modelling the effects of transport policy levers on fuel efficiency and national fuel consumption,"
Toro, E., Franco, J., Echeverri, M., Guimarães, F., & Rendón, R. (2017). Green open location-routing problem considering economic and environmental costs. International Journal of Industrial Engineering Computations, 8(2), 203-216.
Prins, C., "A Simple and Effective Evolutionary Algorithm for the Vehicle Routing Problem," Computers & Operations Research, vol.31, pp.1985–2002,2004.
Jeon, G.,  Leep, H.R. and Shim, J.Y., "A Vehicle Routing Problem Solved by Using a Hybrid Genetic Algorithm, " Computers & Industrial Engineering, vol.53, pp. 680-692, 2007.
Berger, J., Barkaoui, M. and Bräysy, O.,"A Route-directed Hybrid Genetic Approach for the Vehicle Routing Problem with Time Windows," Information Systems and Operational Research, vol.41, pp. 179-194,2003.
Reimann, M., Doerner, K. and Hartl, R.F.,"D-Ants: Savings Based Ants divide and conquer the vehicle routing problem," Computers & Operations Research,vol. 31, pp. 563–591,2004.
 Bektaş, T. and Laporte, G., "The pollution-routing problem," Transportation Research Part B: Methodological, vol. 45, pp. 1232-1250, 2011.
Demir, E., Bektaş, T., and Laporte, G., "An adaptive large neighborhood search heuristic for the Pollution-Routing Problem," European Journal of Operational Research, vol. 223, pp. 346-359, 2012.
Demir, E., Bektaş, T., and Laporte, G.,” The bi-objective pollution routing problem”, Forthcoming European Journal of Operational Research, 2013.
Franceschetti, A., Honhon, D., VanWoensel, T., Bektas, T. and Laporte, G., “Time-dependent pollution routing problem”, Forthcoming to Transportation Research Part B, 2013.
Koc,C., Bektas, T., Jabali, O. and Laporte, G., “The fleet size and mix Pollution routing problem”, Transportation Research Part B: Methodological, vol. 70, pp. 239-254, 2014
Lin, C., Choy, K. L., Ho, G. T., Chung, S. H., & Lam, H. Y. (2014). Survey of green vehicle routing problem: past and future trends. Expert Systems with Applications, 41(4), 1118-1138.
 Solomon, M., "Algorithms for the vehicle routing and scheduling problems with time window constraints", Operations research, vol 35, pp. 254-265, 1987
Thangiah, S.R., Osman, I.H., Sun, T., "Hybrid genetic algorithm, simulated annealing and tabu search methods for vehicle routing problems with time windows", Computer Science Department, Slippery Rock University, Technical Report SRU CpSc-TR-94-27, vol 69, 1994
 R. Storn. " Differential Evolution, A Simple and Efficient Heuristic Strategy for Global Optimization over Continuous Spaces."Journal of Global Optimization11: .341-359, (1997).
Lou, Y., Li, J. and  Wang, Y., "A Binary-Differential Evolution algorithm based on Ordering of individuals", Sixth International Conference on Natural Computation, IEEE, vol 5, pp 2207-2211, 2010
Mingyong, L., & Erbao, C. (2010). An improved differential evolution algorithm for vehicle routing problem with simultaneous pickups and deliveries and time windows. Engineering Applications of Artificial Intelligence, 23(2), 188-195.
Erbao, C., & Mingyong, L. (2009). A hybrid differential evolution algorithm to vehicle routing problem with fuzzy demands. Journal of computational and applied mathematics, 231(1), 302-310.
Marinakis, Y., Marinaki, M., & Spanou, P. (2015). A memetic differential evolution algorithm for the vehicle routing problem with stochastic demands. In Adaptation and hybridization in computational intelligence (pp. 185-204). Springer International Publishing.