In this blog post we will summarize all the possibilities offered by Bing Maps to solve routing problems, including utilities, pricing, constraints and others. The most basic example of routing is the travelling salesman problem and, although we will not go into details about the algorithm, we will explain how the distance matrix API can help us solve it and how much it will cost us.
Travelling Salesman Problem
The Travelling Salesman Problem(also TSP) is an NP-hard problem in combinatorial optimization within graph theory that requires the most efficient (i.e., least total distance) Hamiltonian cycle a salesman can take through each of a set of cities (Figure 1). The TSP has several applications even in its basic concept, such as planning and logistics.
Figure 1. Example of a Travelling Salesman Problem solved.
Bing Maps provides four different APIs: Distance Matrix, Isochrones, Truck Routing and Snap-To-Road. In this post we will talk about the Distance Matrix API and the features that provides for solving the Travelling Salesman and similar problems.
Distance Matrix API
The Bing Maps Distance Matrix API assists in calculating travel time and distances in many-to-many scenarios with an optional travel-time histogram. Used to optimize routing, the Distance Matrix API service determines the best route possible, by reordering stops based on the trip’s parameters, including time or distance, mode of transportation, start and end time, predicted traffic, and more.
In addition, the Bing Maps Distance Matrix API providestravel time and distances for a set of origins and destinations. The distances and times returned are based on the routes calculated by the Bing Maps Route API. Times are based on predictive traffic information, depending on the start time specified in the request. Distance matrices can be calculated for driving, walking and public transit routes. This API can also generate distance matrices that optionally includes a histogram of travel times over a period with a set interval that takes into consideration the predicted traffic at those times.
Distance matrices are used in several different types of applications. The most common is to power algorithms which solve the Travelling Salesman Problem (TSP). Some other common applications include:
- Sorting search results by their actual travel distance or time.
- Determine arrival times based on travel times.
- Calculate the difference in commute times between locations. For example: We are looking to move to a new office, what is the impact on commute times for our staff?
- Clustering data based on travel time and distances. For example: Find all homes that are within one mile of a corner store.
When you make a request, the response returns a Distance Matrix resource that contains either an array of Distance Matrix cells or information on the asynchronous request that was made to calculate a distance matrix. Each distance matrix cell contains the location and index of the origin and destination it is related to, the travel time, and distance. If a distance matrix histogram is requested, a departure time for when in the histogram the cell it is related to will be included.
Requests to the distance matrix API can be done in one of two ways:
- Most requests can be made with a simple synchronous GET or POST request.
- More complex driving related requests which take longer to process, such as calculating a histogram of travel times and distances for each cell of a matrix, can be made by making an asynchronous Distance Matrix request. This type of request is only accepted when the travel mode is set to driving and a start time has been specified.
A distance matrix can be requested that has up to 2500 origins-destinations pairs which is calculated by multiplying the number of origins, by the number of destinations. For example, you can have 1 origin, and 2500 destinations, or 50 origins and 50 destinations. A histogram of travel times and distances can be requested but is limited to a distance matrix that has a maximum of 100 origins-destinations pairs when the request is made asynchronously, and 10 origins-destinations pairs when made synchronously. The maximum time interval between the start and end time when calculating a distance matrix histogram is 24 hours.
When calculating a simple distance matrix each origin-destination pair will generate a single cell in the matrix.
For example, a matrix that has 2 origins, and 5 destinations, will generate 10 cells where 2 * 5 = 10. When a matrix includes a histogram, each origin-destination pair will have a cell in the matrix for each time interval. The number of time intervals that a request will have depends on the resolution, start and end times.
For example, a matrix that has 2 origins, 5 destinations, and retrieves time intervals in 15-minute increments (resolution = 1) over 24 hours, will generate 960 cells where 2 * 5 * 24/0.25 = 2 * 5 * 24 * 4 = 960.
Cells will not be generated for origin-destination pairs that have the same index and coordinate. These will not be included in the transaction counts. If these exist in your query, you can subtract these from the calculated number of cells above to get a more accurate number for estimating transaction counts.
When calculating billable transactions, a billable transaction is generated for every 4 cells in a matrix, rounded up to the nearest whole integer. For a simple matrix, billable transactions will be calculated using the following formula:
For example, a matrix that has 4 origins, and 5 destinations, will generate 5 billable transactions where Ceiling (4 * 5 * 1/4) = 5.
When calculating a matrix which includes a histogram, only the first 30-time intervals in each origin-destination pair are counted towards billable transactions, any additional time intervals are provided for free.
For example, a matrix that has 4 origins, 5 destinations, and retrieves time intervals in 15-minute increments (resolution = 1) over 24 hours, will generate 150 cells where Ceiling (1/4 * 4 * 5 * Min (30, 24/0.25)) = Ceiling (1/4 * 4 * 5 * Min (30, 96)) = Ceiling (1/4 * 4 * 5 * 30) = 150. Note that 24/0.25 = 24 * 4 = 96, but since only the first increments per origin-destination pair is counted towards billable transaction, 66-time intervals are excluded from the transaction calculation per origin-destination pair, thus saving you a total of 330 billable transactions.
In Figure 2 you can see the pricing for every tier and amount of billable transactions based in Azure customers.
Figure 2. Pricing for transactions
Bing Maps key
Bing Maps templates support both HTTP and HTTPS protocols but, to use this API you must have a Bing Maps key. For creating a key, you need to follow these steps:
- Go to the Bing Maps Dev Center at https://www.bingmapsportal.com/.
o If you have a Bing Maps account, sign in with the Microsoft account that you used to create the account or create a new one. For new accounts, follow the instructions in Creating a Bing Maps Account.
- Select My keysunder My Account.
- Select the option to create a new key.
- Provide the following information to create a key:
o Application name: Required. The name of the application.
o Application URL: The URL of the application. This is an optional field which is useful in helping you remember the purpose of that key in the future.
o Key type: Required. Select the key type that you want to create. You can find descriptions of key and application types here.
o Application type: Required. Select the application type that best represents the application that will use this key. You can find descriptions of key and application types here.
- Click the Create The new key displays in the list of available keys. Use this key to authenticate your Bing Maps application as described in the documentation for the Bing Maps API you are using.
Synchronous Distance Matrix Request URL (GET)
Retrieves a simple distance matrix for a set of origins and destinations using a HTTP GET request.
Synchronous Distance Matrix Request URL (POST)
Retrieves a simple distance matrix for a set of origins and destinations using a HTTP POST request.
HTTP POST Request URL
Asynchronous Distance Matrix Request URL (GET)
Creates a job to calculate a distance matrix using an asynchronous GET request. This type of request is only supported when the travel mode is set to driving. A start time must be specified when making asynchronous requests.
Asynchronous Distance Matrix Request URL (POST)
Creates a job to calculate a distance matrix using an asynchronous POST request. This type of request is only supported when the travel mode is set to driving. A start time must be specified when making asynchronous requests.
HTTP POST Request URL
HTTP POST Header
HTTP POST body
URL for checking Asynchronous Request status (GET)
The initial asynchronous response includes a callbackUrl property which contains the URL that can be used to check the status of the job. Alternatively, the callback URL can also be generated by appending the requestId that is returned in the initial asynchronous request along with the same Bing Maps key used, with the DistanceMatrixAsyncCallback endpoint as shown below. The response from this request will indicate if the request is complete or not, if complete it will provide a resultUrl property which is a URL that can be used to download the results.
Once you have full access to Bing Maps Distance Matrix API you can use this matrix for solving the Travelling Salesman Problem not just using straight distance, also road distance and travel time. For this, you can apply any algorithm as metaheuristics by using this matrix for every calculation and optimization to get high precision optimized routes for different applications such as logistics or planning.
At Nouss Intelligence SL we have been used this tool not just for solving the Travelling Salesman Problem, also the routing problems with multiple constraints to provide useful, reliable and stable solutions for most of our customers. These constraints include time windows, capacitated vehicles, multiple origins, rounded and non-rounded trips and a lot more. For solving these constraints, we considered one of the most powerful utilities that we think this API have: the non-limitation to the use of square matrices. This feature allows us to achieve a wide range of possibilities for solving different kind of routing problems with a lot of value for real customers.