Supported solvers in vehicle routing problems

This how-to guide assumes you already completed the get started with vehicle routing tutorial.

These are the supported solvers for vehicle routing problems:

Provider	Description	Use with
Nextmv	Our `nextroute` engine. Get started here.	Nextmv platform & marketplace app
OR-Tools	Open-source solver.	Nextmv platform & Python

When working locally with the Nextmv Platform make sure all necessary assets are up to date by running the following command:

Bash
Output

nextmv sdk install

OR-Tools

OR-Tools is an open-source solver. It is a software suite for optimization, tuned for tackling the world's toughest problems in vehicle routing, flows, integer and linear programming, and constraint programming.

This solver is supported using Python.
When running locally, this solver is not supported natively using Nextmv's SDK and you need to run with the Python command directly.
Does not require additional licensing or setup, for running locally or in the cloud.

Get started by initializing the ortools template. The template contains an example of getting started with Mixed Integer Programming (MIP).

Bash

nextmv sdk init -t ortools

Change directories into the ortools folder.

We are going to modify the template to solve a sample vehicle routing problem. This is an adapted example taken from the OR-Tools VRP guides.

Replace the input.json contained in the template with sample data for the vehicle routing problem.

JSON

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

Similarly, replace the main.py included in the template with the code to solve the VRP.

Python

"""
Adapted example of the vehicle routing problem with Google OR-Tools.
"""

import argparse
import json
import sys
import time
from typing import Any, Dict

from ortools.constraint_solver import pywrapcp, routing_enums_pb2


def main():
    """Entry point for the template."""
    parser = argparse.ArgumentParser(description="Solve problems with OR-Tools.")
    parser.add_argument(
        "-input",
        default="",
        help="Path to input file. Default is stdin.",
    )
    parser.add_argument(
        "-output",
        default="",
        help="Path to output file. Default is stdout.",
    )
    parser.add_argument(
        "-duration",
        default=30,
        help="Max runtime duration (in seconds). Default is 30.",
        type=int,
    )
    args = parser.parse_args()

    # Read input data, solve the problem and write the solution.
    input_data = read_input(args.input)
    solution = solve(input_data, args.duration)
    write_output(args.output, solution)


def solve(input_data: Dict[str, Any], duration: int) -> Dict[str, Any]:
    """Solves the given problem and returns the solution."""

    # Create the routing index manager.
    manager = pywrapcp.RoutingIndexManager(
        len(input_data["distance_matrix"]),
        input_data["num_vehicles"],
        input_data["depot"],
    )

    # Create Routing Model.
    routing = pywrapcp.RoutingModel(manager)

    # Create and register a transit callback.
    def distance_callback(from_index, to_index):
        """Returns the distance between the two nodes."""
        # Convert from routing variable Index to distance matrix NodeIndex.
        from_node = manager.IndexToNode(from_index)
        to_node = manager.IndexToNode(to_index)
        return input_data["distance_matrix"][from_node][to_node]

    transit_callback_index = routing.RegisterTransitCallback(distance_callback)

    # Define cost of each arc.
    routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)

    # Add Distance constraint.
    dimension_name = "Distance"
    routing.AddDimension(
        transit_callback_index,
        0,  # no slack
        3000,  # vehicle maximum travel distance
        True,  # start cumul to zero
        dimension_name,
    )
    distance_dimension = routing.GetDimensionOrDie(dimension_name)
    distance_dimension.SetGlobalSpanCostCoefficient(100)

    # Setting first solution heuristic.
    search_parameters = pywrapcp.DefaultRoutingSearchParameters()
    search_parameters.first_solution_strategy = routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC
    search_parameters.time_limit.FromSeconds(duration)

    # Solve the problem.
    start_time = time.time()
    solution = routing.SolveWithParameters(search_parameters)
    end_time = time.time()

    # Determine the routes.
    routes = []
    max_route_distance = 0
    max_stops_in_vehicle = 0
    min_stops_in_vehicle = len(input_data["distance_matrix"])
    activated_vehicles = 0
    for vehicle_id in range(input_data["num_vehicles"]):
        index = routing.Start(vehicle_id)
        route_distance = 0
        stops = []
        while not routing.IsEnd(index):
            stops.append(manager.IndexToNode(index))
            previous_index = index
            index = solution.Value(routing.NextVar(index))
            route_distance += routing.GetArcCostForVehicle(
                previous_index,
                index,
                vehicle_id,
            )
        stops.append(manager.IndexToNode(index))
        route = {
            "vehicle": vehicle_id,
            "distance": route_distance,
            "stops": stops,
        }
        routes.append(route)
        max_route_distance = max(route_distance, max_route_distance)
        activated_vehicles += 1
        max_stops_in_vehicle = max(max_stops_in_vehicle, len(stops) - 2)
        min_stops_in_vehicle = min(min_stops_in_vehicle, len(stops) - 2)

    # Creates the statistics.
    statistics = {
        "result": {
            "custom": {
                "activated_vehicles": activated_vehicles,
                "max_route_distance": max_route_distance,
                "max_stops_in_vehicle": max_stops_in_vehicle,
                "min_stops_in_vehicle": min_stops_in_vehicle,
            },
            "duration": end_time - start_time,
            "value": solution.ObjectiveValue(),
        },
        "run": {
            "duration": end_time - start_time,
        },
        "schema": "v1",
    }

    return {
        "solutions": [{"vehicles": routes}],
        "statistics": statistics,
    }


