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).

Multi-Itinerary Optimization API Screenshot

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
 
  • Multi-day route planning
  • Multiple agents and multiple shifts
  • Service time windows
  • Priority of stops
  • Dwell time (i.e., how long an agent needs to be at a location
  • Predicted Traffic
 
  • Vehicle capacity
  • Quantity (to be picked up or dropped off) at each itinerary location
  • Pick up and drop off location sequencing dependencies
  • Depot location which can be visited multiple times to pick up loads as needed

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.

Multi-Itinerary Optimization API - Scenario 1 Screenshot

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.

Multi-Itinerary Optimization API - Scenario 2 Screenshot

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

Share on twitter Share on facebook Share on linkedin Share on linkedin