Key problems in network analysis
Table 7‑2 provides a brief list of some of the key (optimization) problems that are encompassed within our use of the term “network analysis”. Solutions for many important practical problems are built upon these core optimization problems and the various procedures (algorithms) applied to them. Examples include: the production of optimal routing and vehicle loading plans; multimodal transport problems; identification of drivetime zones; network partitioning and territory definition; facility location on a network; and travel demand analysis. For selected problems exact solution methods exist, but in some cases these may require an excessive amount of time to complete. Commonly applied exact procedures include linear programming, in some instances augmented with cutting planes where an integer solution is required, branch and bound procedures, and dynamic programming. More details on many of these topics may be found in standard works on algorithms and complexity, for example Cormen et al. (2001) or Daskin (1995).
In many instances provably optimal solutions to key problems of certain sizes are not achievable and solutions based on heuristics that achieve near optimality in most cases are the norm. The majority of these solution procedures are essentially static, but they can be applied to more dynamic or realtime environments if they are fast enough. Many heuristics involve some form of local search or swapping (interchange) procedure. Socalled greedy algorithms make choices based on the progress of steps so far and selecting the next step by choosing the local optimum in the hope of reaching the global optimum, rather than seeking a global optimum directly (e.g. by exhaustive search). A typical example would be attempting to find the shortest tour of a set of cities (a traveling salesman problem) by selecting one city at random as the start point and then selecting the next location to visit by choosing the closest city. The resulting tour will visit all the cities but will almost always be suboptimal. Some greedy algorithms, such as Dijkstra’s procedure for finding shortest paths through a network (see Section 7.3.4, Shortest (network) path problems), always yield exact (optimal) solutions. Interchange heuristics involve swapping one or more components in a current solution, thus changing the order or arrangement of the solution. If the objective function — the value we are trying to optimize — improves, the new arrangement is retained and the process proceeds to further interchanges according to some rule.
Tabu search methods are increasingly used in heuristic algorithms that adopt local searching. The term tabu (taboo) refers to the exclusion of certain options (e.g. adding or dropping a link in a network) based on options that have been recently searched. This has the effect of increasing the range of local searches and thus reducing the risk of solutions being trapped in local optima. There are several related methods such as simulated annealing, genetic algorithms and behavioral models (such as insectbased analogies) that have been shown to be effective in providing heuristics for some particularly difficult problems.
Many of the problems we describe can be modeled using one or more linear equations combined with a number of associated constraint expressions specified as equalities and/or inequalities. This form of standardized representation enables different problems to be compared within the discipline of the spatial sciences and across the broad discipline of optimization as a whole. In addition it enables many problems to be expressed in a form that is suitable for submission to specialized optimization packages such as LEDA, CPLEX, LP‑solve and XpressMP. These provide source code sets and/or compiled libraries that offer optimal or heuristic solutions to a wide range of optimization problems, including linear programming (LP) and mixed integer programming (MIP) tasks. However, many algorithms for solving networking problems do not use linear programming or related techniques as these may be less efficient (i.e. slower) than specialized procedures, or the problems are not amenable to formulation as an LP or MIP problem. A good place to review such topics is the LPsolve website managed by Sourceforge:
http://lpsolve.sourceforge.net/5.5/
This site includes a useful Linear Programming FAQ page from which we have extracted the following explanatory quotation (with minor edits):
“In the context of linear programming, the term "network" is most often associated with the minimumcost network flow problem (MCFP — see Table 7‑2). A network for this problem is viewed as a collection of nodes (vertices or locations) and arcs (or edges or links) connecting selected pairs of nodes. Arcs carry a physical or conceptual flow of some kind, and may be directed (oneway) or undirected (twoway). Some nodes may be sources (permitting flow to enter the network) or sinks (permitting flow to leave).
The network linear programming problem is to minimize the (linear) total cost of flows along all arcs of a network, subject to conservation of flow at each node, and upper and/or lower bounds on the flow along each arc. This is a special case of the general linear programming problem. The transportation problem is an even more special case in which the network is bipartite: all arcs run from nodes in one subset to the nodes in a disjoint subset. A variety of other wellknown network problems, including shortest path problems, maximum flow problems, and certain assignment problems, can also be modeled and solved as network linear programs.
Network linear programs can be solved 10 to 100 times faster than general linear programs of the same size, by use of specialized optimization algorithms. Some commercial LP solvers include a version of the network simplex method for this purpose. That method has the nice property that, if it is given integer flow data, it will return optimal flows that are integral [have integer values]. Integer network LPs can thus be solved efficiently without resort to complex integer programming software.
Unfortunately, many different network problems of practical interest do not have a formulation as a network LP. These include network LPs with additional linear "side constraints" (such as multicommodity flow problems) as well as problems of network routing and design that have completely different kinds of constraints. In principle, nearly all of these network problems can be modeled as integer programs. Some "easy" cases can be solved much more efficiently by specialized network algorithms, however, while other "hard" ones are so difficult that they require specialized methods that may or may not involve some integer programming. “
A compendium of many problems of this type and the best known (approximation) algorithms for their solution can be found at:
http://www.nada.kth.se/~viggo/problemlist/
This website provides details for a very large range of problems for which checking that a result is optimal may be relatively simple, but for which finding such a solution may be extremely difficult (typically would take an extremely long time for any large problem). These are NPhard or NPcomplete problems in the terminology of computational complexity theory (see Section 7.1.4, Algorithms and computational complexity theory for more details).
Key problems in network analysis
The survey by Mitchell (1998, 2000) of geometrical shortest path and network optimization problems provides a further excellent source discussing such questions and solution procedures. Mitchell provides a useful summary of the range of questions that may be addressed by considering various associated parameters (Table 7‑3). There are also many online sources for guidance on conducting transport network analysis, for example the US Department of Transportation planning site: http://www.plan4operations.dot.gov, the US Transportation Research Board’s website: http://www.trb.org/, and the UK Transport Analysis Guidance (TAG) website: http://www.dft.gov.uk/webtag/.
Table 7‑2 Some key optimization problems in network analysis
Problem 
Description 

