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). NP-complete (see further, Section 7.1.4)

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 minimises a pre-defined 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 2^nd, 3^rd… n^th 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 co-located 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. NP-complete (for both Euclidean and Manhattan metrics)

Travelling 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 pre-specified and the vertices are not necessarily assumed to lie on a pre-existing network. If certain nodes must be visited before others, the task is known as a sequential ordering problem (SOP). NP-complete

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 minimise the overall length of the tours, subject to the constraints. There are many variants of this problem, notably those in which there are pre-defined 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 generalised rather than fixed. Most such problems are classified as NP-hard

Transportation problem, Trans-shipment 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 minimised 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 generalisation of the transportation problem is the trans-shipment problem. In the latter case flows from sources to targets can go via trans-shipment 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, snow-ploughing, postal deliveries, meter reading, garbage collection etc. The capacitated version of the problem is known as CARP. NP-complete

Facility location: p‑median/p‑centre/ 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 minimisation of total (or average) travel cost/time to or from customers (the p-median problem). Minimisation of maximum distance or time is known as a p-centre 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 p-median 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 free-space median location problem — a form of location-allocation task whereby facilities are located and customers are allocated to facilities. The p-median and p-centre problems are NP-hard

Objective function

How do we measure the “length" of a path? Options include the Euclidean length, L_p 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 2D-space, 3D-space, 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 off-road vehicular modelling 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). 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 (2^nd, 3^rd 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 real-world 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 on-line, using some kind of sensor? Typically the geometry is known (map-able) in advance, but flows or events may not be