Table 7‑2 provides a brief list of some of the key (optimisation) problems that are encompassed within our use of the term “network analysis”. Solutions for many important practical problems are built upon these core optimisation problems and the various procedures (algorithms) applied to them. Examples include: the production of optimal routing and vehicle loading plans; multi-modal transport problems; identification of drive-time 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 real-time environments if they are fast enough. Many heuristics involve some form of local search or swapping (interchange) procedure. So-called 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 travelling 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), 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 optimise — 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 behavioural models (such as insect-based analogies) that have been shown to be effective in providing heuristics for some particularly difficult problems.

Many of the problems we describe can be modelled using one or more linear equations combined with a number of associated constraint expressions specified as equalities and/or inequalities. This form of standardised representation enables different problems to be compared within the discipline of the spatial sciences and across the broad discipline of optimisation as a whole. In addition it enables many problems to be expressed in a form that is suitable for submission to specialised optimisation packages such as LEDA, CPLEX, LP‑solve and Xpress-MP. These provide source code sets and/or compiled libraries that offer optimal or heuristic solutions to a wide range of optimisation 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 LP-solve 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 minimum-cost 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 (one-way) or undirected (two-way). 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 well-known network problems, including shortest path problems, maximum flow problems, and certain assignment problems, can also be modelled 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 optimisation 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 modelled 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 NP-hard or NP-complete problems in the terminology of computational complexity theory (see Section 7.1.4 for more details).