A method and apparatus for grooming traffic demands according to mileage
based tariffs. An Integer Linear Program (ILP) that captures the traffic
grooming problem is defined, and such a linear program can in principle
be solved by conventional linear program application systems which are
fully familiar to those of ordinary skill in the art. However, the time
required to solve such an ILP is fairly large, even for the moderately
sized networks we are interested in. That is, there are many possible
routes to consider, and hence many integer variables in the ILP.
Therefore, further in accordance with the principles of the present
invention, the ILP is advantageously run on the Delaunay Triangulation of
the network rather than on the completely connected network graph.