Abstract
Routing is the act of selecting a course of travel. Routing problems are one of the most prominent and persistent problems in geoinformatics. This large research area has a strong theoretical foundation with ties to operations research and management science. There are a wide variety of routing models to fit many different application areas, including shortest path problems, vehicle routing problems, and the traveling salesman problem, among many others. There are also a range of optimal and heuristic solution procedures for solving instances of those problems. Research is ongoing to expand the types of routing problems that can be solved, and the environments within which they can be applied.
TopNetwork 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.
Key Terms in this Chapter
Network Design Problems: A set of combinatorially complex network analysis problems where routes across or flows through the network must be determined.
Traveling Salesman Problem: The most prominent problem in combinatorial optimization, defined as the routing problem where a hypothetical salesman must find the most efficient sequence of destinations in his territory, stopping only once at each, and end up at the initial starting location.
Routing: The act of selecting a course of travel.
Network: A connected set of edges and vertices.
Shortest Path Problem: The routing problem of finding the shortest—or least cost—path through a network.
Heuristics: Procedures for quickly finding good alternate—though not guaranteed optimal—solutions to routing problems.
Graph Theory: The mathematical discipline related to the properties of networks.