Hamiltonian circuit (HC) 
If a cycle exists from a given vertex that passes through every other vertex exactly once it is called a Hamiltonian circuit. Testing for the existence of Hamiltonian circuits in a graph is known as the Hamiltonian circuit problem (HCP). NPcomplete (see further, Section 7.1.4, Algorithms and computational complexity theory ) 
Eulerian circuit(EC) 
A circuit in a directed graph that visits every arc exactly once. A condition that a graph contains an Eulerian circuit is that the number of arcs arriving at every included vertex, i, must be the same as the number of arcs leaving vertex i 
Shortest path (SP) 
A path between two vertices that minimizes a predefined metric such as the total number of steps, total distance or time, is called a shortest path. Hence this term is relative to the metric applied and even then may not be unique for any given network. Determination of shortest paths is often described as shortest path analysis (SPA). This is perhaps the central computational problem in network analysis. There are many variants of this problem, including finding the 2nd, 3rd… nth shortest path, finding the shortest path from a given node to all other nodes, and finding the longest path. Can be solved in linear time or better 
Spanning tree (ST) 
Given a fixed set of vertices, find a set of edges such that every vertex is connected and the network contains no cycles. Many spanning trees are possible for a given vertex set 
Minimal spanning tree (MST) 
Find a (Euclidean) spanning tree of minimum total length. Typically this will be unique, but uniqueness is not guaranteed. Solvable in near linear time 
Steiner MST, Steiner tree 
As per the MST but with additional nodes permitted that are not colocated with the original vertex set. In the (spatially) constant cost model, each additional point (known as a Steiner point) will be placed intermediate to three existing vertices and will provide a connection between these via three branches that are equally spaced (i.e. at 120 degrees) about the Steiner point. Steiner points are added to the MST, replacing MST links, if the total network length is reduced by their inclusion. NPcomplete (for both Euclidean and Manhattan metrics) 
Traveling salesman problem (TSP) 
Given a set of vertices and symmetric or asymmetric distance matrix for each pair of vertices, find a Hamiltonian circuit of minimal length (cost). Typically the start location (vertex) is prespecified and the vertices are not necessarily assumed to lie on a preexisting network. If certain nodes must be visited before others, the task is known as a sequential ordering problem (SOP). NPcomplete 
Vehicle routing problem (VRP) 
This class of problems relates to servicing customer demand (e.g. deliveries of fuel to retail garages) from a single depot, where each vehicle may have a known capacity (CVRP). If capacity is not restricted the problem in known simply as a vehicle routing problem (VRP). The number of vehicles and the number of tours of subsets of nodes are variables. The customer locations, depot location and customer demand levels are assumed to be known. The problem is to minimize the overall length of the tours, subject to the constraints. There are many variants of this problem, notably those in which there are predefined time windows for deliveries, problems involving pickups and deliveries, problems involving a series of depots, problems where demand is dynamically variable, problems in which link capacity constraints exist and hence may become congested, and problems where customer locations are generalized rather than fixed. Most such problems are classified as NPhard 
Transportation problem, Transshipment problem 
The general problem of completely servicing a set of target locations with given demand levels from a set of source locations with given supply levels such that total costs are minimized is known as the transportation problem. The unit cost of shipping from each supply point to each demand point is a key input to this problem specification. This problem is an example of a Minimum Cost Flow Problem (MCFP). A generalization of the transportation problem is the transshipment problem. In the latter case flows from sources to targets can go via transshipment points, e.g. factories to warehouses to customers, rather than simply direct to customers 
Arc routing problem (ARP) 
Given a network (typically a street network or subset of a street network) find a route that completely traverses every edge, generally in both directions, that has the least cost (distance or time) subject to selected constraints (e.g. cost of turning). This problem applies to street cleaning, snowplowing, postal deliveries, meter reading, garbage collection etc. The capacitated version of the problem is known as CARP. NPcomplete 
Facility location: p‑median/p‑center/ coverage 
A collection of problems where the objective is to optimally locate one or more facilities within a network in order to satisfy customer requirements (demand, service level). The most commonly cited problem is minimization of total (or average) travel cost/time to or from customers (the pmedian problem). Minimization of maximum distance or time is known as a pcenter problem. A related set of problems seeks to ensure that all customers can be served within a fixed upper time or cost, or at least, as many as possible are served within a fixed time or cost. These are known as coverage problems. They are discussed in Daskin (1995, Ch 4) but are not explored further in this Guide, mainly because their very restrictive constraints tend to generate solutions that are too costly or ineffective to be implemented in practice. Customer demand is often assumed to be located at vertices in which case pmedian solutions for p facilities serving n>p customer sites will always result in the facilities being located at network vertices (although this solution may not be unique). It is the network equivalent of the plane or freespace median location problem — a form of locationallocation task whereby facilities are located and customers are allocated to facilities. The pmedian and pcenter problems are NPhard 
Table 7‑3 Sample network analysis problem parameters
Parameter 
Questions 

