7 Introduction to Optimisation
263
with some category of moving value. To minimise unnecessary problem evaluations,
it is assumed that no points are part of any ‘self-loop’, and so an arc from one point
cannot lead back to the same point. A problem with many arcs and/or edges can be
categorised into one of three forms: ‘directed network’, where only arcs are present;
‘undirected network’, where only edges are present; or ‘mixed network’ if there is a
combination of arcs and edges [85]. In literature, arcs and edges are often considered
as the same entity, and, in the following, they will be generally referred to as lines.
This problem formulation can be optimised for different specific problem
requirements. This option to include specification of algorithm type allows for
maximisation of accuracy and efficiency, as per the NFL theorem. Problems best
suited for network optimisation include:
• Shortest path problem
– Shortest path problems are some of the most commonly encountered network
optimisation problems both in transportation and in communication.
• Maximum flow problem (as discussed)
– Find a feasible flow path from a single source to a single sink, such that the
flow is maximised.
• Minimum weight spanning tree
– This problem requires each node to connect to every other node. If the links
between nodes are expensive, it may be desirable to have each node connect
to only two other nodes.
This can be formulated mathematically by considering a graph or directed
network G = (N, A), where N is a series of nodes (otherwise known as ‘points’
or ‘vertices’) such that N = {1, 2, 3 . . . m} and A is a series of lines A =
{a 1 , a 2 , a 3 . . . a n } [96, 101], with a cost c i,j and a capacity associated with every
line or arc (i, j ) ∈ A. These problems can be shown pictorially by placing all nodes
and connecting lines on a plane, as can be seen in Fig. 7.2.
This problem can also be described mathematically using a graph. Unless
otherwise specified, it can be assumed that the edges are distinct such that if
a = (i, j ) then i = j , this would generate a ‘simple’ graph. Many network problems
can be formulated in this way, where N could be a set of locations, A a set of
Fig. 7.2 Visual
representation of a network
263
with some category of moving value. To minimise unnecessary problem evaluations,
it is assumed that no points are part of any ‘self-loop’, and so an arc from one point
cannot lead back to the same point. A problem with many arcs and/or edges can be
categorised into one of three forms: ‘directed network’, where only arcs are present;
‘undirected network’, where only edges are present; or ‘mixed network’ if there is a
combination of arcs and edges [85]. In literature, arcs and edges are often considered
as the same entity, and, in the following, they will be generally referred to as lines.
This problem formulation can be optimised for different specific problem
requirements. This option to include specification of algorithm type allows for
maximisation of accuracy and efficiency, as per the NFL theorem. Problems best
suited for network optimisation include:
• Shortest path problem
– Shortest path problems are some of the most commonly encountered network
optimisation problems both in transportation and in communication.
• Maximum flow problem (as discussed)
– Find a feasible flow path from a single source to a single sink, such that the
flow is maximised.
• Minimum weight spanning tree
– This problem requires each node to connect to every other node. If the links
between nodes are expensive, it may be desirable to have each node connect
to only two other nodes.
This can be formulated mathematically by considering a graph or directed
network G = (N, A), where N is a series of nodes (otherwise known as ‘points’
or ‘vertices’) such that N = {1, 2, 3 . . . m} and A is a series of lines A =
{a 1 , a 2 , a 3 . . . a n } [96, 101], with a cost c i,j and a capacity associated with every
line or arc (i, j ) ∈ A. These problems can be shown pictorially by placing all nodes
and connecting lines on a plane, as can be seen in Fig. 7.2.
This problem can also be described mathematically using a graph. Unless
otherwise specified, it can be assumed that the edges are distinct such that if
a = (i, j ) then i = j , this would generate a ‘simple’ graph. Many network problems
can be formulated in this way, where N could be a set of locations, A a set of
Fig. 7.2 Visual
representation of a network