You are viewing Nextmv legacy docs. ⚡️ Go to latest docs ⚡️

Router

Update

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).

{
  "stops": [
    {
      "id": "Fushimi Inari Taisha",
      "position": { "lon": 135.772695, "lat": 34.967146 }
    },
    {
      "id": "Kiyomizu-dera",
      "position": { "lon": 135.78506, "lat": 34.994857 }
    },
    {
      "id": "Nijō Castle",
      "position": { "lon": 135.748134, "lat": 35.014239 }
    },
    {
      "id": "Kyoto Imperial Palace",
      "position": { "lon": 135.762057, "lat": 35.025431 }
    },
    {
      "id": "Gionmachi",
      "position": { "lon": 135.775682, "lat": 35.002457 }
    },
    {
      "id": "Kinkaku-ji",
      "position": { "lon": 135.728898, "lat": 35.039705 }
    },
    {
      "id": "Arashiyama Bamboo Forest",
      "position": { "lon": 135.672009, "lat": 35.017209 }
    }
  ],
  "vehicles": ["v1", "v2"],
  "score": { "v1": 10, "v2": 1 }
}
Copy

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 support@nextmv.io.

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.

// Custom data to implement the VehicleUpdater interface.
type vehicleData struct {
    // immutable input data
    stops []route.Stop
    score map[string]int
    // mutable data
    Locations map[string]int `json:"locations,omitempty"`
}
Copy

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.

// Reset locations before updating the vehicle state.
func (d vehicleData) Clone() route.VehicleUpdater {
    d.Locations = make(map[string]int)
    return d
}

// Track the index in the route for each stop. Customize value function to
// incorporate the vehicle's score.
func (d vehicleData) Update(s vehicleEngine.State) (route.VehicleUpdater, *int) {
    // Update a stop's route index.
    route := s.Route()
    for i := 1; i < len(route)-1; i++ {
        stop := d.stops[route[i]]
        d.Locations[stop.ID] = i
    }
    // Apply correct vehicle score to the objective value.
    vehicleID := s.Input().VehicleID.(string)
    value := s.Value() * d.score[vehicleID]
    return d, &value
}
Copy

Similarly, a custom type called fleetData is defined to keep track of the locations at the fleet engine level.

// Custom data to implement the FleetUpdater interface.
type fleetData struct {
    // immutable input data
    stops []route.Stop
    // mutable data
    Locations     map[string]int `json:"locations,omitempty"`
    vehicleValues map[string]int
    fleetValue    int
}
Copy

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.

// Reset global locations and vehicle state values before updating the fleet
// state.
func (d fleetData) Clone() route.FleetUpdater {
    // Deep copy locations stored on fleet state.
    locations := make(map[string]int, len(d.Locations))
    for stopdID, i := range d.Locations {
        locations[stopdID] = i
    }
    d.Locations = locations
    // Deep copy the data required for the value function.
    values := make(map[string]int, len(d.vehicleValues))
    for vehicleID, i := range d.vehicleValues {
        values[vehicleID] = i
    }
    d.vehicleValues = values
    return d
}

// Track the index of the route for each stop in each vehicle route. Customize
// value function to incorporate the custom vehicle engine's value.
func (d fleetData) Update(
    s fleetEngine.State,
    vehicles ...vehicleEngine.State,
) (route.FleetUpdater, *int) {
    for _, vehicle := range vehicles {
        // Update locations based on the changes made on the vehicle state.
        vehicleID := vehicle.Input().VehicleID.(string)
        updater := vehicle.(route.Updater).Updater().(vehicleData)
        for stopdID, i := range updater.Locations {
            d.Locations[stopdID] = i
        }
        // Update value function information.
        value := vehicle.Value()
        d.fleetValue -= d.vehicleValues[vehicleID]
        d.vehicleValues[vehicleID] = value
        d.fleetValue += d.vehicleValues[vehicleID]
    }
    // Remove unassigned locations.
    for it := s.Unassigned().Iterator(); it.Next(); {
        location := it.Value()
        stop := d.stops[location]
        delete(d.Locations, stop.ID)
    }
    return d, &d.fleetValue
}
Copy

Lastly, using the above definitions, you can define your main function and execute the complete program.

package main

import (
    "github.com/nextmv-io/code/engines/route"
    fleetEngine "github.com/nextmv-io/code/engines/route/fleet"
    vehicleEngine "github.com/nextmv-io/code/engines/route/vehicle"
    "github.com/nextmv-io/code/hop/run/cli"
    "github.com/nextmv-io/code/hop/solve"
)

// Custom data to implement the VehicleUpdater interface.
type vehicleData struct {
    // immutable input data
    stops []route.Stop
    score map[string]int
    // mutable data
    Locations map[string]int `json:"locations,omitempty"`
}

// Reset locations before updating the vehicle state.
func (d vehicleData) Clone() route.VehicleUpdater {
    d.Locations = make(map[string]int)
    return d
}

