Kevin M. Curtin (George Mason University, USA)
DOI: 10.4018/978-1-4666-2038-4.ch005
OnDemand PDF Download:


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.
Chapter Preview

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.

Complete Chapter List

Search this Book: