Solve a vehicle routing problem (VRP) using R and Nextmv Cloud

Editor’s note (October 11, 2023): This post was updated to be compatible with the Nextmv Routing app.

In this blog post, we will use the Nextmv routing app, R, and some tidyverse packages to formulate, solve, and visualize a simple capacitated vehicle routing problem (CVRP). We’ll work through a sourcing scenario (meaning we’re focused on pickups rather than dropoffs) using 2 vehicles and 4 stops. 

It’s also worth noting that our Nextmv routing app supports more types of problems, including VRP with pickup and delivery, route limits, time windows, and beyond.

The primary goal of this post is to help folks who want to solve a VRP using R to get started with Nextmv more easily.

The blog post uses the new pipe operator first introduced in R 4.1, but you can of course also use magrittr’s pipe operator if you use an older version of R. In addition, we make use of the following R packages:

• askpass to securely ask for an API-key
• httr for HTTP calls
• purrr, tidyr, and dplyr for easier data processing
• and ggplot2 for visualization.

Let’s get started. 

A (brief) intro to Nextmv Cloud

Nextmv Cloud is a platform for automating decisions, such as how best to assign stops to vehicles. You can create a Nextmv Cloud account and start a free trial to follow along with the tutorial in this post.

In the Nextmv Cloud, you can create apps. Each app usually solves a specific problem, such as vehicle routing or shift scheduling. These apps can either be custom written in Go or Python, or you can use a subscription app that offers a ready-to-use JSON based API.

In this post we will use the Nextmv Routing app. Should you ever require custom code, e.g. in case you’ll need a custom constraint, you can do so by modifying the underlying template and deploying to get a unique endpoint.

Pause here and create a new subscription routing app called nextroute. Once you have done that, you have your own routing app that has a set of APIs that you can use to solve a routing problem.

To start an optimization run you:

1.  Submit a problem encoded as JSON to your app and receive a ^run-id.

2.  Wait and poll the system using the ^run-id until the run is completed.

3.  Download the solution file encoded as JSON and further process it.

Before we can start though, we need an API key and the URL of the endpoint which you can find in the Nextmv console. After you have logged in to the console, go to the Account Page and copy your API key. The key will automatically be copied to your clipboard. Keep it safe, as it alone provides unfettered access to the cloud API.

API_KEY <- askpass::askpass("Please enter the API-Key")
URL <- "https://api.cloud.nextmv.io/v1/applications/nextroute/runs"

The code above uses the askpass package to ask for API-key in a secure way. Another option is to use an environment variable and access it using ^Sys.getenv. In general, we advise not to store keys directly in code files.

But before we dive into the three-step process, we first need to get our CVRP into R. 

Formulate a CVRP in R

Let’s formulate the problem first directly in R using nested lists and then go over the details. The structure corresponds to the required input schema, such that it can be converted to JSON automatically.

problem <- list(
  defaults = list(
    vehicles = list(
      speed = 10,
      start_location = list(lon = -96.659222, lat = 33.122746),
      end_location = list(lon = -96.659222, lat = 33.122746)
    )
  ),
  vehicles = list(
    list(
      id = "Vehicle 1",
      capacity = 2
    ),
    list(
      id = "Vehicle 2",
      capacity = 3
    )
  ),
  stops = list(
    list(
      id = "Stop A",
      location = list(lon = -96.75038245222623, lat = 33.20580830033956),
      quantity = -1
    ),
    list(
      id = "Stop B",
      location = list(lon = -96.54613745932127, lat = 33.2259142720506),
      quantity = -1
    ),
    list(
      id = "Stop C",
      location = list(lon = -96.61059803136642, lat = 33.23528740544529),
      quantity = -1
    ),
    list(
      id = "Stop D",
      location = list(lon = -96.79586982112724, lat = 33.10492159118987),
      quantity = -1
    )
  )
)

Even without having read the full API input schema specification, it is already clear what the problem is about. We have 2 vehicles with different capacities and 4 stops, each consuming 1 quantity. Thus we will need both vehicles to serve all stops. Each stop has a position and we use the global default settings to set a common start/end location for the vehicles as well as a speed in m/s and the date time when the shift of the vehicle starts. 

Note that instead of setting the same quantity for each stop, we could have also used the global default settings for stops.

In the next section we use jsonlite through the httr package to convert the problem from above into the correct JSON format.

A full overview about the cloud format can be found in our docs.

Step 1: Submit the problem

First we need to submit the problem from above to our run endpoint. We can use the httr package for this purpose, which can automatically convert named R lists to a JSON string. The following code constructs the correct HTTP POST request.

We also set an explicit time limit of 5 seconds for the solver in the options part of the problem definition. This means that the solver will stop searching for the better routes after 5 seconds. Our solver is optimized to deliver good solutions fast, but it is always a tradeoff between solution quality and runtime limits.

library(httr)
headers <- add_headers(
  Authorization = paste("Bearer", API_KEY)
)
response <- POST(
  url = URL,
  body = list(
    input = problem,
    options = list(
        solve.duration = "5s"
    )
  ),
  encode = "json",
  headers,
  content_type_json(),
  accept_json()
)
response

