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

Router

ALNS

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

{
  "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"],
  "threads": 3
}
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 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.

package main

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

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

// Use the CLI runner to solve a Vehicle Routing Problem.
func main() {
    f := func(i input, opt solve.Options) (solve.Solver, error) {
        // Custom ALNS implementation
        repairOptions := opt
        repairOptions.Limits.Solutions = 1
        operators := []alns.Operator{
            {
                Destroy: vehicleEngine.DestroySwap(),
                Repair:  vehicleEngine.Repair(repairOptions),
            },
        }
        acceptor := alns.Hill(model.Minimize)

        // Declare the router and its solver.
        router, err := route.NewRouter(
            i.Stops,
            i.Vehicles,
            // Do not append operators
            route.Operators(operators, false),
            route.Acceptor(acceptor),
            route.Threads(i.Threads),
        )
        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:

{
  "vehicles": [
    {
      "id": "v1",
      "route": [
        {
          "id": "Arashiyama Bamboo Forest",
          "position": {
            "lon": 135.672009,
            "lat": 35.017209
          }
        },
        {
          "id": "Kinkaku-ji",
          "position": {
            "lon": 135.728898,
            "lat": 35.039705
          }
        },
        {
          "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": "Kiyomizu-dera",
          "position": {
            "lon": 135.78506,
            "lat": 34.994857
          }
        },
        {
          "id": "Fushimi Inari Taisha",
          "position": {
            "lon": 135.772695,
            "lat": 34.967146
          }
        }
      ],
      "route_duration": 1818
    }
  ]
}
Copy

You can see that the stops are assigned in a fashion that minimizes the route distance.

alns-output

Page last updated

Go to on-page nav menu