Routing

Network Design Problems

The shortest path problem is just one of a class of related routing problems that can be described as network design problems. Network design problems require that some combination of the elements of a network (edges and vertices) be chosen in order to provide a route (or routes) through the network. This group includes the minimal spanning tree problem, the Steiner tree problem, the Traveling Salesman Problem, and the vehicle routing problem, among many others (Magnanti & Wong, 1984). The modeling of these problems frequently takes the form of integer programming models. Such models define an objective and a set of constraints. Solution procedures are applied that require decisions to be made that generate a route that optimizes the objective while respecting the constraints. Given the limited space in this forum, the following sections will focus on the modeling of two significant routing problems in an effort to demonstrate the characteristics of the general class. Vehicle Routing Problems are presented in order to discuss the range of possible objectives for routing problems, and the Traveling Salesman Problem is presented to demonstrate the formulation of the objectives and constraints.