Routing Without Constraints

Routing without constraints

A how-to guide for specifying the input and output schemas in 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.

nextmv community clone -a routing-ortools
Copy

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 nameRequiredData typeSI UnitDescriptionExample
distance_matrixYesarray of array of intNAA matrix of distances from each stop to each stop.{"distance_matrix": [[1, 4], [7, 8]]}
num_vehiclesYesintNAThe number of available vehicles.{"num_vehicles": 50}
depotYesintNAThe 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:

{
  "distance_matrix": [
    [
      0, 548, 776, 696, 582, 274, 502, 194, 308, 194, 536, 502, 388, 354, 468,
      776, 662
    ],
    [
      548, 0, 684, 308, 194, 502, 730, 354, 696, 742, 1084, 594, 480, 674, 1016,
      868, 1210
    ],
    [
      776, 684, 0, 992, 878, 502, 274, 810, 468, 742, 400, 1278, 1164, 1130,
      788, 1552, 754
    ],
    [
      696, 308, 992, 0, 114, 650, 878, 502, 844, 890, 1232, 514, 628, 822, 1164,
      560, 1358
    ],
    [
      582, 194, 878, 114, 0, 536, 764, 388, 730, 776, 1118, 400, 514, 708, 1050,
      674, 1244
    ],
    [
      274, 502, 502, 650, 536, 0, 228, 308, 194, 240, 582, 776, 662, 628, 514,
      1050, 708
    ],
    [
      502, 730, 274, 878, 764, 228, 0, 536, 194, 468, 354, 1004, 890, 856, 514,
      1278, 480
    ],
    [
      194, 354, 810, 502, 388, 308, 536, 0, 342, 388, 730, 468, 354, 320, 662,
      742, 856
    ],
    [
      308, 696, 468, 844, 730, 194, 194, 342, 0, 274, 388, 810, 696, 662, 320,
      1084, 514
    ],
    [
      194, 742, 742, 890, 776, 240, 468, 388, 274, 0, 342, 536, 422, 388, 274,
      810, 468
    ],
    [
      536, 1084, 400, 1232, 1118, 582, 354, 730, 388, 342, 0, 878, 764, 730,
      388, 1152, 354
    ],
    [
      502, 594, 1278, 514, 400, 776, 1004, 468, 810, 536, 878, 0, 114, 308, 650,
      274, 844
    ],
    [
      388, 480, 1164, 628, 514, 662, 890, 354, 696, 422, 764, 114, 0, 194, 536,
      388, 730
    ],
    [
      354, 674, 1130, 822, 708, 628, 856, 320, 662, 388, 730, 308, 194, 0, 342,
      422, 536
    ],
    [
      468, 1016, 788, 1164, 1050, 514, 514, 662, 320, 274, 388, 650, 536, 342,
      0, 764, 194
    ],
    [
      776, 868, 1552, 560, 674, 1050, 1278, 742, 1084, 810, 1152, 274, 388, 422,
      764, 0, 798
    ],
    [
      662, 1210, 754, 1358, 1244, 708, 480, 856, 514, 468, 354, 844, 730, 536,
      194, 798, 0
    ]
  ],
  "num_vehicles": 4,
  "depot": 0
}
Copy

Output

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

Field nameAlways presentData typeSI UnitDescriptionExample
solutionsYesarray of solutionNASolutions to the routing problem.{"solutions": []}
statisticsYesstatisticsNASummary statistics of the solution.{"statistics": {"total_cost": 123}}
{
  "solutions": [
    {
      "vehicles": [
        {
          "distance": 0,
          "stops": [
            0,
            0
          ],
          "vehicle": 0
        },
        {
          "distance": 0,
          "stops": [
            0,
            0
          ],
          "vehicle": 1
        },
        {
          "distance": 0,
          "stops": [
            0,
            0
          ],
          "vehicle": 2
        },
        {
          "distance": 4384,
          "stops": [
            0,
            9,
            5,
            8,
            6,
            2,
            10,
            16,
            14,
            13,
            12,
            11,
            15,
            3,
            4,
            1,
            7,
            0
          ],
          "vehicle": 3
        }
      ]
    }
  ],
  "statistics": {
    "result": {
      "custom": {
        "activated_vehicles": 4,
        "max_route_distance": 4384,
        "max_stops_in_vehicle": 16,
        "min_stops_in_vehicle": 0
      },
      "duration": 0.0024492740631103516,
      "value": 4384
    },
    "run": {
      "duration": 0.0024492740631103516
    },
    "schema": "v1"
  }
}
Copy

Solution

Field nameAlways presentData typeSI UnitDescriptionExample
vehiclesYesarray of vehicleNASolution to the unconstrained vehicle routing problemSee vehicle

Vehicle

Field nameAlways presentData typeSI UnitDescriptionExample
vehicleYesintNAThe vehicle number{"vehicle": 0}
distanceYesintNAThe distance traveled by the vehicle{"distance": 1712}
stopsYesarray of intNAThe route of the vehicle (represented as indices of the stops used to generate the distance_matrix){"stops": [0, 3, 9]}

Statistics

Field nameAlways presentData typeSI UnitDescriptionExample
resultNoresultNAFinal result of the solutions.See result
runYesrunNAInformation about the run.See run
schemaYesstringNASchema of the statistics.{"schema": "v1"}

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

  • result

    Field nameAlways presentData typeSI UnitDescriptionExample
    durationYesfloatsecondsTime duration to get to the final result.{"duration": 0.123}
    valueYesfloatNAValue of the final result.{"value": 0.123}
    customYesanyNACustom solver metrics.See custom
  • run

    Field nameAlways presentData typeSI UnitDescriptionExample
    durationYesfloatsecondsTime duration of the run.{"duration": 0.123}
  • custom

    Field nameAlways presentData typeSI UnitDescriptionExample
    constraintsYesintNANumber of constraints.{"constraints": 123}
    providerYesstringNASolver provider.{"provider": "highs"}
    statusYesstringNASolver status.{"status": "optimal"}
    variablesYesintNANumber of variables.{"variables": 123}

Run options

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

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

Page last updated

Go to on-page nav menu