Overview - network and locational analysis

Navigation:  Network and Location Analysis > Key Problems in Network and Location Analysis >

Overview - network and locational analysis

Previous pageReturn to chapter overviewNext page

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; 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 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 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 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 Xpress-MP. 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 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 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 NP-hard or NP-complete 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). NP-complete (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 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 2nd, 3rdnth 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)

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 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 minimize 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 generalized 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 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 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-plowing, postal deliveries, meter reading, garbage collection etc. The capacitated version of the problem is known as CARP. NP-complete

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 p-median problem). Minimization of maximum distance or time is known as a p-center 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-center problems are NP-hard

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 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 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 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

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 purpose-built 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 one-way 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.orms-today.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

Real-time 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.orms-today.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 small-scale problems, such as the approach to intersections or traffic lights, or larger problems such as urban- and regional-scale modeling. Tools to support such modeling are sometimes grouped by scale into macro-, meso- and micro-scale classifications. At the micro-scale application-specific simulation software tends to be employed, rather than generic Cellular Automata (CA) or Agent-based 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 multi-mode traffic flows at a range of scales. The principal packages include: TSIS-CORSIM and SIMTraffic (extensively used for micro-simulation 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 so-called 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 left-turning 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 color-coded according to occupancy, flow, density, speed or count.

Figure 7‑2 Visualization of lane/movement simulation (Dynameq)

clip0351

Many of these traffic and transport software packages provide a wide range of facilities, from small to large-scale modeling and forecasting, and providing sophisticated 2D and increasingly, 3D-style 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 pre-specified (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 decision-making 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/multi-objective

In most instances single-objective solutions are sought (e.g. time, distance or cost minimization). However, real-world situations are almost always multi-objective. 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 multi-objective 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 call-out vehicles; individual paramedics on-call; and ambulances for non-emergency 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 pre-requisite for locating facilities at the next (e.g. large-scale 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 multi-level 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)