Premium
Robust routing and optimal partitioning of a traffic demand polytope
Author(s) -
BenAmeur Walid,
Żotkiewicz Mateusz
Publication year - 2011
Publication title -
international transactions in operational research
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.032
H-Index - 52
eISSN - 1475-3995
pISSN - 0969-6016
DOI - 10.1111/j.1475-3995.2010.00764.x
Subject(s) - hyperplane , polytope , routing (electronic design automation) , computer science , mathematical optimization , reservation , polytope model , vehicle routing problem , mathematics , combinatorics , computer network
In this paper we consider the problem of optimal partitioning of a traffic demand polytope using a hyperplane. In our model all possible demand matrices belong to a polytope. The polytope can be divided into parts, and different routing schemes can be applied while dealing with traffic matrices from different parts of the polytope. We consider three basic models: Robust‐Routing, No‐Sharing and Dynamic‐Routing . We apply two different partitioning strategies depending on whether the reservation vectors on opposite sides of the hyperplane are required to be identical, or allowed to differ. We provide efficient algorithms that solve these problems. Moreover, we prove polynomiality of some of the considered cases. Finally, we present numerical results proving the applicability of the introduced algorithms and showing differences between the routing strategies.