Network Analysis and Routing

Many of the most economically important GIS applications concern not areas or surfaces but networks: interconnected systems of roads, rivers, pipelines, or transit lines represented mathematically as a graph of nodes (intersections, stops) connected by edges (road segments, pipe sections), each typically weighted by a cost such as distance, travel time, or elevation change. Network analysis applies graph theory to answer practical questions over this structure: what is the shortest route between two points, which areas fall within a ten-minute drive of a hospital (a "service area" analysis), or how should a fleet of delivery vehicles be routed to visit a set of stops at minimum total cost, a classic instance of the traveling salesman problem.