Abstract
The Multiobjective Energy Reduction Vehicle Routing Problem is a variant of the classic Vehicle Routing Problem where simultaneous optimization of more than one objective functions is required. In this paper, the problem is formulated with three different competitive objective functions. The first objective function corresponds to the optimization of the time needed for the vehicle to travel between two customers or between the customer and the depot, the second objective function is the minimization of the distance and the fuel consumption when a delivery route is planned and the third objective function is the minimization of the distance and the fuel consumption when a pickup route is planned. The problem is solved with a modified version of the NSGA II, with a use of more than one population, a multi start method for the creation of the initial population and a Variable Neighborhood Search algorithm for the improvement of the solution of each individual separately. In order to give the quality of the methodology, experiments are conducted using appropriately modified for the Vehicle Routing Problem instances based on the classic Euclidean Traveling Salesman Problem benchmark instances taken from the TSP library.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Chand, P., Mohanty, J.R.: Multi objective genetic approach for solving vehicle routing problem. International Journal of Computer Theory and Engineering 5(6), 846–849 (2013)
Christofides, N., Mingozzi, A., Toth, P.: The vehicle routing problem. In: Christofides, N., Mingozzi, A., Toth, P., Sandi, C. (Eds.) Combinatorial Optimization. Wiley, Chichester (1979)
Coello Coello, C.A., Van Veldhuizen, D.A., Lamont, G.B.: Evolutionary Algorithms for Solving Multi-Objective Problems. Springer (2007)
Deb, K., Agrawal, S., Pratap, A., Meyarivan, T.: A fast elitist non-dominated sorting genetic algorithm for multi-objective optimization: NSGA-II. In: Deb, K., Rudolph, G., Lutton, E., Merelo, J.J., Schoenauer, M., Schwefel, H.-P., Yao, X. (eds.) PPSN 2000. LNCS, vol. 1917, pp. 849–858. Springer, Heidelberg (2000)
Deb, K., Pratap, A., Agarwal, S., Meyarivan, T.: A fast and elitist Multiobjective Genetic Algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation 6(2), 182–197 (2002)
Feo, T.A., Resende, M.G.C.: Greedy randomized adaptive search procedure. Journal of Global Optimization 6, 109–133 (1995)
Gutin, G., Punnen, A.P.: The Traveling Salesman Problem and its Variations. Kluwer Academic Publishers, Dordrecht (2002)
Hansen, P., Mladenovic, N.: Variable neighborhood search: Principles and applications. European Journal of Operational Research 130, 449–467 (2001)
Huayu, X., Wenhui, F., Tian, W., Lijun, Y.: An Or-opt NSGA-II algorithm for multi-objective vehicle routing problem with time windows. In: 4th IEEE Conference on Automation Science and Engineering, 309–314 (2008)
Jemai, J., Zekri, M., Mellouli, K.: An NSGA-II Algorithm for the Green Vehicle Routing Problem. In: Hao, J.-K., Middendorf, M. (eds.) EvoCOP 2012. LNCS, vol. 7245, pp. 37–48. Springer, Heidelberg (2012)
Johnson, D.S., Papadimitriou, C.H.: Computational complexity. In: Lawer, E.L., Lenstra, J.K., Rinnoy Kan, A.H.D., Shmoys, D.B., (Eds.) The traveling salesman problem: a guided tour of combinatorial optimization. Wiley and Sons, 37–85 (1985)
Jozefowiez, N., Semet, F., Talbi, E.-G.: Enhancements of NSGA II and Its Application to the Vehicle Routing Problem with Route Balancing. In: Talbi, E.-G., Liardet, P., Collet, P., Lutton, E., Schoenauer, M. (eds.) EA 2005. LNCS, vol. 3871, pp. 131–142. Springer, Heidelberg (2006)
Jozefowiez, N., Semet, F., Talbi, E.G.: Multi-objective vehicle routing problems. European Journal of Operational Research 189, 293–309 (2008)
Laporte, G.: The vehicle routing problem: An overview of exact and approximate algorithms. European Journal of Operational Research 59, 345–358 (1992)
Lawer, E.L., Lenstra, J.K., Rinnoy Kan, A.H.G.R., Shmoys, D.B.: The Traveling Salesman Problem: a guided tour of combinatorial optimization. Wiley and Sons (1985)
Lichtblau, D.: Discrete optimization using Mathematica. In: Callaos, N., Ebisuzaki, T., Starr, B., Abe, J.M., Lichtblau, D. (Eds.) World multi-conference on systemics, cybernetics and informatics (SCI 2002), International Institute of Informatics and Systemics, 16, 169–174 (2002)
Lin, S.: Computer solutions of the traveling salesman problem. Bell Systems Technical Journal 44(10), 2245–2269 (1965)
Ombuki, B., Ross, B.J., Hanshar, F.: Multi-objective genetic algorithms for vehicle routing problem with time windows. Applied Intelligence 24, 17–30 (2006)
Sarker, R., Coello Coello, C.A.: Assessment methodologies for multiobjective evolutionary algorithms. Evolutionary Optimization, International Series in Operations Research and Management Science 48, 177–195 (2002)
Toth, P., Vigo, D.: The Vehicle Routing Problem. Monographs on Discrete Mathematics and Applications, Siam (2002)
Xiao, Y., Zhao, Q., Kaku, I., Xu, Y.: Development of a fuel consumption optimization model for the capacitated vehicle routing problem. Computers and Operations Research 39(7), 1419–1431 (2012)
Zitzler, E., Deb, K., Thiele, L.: Comparison of multiobjective evolutionary algorithms: Empirical results. Evolutionary Computation 8(2), 173–195 (2000)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Psychas, ID., Marinaki, M., Marinakis, Y. (2015). A Parallel Multi-Start NSGA II Algorithm for Multiobjective Energy Reduction Vehicle Routing Problem. In: Gaspar-Cunha, A., Henggeler Antunes, C., Coello, C. (eds) Evolutionary Multi-Criterion Optimization. EMO 2015. Lecture Notes in Computer Science(), vol 9018. Springer, Cham. https://doi.org/10.1007/978-3-319-15934-8_23
Download citation
DOI: https://doi.org/10.1007/978-3-319-15934-8_23
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-15933-1
Online ISBN: 978-3-319-15934-8
eBook Packages: Computer ScienceComputer Science (R0)