Objective function 
How do we measure the “length" of a path? Options include the Euclidean length, Lp length, link distance/time/cost etc. 
Constraints on the path 
Are we simply to get from point s to point t, or must we also visit other points or other regions along a path or cycle? 
Input geometry 
What types of obstacles or other entities are specified in the input map? 
Dimension of the problem 
Are we in 2Dspace, 3Dspace, or higher dimensions? Typically within GIS we only consider 2D, but transport networks may not be planar 
Type of moving object 
Are we moving a single point along the path, or is movement specified by some more complex geometry? In GIS offroad vehicular modeling is usually performed using Accumulated Cost Surface (ACS) or Distance Transform (DT) procedures applied to grid datasets rather than vector networks (see Section 4.4.2, Cost distance). Constraints on routes may also be applied to vehicles of particular sizes, types or weights (e.g. height restrictions) 
Single shot vs. repetitive mode queries 
Do we want to build an effective data structure for efficient queries? Many network problems involve very similar searches — for example determining an alternative route (2nd, 3rd best) 
Static vs. dynamic environments 
Do we allow obstacles to be inserted or deleted, or do we allow obstacles to be moving along known trajectories? Flow and event dynamics may also be important considerations 
Exact vs. approximate algorithms 
Are we content with an answer that is guaranteed to be within some small margin of optimal? Larger problems in many cases cannot be solved exactly in a finite amount of time. Ideally realworld problems should be solved to within a specified level of the optimum for suitably defined subset problems 
Known vs. unknown map 
Is the complete geometry of the map known in advance, or is it discovered online, using some kind of sensor? Typically the geometry is known (mapable) in advance, but flows or events may not be 
After Mitchell J S B (1998, 2000)
Network analysis software
Whilst some GIS packages, such as Caliper’s TransCAD and the ESRI ArcGIS Transportation Analytics option, include functionality designed to solve a wide range of network analysis and associated planning and modeling tasks, problems of this type are often addressed using a range of bespoke or specialized transportation and logistics software. Some of these, such as eRouteLogistics and RouteSmart are built on/integrate with GIS packages (ESRI software in these two examples), whilst many others are purposebuilt components of logistics systems, Enterprise Resource Planning (ERP) software or navigation suites. Examples include those from MJC2 (http://www.mjc2.com), and TruckStops.
Most of the latter class of software takes into account the many practical, real world constraints that must be incorporated in operational software. Examples (from the MJC2 product) include: vehicle routing taking oneway streets into account; trip routing taking restricted junctions into account; varying speeds by road type and time of day; trip routing of vehicles to avoid toll roads and toll bridges; trip routing vehicles taking account of congestion charges; delivery routing taking account of customer access constraints by time of day; night time/weekend lorry routing controls (e.g. the London 'brown' routes); weight restrictions (e.g. for truck routing); height restrictions (e.g. for truck routing); vehicle routing costs per mile/km; vehicle routing costs per hour; weight related vehicle routing costs; altitude related truck routing costs (e.g. trip routing to reduce hill climbing).
The annual review of packaged logistics software by OR/MS (the magazine of the Institute for Operations Research and Management Sciences in the USA) includes a selected list of providers for networking/routing software, with routing functionality as shown in Table 7‑4. Products highlighted with a yellow background are stated to have >100 customers. Note that this Table is by no means an exhaustive list and may not be entirely accurate – check with the individual suppliers for more detail. The latest (2014) survey can be found at:
http://www.ormstoday.org/surveys/Vehicle_Routing/vrss.html
Table 7‑4 Routing functionality in selected logistics software packages
Product 
GIS/Mapping support 
Routing Functions 


Node Routing 
Arc Routing 
Realtime Routing 
Daily Routing 
Route Planning & Analysis 

ArcLogistics 
Y 
Y 

Y 
Y 
Y 
Descartes 
Y 
Y 
Y 
Y 
Y 
Y 
DISC 
Y 
Y 
Y 
Y 
Y 
Y 
ILOG Dispatcher 
Y 
Y 
Y 

Y 

JOpt.SDK 

Y 
Y 

Y 
Y 
Optrak4 
Y 
Y 

Y 
Y 
Y 
Paragon 
Y 
Y 
Y 

Y 
Y 
Roadnet 
Y 

Y 
Y 
Y 
Y 
StreetSync 
Y 

Y 
Y 
Y 
Y 
TMW Appian Direct Route 
Y 
Y 
Y 

Y 
Y 
Truckstops 
Y 
Y 
Y 

Y 
Y 
Webstars 
Y 
Y 
Y 
Y 
Y 
Y 
Based on OR/MS Survey, 2012.http://www.ormstoday.org/surveys/Vehicle_Routing/vrss.html
In addition to software that focuses on routing and logistics, there are a very large number of packages that address traffic modeling and simulation. These may deal with smallscale problems, such as the approach to intersections or traffic lights, or larger problems such as urban and regionalscale modeling. Tools to support such modeling are sometimes grouped by scale into macro, meso and microscale classifications. At the microscale applicationspecific simulation software tends to be employed, rather than generic Cellular Automata (CA) or Agentbased Models (ABM) ― see, for example, Martin Treiber’s Java applet (accessible via http://www.mtreiber.de/) for a clear view of such microsimulation.
Widely used software packages exist for modeling single or multimode traffic flows at a range of scales. The principal packages include: TSISCORSIM and SIMTraffic (extensively used for microsimulation as well as more generic traffic modeling); Transmodeller (from Caliper, which can import data from CORSIM and SimTraffic); VISUM (produced by PTV, which they describe as a “comprehensive, flexible software system for transportation planning, travel demand modeling and network data management”); and INRO’s offerings: EMME (trip forecasting) and DYNAMEQ (microsimulation, providing socalled dynamic equilibrium modeling). Figure 7‑2 provides a visualization snapshot from a lane occupancy and movement simulation using DYNAMEQ. The warm colors show increased occupancy by lane where vehicles are queuing behind unprotected leftturning movements or traffic light signals. Intersection movements are colored similarly. Animated movement plots provide a more detailed breakdown of results that pinpoint the congestion. Each lane and turning movement can be colorcoded according to occupancy, flow, density, speed or count.
Figure 7‑2 Visualization of lane/movement simulation (Dynameq)
Many of these traffic and transport software packages provide a wide range of facilities, from small to largescale modeling and forecasting, and providing sophisticated 2D and increasingly, 3Dstyle visualizations. Many can import from and export data to a number of standard GIS packages, most commonly supporting ESRI and MapInfo vector file formats.
Key problems in location analysis
Daskin (1995, Ch.1) provides a useful taxonomy of and commentary on location problems and models. We have adapted and extended his taxonomy (Table 7‑5), in part using the work of Schietzelt and Densham (2003). Although Daskin’s focus is on network and discrete location problems, rather than the broader sweep of network design and planar problems, this summary does offer an insight into many of the practical problems that may be encountered.
Table 7‑5 Taxonomy of location analysis problems
Component 
Description 

Planar/network/discrete 
Planar — demand occurs anywhere in the plane (possibly represented by a deterministic or probabilistic field). Facilities may be located anywhere in the plane; Network — demand and facilities can only be located at network nodes or on links, and travel is restricted to the network; Discrete — nodes are fixed but the cost of travel between nodes is not determined by an underlying network 
Tree/graph 
Some network problems are amenable to treatment as if the graph is a tree, which can make solution far simpler 
Distance metric 
We have previously noted (Section 4.4.1, Metrics) that a variety of metrics can be used in spatial analysis and this applies equally to location problems, notably planar and discrete cases 
Facilities 
The number of facilities to locate can be prespecified (e.g. as p) or generated as part of the optimization process (as in the set coverage problem — see below). Problems involving the location of only one facility are often relatively straightforward to solve, and some procedures use this fact to develop heuristics that incrementally increase the number of facilities based on local optimization of the next facility added 
Static/dynamic 
Most of the problems and techniques described in this chapter are essentially static. Such methods may be applied to some dynamic problems, but in many cases these procedures require extension or alternative approaches to deal with dynamic cases. Examples include: choosing when as well as where to locate the next 1,2… facilities; incorporating dynamic demand and possibly supply into the model; modifying vehicle locations as demand varies by time of day or week (e.g. relocating emergency vehicles on standby based on time of day) 
Private/public 
The principal issue here relates to the definition of the objective function — can this be done in purely monetary (or equivalent) terms or do social, environmental and other factors require evaluation? Generally all location selection processes are part of a broader decisionmaking environment (as identified in the PPDAC model, Section 3.3). In public facilities location it is also often possible to dictate allocations whereas for private facilities this is almost never possible, requiring the modeling of allocation (e.g. using spatial interaction models) 
Single/multiobjective 
In most instances singleobjective solutions are sought (e.g. time, distance or cost minimization). However, realworld situations are almost always multiobjective. One approach to this is to compute multiple solutions for variations in parameters that reflect the multiple objectives, and examine the nature and robustness of these solutions. This is not equivalent to true multiobjective analysis but may provide benchmarks and guidance for such problems as part of a broader analytical framework 
Unique/diverse service 
A unique service is one in which a single (principal) service is being modeled, such as ambulance provision. A diverse service might be a similar problem, but where different categories of ambulance service and associated vehicles and staffing were modeled — for example, full emergency callout vehicles; individual paramedics oncall; and ambulances for nonemergency usage (e.g. transport of patients, medical supplies etc.) 
Elastic/inelastic demand 
Most models assume that demand and supply are independent. However, it must be recognized that improved supply frequently increases demand, i.e. that demand is elastic, and that supply may or may not be 
Deterministic/adaptive/ stochastic 
Many models are deterministic in terms of supply, demand and feasible solutions; others may assume demand is probabilistic and often dynamic, with solutions being sought that are optimal with respect to the inputs, but which are often adaptive reflecting changes in demand, supply and transport dynamics 
Capacitated/uncapacitated 
Basic models do not consider the capacity of facilities (e.g. warehouses, storage depots, hospitals, vehicles) or links (e.g. transport networks or pipelines) as a constraint. Tools are available that allow for the inclusion of such constraints (an example is provided in Section 7.3.5, Tours, traveling salesman problems and vehicle routing) 
Nearest facility/ General demand allocation 
Demand is often assumed to be allocated to the nearest facility. In capacitated models this may require that some demand is split between facilities (fractional allocation) — e.g. a retail store may need to be serviced by more than one warehouse, or patients may be sent to more distant hospitals in times of high demand or major emergencies 
Hierarchical/single level 
Some problems are intrinsically hierarchical, in that products or services are provided from larger centers (e.g. national) to smaller regional centers and on to district and local facilities (or vice versa, upwards flow rather than downwards distribution). This may apply for product or service offerings. In such problems the existence of facilities at one level (up or down) may be a prerequisite for locating facilities at the next (e.g. largescale regional hospitals are only provided where at least a certain number of local level medical facilities already exist). A similar example would be the design of a completely new multilevel health infrastructure for a region previously not served with these kinds of facility 
Desirable/undesirable 
Most location modeling relates to desirable facilities — the distance or cost of travel to or from facilities is to be minimized, according to some criterion. For some facilities, such as waste disposal sites, incinerators, nuclear power plants, etc. the facility location problem becomes more complex because there are often conflicting objectives. For example, the location of waste disposal sites need to be as near as possible to the waste creation points (towns say), but ideally as far away as possible from habitation 
After Daskin (1995) and Schietzelt and Densham (2003)