Evolutionary Approach for Energy Minimizing Vehicle Routing Problem with Time Windows and Customers’ Priority

Document Type : Research Paper

Author

Assistant Professor, School of Industrial Engineering, Iran University of Science and Technology, Tehran, Iran

Abstract

A new model and solution for the energy minimizing vehicle routing problem with time windows (EVRPTW) and customers’ priority is presented in this paper. In this paper unlike prior attempts to minimize cost by minimizing overall traveling distance, the model also incorporates energy minimizing which meets the latest requirements of green logistics. This paper includes the vehicles load as an additional indicator of the cost in addition to the distance traveled cost. Moreover, this paper tries to maximize the customers' satisfaction using their preference and considers the customers' priority for servicing. Every customer is assigned to a group (e.g., very important, important, casual and unimportant) and the customers’ preference is represented as a convex fuzzy number with respect to the satisfaction for service time. The detailed mathematical formulation of proposed model is provided and it is interpreted as multi-objective optimization where, the energy consumed and the total number of vehicles are minimized and the total satisfaction rate of customers is maximized. In general, the relationship between these defined objectives is unknown until the problem is solved in a proper multi-objective manner. Thus, a multi-objective evolutionary algorithm is proposed and its performance on several completely random instances is compared with Non-dominated Sorting Genetic Algorithm II (NSGA II) and CPLEX Solver. The hypervolume indicator is used to evaluate the two Pareto set approximations found by NSGA-II and the proposed approach. The performance proposed evolutionary is further demonstrated through several computational experiments and the results indicate the good quality of the method.

Keywords

References

