Abstract
The generalized vehicle routing problem (GVRP) is one of the challenging combinatorial optimization problems that finds a lot of practical applications. The GVRP is a natural extension of the classical vehicle routing problem (VRP) and it is an NP-hard optimization problem belonging to the class of generalized combinatorial optimization problems. The aim of this paper is to present a new approach to tackle this complex problem. Combining this approach with a genetic algorithm results an efficient hybrid soft computing technique for solving the generalized vehicle routing problem. The proposed algorithm is competitive with other heuristics published to date in both solution quality and computation time. The computational results for several benchmarks problems are reported and the results point out that our proposed algorithm is an appropriate method to explore the search space of this complex problem and leads to good solutions in a reasonable amount of time.
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
Baldacci, R., Bartolini, E., Laporte, G.: Some applications of the generalized vehicle routing problem. Journal of the Operational Research Society 61(7), 1072–1077 (2010)
Banerjee, T.P., Das, S., Roychoudhury, J., Abraham, A.: Implementation of a New Hybrid Methodology for Fault Signal Classification Using Short -Time Fourier Transform and Support Vector Machines. In: Corchado, E., Novais, P., Analide, C., Sedano, J. (eds.) SOCO 2010. AISC, vol. 73, pp. 219–225. Springer, Heidelberg (2010)
Bektas, T., Erdogan, G., Ropke, S.: Formulations and Branch-and-Cut Algorithms for the Generalized Vehicle Routing Problem. To appear in Transportation Science (2011)
Corchado, E., Arroyo, A., Tricio, V.: Soft computing models to identify typical meteorological days. Logic Journal of thel IGPL (2010), doi:10.1093/jigpal/jzq035
Ghiani, G., Improta, G.: An efficient transformation of the generalized vehicle routing problem. European Journal of Operational Research 122, 11–17 (2000)
Fischetti, M., Salazar, J.J., Toth, P.: A branch-and-cut algorithm for the symmetric generalized traveling salesman problem. Operations Research 45, 378–394 (1997)
Moccia, L., Cordeau, J-F., Laporte, G.: An incremental neighbourhood tabu search heuristic for the generalized vehicle routing problem with time windows. Technical Report (2010), https://www.cirrelt.ca/DocumentsTravail/CIRRELT-2010-12.pdf
Pop, P.C.: The Generalized Minimum Spanning Tree Problem. PhD thesis, University of Twente, The Netherlands (2002)
Pop, P.C., Pintea, C., Zelina, I., Dumitrescu, D.: Solving the Generalized Vehicle Routing Problem with an ACS-based Algorithm. American Institute of Physics 1117, 157–162 (2009)
Pop, P.C., Matei, O., Pop Sitar, C., Chira, C.: A genetic algorithm for solving the generalized vehicle routing problem. In: Corchado, E., Graña Romay, M., Manhaes Savio, A. (eds.) HAIS 2010. LNCS (LNAI), vol. 6077, pp. 119–126. Springer, Heidelberg (2010)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Pop, P., Matei, O., Valean, H. (2011). An Efficient Hybrid Soft Computing Approach to the Generalized Vehicle Routing Problem. In: Corchado, E., Snášel, V., Sedano, J., Hassanien, A.E., Calvo, J.L., Ślȩzak, D. (eds) Soft Computing Models in Industrial and Environmental Applications, 6th International Conference SOCO 2011. Advances in Intelligent and Soft Computing, vol 87. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-19644-7_30
Download citation
DOI: https://doi.org/10.1007/978-3-642-19644-7_30
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-19643-0
Online ISBN: 978-3-642-19644-7
eBook Packages: EngineeringEngineering (R0)