def read_input(input_path) -> Dict[str, Any]:
    """Reads the input from stdin or a given input file."""
    input_file = {}
    if input_path:
        with open(input_path) as file:
            input_file = json.load(file)
    else:
        input_file = json.load(sys.stdin)

    return input_file


def write_output(output_path, output) -> None:
    """Writes the output to stdout or a given output file."""
    content = json.dumps(output, indent=2)
    if output_path:
        with open(output_path, "w") as file:
            file.write(content + "\n")
    else:
        print(content)


if __name__ == "__main__":
    main()

Because this is a Python template, make sure that the requirements described in the requirements.txt file are installed.

Bash

pip3 install -r requirements.txt

Run the code, specifying the file to be used as input.

Bash

python3 main.py -input input.json -duration 10

After running, the output should have been printed to stdout, similar to this one:

JSON

{
  "solutions": [
    {
      "vehicles": [
        {
          "vehicle": 0,
          "distance": 1712,
          "stops": [
            0,
            9,
            10,
            2,
            6,
            5,
            0
          ]
        },
        {
          "vehicle": 1,
          "distance": 1484,
          "stops": [
            0,
            16,
            14,
            8,
            0
          ]
        },
        {
          "vehicle": 2,
          "distance": 1552,
          "stops": [
            0,
            7,
            1,
            4,
            3,
            0
          ]
        },
        {
          "vehicle": 3,
          "distance": 1552,
          "stops": [
            0,
            13,
            15,
            11,
            12,
            0
          ]
        }
      ]
    }
  ],
  "statistics": {
    "result": {
      "custom": {
        "activated_vehicles": 4,
        "max_route_distance": 1712,
        "max_stops_in_vehicle": 5,
        "min_stops_in_vehicle": 3
      },
      "duration": 0.12345,
      "value": 177500
    },
    "run": {
      "duration": 0.12345
    },
    "schema": "v1"
  }
}

The template contains an app.yaml manifest that specifies how to execute the app in the cloud.

YAML

# This manifest holds the information the app needs to run on the Nextmv Cloud.
type: python
runtime: ghcr.io/nextmv-io/runtime/ortools:latest
# List all files/directories that should be included in the app. Globbing
# (e.g.: configs/*.json) is supported.
files:
  - main.py

type (do not modify this value): specifies that the app uses Python instead of the Nextmv SDK.
runtime (do not modify this value): specifies the docker runtime where the app is run. This value must not be modified because the runtime is specific for OR-Tools.
files: a list of all the files that should be included in the app. Globbing is supported, so you may specify individual files or whole directories. In the simple template, just the main.py needs to be included.

The OR-Tools runtime has no access to network calls. This means that importing other packages or performing HTTP requests is not yet available. If you would like more Python packages to be supported in the runtime, please contact support.

After running locally, and making sure your app manifest is correctly set up, you may follow the steps for deploying a custom app.

Supported solvers in vehicle routing problems

A how-to guide for working with different solvers.

OR-Tools

Contents