Hybrid Genetic Search meta-heuristic example

The meta-heuristic used is vidalt/HGS-CVRP: Modern implementation of the hybrid genetic search (HGS) algorithm specialized to the capacitated vehicle routing problem (CVRP). This code also includes an additional neighborhood called SWAP*.

HGS-CVRP can only produce radial topologies. Since a radial topology is a special case of the branched topology, solutions produced by this method can be used to warm-start both branched- and radial-topology models.

If a routeset is desired, use PathFinder.

from optiwindnet.importer import load_repository
from optiwindnet.svg import svgplot
from optiwindnet.baselines.hgs import hgs_cvrp
from optiwindnet.mesh import make_planar_embedding
from optiwindnet.pathfinding import PathFinder
from optiwindnet.interarraylib import G_from_S, as_normalized

Load Hornsea

locations = load_repository()

L = locations.hornsea
svgplot(L)

Optimize Hornsea

P, A = make_planar_embedding(L)
S = hgs_cvrp(as_normalized(A), capacity=7, time_limit=0.5)
print(S.graph['solution_time'])
G = G_from_S(S, A)
svgplot(G)

(0.12, 0.1, 0.15)

Route the feeders so as to avoid crossings

H = PathFinder(G, P, A).create_detours()
svgplot(H)

Check the HGS-CVRP log

There are two alternatives to see the HGS log:

1. Store it in the solution object (must wait until HGS has finished)

2. Stream it using a callback function that gets one line per call

L = locations.meerwind
P, A = make_planar_embedding(L)

Store the log

S = hgs_cvrp(
    as_normalized(A),
    capacity=7,
    time_limit=0.5,
    keep_log=True,
)

print(S.graph['method_log'])

----- FLEET SIZE WAS NOT SPECIFIED: DEFAULT INITIALIZATION TO 18 VEHICLES
----- INSTANCE SUCCESSFULLY LOADED WITH 80 CLIENTS AND 18 VEHICLES
----- BUILDING INITIAL POPULATION
----- STARTING GENETIC ALGORITHM
It      0      2 | T(s) 0.05 | Feas 60 11.16 11.32 | NO-INFEASIBLE | Div 0.42 -1.00 | Feas 1.00 1.00 | Pen 5.81 0.85
It    500    160 | T(s) 0.19 | Feas 27 11.02 11.14 | NO-INFEASIBLE | Div 0.41 -1.00 | Feas 1.00 1.00 | Pen 2.58 0.38
It   1000      8 | T(s) 0.32 | Feas 35 11.02 11.08 | NO-INFEASIBLE | Div 0.33 -1.00 | Feas 1.00 1.00 | Pen 1.14 0.17
It   1500    249 | T(s) 0.47 | Feas 42 11.02 11.08 | Inf 3 11.62 11.71 | Div 0.33 0.40 | Feas 0.97 1.00 | Pen 0.51 0.10
----- GENETIC ALGORITHM FINISHED AFTER 1604 ITERATIONS. TIME SPENT: 0.500326

Stream the log

S = hgs_cvrp(
    as_normalized(A),
    capacity=7,
    time_limit=0.5,
    log_callback=(lambda line: print(line, end='')),
)

----- FLEET SIZE WAS NOT SPECIFIED: DEFAULT INITIALIZATION TO 18 VEHICLES
----- INSTANCE SUCCESSFULLY LOADED WITH 80 CLIENTS AND 18 VEHICLES
----- BUILDING INITIAL POPULATION
----- STARTING GENETIC ALGORITHM
It      0      2 | T(s) 0.05 | Feas 60 11.15 11.35 | NO-INFEASIBLE | Div 0.43 -1.00 | Feas 1.00 1.00 | Pen 5.81 0.85
It    500    277 | T(s) 0.18 | Feas 27 11.02 11.15 | NO-INFEASIBLE | Div 0.41 -1.00 | Feas 1.00 1.00 | Pen 2.58 0.38
It   1000    777 | T(s) 0.31 | Feas 35 11.02 11.08 | NO-INFEASIBLE | Div 0.33 -1.00 | Feas 1.00 1.00 | Pen 1.14 0.17
It   1500   1277 | T(s) 0.47 | Feas 40 11.02 11.10 | Inf 6 11.59 11.74 | Div 0.37 0.36 | Feas 0.95 1.00 | Pen 0.51 0.10
----- GENETIC ALGORITHM FINISHED AFTER 1608 ITERATIONS. TIME SPENT: 0.500064

print(S.graph['solution_time'])
G = G_from_S(S, A)
svgplot(G)

0.500064