Value functions & state updates

Search…
You will learn how to use the Update option with a practical example.
The router engine uses decision diagrams to search for the best solution in the time alloted. Sometimes you may want to interact with state transitions to keep track of custom information. In particular, custom information may be used to calculate the value function to optimize. The router engine provides the Update option to:
Create a personalized value function.
Perform bookkeeping of custom data.
The router engine relies on the vehicle and fleet engines. Given this distinction, the Update option takes two arguments: VehicleUpdater and FleetUpdater interfaces, part of the router engine. You can specify custom types to implement these interfaces and personalize the state transitions in the underlying vehicle and fleet engines. The user-defined custom types that implement the interfaces will be marshalled to be part of the output. To achieve efficient customizations, always try to update the components of the state that changed, as opposed to the complete state in both the vehicle and fleet engines.
To customize the value function that will be optimized by each engine, the integer return value from the Update method in either interface must not be nil. If the value is nil, the default value is used and it corresponds to the configured measure.
The Update option is often used together with the Sorter option.
Example
The router example is used as a base, where routes are created to visit seven landmarks in Kyoto using two vehicles. This time, custom data is updated and a personalized value function is used. A custom type is used to save the locations, which map a stop's ID to its index in the corresponding route. The value function is modified to apply a score which is different for each vehicle.
update-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", "v2"],
33
  "score": { "v1": 10, "v2": 1 }
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 following code snippets. A custom type called vehicleData is defined to keep track of the aforementioned locations at the vehicle engine level.
Go
1
// Custom data to implement the VehicleUpdater interface.
2
type vehicleData struct {
3
    // immutable input data
4
    stops []route.Stop
5
    score map[string]int
6
    // mutable data
7
    Locations map[string]int `json:"locations,omitempty"`
8
}
Copied!
The vehicleData type implements the VehicleUpdater interface. Before updating the state, the Clone function is applied. This function is used to prepare the custom type before being updated. This is useful for clearing data. Note that the Update function returns a non-nil integer which corresponds to the vehicle's objective value. You can notice that the value is obtained by applying the vehicle's score. The locations attribute is updated for every state transition.
Go
1
// Reset locations before updating the vehicle state.
2
func (d vehicleData) Clone() route.VehicleUpdater {
3
    d.Locations = make(map[string]int)
4
    return d
5
}
6
​
7
// Track the index in the route for each stop. Customize value function to
8
// incorporate the vehicle's score.
9
func (d vehicleData) Update(s vehicleEngine.State) (route.VehicleUpdater, *int) {
10
    // Update a stop's route index.
11
    route := s.Route()
12
    for i := 1; i < len(route)-1; i++ {
13
        stop := d.stops[route[i]]
14
        d.Locations[stop.ID] = i
15
    }
16
    // Apply correct vehicle score to the objective value.
17
    vehicleID := s.Input().VehicleID.(string)
18
    value := s.Value() * d.score[vehicleID]
19
    return d, &value
20
}
Copied!
Similarly, a custom type called fleetData is defined to keep track of the locations at the fleet engine level.
Go
1
// Custom data to implement the FleetUpdater interface.
2
type fleetData struct {
3
    // immutable input data
4
    stops []route.Stop
5
    // mutable data
6
    Locations     map[string]int `json:"locations,omitempty"`
7
    vehicleValues map[string]int
8
    fleetValue    int
9
}
Copied!
The fleetData type implements the FleetUpdater interface. Before updating the state, the Clone function is applied. Note that the Update function returns a non-nil integer which corresponds to the sum of the vehicles' objective values. At each fleet state, only the modified vehicles are processed to calculate the total value. In a comparable way, the global locations type is updated based on the particular locations at each vehicle. To achieve this, the vehicle engine's state is cast to the Updater interface. Calling on the Updater() method returns the customized vehicle updater, which in this example is the vehicleData struct. There is no need to implement the Updater interface as it is done in the underlying vehicle engine. The locations attribute is updated for every state transition.
Go
1
// Reset global locations and vehicle state values before updating the fleet
2
// state.
3
func (d fleetData) Clone() route.FleetUpdater {
4
    // Deep copy locations stored on fleet state.
5
    locations := make(map[string]int, len(d.Locations))
6
    for stopdID, i := range d.Locations {
7
        locations[stopdID] = i
8
    }
9
    d.Locations = locations
10
    // Deep copy the data required for the value function.
11
    values := make(map[string]int, len(d.vehicleValues))
12
    for vehicleID, i := range d.vehicleValues {
13
        values[vehicleID] = i
14
    }
15
    d.vehicleValues = values
16
    return d
17
}
18
​
19
// Track the index of the route for each stop in each vehicle route. Customize
20
// value function to incorporate the custom vehicle engine's value.
21
func (d fleetData) Update(
22
    s fleetEngine.State,
23
    vehicles ...vehicleEngine.State,
24
) (route.FleetUpdater, *int) {
25
    for _, vehicle := range vehicles {
26
        // Update locations based on the changes made on the vehicle state.
27
        vehicleID := vehicle.Input().VehicleID.(string)
28
        updater := vehicle.(route.Updater).Updater().(vehicleData)
29
        for stopdID, i := range updater.Locations {
30
            d.Locations[stopdID] = i
31
        }
32
        // Update value function information.
33
        value := vehicle.Value()
34
        d.fleetValue -= d.vehicleValues[vehicleID]
35
        d.vehicleValues[vehicleID] = value
36
        d.fleetValue += d.vehicleValues[vehicleID]
37
    }
38
    // Remove unassigned locations.
39
    for it := s.Unassigned().Iterator(); it.Next(); {
40
        location := it.Value()
41
        stop := d.stops[location]
42
        delete(d.Locations, stop.ID)
43
    }
44
    return d, &d.fleetValue
45
}
Copied!
Lastly, using the above definitions, you can define your main function and execute the complete program.
Go
1
package main
2
​
3
import (
4
    "github.com/nextmv-io/code/engines/route"
5
    fleetEngine "github.com/nextmv-io/code/engines/route/fleet"
6
    vehicleEngine "github.com/nextmv-io/code/engines/route/vehicle"
7
    "github.com/nextmv-io/code/hop/run/cli"
8
    "github.com/nextmv-io/code/hop/solve"
9
)
10
​
11
// Custom data to implement the VehicleUpdater interface.
12
type vehicleData struct {
13
    // immutable input data
14
    stops []route.Stop
15
    score map[string]int
16
    // mutable data
17
    Locations map[string]int `json:"locations,omitempty"`
18
}
19
​
20
// Reset locations before updating the vehicle state.
21
func (d vehicleData) Clone() route.VehicleUpdater {
22
    d.Locations = make(map[string]int)
23
    return d
24
}
25
​
26
// Track the index in the route for each stop. Customize value function to
27
// incorporate the vehicle's score.
28
func (d vehicleData) Update(s vehicleEngine.State) (route.VehicleUpdater, *int) {
29
    // Update a stop's route index.
30
    route := s.Route()
31
    for i := 1; i < len(route)-1; i++ {
32
        stop := d.stops[route[i]]
33
        d.Locations[stop.ID] = i
34
    }
35
    // Apply correct vehicle score to the objective value.
36
    vehicleID := s.Input().VehicleID.(string)
37
    value := s.Value() * d.score[vehicleID]
38
    return d, &value
39
}
40
​
41
// Custom data to implement the FleetUpdater interface.
42
type fleetData struct {
43
    // immutable input data
44
    stops []route.Stop
45
    // mutable data
46
    Locations     map[string]int `json:"locations,omitempty"`
47
    vehicleValues map[string]int
48
    fleetValue    int
49
}
50
​
51
// Reset global locations and vehicle state values before updating the fleet
52
// state.
53
func (d fleetData) Clone() route.FleetUpdater {
54
    // Deep copy locations stored on fleet state.
55
    locations := make(map[string]int, len(d.Locations))
56
    for stopdID, i := range d.Locations {
57
        locations[stopdID] = i
58
    }
59
    d.Locations = locations
60
    // Deep copy the data required for the value function.
61
    values := make(map[string]int, len(d.vehicleValues))
62
    for vehicleID, i := range d.vehicleValues {
63
        values[vehicleID] = i
64
    }
65
    d.vehicleValues = values
66
    return d
67
}
68
​
69
// Track the index of the route for each stop in each vehicle route. Customize
70
// value function to incorporate the custom vehicle engine's value.
71
func (d fleetData) Update(
72
    s fleetEngine.State,
73
    vehicles ...vehicleEngine.State,
74
) (route.FleetUpdater, *int) {
75
    for _, vehicle := range vehicles {
76
        // Update locations based on the changes made on the vehicle state.
77
        vehicleID := vehicle.Input().VehicleID.(string)
78
        updater := vehicle.(route.Updater).Updater().(vehicleData)
79
        for stopdID, i := range updater.Locations {
80
            d.Locations[stopdID] = i
81
        }
82
        // Update value function information.
83
        value := vehicle.Value()
84
        d.fleetValue -= d.vehicleValues[vehicleID]
85
        d.vehicleValues[vehicleID] = value
86
        d.fleetValue += d.vehicleValues[vehicleID]
87
    }
88
    // Remove unassigned locations.
89
    for it := s.Unassigned().Iterator(); it.Next(); {
90
        location := it.Value()
91
        stop := d.stops[location]
92
        delete(d.Locations, stop.ID)
93
    }
94
    return d, &d.fleetValue
95
}
96
​
97
// Struct to read from JSON in.
98
type input struct {
99
    Stops    []route.Stop   `json:"stops,omitempty"`
100
    Vehicles []string       `json:"vehicles,omitempty"`
101
    Score    map[string]int `json:"score,omitempty"`
102
}
103
​
104
// Use the CLI runner to solve a Vehicle Routing Problem.
105
func main() {
106
    f := func(i input, opt solve.Options) (solve.Solver, error) {
107
        v := vehicleData{stops: i.Stops, score: i.Score}
108
        f := fleetData{stops: i.Stops}
109
        router, err := route.NewRouter(
110
            i.Stops,
111
            i.Vehicles,
112
            route.Update(v, f),
113
        )
114
        if err != nil {
115
            return nil, err
116
        }
117
​
118
        return router.Solver(opt)
119
    }
120
​
121
    cli.Run(f)
122
}
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
  "unassigned": [],
