Routing without constraints

The routing without constraints app is available in one modeling languages as a Mixed Integer Problem (MIP). You can also choose to make customizations to the model by instantiating the app first.

OR-Tools
- Default solver: SCIP
- Marketplace subscription app IDs
  - Python: nextmv-routing.ortools

Bash

nextmv sdk init -t routing-ortools

Once you have the code locally, you can customize the model, run it locally and deploy it to Nextmv Platform.

Input

The input schema is a JSON payload defining the distance matrix, number of available vehicles, and the index of the depot for the unconstrained vehicle routing problem. Nextmv's tools are designed to operate directly on business data (in JSON) to produce decisions that are actionable by software systems. This makes decisions more interpretable and easier to test. It also makes integration with data warehouses and business intelligence platforms significantly easier. An input contains the following components:

Field name	Required	Data type	SI Unit	Description	Example
`distance_matrix`	Yes	`array` of `array` of `int`	NA	A matrix of distances from each stop to each stop.	`{"distance_matrix": [[1, 4], [7, 8]]}`
`num_vehicles`	Yes	`int`	NA	The number of available vehicles.	`{"num_vehicles": 50}`
`depot`	Yes	`int`	NA	The index of the depot in the stops used to generate the distance_matrix.	`{"depot": 0}`

Here you can find a sample .json with the input schema:

JSON

{
  "defaults": {
    "vehicles": {
      "start_location": {
        "lon": 7.625,
        "lat": 51.9622
      },
      "end_location": {
        "lon": 7.625,
        "lat": 51.9622
      },
      "start_time": "2024-03-19T11:00:00+00:00",
      "speed": 10,
      "capacity": 5
    },
    "stops": {
      "quantity": 1
    }
  },
  "vehicles": [
    {
      "id": "vehicle-1"
    },
    {
      "id": "vehicle-2"
    }
  ],
  "stops": [
    {
      "id": "location-1",
      "location": {
        "lon": 7.6228,
        "lat": 51.9624
      }
    },
    {
      "id": "location-2",
      "location": {
        "lon": 7.6353,
        "lat": 51.9584
      }
    },
    {
      "id": "location-3",
      "location": {
        "lon": 7.6233,
        "lat": 51.9638
      }
    },
    {
      "id": "location-4",
      "location": {
        "lon": 7.6163,
        "lat": 51.9635
      }
    },
    {
      "id": "location-5",
      "location": {
        "lon": 7.6045,
        "lat": 51.9509
      }
    },
    {
      "id": "location-6",
      "location": {
        "lon": 7.6292,
        "lat": 51.9577
      }
    },
    {
      "id": "location-7",
      "location": {
        "lon": 7.6385,
        "lat": 51.9694
      }
    },
    {
      "id": "location-8",
      "location": {
        "lon": 7.6628,
        "lat": 51.9616
      }
    },
    {
      "id": "location-9",
      "location": {
        "lon": 7.6217,
        "lat": 51.9667
      }
    },
    {
      "id": "location-10",
      "location": {
        "lon": 7.6299,
        "lat": 51.9582
      }
    }
  ],
  "duration_matrix": [
    [0, 831, 968, 648, 773, 689, 872, 997, 685, 698, 613, 613, 613, 613],
    [822, 0, 415, 257, 273, 83, 152, 266, 212, 74, 262, 262, 262, 262],
    [925, 466, 0, 342, 499, 454, 447, 624, 294, 463, 372, 372, 372, 372],
    [647, 293, 456, 0, 207, 168, 275, 452, 88, 178, 101, 101, 101, 101],
    [775, 385, 584, 202, 0, 280, 387, 544, 238, 289, 229, 229, 229, 229],
    [739, 143, 455, 211, 228, 0, 191, 308, 249, 9, 179, 179, 179, 179],
    [843, 152, 415, 260, 348, 158, 0, 274, 201, 149, 297, 297, 297, 297],
    [1001, 270, 573, 418, 466, 276, 293, 0, 370, 267, 455, 455, 455, 455],
    [687, 217, 444, 89, 247, 208, 199, 375, 0, 214, 141, 141, 141, 141],
    [748, 134, 446, 203, 219, 9, 182, 299, 240, 0, 188, 188, 188, 188],
    [613, 272, 372, 102, 221, 129, 320, 437, 139, 138, 0, 0, 0, 0],
    [613, 272, 372, 102, 221, 129, 320, 437, 139, 138, 0, 0, 0, 0],
    [613, 272, 372, 102, 221, 129, 320, 437, 139, 138, 0, 0, 0, 0],
    [613, 272, 372, 102, 221, 129, 320, 437, 139, 138, 0, 0, 0, 0]
  ],
  "distance_matrix": [
    [0, 1840, 583, 842, 2287, 994, 1942, 3549, 1016, 1070, 442, 442, 442, 442],
    [
      1954, 0, 1464, 2068, 2983, 806, 1409, 2530, 1759, 730, 1512, 1512, 1512,
      1512
    ],
    [583, 1734, 0, 742, 2432, 1139, 1746, 3443, 433, 1215, 291, 291, 291, 291],
    [838, 2356, 1099, 0, 2356, 1510, 2272, 4065, 726, 1586, 958, 958, 958, 958],
    [
      2632, 4040, 2893, 2154, 0, 3059, 4252, 5859, 2860, 3135, 2752, 2752, 2752,
      2752
    ],
    [1300, 1122, 1149, 1769, 2255, 0, 1662, 2880, 1564, 76, 858, 858, 858, 858],
    [
      2060, 1439, 1477, 2081, 3868, 1675, 0, 2380, 1526, 1599, 1768, 1768, 1768,
      1768
    ],
    [
      3747, 2530, 3164, 3768, 5169, 2992, 2392, 0, 3459, 2916, 3455, 3455, 3455,
      3455
    ],
    [
      1267, 1782, 1197, 712, 2911, 1939, 1657, 3491, 0, 2015, 1387, 1387, 1387,
      1387
    ],
    [1224, 1046, 1073, 1744, 2331, 76, 1586, 2804, 1488, 0, 782, 782, 782, 782],
    [442, 1443, 291, 962, 2291, 998, 1545, 3152, 724, 1074, 0, 0, 0, 0],
    [442, 1443, 291, 962, 2291, 998, 1545, 3152, 724, 1074, 0, 0, 0, 0],
    [442, 1443, 291, 962, 2291, 998, 1545, 3152, 724, 1074, 0, 0, 0, 0],
    [442, 1443, 291, 962, 2291, 998, 1545, 3152, 724, 1074, 0, 0, 0, 0]
  ]
}

