Overview
Minimize or Maximize
You will learn how to use the Minimize and Maximize options with a practical example.
Not every vehicle routing problem (VRP) is about minimizing time or distance. Sometimes, you want to maximize profit or another measure of your business. The router engine provides the
Minimize and Maximize options to configure the desired solver type to minimize or maximize the target value, respectively. As a default, the router uses minimization as its configuration.Example
The router example is used as a base, where routes are created to visit seven landmarks in Kyoto. This time, only one vehicle is used.
minimize-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
}
Copied!
Code
To minimize the total route distance, the same code from the base router example can be used, given that minimization is the default configuration. To maximize, you can run a different program.
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 maximization example, create a
main.go file and use the code snippet below.Go
1
package main
2
3
import (
4
"github.com/nextmv-io/code/engines/route"
5
"github.com/nextmv-io/code/hop/run/cli"
6
"github.com/nextmv-io/code/hop/solve"
7
)
8
9
// Struct to read from JSON in.
10
type input struct {
11
Stops []route.Stop `json:"stops,omitempty"`
12
Vehicles []string `json:"vehicles,omitempty"`
13
}
14
15
// Use the CLI runner to solve a Vehicle Routing Problem.
16
func main() {
17
f := func(i input, opt solve.Options) (solve.Solver, error) {
18
router, err := route.NewRouter(i.Stops, i.Vehicles, route.Maximize())
19
if err != nil {
20
return nil, err
21
}
22
23
return router.Solver(opt)
24
}
25
26
cli.Run(f)
27
}
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 for minimization (default or via the
Minimize option) 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!
minimize-output
The solution for maximization, using the program in the code snippet, should look similar to this:
JSON
1
{
2
"vehicles": [
3
{
4
"id": "v1",
5
"route": [
6
{
7
"id": "Nijō Castle",
8
"position": {
9
"lon": 135.748134,
10
"lat": 35.014239
11
}
12
},
13
{
14
"id": "Gionmachi",
15
"position": {
16
"lon": 135.775682,
17
"lat": 35.002457
18
}
19
},
20
{
21
"id": "Arashiyama Bamboo Forest",
22
"position": {
23
"lon": 135.672009,
24
"lat": 35.017209
25
}
26
},
27
{
28
"id": "Kiyomizu-dera",
29
"position": {
30
"lon": 135.78506,
31
"lat": 34.994857
32
}
33
},
34
{
35
"id": "Kinkaku-ji",
36
"position": {
37
"lon": 135.728898,
38
"lat": 35.039705
39
}
40
},
41
{
42
"id": "Fushimi Inari Taisha",
43
"position": {
44
"lon": 135.772695,
45
"lat": 34.967146
46
}
47
},
48
{
49
"id": "Kyoto Imperial Palace",
50
"position": {
51
"lon": 135.762057,
52
"lat": 35.025431
53
}
54
}
55
],
56
"route_duration": 4570
57
}
58
]
59
}
Copied!
maximize-output
You can notice that by using the
Maximize option, the route distance for a single vehicle is maximized to be the longest possible.Last modified 3mo ago