Overview
ALNS customization
You will learn how to use the Operators, Acceptor and Threads options with a practical example.
The router engine relies on the ALNS heuristic to solve a routing problem. The underlying solver of the
router is hybrid, meaning it is composed of Decision Diagram (DD) and ALNS solvers. The ALNS solvers also use DDs to find a feasible solution. After feasible solutions are encountered, ALNS is activated to search for the best solution in the time alloted. To customize how ALNS is used in the router, the following options are provided:Operators: Sets the ALNS operators used. An operator is a tuple of a Destroyer and a Repairer. The Destroyer is used to "destroy" a solution state, so that it is often not feasible anymore. The Repairer takes this state and repairs it so that it represents a feasible solution. New operators can either be appended to the existing default operators or replace the default operators entirely.Acceptor: Sets the acceptance criterion that decides whether a candidate is accepted as the new current best state.Threads: Sets the number of threads that the hybrid solver uses. If the number is one, it means that only the first solver is used, which corresponds to pure DD. As a default, threads are calculated based on the number of machine processors
Example
The aim of this example is to briefly show how you can interact with the configuration of the ALNS heuristic. The introductory router example is used as a base, where routes are created to visit seven landmarks in Kyoto using one vehicle. The number of threads are specified as part of the input.
alns-input
Save the following information in an
input.json file (see input and output for more information on working with input files).JSON
1
{
2
"stops": [
3
{
4
"id": "Fushimi Inari Taisha",
5
"position": { "lon": 135.772695, "lat": 34.967146 }
6
},
7
{
8
"id": "Kiyomizu-dera",
9
"position": { "lon": 135.78506, "lat": 34.994857 }
10
},
11
{
12
"id": "Nijō Castle",
13
"position": { "lon": 135.748134, "lat": 35.014239 }
14
},
15
{
16
"id": "Kyoto Imperial Palace",
17
"position": { "lon": 135.762057, "lat": 35.025431 }
18
},
19
{
20
"id": "Gionmachi",
21
"position": { "lon": 135.775682, "lat": 35.002457 }
22
},
23
{
24
"id": "Kinkaku-ji",
25
"position": { "lon": 135.728898, "lat": 35.039705 }
26
},
27
{
28
"id": "Arashiyama Bamboo Forest",
29
"position": { "lon": 135.672009, "lat": 35.017209 }
30
}
31
],
32
"vehicles": ["v1"],
33
"threads": 3
34
}
Copied!
Code
The following program uses the CLI Runner to obtain a solution and requires access to the Nextmv code repository on GitHub. To request access, please contact [email protected].
To proceed with running the example, create a
main.go file and use the code snippet below.Note that the
Operators, Acceptor and Threads options are used simultaneously. A DestroySwap operator is used as a Destroyer and solutions for the Repairer are limited to one. Additionally, a Hill acceptor is used.Go
1
package main
2
3
import (
4
"github.com/nextmv-io/code/engines/route"
5
vehicleEngine "github.com/nextmv-io/code/engines/route/vehicle"
6
"github.com/nextmv-io/code/hop/model"
7
"github.com/nextmv-io/code/hop/run/cli"
8
"github.com/nextmv-io/code/hop/solve"
9
"github.com/nextmv-io/code/hop/solve/alns"
10
)
11
12
// Struct to read from JSON in.
13
type input struct {
14
Stops []route.Stop `json:"stops,omitempty"`
15
Vehicles []string `json:"vehicles,omitempty"`
16
Threads int `json:"threads,omitempty"`
17
}
18
19
// Use the CLI runner to solve a Vehicle Routing Problem.
20
func main() {
21
f := func(i input, opt solve.Options) (solve.Solver, error) {
22
// Custom ALNS implementation
23
repairOptions := opt
24
repairOptions.Limits.Solutions = 1
25
operators := []alns.Operator{
26
{
27
Destroy: vehicleEngine.DestroySwap(),
28
Repair: vehicleEngine.Repair(repairOptions),
29
},
30
}
31
acceptor := alns.Hill(model.Minimize)
32
33
// Declare the router and its solver.
34
router, err := route.NewRouter(
35
i.Stops,
36
i.Vehicles,
37
// Do not append operators
38
route.Operators(operators, false),
39
route.Acceptor(acceptor),
40
route.Threads(i.Threads),
41
)
42
if err != nil {
43
return nil, err
44
}
45
46
return router.Solver(opt)
47
}
48
49
cli.Run(f)
50
}
Copied!
To execute the example, specify the path to the
input.json file using command-line flags and use jq to extract the solution state (see runners for more information on building and running programs).Bash
1
go run main.go -hop.runner.input.path input.json | jq .state
Copied!
Solution
The solution should look similar to this one:
JSON
1
{
2
"vehicles": [
3
{
4
"id": "v1",
5
"route": [
6
{
7
"id": "Arashiyama Bamboo Forest",
8
"position": {
9
"lon": 135.672009,
10
"lat": 35.017209
11
}
12
},
13
{
14
"id": "Kinkaku-ji",
15
"position": {
16
"lon": 135.728898,
17
"lat": 35.039705
18
}
19
},
20
{
21
"id": "Nijō Castle",
22
"position": {
23
"lon": 135.748134,
24
"lat": 35.014239
25
}
26
},
27
{
28
"id": "Kyoto Imperial Palace",
29
"position": {
30
"lon": 135.762057,
31
"lat": 35.025431
32
}
33
},
34
{
35
"id": "Gionmachi",
36
"position": {
37
"lon": 135.775682,
38
"lat": 35.002457
39
}
40
},
41
{
42
"id": "Kiyomizu-dera",
43
"position": {
44
"lon": 135.78506,
45
"lat": 34.994857
46
}
47
},
48
{
49
"id": "Fushimi Inari Taisha",
50
"position": {
51
"lon": 135.772695,
52
"lat": 34.967146
53
}
54
}
55
],
56
"route_duration": 1818
57
}
58
]
59
}
Copied!
You can see that the stops are assigned in a fashion that minimizes the route distance.
alns-output
Last modified 2mo ago