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.13, 0.11, 0.29)

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.12 11.35 | NO-INFEASIBLE | Div 0.45 -1.00 | Feas 1.00 1.00 | Pen 5.81 0.85
It    500    225 | T(s) 0.18 | Feas 27 11.02 11.10 | NO-INFEASIBLE | Div 0.36 -1.00 | Feas 1.00 1.00 | Pen 2.58 0.38
It   1000    725 | T(s) 0.31 | Feas 35 11.02 11.11 | NO-INFEASIBLE | Div 0.38 -1.00 | Feas 1.00 1.00 | Pen 1.14 0.17
It   1500   1225 | T(s) 0.46 | Feas 40 11.02 11.10 | Inf 4 11.61 11.79 | Div 0.38 0.40 | Feas 0.97 1.00 | Pen 0.51 0.10
----- GENETIC ALGORITHM FINISHED AFTER 1625 ITERATIONS. TIME SPENT: 0.50001

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.19 11.33 | NO-INFEASIBLE | Div 0.44 -1.00 | Feas 1.00 1.00 | Pen 5.81 0.85
It    500     43 | T(s) 0.18 | Feas 27 11.02 11.12 | NO-INFEASIBLE | Div 0.38 -1.00 | Feas 1.00 1.00 | Pen 2.58 0.38
It   1000    543 | T(s) 0.31 | Feas 35 11.02 11.09 | NO-INFEASIBLE | Div 0.35 -1.00 | Feas 1.00 1.00 | Pen 1.14 0.17
It   1500   1043 | T(s) 0.47 | Feas 43 11.02 11.10 | Inf 2 11.70 11.80 | Div 0.36 0.59 | Feas 0.98 1.00 | Pen 0.51 0.10
----- GENETIC ALGORITHM FINISHED AFTER 1602 ITERATIONS. TIME SPENT: 0.500113

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

0.18