Solving Vehicle Routing Problems with the Nextmv routing app

This how-to guide assumes you already completed the steps described in the 5-minute getting started experience. To test that the Nextmv CLI is correctly configured, you can optionally run the following command on your terminal. It will get some files that are necessary to work with the Nextmv Platform. You can see the expected output as well.

Bash
Output

nextmv sdk install

The Nextmv routing app provides you with API endpoints to run a model, check the status of your run, and get run results, and a user interface to configure the app. Follow the steps below to use the app.

The Nextmv routing app is built on top of the router and provides a configurable interface for solving vehicle routing problems. It requires a set of stops that must be serviced by a fleet of vehicles as input following a specified schema. It returns routes for each vehicle, a list of unassigned stops (if any), and search output statistics.

In this guide, you will learn how to use the Nextmv routing app with a simple example where routes are created to visit seven landmarks in Kyoto using two vehicles.

Let's see how.

base-input

Note, you will need your Nextmv API key and the Nextmv CLI to use the Nextmv routing app. Log in to Nextmv and navigate to your account page to find your key. Keep it safe, as it alone provides unfettered access to the cloud API.

Input

Save the following information in an input.json file.

input.json

{
  "defaults": {
    "vehicles": {
      "shift_start": "2022-09-15T09:00:00-06:00",
      "speed": 10,
      "start": { "lon": 135.759901, "lat": 35.024521 }
    }
  },
  "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": [{ "id": "v1" }, { "id": "v2" }]
}

Run profile

To proceed with running the example, you will need to create a run profile via the Nextmv console. After you log in, navigate to the run profile configuration page to create or edit a run profile. Be sure to note your run profile id as you will need this below. Run profiles can also be created via the Nextmv routing app API.

Output

To execute the example, use the Nextmv CLI to specify the path to an input.json file, write results to a file, and use a specific run profile.

Bash

nextmv run submit --wait --input "input.json" --output --run-profile test-profile

The output is saved to the folder output. The solution state should look similar to this:

JSON

{
  "vehicles": [
    {
      "id": "v1",
      "value": 754,
      "travel_distance": 7543.258,
      "travel_time": 754,
      "vehicle_initialization_costs": 0,
      "route": [
        {
          "id": "v1-start",
          "lon": 135.759901,
          "lat": 35.024521,
          "distance": 0,
          "eta": "2022-09-15T09:00:00-06:00",
          "ets": "2022-09-15T09:00:00-06:00",
          "etd": "2022-09-15T09:00:00-06:00"
        },
        {
          "id": "Kyoto Imperial Palace",
          "lon": 135.762057,
          "lat": 35.025431,
          "distance": 220.863,
          "eta": "2022-09-15T09:00:22-06:00",
          "ets": "2022-09-15T09:00:22-06:00",
          "etd": "2022-09-15T09:00:22-06:00"
        },
        {
          "id": "Gionmachi",
          "lon": 135.775682,
          "lat": 35.002457,
          "distance": 3060.8619999999996,
          "eta": "2022-09-15T09:05:06-06:00",
          "ets": "2022-09-15T09:05:06-06:00",
          "etd": "2022-09-15T09:05:06-06:00"
        },
        {
          "id": "Kiyomizu-dera",
          "lon": 135.78506,
          "lat": 34.994857,
          "distance": 4262.4619999999995,
          "eta": "2022-09-15T09:07:06-06:00",
          "ets": "2022-09-15T09:07:06-06:00",
          "etd": "2022-09-15T09:07:06-06:00"
        },
        {
          "id": "Fushimi Inari Taisha",
          "lon": 135.772695,
          "lat": 34.967146,
          "distance": 7543.258,
          "eta": "2022-09-15T09:12:34-06:00",
          "ets": "2022-09-15T09:12:34-06:00",
          "etd": "2022-09-15T09:12:34-06:00"
        }
      ],
      "polyline": "gvwtEkrr{XuDoLpnCctAnn@sy@dlDflA"
    },
    {
      "id": "v2",
      "value": 1065,
      "travel_distance": 10648.904,
      "travel_time": 1065,
      "vehicle_initialization_costs": 0,
      "route": [
        {
          "id": "v2-start",
          "lon": 135.759901,
          "lat": 35.024521,
          "distance": 0,
          "eta": "2022-09-15T09:00:00-06:00",
          "ets": "2022-09-15T09:00:00-06:00",
          "etd": "2022-09-15T09:00:00-06:00"
        },
        {
          "id": "Nijō Castle",
          "lon": 135.748134,
          "lat": 35.014239,
          "distance": 1566.961,
          "eta": "2022-09-15T09:02:37-06:00",
          "ets": "2022-09-15T09:02:37-06:00",
          "etd": "2022-09-15T09:02:37-06:00"
        },
        {
          "id": "Kinkaku-ji",
          "lon": 135.728898,
          "lat": 35.039705,
          "distance": 4896.581,
          "eta": "2022-09-15T09:08:10-06:00",
          "ets": "2022-09-15T09:08:10-06:00",
          "etd": "2022-09-15T09:08:10-06:00"
        },
        {
          "id": "Arashiyama Bamboo Forest",
          "lon": 135.672009,
          "lat": 35.017209,
          "distance": 10648.904,
          "eta": "2022-09-15T09:17:45-06:00",
          "ets": "2022-09-15T09:17:45-06:00",
          "etd": "2022-09-15T09:17:45-06:00"
        }
      ],
      "polyline": "gvwtEkrr{Xf_AphAe~CdwBrkCpbJ"
    }
  ],
  "unassigned": [],
  "value_summary": {
    "value": 1819,
    "total_travel_distance": 18192.162,
    "total_travel_time": 1819,
    "total_unassigned_penalty": 0,
    "total_vehicle_initialization_costs": 0
  }
}