3
  "updater": {
4
    "locations": {
5
      "Arashiyama Bamboo Forest": 1,
6
      "Fushimi Inari Taisha": 1,
7
      "Gionmachi": 3,
8
      "Kinkaku-ji": 6,
9
      "Kiyomizu-dera": 2,
10
      "Kyoto Imperial Palace": 4,
11
      "Nijō Castle": 5
12
    }
13
  },
14
  "vehicles": [
15
    {
16
      "id": "v1",
17
      "route": [
18
        {
19
          "id": "Arashiyama Bamboo Forest",
20
          "position": {
21
            "lon": 135.672009,
22
            "lat": 35.017209
23
          }
24
        }
25
      ],
26
      "route_duration": 0
27
    },
28
    {
29
      "id": "v2",
30
      "route": [
31
        {
32
          "id": "Fushimi Inari Taisha",
33
          "position": {
34
            "lon": 135.772695,
35
            "lat": 34.967146
36
          }
37
        },
38
        {
39
          "id": "Kiyomizu-dera",
40
          "position": {
41
            "lon": 135.78506,
42
            "lat": 34.994857
43
          }
44
        },
45
        {
46
          "id": "Gionmachi",
47
          "position": {
48
            "lon": 135.775682,
49
            "lat": 35.002457
50
          }
51
        },
52
        {
53
          "id": "Kyoto Imperial Palace",
54
          "position": {
55
            "lon": 135.762057,
56
            "lat": 35.025431
57
          }
58
        },
59
        {
60
          "id": "Nijō Castle",
61
          "position": {
62
            "lon": 135.748134,
63
            "lat": 35.014239
64
          }
65
        },
66
        {
67
          "id": "Kinkaku-ji",
68
          "position": {
69
            "lon": 135.728898,
70
            "lat": 35.039705
71
          }
72
        }
73
      ],
74
      "route_duration": 1242
75
    }
76
  ]
77
}
Copied!
Please note that:
An updater object is marshalled as part of the output holding the information for the locations indicating the route position for each stop.
Most of the stops are assigned to the vehicle with the lowest score.
update-output
Measures (cost)
Route limits
Last modified 1mo ago
Export as PDF
Copy link
Contents
Example
Code
Solution