262
A. Riccardi et al.
then linked by paths along which feasible solutions are searched. The main goal of
Scatter search is to diversify the set of solutions and not improving the incumbent.
The Octahedral Neighbourhood Enumeration (OCTANE) search is a heuristic
for BPs based on a ray shooting algorithm starting at the LP-optimum and hitting
the facets of the octahedron dual to the unit hypercube [94].
In more recent years, some large neighbourhood search heuristics have been presented, such as the local branching [92] and the relaxation Induced Neighborhood
Search (Rins) [95].
7.3.3 Network Optimisation
Network optimisation is a special type of linear programming, where variables
are represented as flows in a network. Many real practical problems can be
formulated as a ‘network optimisation’ problem, most commonly very large
problems including the study of traffic, train and population flow, distribution
analysis and communication problems. Consequently, many optimisation nonspecialists understand the importance of these optimisation algorithms, which led
to the widespread use of network optimisation in the testing and devising of new
theories. This problem-solving method can be used to solve a series of combinatorial
problems, for example [96, 97]:
• Space-time networks [98]
– Traffic flow simulating, airline scheduling [85]
• Physical networks
– Designing of streets and pipelines [99] to best manage flow
• Route networks
– Vehicle route flows, map route optimisation (e.g. bus routes) [100]
• Constructing matches
– Bipartite matching, survey design
Please note that problems such as TSP, VRP and scheduling may be represented
using a network, but that does not mean they are network optimisation problems.
Network optimisation is still LP and does not contain any integer variables; then the
problems can be solved very effectively.
Standard Network Flow Formulation and Notation
A typical ‘network’ is a series of nodes (or vertices) connected by arcs (or edges),
where each node is associated with a new design value and each arc is associated
A. Riccardi et al.
then linked by paths along which feasible solutions are searched. The main goal of
Scatter search is to diversify the set of solutions and not improving the incumbent.
The Octahedral Neighbourhood Enumeration (OCTANE) search is a heuristic
for BPs based on a ray shooting algorithm starting at the LP-optimum and hitting
the facets of the octahedron dual to the unit hypercube [94].
In more recent years, some large neighbourhood search heuristics have been presented, such as the local branching [92] and the relaxation Induced Neighborhood
Search (Rins) [95].
7.3.3 Network Optimisation
Network optimisation is a special type of linear programming, where variables
are represented as flows in a network. Many real practical problems can be
formulated as a ‘network optimisation’ problem, most commonly very large
problems including the study of traffic, train and population flow, distribution
analysis and communication problems. Consequently, many optimisation nonspecialists understand the importance of these optimisation algorithms, which led
to the widespread use of network optimisation in the testing and devising of new
theories. This problem-solving method can be used to solve a series of combinatorial
problems, for example [96, 97]:
• Space-time networks [98]
– Traffic flow simulating, airline scheduling [85]
• Physical networks
– Designing of streets and pipelines [99] to best manage flow
• Route networks
– Vehicle route flows, map route optimisation (e.g. bus routes) [100]
• Constructing matches
– Bipartite matching, survey design
Please note that problems such as TSP, VRP and scheduling may be represented
using a network, but that does not mean they are network optimisation problems.
Network optimisation is still LP and does not contain any integer variables; then the
problems can be solved very effectively.
Standard Network Flow Formulation and Notation
A typical ‘network’ is a series of nodes (or vertices) connected by arcs (or edges),
where each node is associated with a new design value and each arc is associated