You can see that six stops were assigned to one vehicle and just a single stop which is farthest from the others was assigned to the other vehicle.

base-output

Additional options can be added to the input.json to extend this basic example. See the routing app features how-to guide for more information on how to add additional Nextmv routing app features to your input file.

Using the API directly

The Nextmv routing app is made up of a collection of API endpoints that you can query directly. This section will instruct you on doing so. However, we recommend that you use the Nextmv CLI to interact with the routing app directly, when possible.

API Key

Your Nextmv API key can be copied from under your account profile after logging in to the Nextmv Cloud console.

Endpoints

Note, all requests must be authenticated with Bearer Authentication. Make sure your request has a header containing your Nextmv API key, as such:

Key: Authorization
Value: Bearer <YOUR-API-KEY>

Bash

Authorization: Bearer <YOUR-API-KEY>

No API specified.

Polling

The routing app API should be used through polling.

polling-sample

Send a request to the /v0/run endpoint with a JSON body that follows the input schema, e.g.: the previous input.json. The API server should return a runID similar to the following:

JSON

{ "runID": "<YOUR_RUN_ID>" }

This means that a Nextmv solver has been spun up to solve the model with the given input. The time it takes to finish execution varies by the size of the input and solver options. Wait for approximately the duration set in the run options. Depending on the problem, the solver may finish sooner than the alloted time.

Poll the /v0/run/{run_id}/status endpoint with the runID obtained from the previous request.

If the status of the run is succeeded, you may request the result using the /v0/run/{run_id}/result endpoint.
If the status is requested or started, it means that the solver is still running and you should wait to request the result. We recommend you set a maximum number of retries for the polling. Sleep for a short time, then poll the endpoint until there are no retries left or the status is succeeded. Instead of retries, you can also use a timeout.
If the status is failed or timed_out, it means that you will not be able to request the result.

Request the result from the /v0/run/{run_id}/result endpoint using the runID obtained from the first request. The response is a JSON payload that follows the output schema, e.g.: the previous output.json. Modify the input of your run request to see how your result changes.

Code snippets

These code snippets demonstrate how to use the API through polling in select languages. They assume the input.json file is present in the same directory as the script.

To start, get your API key and set the following environment variable:

Bash

export API_KEY=<YOUR-API-KEY>

Run one of the following scripts:

Go
Python

package main

import (
	"bytes"
	"context"
	"encoding/json"
	"errors"
	"fmt"
	"io"
	"math"
	"net/http"
	"os"
	"time"
)

var apiKey = os.Getenv("API_KEY")

var url = "https://api.cloud.nextmv.io/v0/run"

type output struct {
	Hop        any \`json:"hop,omitempty"\`
	Options    any \`json:"options,omitempty"\`
	State      any \`json:"state,omitempty"\`
	Statistics any \`json:"statistics,omitempty"\`
}

func (o output) MarshalJSON() ([]byte, error) {
	v := map[string]any{
		"state": o.State,
	}

	return json.Marshal(v)
}

// solve solves the problem using the Nextmv Cloud API.
func solve(data io.Reader) (*output, error) {
	// Post job to Nextmv Cloud endpoint.
	response, err := request("POST", url, data)
	if err != nil {
		return nil, err
	}
	runIDResp := &struct {
		RunID string
	}{}
	if err = json.Unmarshal(response, runIDResp); err != nil {
		return nil, err
	}
	runID := runIDResp.RunID

	// Poll job status until it is finished or there is a timeout.
	start, waitTime, waitMax, timeout := time.Now(), 0.2, 5., 60.
	if err := poll(runID, start, waitTime, waitMax, timeout); err != nil {
		return nil, err
	}

	// Get the solution.
	response, err = request("GET", url+"/"+runID+"/result", nil)
	if err != nil {
		return nil, err
	}
	output := &output{}
	if err := json.Unmarshal(response, output); err != nil {
		return nil, err
	}

	return output, nil
}

// request performs an HTTP request.
func request(method string, url string, data io.Reader) ([]byte, error) {
	client := &http.Client{}
	req, err := http.NewRequestWithContext(
		context.Background(),
		method,
		url,
		data,
	)
	if err != nil {
		return nil, err
	}

	req.Header.Add("Authorization", "Bearer "+apiKey)
	if method == "POST" {
		req.Header.Add("Content-Type", "application/json")
		req.Header.Add("accept", "application/json")
	}

	res, err := client.Do(req)
	if err != nil {
		return nil, err
	}
	if res.StatusCode != http.StatusOK &&
		res.StatusCode != http.StatusAccepted {
		return nil, fmt.Errorf("unexpected status code: %d (%s / %s)",
			res.StatusCode,
			method,
			url)
	}

	defer func() {
		err := res.Body.Close()
		if err != nil {
			panic(err)
		}
	}()

	body, err := io.ReadAll(res.Body)
	if err != nil {
		return nil, err
	}

	return body, nil
}

func poll(
	runID string,
	start time.Time,
	waitTime, waitMax, timeout float64,
) error {
	for {
		// Check for timeout.
		if time.Since(start).Seconds() > timeout {
			return fmt.Errorf("timed out after %f", timeout)
		}

		// Get job status.
		response, err := request("GET", url+"/"+runID+"/status", nil)
		if err != nil {
			return err
		}
		statusResp := &struct {
			Status string
		}{}
		if err = json.Unmarshal(response, statusResp); err != nil {
			return err
		}
		status := statusResp.Status
		if status == "started" || status == "requested" {
			time.Sleep(time.Duration(waitTime) * time.Second)
			waitTime = math.Min(waitTime*2, waitMax)
			continue
		}
		if status == "succeeded" {
			break
		}
		if status == "timed_out" {
			return errors.New("no solution found within time limit")
		}
		if status == "failed" {
			return errors.New("failed to solve the problem")
		}

		return fmt.Errorf("unknown status occurred: %s", status)
	}

	return nil
}

func main() {
	file, err := os.Open("input.json")
	// if os.Open returns an error then we handle it.
	if err != nil {
		panic(err)
	}
	b, err := io.ReadAll(file)
	if err != nil {
		panic(err)
	}
	reader := bytes.NewReader(b)

	// Solve the problem.
	output, err := solve(reader)
	if err != nil {
		panic(err)
	}

	// Print the result.
	b, err = json.MarshalIndent(output, "", "  ")
	if err != nil {
		panic(err)
	}
	fmt.Println(string(b))
}

You should obtain the same output as before.