Matching filters

Search…
Matching filters
You will learn how to use the Filter With Route option with a practical example.
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
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
}
Copied!
Filter
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 [email protected].
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.
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
        // Define a filter. In this example v2 is not compatible with the
19
        // location 5 and 6
20
        filter := func(v, l int) bool {
21
            if v == 1 { //v2
22
                if l == 6 || l == 5 { // "Arashiyama Bamboo Forest" and "Kinkaku-ji"
23
                    return false
24
                }
25
            }
26
            return true
27
        }
28
        router, err := route.NewRouter(
29
            i.Stops,
30
            i.Vehicles,
31
            route.Filter(filter),
32
        )
33
        if err != nil {
34
            return nil, err
35
        }
36
​
37
        return router.Solver(opt)
38
    }
39
​
40
    cli.Run(f)
41
}
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!
The solution should look similar to this one:
JSON
1
{
2
  "unassigned": [],
3
  "vehicles": [
4
    {
5
      "id": "v1",
6
      "route": [
7
        {
8
          "id": "Kinkaku-ji",
9
          "position": {
10
            "lon": 135.728898,
11
            "lat": 35.039705
12
          }
13
        },
14
        {
15
          "id": "Arashiyama Bamboo Forest",
16
          "position": {
17
            "lon": 135.672009,
18
            "lat": 35.017209
19
          }
20
        }
21
      ],
22
      "route_duration": 575
23
    },
24
    {
25
      "id": "v2",
26
      "route": [
27
        {
28
          "id": "Fushimi Inari Taisha",
29
          "position": {
30
            "lon": 135.772695,
31
            "lat": 34.967146
32
          }
33
        },
34
        {
35
          "id": "Kiyomizu-dera",
36
          "position": {
37
            "lon": 135.78506,
38
            "lat": 34.994857
39
          }
40
        },
41
        {
42
          "id": "Gionmachi",
43
          "position": {
44
            "lon": 135.775682,
45
            "lat": 35.002457
46
          }
47
        },
48
        {
49
          "id": "Nijō Castle",
50
          "position": {
51
            "lon": 135.748134,
52
            "lat": 35.014239
53
          }
54
        },
55
        {
56
          "id": "Kyoto Imperial Palace",
57
          "position": {
58
            "lon": 135.762057,
59
            "lat": 35.025431
60
          }
61
        }
62
      ],
63
      "route_duration": 908
64
    }
65
  ]
66
}
Copied!
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 [email protected].
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.
Go
1
package main
2
​
3
import (
4
    "github.com/nextmv-io/code/engines/route"
5
    "github.com/nextmv-io/code/engines/route/vehicle/schema"
6
    "github.com/nextmv-io/code/hop/model"
7
    "github.com/nextmv-io/code/hop/run/cli"
8
    "github.com/nextmv-io/code/hop/solve"
9
)
10
​
11
// Struct to read from JSON in.
12
type input struct {
13
    Stops    []route.Stop `json:"stops,omitempty"`
14
    Vehicles []string     `json:"vehicles,omitempty"`
15
}
16
​
17
// Use the CLI runner to solve a Vehicle Routing Problem.
18
func main() {
19
    f := func(i input, opt solve.Options) (solve.Solver, error) {
20
        // Define unassignment penalties to allow for unassigning stops
21
        penalties := []int{100000, 100000, 100000, 100000, 100000, 100000, 100000}
22
​
23
        // Define a filter. In this example a vehicle may not have more than 3 stops
24
        maxStops := 3
25
        filter := func(vehicles, locations model.IntDomain, routes []schema.Route) model.IntDomain {
26
            vehiclesToRemove := model.Domain()
27
            locationCount := locations.Len()
28
            // Determine vehicles which can get the set of locations assigned
29
            iter := vehicles.Iterator()
30
            for iter.Next() {
31
                index := iter.Value()
32
                // Remove vehicle from options, if assigning the locations would
33
                // overflow the maximum number of stops (start&end do not count
34
                // towards maximum number of stops; negative maximum indicates
35
                // unlimited number of stops)
36
                if len(routes[index])-2+locationCount > maxStops {
37
                    vehiclesToRemove = vehiclesToRemove.Add(index)
38
                }
39
            }
40
            return vehiclesToRemove
41
        }
42
        router, err := route.NewRouter(
43
            i.Stops,
44
            i.Vehicles,
45
            route.FilterWithRoute(filter),
46
            route.Unassigned(penalties),
47
        )
48
        if err != nil {
49
            return nil, err
50
        }
51
​
52
        return router.Solver(opt)
53
    }
54
​
55
    cli.Run(f)
56
}
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!
The solution should look similar to this one:
JSON
1
{
2
  "unassigned": [
3
    {
4
      "id": "Arashiyama Bamboo Forest",
5
      "position": {
6
        "lon": 135.672009,
7
        "lat": 35.017209
8
      }
9
    }
10
  ],
11
  "vehicles": [
12
    {
13
      "id": "v1",
14
      "route": [
15
        {
16
          "id": "Kinkaku-ji",
17
          "position": {
18
            "lon": 135.728898,
19
            "lat": 35.039705
20
          }
21
        },
22
        {
23
          "id": "Nijō Castle",
24
          "position": {
25
            "lon": 135.748134,
26
            "lat": 35.014239
27
          }
28
        },
29
        {
30
          "id": "Kyoto Imperial Palace",
31
          "position": {
32
            "lon": 135.762057,
33
            "lat": 35.025431
34
          }
35
        }
36
      ],
37
      "route_duration": 510
38
    },
39
    {
40
      "id": "v2",
41
      "route": [
42
        {
43
          "id": "Fushimi Inari Taisha",
44
          "position": {
45
            "lon": 135.772695,
46
            "lat": 34.967146
47
          }
48
        },
49
        {
50
          "id": "Kiyomizu-dera",
51
          "position": {
52
            "lon": 135.78506,
53
            "lat": 34.994857
54
          }
55
        },
56
        {
57
          "id": "Gionmachi",
58
          "position": {
59
            "lon": 135.775682,
60
            "lat": 35.002457
61
          }
62
        }
63
      ],
64
      "route_duration": 448
65
    }
66
  ]
67
}
Copied!
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.
Custom constraints
Output marshalling
Last modified 2mo ago
Export as PDF
Copy link
Contents
Example
Filter
Filter with route