// Track the index in the route for each stop. Customize value function to
// incorporate the vehicle's score.
func (d vehicleData) Update(s vehicleEngine.State) (route.VehicleUpdater, *int) {
    // Update a stop's route index.
    route := s.Route()
    for i := 1; i < len(route)-1; i++ {
        stop := d.stops[route[i]]
        d.Locations[stop.ID] = i
    }
    // Apply correct vehicle score to the objective value.
    vehicleID := s.Input().VehicleID.(string)
    value := s.Value() * d.score[vehicleID]
    return d, &value
}

// Custom data to implement the FleetUpdater interface.
type fleetData struct {
    // immutable input data
    stops []route.Stop
    // mutable data
    Locations     map[string]int `json:"locations,omitempty"`
    vehicleValues map[string]int
    fleetValue    int
}

// Reset global locations and vehicle state values before updating the fleet
// state.
func (d fleetData) Clone() route.FleetUpdater {
    // Deep copy locations stored on fleet state.
    locations := make(map[string]int, len(d.Locations))
    for stopdID, i := range d.Locations {
        locations[stopdID] = i
    }
    d.Locations = locations
    // Deep copy the data required for the value function.
    values := make(map[string]int, len(d.vehicleValues))
    for vehicleID, i := range d.vehicleValues {
        values[vehicleID] = i
    }
    d.vehicleValues = values
    return d
}

// Track the index of the route for each stop in each vehicle route. Customize
// value function to incorporate the custom vehicle engine's value.
func (d fleetData) Update(
    s fleetEngine.State,
    vehicles ...vehicleEngine.State,
) (route.FleetUpdater, *int) {
    for _, vehicle := range vehicles {
        // Update locations based on the changes made on the vehicle state.
        vehicleID := vehicle.Input().VehicleID.(string)
        updater := vehicle.(route.Updater).Updater().(vehicleData)
        for stopdID, i := range updater.Locations {
            d.Locations[stopdID] = i
        }
        // Update value function information.
        value := vehicle.Value()
        d.fleetValue -= d.vehicleValues[vehicleID]
        d.vehicleValues[vehicleID] = value
        d.fleetValue += d.vehicleValues[vehicleID]
    }
    // Remove unassigned locations.
    for it := s.Unassigned().Iterator(); it.Next(); {
        location := it.Value()
        stop := d.stops[location]
        delete(d.Locations, stop.ID)
    }
    return d, &d.fleetValue
}

// Struct to read from JSON in.
type input struct {
    Stops    []route.Stop   `json:"stops,omitempty"`
    Vehicles []string       `json:"vehicles,omitempty"`
    Score    map[string]int `json:"score,omitempty"`
}

// Use the CLI runner to solve a Vehicle Routing Problem.
func main() {
    f := func(i input, opt solve.Options) (solve.Solver, error) {
        v := vehicleData{stops: i.Stops, score: i.Score}
        f := fleetData{stops: i.Stops}
        router, err := route.NewRouter(
            i.Stops,
            i.Vehicles,
            route.Update(v, f),
        )
        if err != nil {
            return nil, err
        }

        return router.Solver(opt)
    }

    cli.Run(f)
}
Copy

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).

go run main.go -hop.runner.input.path input.json | jq .state
Copy

Solution

The solution should look similar to this one:

{
  "unassigned": [],
  "updater": {
    "locations": {
      "Arashiyama Bamboo Forest": 1,
      "Fushimi Inari Taisha": 1,
      "Gionmachi": 3,
      "Kinkaku-ji": 6,
      "Kiyomizu-dera": 2,
      "Kyoto Imperial Palace": 4,
      "Nijō Castle": 5
    }
  },
  "vehicles": [
    {
      "id": "v1",
      "route": [
        {
          "id": "Arashiyama Bamboo Forest",
          "position": {
            "lon": 135.672009,
            "lat": 35.017209
          }
        }
      ],
      "route_duration": 0
    },
    {
      "id": "v2",
      "route": [
        {
          "id": "Fushimi Inari Taisha",
          "position": {
            "lon": 135.772695,
            "lat": 34.967146
          }
        },
        {
          "id": "Kiyomizu-dera",
          "position": {
            "lon": 135.78506,
            "lat": 34.994857
          }
        },
        {
          "id": "Gionmachi",
          "position": {
            "lon": 135.775682,
            "lat": 35.002457
          }
        },
        {
          "id": "Kyoto Imperial Palace",
          "position": {
            "lon": 135.762057,
            "lat": 35.025431
          }
        },
        {
          "id": "Nijō Castle",
          "position": {
            "lon": 135.748134,
            "lat": 35.014239
          }
        },
        {
          "id": "Kinkaku-ji",
          "position": {
            "lon": 135.728898,
            "lat": 35.039705
          }
        }
      ],
      "route_duration": 1242
    }
  ]
}
Copy

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

Page last updated

Go to on-page nav menu