Enhanced Features Support Fleets as Delivery Demand Surges Amid COVID-19
The demand for deliveries has surged because of the COVID-19 pandemic. People are staying home and getting their groceries and other essentials delivered to their doorsteps. With this increase in demand comes a greater need for effective multi-stop route planning for delivery drivers. Launched in May 2019, the Bing Maps Multi-Itinerary Optimization (MIO) API automates route planning for multiple agents travelling between multiple locations. Since launch, we have listened to customer feedback and made a series of enhancements to meet the growing need.
We're happy to announce that the MIO API now supports up to 50 agents and 500 itinerary locations (versus 10 agents and 100 locations at the initial launch).
On top of the rich features introduced in the previous Bing Blog, we have also added some new features to the MIO API to support more scenarios. The following table summarizes the previously supported features and newly added ones.
| Features Supported at Launch | New Features Added Since Launch |
|---|---|
|
|
We encourage you to try the MIO API demo to see how the API handles optimization for the sample scenarios and selected parameters.
In this blog, we will further explain how the new features work using some new sample scenarios below. For simplicity of interpreting the optimization results, we will use single agent examples to demonstrate how the optional parameters capacity, quantity, depot, and dropOffFrom can be used, respectively.
Scenario 1: Food delivery courier picking up food from restaurants and delivering to customers
This scenario will make use of capacity, quantity, and dropOffFrom options. A food delivery carrier named “Sam” has a thermal bag which can carry up to 12 food containers. He needs to pick up the food orders from some restaurants before delivering the orders to customers. To define this sequence of constraints, we’ll use the dropOffFrom parameter.
Agents
| Agent | Shift Start | Start Location | Shift End | End Location | Capacity |
|---|---|---|---|---|---|
| Carrier_Sam | 2020-01-09T08:00:00 | 47.694117,-122.378189 | 2020-01-09T19:00:00 | 47.707079,-122.355227 | 12 |
Itinerary Items
| Location Name | Opening | Closing | Dwell | Priority | Location | Quantity | Drop Off |
|---|---|---|---|---|---|---|---|
| Customer 1 | 2020-01-09T18:00:00 | 2020-01-09T20:00:00 | 0:02:00 | 1 | 47.679810,-122.383036 | -1 | Pizza Place |
| Customer 2 | 2020-01-09T17:30:00 | 2020-01-09T19:00:00 | 0:02:00 | 1 | 47.677159,-122.365525 | -1 | Mexican Food |
| Customer 3 | 2020-01-09T18:00:00 | 2020-01-09T20:00:00 | 0:02:00 | 1 | 47.684664,-122.364840 | -2 | Pizza Place |
| Customer 4 | 2020-01-09T17:30:00 | 2020-01-09T19:00:00 | 0:02:00 | 1 | 47.686744,-122.354712 | -1 | Mexican Food |
| Customer 5 | 2020-01-09T18:00:00 | 2020-01-09T20:00:00 | 0:02:00 | 1 | 47.696219,-122.342180 | -1 | Pizza Place |
| Customer 6 | 2020-01-09T18:00:00 | 2020-01-09T19:00:00 | 0:02:00 | 1 | 47.692430,-122.391997 | -1 | Pizza Place |
| Pizza Place | 2020-01-09T18:00:00 | 2020-01-09T20:00:00 | 0:10:00 | 1 | 47.670204,-122.382122 | 5 | |
| Mexican Food | 2020-01-09T17:30:00 | 2020-01-09T20:00:00 | 0:10:00 | 1 | 47.694184,-122.355996 | 2 |
Note that quantity is an optional parameter defined by numeric values that represents the load quantity in terms of volume, weight or amount (i.e., pallet, case or passenger counts), etc. that the vehicle delivers to or picks up from each location. In this scenario, it can be used to define the number of food containers the carrier can carry. A negative value of quantity indicates dropping off loads at a location, while a positive value of quantity indicates picking up loads from a location. The table below summarizes the optimized itinerary for Carrier_Sam for the above itinerary items.
Optimized Itinerary
| Location Index | Agent | Start Time | Duration | End Time | Location Name | Priority | Location | Quantity | Drop Off |
|---|---|---|---|---|---|---|---|---|---|
| 1 | Carrier_Sam | Shift 1 Start: 2020-01-09T17:21:50 | 1 | 47.694117,-122.378189 | |||||
| 2 | Carrier_Sam | 2020-01-09T17:30:00 | 00:10:00 | 2020-01-09T17:40:00 | Mexican Food | 1 | 47.694184,-122.355996 | 2 | |
| 3 | Carrier_Sam | 2020-01-09T17:47:39 | 00:02:00 | 2020-01-09T17:49:39 | Customer 2 | 1 | 47.677159,-122.365525 | -1 | Mexican Food |
| 4 | Carrier_Sam | 2020-01-09T18:00:00 | 00:10:00 | 2020-01-09T18:10:00 | Pizza Place | 1 | 47.670204,-122.382122 | 5 | |
| 5 | Carrier_Sam | 2020-01-09T18:17:14 | 00:02:00 | 2020-01-09T18:19:14 | Customer 1 | 1 | 47.679810,-122.383036 | -1 | Pizza Place |
| 6 | Carrier_Sam | 2020-01-09T18:26:16 | 00:02:00 | 2020-01-09T18:28:16 | Customer 6 | 1 | 47.692430,-122.391997 | -1 | Pizza Place |
| 7 | Carrier_Sam | 2020-01-09T18:37:29 | 00:02:00 | 2020-01-09T18:39:29 | Customer 3 | 1 | 47.684664,-122.364840 | -2 | Pizza Place |
| 8 | Carrier_Sam | 2020-01-09T18:42:06 | 00:02:00 | 2020-01-09T18:44:06 | Customer 4 | 1 | 47.686744,-122.354712 | -1 | Mexican Food |
| 9 | Carrier_Sam | 2020-01-09T18:48:56 | 00:02:00 | 2020-01-09T18:50:56 | Customer 5 | 1 | 47.696219,-122.342180 | -1 | Pizza Place |
| 10 | Carrier_Sam | Shift 1 End: 2020-01-09T18:55:53 | 1 | 47.707079,-122.355227 |
The itinerary for Carrier_Sam is illustrated in the map below. Location 1 is where the agent starts his shift and Location 10 is where his shifts ends.
Note that Carrier_Sam first picks up two orders from “Mexican Food” at Location 2 and then makes his first Mexican Food delivery to “Customer 2” at Location 3. After that, he picks up all orders from “Pizza Place” at Location 4 and completes the route with four “Pizza Place” deliveries at different locations as well as another Mexican Food delivery at “Customer 4” at Location 8.
Scenario 2: Home delivery service picking up orders from the warehouse and delivering to customers during different time slots.
This scenario will make use of the capacity, quantity, and depot parameter options. A delivery driver “John” needs to pick up some large objects like home appliances and furniture from a warehouse and have them delivered to customers at different locations. Each customer has a specified time window for delivery.
If the delivery quantity is large and exceeds the capacity of the agent’s vehicle, the agent needs to be able to make multiple trips during the day to reload at the "Warehouse" and deliver all goods. In the MIO API request, we can define the “Warehouse” as depot to allow the location to be visited more than once. In this example, quantity can be used to represent the volume in square meters.
Agents
| Agent | Shift Start | Start Location | Shift End | End Location | Capacity |
|---|---|---|---|---|---|
| driver_John | 2020-01-09T08:00:00 | 47.663181,-122.299885 | 2020-01-09T18:00:00 | 47.663181,-122.299885 | 16 |
Itinerary Items
| Location Name | Opening | Closing | Dwell | Priority | Location | Quantity | Depot |
|---|---|---|---|---|---|---|---|
| Warehouse | 2020-01-09T08:00:00 | 2020-01-09T18:00:00 | 00:30:00 | undefined | 47.664275,-122.300303 | 100 | True |
| Customer 5 | 2020-01-09T08:00:00 | 2020-01-09T11:00:00 | 00:10:00 | undefined | 47.696219,-122.342180 | -1 | |
| Customer 6 | 2020-01-09T13:00:00 | 2020-01-09T18:00:00 | 00:10:00 | undefined | 47.692430,-122.391997 | -2 | |
| Customer 1 | 2020-01-09T10:00:00 | 2020-01-09T14:00:00 | 00:10:00 | undefined | 47.679810,-122.383036 | -4 | |
| Customer 2 | 2020-01-09T08:00:00 | 2020-01-09T12:00:00 | 00:10:00 | undefined | 47.677159,-122.365525 | -1 | |
| Customer 3 | 2020-01-09T13:00:00 | 2020-01-09T18:00:00 | 00:10:00 | undefined | 47.684664,-122.364840 | -2 | |
| Customer 4 | 2020-01-09T08:00:00 | 2020-01-09T18:00:00 | 00:10:00 | undefined | 47.686744,-122.354712 | -5 | |
| Customer 7 | 2020-01-09T08:00:00 | 2020-01-09T11:00:00 | 00:10:00 | undefined | 47.687759,-122.302118 | -3 | |
| Customer 8 | 2020-01-09T12:00:00 | 2020-01-09T17:00:00 | 00:10:00 | undefined | 47.701393,-122.295252 | -2 | |
| Customer 9 | 2020-01-09T08:00:00 | 2020-01-09T11:00:00 | 00:10:00 | undefined | 47.660018,-122.356535 | -6 | |
| Customer 10 | 2020-01-09T14:00:00 | 2020-01-09T18:00:00 | 00:10:00 | undefined | 47.700006,-122.363230 | -1 | |
| Customer 11 | 2020-01-09T10:00:00 | 2020-01-09T18:00:00 | 00:10:00 | undefined | 47.673312,-122.329413 | -2 | |
| Customer 12 | 2020-01-09T08:00:00 | 2020-01-09T18:00:00 | 00:10:00 | undefined | 47.691688,-122.323233 | -3 | |
| Customer 13 | 2020-01-09T13:00:00 | 2020-01-09T17:00:00 | 00:10:00 | undefined | 47.680131,-122.350699 | -3 |
The table below summarizes the optimized itinerary for driver_John for the above itinerary items.
Optimized Itinerary
| Location Index | Agent | Start Time | Duration | End Time | Location Name | Priority | Location | Quantity | Depot |
|---|---|---|---|---|---|---|---|---|---|
| 1 | driver_John | Shift 1 Start: 2020-01-09T08:00:00 | 1 | 47.664100,-122.300928 | |||||
| 2 | driver_John | 2020-01-09T08:01:16 | 00:30:00 | 2020-01-09T08:31:16 | Warehouse | 1 | 47.664275,-122.300303 | 16 | True |
| 3 | driver_John | 2020-01-09T08:40:28 | 00:10:00 | 2020-01-09T08:50:28 | Customer 12 | 1 | 47.691688,-122.323233 | -3 | |
| 4 | driver_John | 2020-01-09T08:55:15 | 00:10:00 | 2020-01-09T09:05:15 | Customer 5 | 1 | 47.696219,-122.342180 | -1 | |
| 5 | driver_John | 2020-01-09T09:08:24 | 00:10:00 | 2020-01-09T09:18:24 | Customer 4 | 1 | 47.686744,-122.354712 | -5 | |
| 6 | driver_John | 2020-01-09T09:22:14 | 00:10:00 | 2020-01-09T09:32:14 | Customer 2 | 1 | 47.677159,-122.365525 | -1 | |
| 7 | driver_John | 2020-01-09T09:36:57 | 00:10:00 | 2020-01-09T09:46:57 | Customer 9 | 1 | 47.660018,-122.356535 | -6 | |
| 8 | driver_John | 2020-01-09T09:56:31 | 00:30:00 | 2020-01-09T10:26:31 | Warehouse | 1 | 47.664275,-122.300303 | 3 | True |
| 9 | driver_John | 2020-01-09T10:32:41 | 00:10:00 | 2020-01-09T10:42:41 | Customer 7 | 1 | 47.687759,-122.302118 | -3 | |
| 10 | driver_John | 2020-01-09T10:49:02 | 00:30:00 | 2020-01-09T11:19:02 | Warehouse | 1 | 47.664275,-122.300303 | 16 | True |
| 11 | driver_John | 2020-01-09T11:26:10 | 00:10:00 | 2020-01-09T11:36:10 | Customer 11 | 1 | 47.673312,-122.329413 | -2 | |
| 12 | driver_John | 2020-01-09T13:00:00 | 00:10:00 | 2020-01-09T13:10:00 | Customer 13 | 1 | 47.680131,-122.350699 | -3 | |
| 13 | driver_John | 2020-01-09T13:15:32 | 00:10:00 | 2020-01-09T13:25:32 | Customer 3 | 1 | 47.684664,-122.364840 | -2 | |
| 14 | driver_John | 2020-01-09T13:32:33 | 00:10:00 | 2020-01-09T13:42:33 | Customer 1 | 1 | 47.679810,-122.383036 | -4 | |
| 15 | driver_John | 2020-01-09T13:48:19 | 00:10:00 | 2020-01-09T13:58:19 | Customer 6 | 1 | 47.692430,-122.391997 | -2 | |
| 16 | driver_John | 2020-01-09T14:03:59 | 00:10:00 | 2020-01-09T14:13:59 | Customer 10 | 1 | 47.700006,-122.363230 | -1 | |
| 17 | driver_John | 2020-01-09T14:26:41 | 00:10:00 | 2020-01-09T14:36:41 | Customer 8 | 1 | 47.701393,-122.295252 | -2 | |
| 18 | driver_John | Shift 1 End: 2020-01-09T14:46:18 | 1 | 47.664100,-122.300928 |
The itinerary for driver_John is illustrated in the map below. With a capacity constraint of 16, driver_John needs to return to the “Warehouse” several times to pick up more quantity to fulfil the delivery requests from all the customers with a total quantity of 35.
On the map, Location 1 denotes where the agent starts his shift. Location 2, Location 8 and Location 10 all overlap with Location 1, as the driver needs to load several times from the “Warehouse." By setting "depot": true in the JSON request, the API allows the truck to visit an itinerary location more than once.
Learn More
To learn more about using the MIO API to develop a multi-itinerary optimization solution, please refer to the MIO API documentation. This documentation has details including various options, how each scenario works, supported methods, sample Request Body and Response, how a transaction is calculated and more.
For details about all of the Bing Maps APIs that are part of the Bing Maps Platform and how to get licensed, please visit microsoft.com/maps.
As we continue to enhance and expand on our APIs, we encourage you to connect with us on the Bing Maps Forum to share your thoughts and let us know what features you would like to see us add in the future.
– Bing Maps
Source: Bing Blog Feed