A new efficient transformation of the generalized vehicle routing problem into the classical vehicle routing problem
DOI:
https://doi.org/10.2298/YJOR1102187PKeywords:
combinatorial optimization, efficient transformations, generalized combinatorial optimization problems, integer programmingAbstract
Classical combinatorial optimization problems can be generalized in a natural way by considering a related problem relative to a given partition of the nodes of the graph into node sets. In the literature one can find generalized problems such as: generalized minimum spanning tree, generalized traveling salesman problem, generalized Steiner tree problem, generalized vehicle routing problem, etc. These generalized problems typically belong to the class of NP-complete problems; they are harder than the classical ones, and nowadays are intensively studied due to their interesting properties and applications in the real world. Because of the complexity of finding the optimal or near-optimal solution in case of the generalized combinatorial optimization problems, great effort has been made, by many researchers, to develop efficient ways of their transformation into classical corresponding variants. We present in this paper an efficient way of transforming the generalized vehicle routing problem into the vehicle routing problem, and a new integer programming formulation of the problem.References
Araque, J.R., Kudva, G., Morin, T.L., and Pekny, J.K., “A branch and cut algorithm for vehicle routing problem”, Annals of Operations Research, 50 (1994) 37-59.
Baldacci, R., Bartolini, E., and Laporte, G., “Some applications of the Generalized Vehicle Routing Problem”, Le Cahiers du GERAD, G-2008-82, 2008.
Behzad, A., and Modarres, M., “A new efficient transformation of generalized traveling salesman problem into traveling salesman problem”, in: Proc. of the 15th International Conference of Systems Engineering, 2002, 6-8.
Dimitrijevic, D., and Saric, Z., “Efficient transformation of the generalized traveling Salesman problem into the traveling salesman problem on digraphs”, Information Sciences, 102 (1997) 65-110.
Feillet, D., Dejax, P., and Gendreau, M., “Traveling salesman problems with profits”, Transportation Science, 39 (2005) 188-205.
Ghiani, G., and Improta, G., “An efficient transformation of the generalized vehicle routing problem”, European Journal of Operational Research, 122 (2000) 11-17.
Hadjicharalambous, G., Pop, P.C., Pyrga, E., Tsaggouris, G., and Zaroliagis, C.D., “The railway traveling salesman problem”, Lecture Notes in Computer Science, 4359 (2007) 264-275.
Hu, B., Leitner, M., and Raidl, G., “Combining variable neighborhood search with integer linear programming for the generalized minimum spanning tree problem”, Journal of Heuristics, 14 (5) (2008) 473-499.
Hu, B., and Raidl, G., “Solving the railway traveling salesman problem via a transformation into the classical traveling salesman problem”, in: Proc. of the 8th International Conference on Hybrid Intelligent Systems, 2008, 73-78.
Kara, I., and Bektas, T., “Integer linear programming formulation of the generalized vehicle routing problem”, in: Proc. of the 5-th EURO/INFORMS Joint International Meeting, 2003.
Kara, I., and Pop, P.C., “New mathematical models of the generalized vehicle routing problem and extensions”, in: Proc. of the International Conference on Applied Mathematical Programming and Modelling, Bratislava, Slovakia, May 27-30, 2008.
Laporte, G., “What you should know about the Vehicle Routing Problem,” Naval Research Logistics, 54 (2007) 811-819.
Laporte, G., Asef-Vaziri, A., and Sriskandarajah, C., “Some applications of the generalized traveling salesman problem,” Journal of Operational Research Society, 47 (1996), 1461-1467.
Laporte, G., and Osman, I.H., “Routing problems: A bibliography,” Annals of Operations Research, 61 (1995) 227-262.
Lien, Y., Ma, E., and Wah, B.W., “Transformation of the generalized traveling salesman problem into the standard traveling salesman problem”, Information Sciences, 74 (1993) 177-189.
Oncan, T., Cardeau, J.-F., and Laporte, G., “A tabu search heuristic for the generalized minimum spanning tree problem”, European Journal of Operational Research, 191 (2008), 306-319.
Pintea, C.M., Dumitrescu, D., and Pop, P.C., “Combining heuristics and modifying local information to guide ant-based search”, Carpathian Journal of Mathematics, 24 (1) (2008) 94-103.
Pop, P.C., “A survey of different integer programming formulations of the generalized minimum spanning tree problem”, Carpathian Journal of Mathematics, 25 (1) (2009) 104-118.
Pop, P.C., Kern, W., and Still, G., “An approximation algorithm for the generalized minimum spanning tree problem with bounded cluster size,” Texts in Algorithms, 4 (2005) 115-122.
Pop, P.C., Kern, W., and Still, G., “A new relaxation method for solving the generalized minimum spanning tree problem”, European Journal of Operational Research, 170 (2006) 900-908.
Pop, P.C., Pintea, C.M., Zelina, I., and Dumitrescu, D., “Solving the generalized vehicle problem with an ACS-algorithm", American Institute of Physics, 1117 (2009) 157-162.
Pop, P.C., Pop Sitar, C., Zelina, I., and Tascu, I., “Exact algorithms for generalized combinatorial optimization problems”, Lecture Notes in Computer Science, 4616 (2007) 154-162.
Pop, P.C., Sabo, C., Pop Sitar, C., and Craciun, M., “A simulated annealing based approach for solving the generalized minimum spanning tree problem,” Creative Mathematics and Informatics, 16 (2007) 42-53.
Downloads
Published
Issue
Section
License
Copyright (c) 2011 YUJOR
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