-Alinaghian, M. and Naderipour, M. (2016) "A novel comprehensive macroscopic model for time-dependent vehicle routing problem with multi-alternative graph to reduce fuel consumption: A case study", Computers & Industrial Engineering, Vol. 99, pp.210–222.
-Bektaş, T. and Laporte, G. (2011) 'the pollution-routing problem", Transportation Research Part B: methodological, Vol. 45, No. 8, pp.1232-1250.
-Chiang, T. C. and Hsu, W. H. (2014) "A knowledge-based evolutionary algorithm for the multiobjective vehicle routing problem with time windows", Computers & Operations Research, Vol. 45, pp.25-37.
-Deb, K. (2002) "A fast and elitist multiobjective genetic algorithm: NSGA-II", IEEE Transaction on Evolutionary Computation, Vol. 6, No. 2, pp.182-197
-Derrac, J., Garcia, S., Molina, D., Herrera, F. (2011) "A practical tutorial on the use of nonparametric statistical tests as a methodology for comparing evolutionary and swarm intelligence algorithms", Swarm and Evolutionary Computation, Vol. 1, No. 1, pp.3-18. 
-Dondo, R., Cerda, J. (2007) "A cluster-based optimization approach for the multi-depot heterogeneous fleet vehicle routing problem with time windows", European Journal of Operational Research, Vol. 176, No. 3, pp. 1478-1507. 
-Erbao, C., Mingyong, L. (2010) "The open vehicle routing problem with fuzzy demands", Expert Systems with Applications, Vol. 37, No. 3, pp.2405-2411.
-Euchi, J., Yassine, A., Chabchoub, H. (2015) "The dynamic vehicle routing problem: Solution with hybrid metaheuristic approach", Swarm and Evolutionary Computation, Vol. 21, pp.41-53.
-Feng, H.M., Liao, K.L. (2014) "Hybrid evolutionary fuzzy learning scheme in the applications of traveling salesman problems", Information Sciences, Vol. 270, pp.204-225.
-Fernández, E., Roca-Riu, M., Speranza, M.G. (2018) "The Shared Customer Collaboration Vehicle Routing Problem", European Journal of Operational Research, Vol. 265, No. 3, pp. 1078-1093.
-Garcia-Najera, A., Bullinaria, J. A. and  Gutiérrez-Andrade, M. A. (2015) "An evolutionary approach for multi-objective vehicle routing problems with backhauls", Computers & Industrial Engineering, Vol. 81, pp.90-108.
-Gaur, D. R., Mudgal, A. and Singh,  R. R.  (2013) "Routing vehicles to minimize fuel consumption", Operations Research Letters, Vol. 41, pp.576-580.
-Ghannadpour, S. F., Noori, S. and Tavakkoli-Moghaddam, R. (2014) "A multi-objective vehicle routing and scheduling problem with uncertainty in customers’ request and priority", Journal of Combinatorial Optimization, Vol. 28, No. 2, pp.414-446.
-Ghoseiri, K. and Ghannadpour, S. F. (2010) "Multi-objective vehicle routing problem with time windows using goal programming and genetic algorithm", Applied Soft Computing, Vol. 10, No. 4, pp.1096-1107.
-Hosseini-Nasab, H. and Lotfalian, P. (2017) "Green routing for truck systems with classification of path types", Journal of Cleaner Production, No. 146, pp.228-233.  
-Kara, I., Kara, B.Y. and Yetis, M. K. (2007) "Energy minimizing vehicle routing problem", Lecture Notes in Computer Science, Vol. 146, pp.62-71.
-Li, F., Golden, B. and Wasil, E. (2005) "Very large scale vehicle routing: new test problems algorithms and results", Computers and Operations Research, Vol. 32, No. 5, pp.1165-1179.
-Li, K., Kwong, S. and Deb, K. (2015) "A dual-population paradigm for evolutionary multiobjective optimization", Information Sciences, Vol. 309, pp.50-72. 
-Lin, C., Choy, K. L., Ho, G. T. S., Chung, S.H. and Lam, H.Y. (2014) "Survey of green vehicle routing problem: past and future trends", Expert Systems with Applications, Vol. 41, No. 4, pp.1118 – 1138. 
-Lqbal, S., Kaykobad, M. and Rahman, M. S. "Solving the multi-objective vehicle routing problem with soft time windows with the help of bees", Swarm and Evolutionary Computation, Vol. 24, pp.50–64.
-Montoya, A., Gueret, C., Mendoza, J. E. and Villegas, J. G. (2016) "A multi-space sampling heuristic for the green vehicle routing problem", Transportation Research Part C: Emerging Technologies, Vol. 70, pp.113-128.
-Nikkhah Qamsari, A. S. A., Hosseini Motlagh, S. M. and  Jokar, A. (2017) "A two-phase hybrid heuristic method for a multi-depot inventory-routing problem", International Journal of Transportation Engineering, Vol. 4, No. 3, pp. 287-304
-Ombuki, B., Ross, B. and Hanshar, F. (2006) "Multi-objective genetic algorithm for vehicle routing problem with time windows", Applied Intelligence, Vol. 24, No. 1, pp.17-30.
-Pepin, A. S., Desaulniers, G., Herts, A. and Huisman, D. (2009) "A comparison of five heuristics for the multiple depot vehicle scheduling problem", Journal of Scheduling, Vol. 39, pp.17-30.
-Qian, J. and Eglese, R. (2016) "Fuel emissions optimization in vehicle routing problems with time-varying speeds", European Journal of Operational Research, Vol. 248, No. 3, pp.840-848.
-Shim, V. A., Tan, K. C. and Tang, H. (2015) "adaptive memetic computing for evolutionary multiobjective optimization", IEEE Transactions on Cybernetics, Vol. 45, No. 4, pp. 610-621. 
-Sivaram Kumar, V., Thansekhar, M. R., Sarvanan, R. and Miruna Joe Amali, S. (2014) "Solving multi – objective vehicle routing problem with time windows by FAGA", Procedia Engineering, Vol. 97, pp.2176-2185. 
-Solomon, M. M. (1987) "Algorithms for the vehicle routing and scheduling problems with time window constraints", Operations Research, Vol. 35, pp.254–265.
-Tan, K. C., Cheong, C.Y. and Goh, C. K. (2007) "Solving multiobjective vehicle routing problem with stochastic demand via evolutionary computation", European Journal of Operational Research, Vol. 177, No. 2, pp.813-139.
-Tan, K. C., Chew, Y. H. and  Lee, L. H. (2006) "A hybrid multiobjective evolutionary algorithm for solving vehicle routing problem with time windows", Computational Optimization and Applications, Vol. 34, pp.115-151. 
-Tanga, J., Pan, Z.H., Fung, R.Y.K. and  Lau, H. (2009) "Vehicle routing problem with fuzzy time windows", Fuzzy Sets and Systems, Vol. 160, pp.683–695.
-Tavares, G., Zsigraiova, Z., Semiao, V. and Carvalho, M. G. (2008) "A case study of fuel savings through optimisation of MSW transportation routes", Management of Environmental Quality: An International Journal, Vol. 19, No. 4, pp. 444 – 454.
-Xiao, Y., Zhao, Q., Kaku, I. and Xu, Y. (2012) "Development of fuel consumption optimization model for the capacitated vehicle routing problem", Computers & Operations Research, Vol. 39, No. 7, pp.1419-1431.
-Yu, V., Jewpanaya, P. and Perwira Redi, A. A. N. (2016) "Open vehicle routing problem with cross-docking", Computers & Industrial Engineering, Vol. 94, pp.6-17.
-Yu, V. F., Perwira Redi, A. A. N., Hidayat, Y. A., and Wibowo, O. J. (2017) "A simulated annealing heuristic for the hybrid vehicle routingproblem", Applied Soft Computing, Vol. 53, pp.119-132. 
-Zhang, S., Lee, C. K. M., Choy, K. L., Ho, W. and Ip, W.H. (2014) "Design and development of a hybrid artificial bee colony algorithm for the environmental vehicle routing problem", Transportation Research Part D: Transport and Environment, Vol. 31, pp.85-99.
-Zhang, X., Tian, Y., Cheng, R. and Jin, Y. (2015) "An efficient approach to nondominated sorting for evolutionary multiobjective optimization", IEEE Transaction on Evolutionary Computation, Vol. 19, No. 2, pp. 201-213.
-Zhou, Y. and Wang, J. (2015) "A local search-based multiobjective optimization algorithm for multiobjective vehicle routing problem with time windows", IEEE Systems Journal, Vol. 9, No. 3, pp.1100-1113.
-Zhu, Q., Lin, Q., Du, Z., Liang, Z., Wang, W., Zhu, Z., Chen, J., Huang, P. and Ming, Z. (2016) "A novel adaptive hybrid crossover operator for multi objective evolutionary algorithm", Information Sciences, Vol. 345, pp.177-198.
-Zitzler, E., Knowles, J. and Thiele, L. (2008) "Quality assessment of pareto set approximations", In J. Branke et al. (Eds.) Multiobjective Optimization, pp.373-404, Springer-Verlag, Berline.
International Journal of Transportation Engineering
Volume 6, Issue 3 - Serial Number 23
January 2019
Pages 237-264

Files

Share

How to cite

Statistics