Output

The output schema defines the solution to the routing without constraints problem in JSON format. The output schema contains the following components.

Field name	Always present	Data type	SI Unit	Description	Example
`solutions`	Yes	`array` of `solution`	NA	Solutions to the routing problem.	`{"solutions": []}`
`statistics`	Yes	`statistics`	NA	Summary statistics of the solution.	`{"statistics": {"total_cost": 123}}`

JSON

{
  "solutions": [
    {
      "unplanned": [],
      "vehicles": [
        {
          "id": "vehicle-1",
          "route": [
            {
              "stop": {
                "id": "vehicle-1_start",
                "location": {
                  "lat": 51.9622,
                  "lon": 7.625
                }
              }
            },
            {
              "stop": {
                "id": "location-4",
                "location": {
                  "lat": 51.9635,
                  "lon": 7.6163
                },
                "quantity": 1
              }
            },
            {
              "stop": {
                "id": "location-9",
                "location": {
                  "lat": 51.9667,
                  "lon": 7.6217
                },
                "quantity": 1
              }
            },
            {
              "stop": {
                "id": "location-7",
                "location": {
                  "lat": 51.9694,
                  "lon": 7.6385
                },
                "quantity": 1
              }
            },
            {
              "stop": {
                "id": "location-8",
                "location": {
                  "lat": 51.9616,
                  "lon": 7.6628
                },
                "quantity": 1
              }
            },
            {
              "stop": {
                "id": "location-3",
                "location": {
                  "lat": 51.9638,
                  "lon": 7.6233
                },
                "quantity": 1
              }
            },
            {
              "stop": {
                "id": "vehicle-1_end",
                "location": {
                  "lat": 51.9622,
                  "lon": 7.625
                }
              }
            }
          ],
          "route_travel_distance": 1608
        },
        {
          "id": "vehicle-2",
          "route": [
            {
              "stop": {
                "id": "vehicle-2_start",
                "location": {
                  "lat": 51.9622,
                  "lon": 7.625
                }
              }
            },
            {
              "stop": {
                "id": "location-6",
                "location": {
                  "lat": 51.9577,
                  "lon": 7.6292
                },
                "quantity": 1
              }
            },
            {
              "stop": {
                "id": "location-10",
                "location": {
                  "lat": 51.9582,
                  "lon": 7.6299
                },
                "quantity": 1
              }
            },
            {
              "stop": {
                "id": "location-2",
                "location": {
                  "lat": 51.9584,
                  "lon": 7.6353
                },
                "quantity": 1
              }
            },
            {
              "stop": {
                "id": "location-5",
                "location": {
                  "lat": 51.9509,
                  "lon": 7.6045
                },
                "quantity": 1
              }
            },
            {
              "stop": {
                "id": "location-1",
                "location": {
                  "lat": 51.9624,
                  "lon": 7.6228
                },
                "quantity": 1
              }
            },
            {
              "stop": {
                "id": "vehicle-2_end",
                "location": {
                  "lat": 51.9622,
                  "lon": 7.625
                }
              }
            }
          ],
          "route_travel_distance": 1320
        }
      ]
    }
  ],
  "statistics": {
    "result": {
      "custom": {
        "activated_vehicles": 2,
        "max_route_duration": 1608,
        "max_stops_in_vehicle": 5,
        "min_stops_in_vehicle": 5,
        "solution_found": true
      },
      "duration": 0.123,
      "value": 3541
    },
    "run": {
      "duration": 0.123
    },
    "schema": "v1"
  },
  "version": {
    "ortools": "9.8.3296"
  }
}

