In this blog post, we will use Nextmv Cloud, 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.
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 JSON-in-JSON-out API for automating decisions, such as how best to assign stops to vehicles. You can create a free Nextmv Cloud account (no credit card required) to follow along with the tutorial in this post.
There are essentially three steps involved when calling our cloud API:
- Submit a problem encoded as JSON and receive a runID.
- Wait and poll the system using the runID until the run is completed.
- 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 Cloud console. After you have logged in to the console, go to the API page and click "Click to reveal API Key" under the header "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.
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.
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 one 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. 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.
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.
If successful, the returned result is a runID. This ID identifies your run and lets you query the status and retrieve the result.
We assume here that the call never fails. In a production system, you would need to check that the server responded with status 202 Accepted before continuing. In addition you may want to use jsonlite directly to construct the JSON string first, before passing it to httr to have more control about 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.
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 Go and 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.
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.
- state - the final state (aka. solution) found by the solver.
- 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.
Then we build a data frame of all routes:
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.
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, penalties, backlogs, route limits, vehicle initialization costs, and more.