Response [https://api.cloud.nextmv.io/v1/applications/nextroute/runs]
  Date: 2022-04-26 11:02
  Status: 202
  Content-Type: application/json
  Size: 49 B
{"run_id":"RUN_ID_IS_HERE", …}

If successful, the returned result is a ^runID. This ID identifies your run and lets you query the status and retrieve the result.

stopifnot(status_code(response) == 202)
run_id <- content(response)$run_id

In a production system, you would need to check that the server responded with status `202 Accepted` before continuing. For example, the system could respond with a `429` status code that indicates you hit a rate limit and you’ll need to try it again in a few moments. In addition, you may want to use jsonlite directly to construct the JSON string first, before passing it to httr, to have more control over the conversion process and to increase testability of your code.

Step 2: Wait until the problem is solved

The Nextmv Cloud API is designed to be regularly polled until the status of a run is final. We use purrr’s insistently function to retry the status query multiple times. Wrapping everything with possibly then ensures that we always retrieve the status as a character.

library(purrr)
query_for_status <- function(run_id) {
  response <- GET(
    url = paste0(URL, "/", run_id),
    headers,
    content_type_json(),
    accept_json()
  )
  if (status_code(response) != 200) {
    stop("Call to API failed")
  }
  result <- content(response)
  status <- result$metadata$status
  if (!(status %in% c("succeeded", "failed"))) {
    stop("Run is not final yet")
  }
  status
}

robust_query_for_status <- insistently(
  query_for_status, 
  # try 5 times and wait 2 seconds between calls
  rate_backoff(pause_min = 2, pause_cap = 2, jitter = FALSE),
) |> possibly(otherwise = "failed")

# The following call only returns "succeeded" or "failed" if anything goes
# wrong.
stopifnot(robust_query_for_status(run_id) == "succeeded")

Alternatively, you can write a simple for loop retrying the HTTP call until the status changes from started or requested to succeeded, failed or timed_out. Our code snippets in Python give a good template for that approach.

Step 3: Download the solution

Now since we know the status is succeeded, we can download the result. Again, we use the httr package to send the HTTP GET request and also convert the response into a named list.

response <- GET(
  url = paste0(URL, "/", run_id),
  headers,
  content_type_json(),
  accept_json()
)
output <- content(response)$output
solution <- output$solutions[[1]]

The solution variable is a list with four named elements:

• ^hop - information about our internal solver version.
• ^options - the solver options used for this run.
• ^solutions - the solutions returned by the solver. In the case of nextroute, this is always exactly one.
• ^statistics - some statistics about the run.

Plot the result

As a final step, we show how to extract the routes from the solution and plot it.

First, let’s extract the overall travel time, which is the quantity that is minimized by default.

objective_value <- solution$objective$value

Then we build a data frame of all routes:

library(dplyr)
routes <- solution$vehicles |>
  # Collect the route for each vehicle
  map(~ bind_cols(
    vehicle = .x$id, bind_rows(map(.x$route, ~flatten(.x$stop)))
    )) |>
  # Combine everything into one data frame
  bind_rows()
routes

# A tibble: 8 × 4
  vehicle   id               lon      lat
  <chr>     <chr>            <dbl>    <dbl>
1 Vehicle 1 Vehicle 1-start  -96.7    33.1
2 Vehicle 1 Stop D           -96.8    33.1
3 Vehicle 1 Stop A           -96.8    33.2
4 Vehicle 1 Vehicle 1-end    -96.7    33.1
5 Vehicle 2 Vehicle 2-start  -96.7    33.1
6 Vehicle 2 Stop C           -96.6    33.2
7 Vehicle 2 Stop B           -96.5    33.2
8 Vehicle 2 Vehicle 2-end    -96.7    33.1

Having everything in a data frame now lets us easily use ggplot2 to create a very basic plot of the routes as an illustrative example.

library(ggplot2)
ggplot(routes) +
  aes(x = lon, y = lat, color = vehicle, group = vehicle) +
  geom_point() +
  geom_path() +
  coord_map() +
  ggtitle(
    "Optimized plan for 2 vehicles and 4 stops",
    paste("Total travel time:", round(objective_value, 3))
  )

Nextmv Cloud also offers interactive visualizations out of the box that utilize the real road network:

How to continue from here

Congratulations, you’ve successfully solved a simple CVRP with R and the Nextmv Cloud API. There’s more to explore from here. 

For example, if you want to integrate the Nextmv solver into a Shiny application, take a look into promises to better build a responsive app using asynchronous calls to our API. And if you are interested in the broader spectrum of optimization packages in R, you should definitely take a look at CRAN’s Task View on Optimization and Mathematical Programming.

There are also several other demo input files to explore within the Nextmv Cloud console. It’s also easy to experiment with many other features such as compatibility attributes, cluster objectives and constraints, route limits such as maximum duration or distance, vehicle activation penalty, and more. 

It’s easy to create a free Nextmv Cloud account. We have options for more customization. If you want to talk to our team, just contact us.