Filter

In vehicle routing problems (VRPs) sometimes not all stops can be served by every vehicle. The router engine offers the Attribute option to add a compatibility check. For most cases the Filter option gives enough flexibility while maintaining simplicity. However, some problems may need to check for general compatibility but also have access to the current solution's route. In this case you can use the FilterWithRoute option.

Filters are used to prevent assigning stops to a vehicle that they are incompatible with under any circumstance. However, if a stop is suitable for a vehicle according to the given filters, assigning it to a vehicle might not result in a valid solution in the current solution. This is checked and limited by the given constraints, e.g. capacities or custom constraints. This means filters are used to exclude stops from being assigned to certain vehicles, while Constraints make sure that when stops are being inserted into a route, the the route is still feasible.

The router engine provides the Filter and FilterWithRoute options to add a custom filter.

Example

The aim of this example is to define a function to create a custom filter using the Filter and FilterWithRoute options. The introductory router example is used as a base, where routes are created to visit seven landmarks in Kyoto using two vehicles.

Save the following information in an input.json file (see input and output for more information on working with input files).

JSON

{
  "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"]
}

The Filter option works by defining a compatibility function which checks if a vehicle is compatible with a stop. Often the Filter option is combined with the custom constraints option. It is possible to use the Filter option multiple times to add multiple filters.

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. We create a function to prohibit assigning the stops Arashiyama Bamboo Forest and Kinkaku-ji to vehicle v2 then pass into the Filter option.

package main

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

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

// Use the CLI runner to solve a Vehicle Routing Problem.
func main() {
    f := func(i input, opt solve.Options) (solve.Solver, error) {
        // Define a filter. In this example v2 is not compatible with the
        // location 5 and 6
        filter := func(v, l int) bool {
            if v == 1 { //v2
                if l == 6 || l == 5 { // "Arashiyama Bamboo Forest" and "Kinkaku-ji"
                    return false
                }
            }
            return true
        }
        router, err := route.NewRouter(
            i.Stops,
            i.Vehicles,
            route.Filter(filter),
        )
        if err != nil {
            return nil, err
        }

        return router.Solver(opt)
    }

    cli.Run(f)
}

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

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

The solution should look similar to this one:

JSON

{
  "unassigned": [],
  "vehicles": [
    {
      "id": "v1",
      "route": [
        {
          "id": "Kinkaku-ji",
          "position": {
            "lon": 135.728898,
            "lat": 35.039705
          }
        },
        {
          "id": "Arashiyama Bamboo Forest",
          "position": {
            "lon": 135.672009,
            "lat": 35.017209
          }
        }
      ],
      "route_duration": 575
    },
    {
      "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": "Nijō Castle",
          "position": {
            "lon": 135.748134,
            "lat": 35.014239
          }
        },
        {
          "id": "Kyoto Imperial Palace",
          "position": {
            "lon": 135.762057,
            "lat": 35.025431
          }
        }
      ],
      "route_duration": 908
    }
  ]
}

You can see that the stops Arashiyama Bamboo Forest and Kinkaku-ji are assigned to vehicle v1 because they are not compatible with v2, due to the custom filter.

Filter with route

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. That limits the number of assigned stops to a vehicle to a fixed number of 3 using the FilterWithRoute option. This is done by filtering out vehicles that may not be assigned additional stops due to the number of stops that are already in the vehicle's route.

package main

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

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

// Use the CLI runner to solve a Vehicle Routing Problem.
func main() {
    f := func(i input, opt solve.Options) (solve.Solver, error) {
        // Define unassignment penalties to allow for unassigning stops
        penalties := []int{100000, 100000, 100000, 100000, 100000, 100000, 100000}

        // Define a filter. In this example a vehicle may not have more than 3 stops
        maxStops := 3
        filter := func(vehicles, locations model.IntDomain, routes []schema.Route) model.IntDomain {
            vehiclesToRemove := model.Domain()
            locationCount := locations.Len()
            // Determine vehicles which can get the set of locations assigned
            iter := vehicles.Iterator()
            for iter.Next() {
                index := iter.Value()
                // Remove vehicle from options, if assigning the locations would
                // overflow the maximum number of stops (start&end do not count
                // towards maximum number of stops; negative maximum indicates
                // unlimited number of stops)
                if len(routes[index])-2+locationCount > maxStops {
                    vehiclesToRemove = vehiclesToRemove.Add(index)
                }
            }
            return vehiclesToRemove
        }
        router, err := route.NewRouter(
            i.Stops,
            i.Vehicles,
            route.FilterWithRoute(filter),
            route.Unassigned(penalties),
        )
        if err != nil {
            return nil, err
        }

        return router.Solver(opt)
    }

    cli.Run(f)
}

Bash

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

The solution should look similar to this one:

JSON

{
  "unassigned": [
    {
      "id": "Arashiyama Bamboo Forest",
      "position": {
        "lon": 135.672009,
        "lat": 35.017209
      }
    }
  ],
  "vehicles": [
    {
      "id": "v1",
      "route": [
        {
          "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
          }
        }
      ],
      "route_duration": 510
    },
    {
      "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
          }
        }
      ],
      "route_duration": 448
    }
  ]
}

You can see that the stop Arashiyama Bamboo Forest is not assigned because the maximum number of stops per route has been already reached for both vehicles v1 and v2.

Filter

You will learn how to use the Filter With Route option with a practical example.

Example

Filter

Filter with route

Contents