This project includes an algorithm and visual for the Vehicle Routing Problem with Drones (VRPD) using a dataset from the 2021 Amazon Last Mile Routing Research Challenge. The VRPD is a variant of the Vehicle Routing Problem (VRP) that includes the use of drones to deliver packages. Solving the VRPD involves optimization, such as those used for the Traveling Salesman Problem (more spefically, the Flying Sidekick Traveling Salesman Problem). Our algorithm and visuals is the first time VRPD is applied on a real-world, large, public dataset.
The dataset is from the 2021 Amazon Last Mile Routing Research Challenge and includes Amazon routing information from Amazon drivers in 2018 in Seattle, Los Angeles, Austin, Chicago, and Boston. This dataset is the "first large, real-world, publicly available routing data set" and includes a training and evaluation dataset. The training dataset consists of 6,112 routes performed by Amazon drivers labeled by perceived quality (low, medium, or high). The evaluation dataset contains an additional 3,072 historically observed routes all with high quality
Dataset (3.1 GB) can be downloaded from an S3 bucket using the AWS CLI using the command
aws s3 sync --no-sign-request s3://amazon-last-mile-challenges/almrrc2021/ ./almrrc2021/
or following the instructions here https://registry.opendata.aws/amazon-last-mile-challenges/
The algorithm section includes an analysis of the Amazon Dataset (analysis.ipynb), a very naive algorithm for route creation with drone (initial_algorithm.ipynb), the main algorithm for route creation (main_algorithm.ipynb), and a file to analyze the times of creates sequences (time_analysis.ipynb). The helper.ipynb file is to generate a vehicle only events and paths.
For our visual, we need the timesteps of every action by the vehicle and drone. Thus even if we have an existing route path, we must still need to create the events accompanying the path.
For a given route, the drone and vehicle have their own events and path.
The path is a series of stops with timestops and location. The structure is the same for drones and vehicles.
[
"id": 1,
"stop": "UX",
"coordinates": {
"lat": 47.937344,
"lng": -122.244952
}
},
{
"id": 2,
"stop": "GC",
"coordinates": {
"lat": 47.675824,
"lng": -122.308083
}
}, ... ]This is a sample of the events. The drone events are same in structure to vehcile events, except it may have different event_type.
[
{
"id": 1,
"event_type": "DEPART",
"stop_id": "UX",
"time": 0,
"coordinates": {
"lat": 47.937344,
"lng": -122.244952
}
}, ...
]This JSON element represents an event where a transport entity departs from stop UX at the very start of tracking (time: 0). The geographical position of the stop is given by the latitude and longitude coordinates, which place it at approximately 47.937344, -122.244952.
proposed_sequences.json are proposed vehicle only route sequences generated by solution of the 3rd place finisher of the Last Mile Routing Research Challenge - https://github.com/rasitabay/lastmile_challenge/tree/main. This repository contains instructions on how to generate proposed routes (we used a linux enviroment). We saved 100 generated sequences to proposed_sequences.json, so this step is not necessary.
Ensure that you have the Amazon dataset downloaded and is within the algorithm directory. Clone this repository and install necessary packages
pip install pandas plotly geopy numpy
Running this code should be simple as we only have Jupyter Notebooks. Cells must be run sequentially, and ensure each cell's output matches the exisiting output.
In order to visualize the results of our algorithm, we are using a Jupyter notebook (visualization.ipynb) with a Python package called VeRoViz (vehicle routing visualization) that has support for storing vehicle routing data and visualization it. Specifically, we can create vehicle routes with Pandas dataframes and plug them into VeRoViz methods that can create Leaflet maps or Cesium animations. Therefore, using our notebook, we generate a Cesium file that animates our results from the algorithm. Additionally, users can compare different routes on the webpage.
Run npm install.
Inside the Cesium folder, run command node server.js to run the Cesium animation on a webpage. Go to the generated link and add /veroviz to the end of the URL.