A new efficient transformation of the generalized vehicle routing problem into the classical vehicle routing problem

Yugoslav Journal of Operations Research
Volume 21, Issue 2, 2011, Pages 187-198

Pop, P., Pop Sitar, C.

Department of Mathematics and Computer Science, North University of Baia Mare, Romania
Romanian Academy, Iasi Branch, Romania

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.

Author keywords
Combinatorial optimization; Efficient transformations; Generalized combinatorial optimization problems; Integer programming.