Solution

Field name	Always present	Data type	SI Unit	Description	Example
`vehicles`	Yes	`array` of `vehicle`	NA	Solution to the unconstrained vehicle routing problem	See `vehicle`

Vehicle

Field name	Always present	Data type	SI Unit	Description	Example
`vehicle`	Yes	`int`	NA	The vehicle number	`{"vehicle": 0}`
`distance`	Yes	`int`	NA	The distance traveled by the vehicle	`{"distance": 1712}`
`stops`	Yes	array of `int`	NA	The route of the vehicle (represented as indices of the stops used to generate the distance_matrix)	`{"stops": [0, 3, 9]}`

Statistics

Field name	Always present	Data type	SI Unit	Description	Example
`result`	No	`result`	NA	Final result of the solutions.	See `result`
`run`	Yes	`run`	NA	Information about the run.	See `run`
`schema`	Yes	`string`	NA	Schema of the statistics.	`{"schema": "v1"}`

Here you can find additional definitions used in the statistics schema:

result

Field name	Always present	Data type	SI Unit	Description	Example
`duration`	Yes	`float`	`seconds`	Time duration to get to the final result.	`{"duration": 0.123}`
`value`	Yes	`float`	NA	Value of the final result.	`{"value": 0.123}`
`custom`	Yes	`any`	NA	Custom solver metrics.	See `custom`

run
Field name Always present Data type SI Unit Description Example
duration Yes float seconds Time duration of the run. {"duration": 0.123}

Field name	Always present	Data type	SI Unit	Description	Example
`duration`	Yes	`float`	`seconds`	Time duration of the run.	`{"duration": 0.123}`

custom

Field name	Always present	Data type	SI Unit	Description	Example
`constraints`	Yes	`int`	NA	Number of constraints.	`{"constraints": 123}`
`provider`	Yes	`string`	NA	Solver provider.	`{"provider": "highs"}`
`status`	Yes	`string`	NA	Solver status.	`{"status": "optimal"}`
`variables`	Yes	`int`	NA	Number of variables.	`{"variables": 123}`

Run options

These are the default options that are available with routing without constraints.

Text

usage: main.py [-h] [-input INPUT] [-output OUTPUT] [-duration DURATION]

Solve a routing problem with OR-Tools.

options:
  -h, --help          show this help message and exit
  -input INPUT        Path to input file. Default is stdin.
  -output OUTPUT      Path to output file. Default is stdout.
  -duration DURATION  Max runtime duration (in seconds). Default is 30.

Routing without constraints

A how-to guide for specifying the input and output schemas in routing without constraints.

Input

Output

Solution

Vehicle

Statistics

Run options

Knapsack

Demand Forecasting

Contents