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. | Yugoslav Journal of Operations Research 21 (2011), Number 2, 187-198 DOI: A NEW EFFICIENT TRANSFORMATION OF THE GENERALIZED VEHICLE ROUTING PROBLEM INTO THE CLASSICAL VEHICLE ROUTING PROBLEM Petrica POP Department of Mathematics and Computer Science, North University of Baia Mare, Romania Corina POP SITAR Fellow of Romanian Academy, Iasi Branch, Romania sitarcorina@ Received: September 2009 / Accepted: September 2011 Abstract: 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. Keywords: Combinatorial optimization, efficient transformations, generalized combinatorial optimization problems, integer programming. MCN: 90C27, 90C10, 68M10. 188 P. Pop, C. Pop Sitar / A New Efficient Transformation 1. INTRODUCTION Combinatorial optimization is a branch of optimization; its domain is optimization problems where the set of feasible solutions is discrete or can be reduced to a discrete one, and
