Delivery made easy with the HERE Waypoint Sequence API

The HERE Routing API is great. If you know where you need to be, it will help get you there, whether you’re walking or driving a truck. It will even help you dodge traffic jams and let you catch the subway in time. Sometimes though, knowing where you’re going isn’t enough. This is particularly true if you’re going to a lot of different places.

Let’s look at an example and pretend we are in the package delivery business around the picturesque seaside resort of Milton Keynes. We have ten packages deliver to ten different addresses. Obviously, we want to deliver these packages as efficiently as possible.

As a first step, we can use the HERE Geocoder API to convert those addresses into geographic coordinates. Check the Geocoder documentation for details on how to do this. We can then call the Routing API, using these coordinates as waypoints.

This returns the following route. (If you need and app code and id, you can sign up for a HERE free trial.)

Source: HERE

While this will certainly allow us to deliver all our packages, it would require a lot of driving back and forth on the A5, taking over 150km of driving to get the job done! Clearly, a better route needs to be found.

At this point, we could start a discourse on combinatorial optimisation, and argue that delivering packages is not just hard, but actually NP-hard work. (Unfortunately, our boss doesn’t have a computer science degree and doesn’t care about our excuses.)

In fact, he would probably just tell us to deliver the packages faster, or else. (And if he did have a relevant degree, he’d probably start yelling at us about heuristic techniques.)

So, what are we to do? Well, fortunately there’s an API for that! It’s called the Waypoint Sequence API. The Waypoint Sequence API allows us to request the optimal order in which we should travel between a set of waypoints to minimise either the overall travel time or the distance travelled. It will even take road network restriction and traffic patterns into account while doing so.

This sounds exactly like what we need, so let’s have a look at another example and pretend we’re in Auckland for a business trip. We have found a few hours of free time before our flight leaves and we want to see as much of the city as possible in as little time as possible. Here’s a list of sights we figure we can squeeze in.

We can see that the API has a reasonably simple interface. All we need to do is give it the list of destinations, our preferred mode of transport and whether we want to optimise for time or distance. We also need to provide a start point. When delivering packages this will likely be our logistics hub, but for our sightseeing tour we’ve picked a hotel. Finally, we need to provide a startwaypoint and a departureTime. The departure time is needed, because the Waypoint Sequence API cleverly takes both current and historic traffic into account for its calculations.

Note that the id strings in the destination parameter are optional, but can be helpful as they will also be included in the response. Of course, you can simple use the lat/long coordinates by themselves (e.g. destination4=-36.84827,174.76223).

You may note that we seem to be optimising for time twice, once with the mode=fastest parameter and once with the improveFor=time parameter. Using improveFor will optimise the entire sequence for time, while mode will optimise the routes between two individual waypoints for time. In our example we are short on time, so we will optimise for speed in both instances.

Let’s have a look at the result.

As we can see, the result contains a waypoint object with the optimised sequence of waypoints, conveniently numbered, and an interconnections object with information about time and distance for each route between two consecutive waypoints. It also gives us some information about the time and distance of the total route.

What it doesn’t give us, however, is an actual route. So, we once again need to put the waypoints into the routing algorithm, except this time we do it in the optimised order.

Our sightseeing route now looks like this:

Source: HERE

We can get all our sightseeing done in under 2 hours and catch our plane back home in time. Let’s go back to our original example now.

Speed is important, but our boss also cares about fuel economy, so this time we are going to optimise by distance. Thus, we set improveFor=distance. We’re also driving a delivery truck, not a car, which means we will be using the truck mode for routing. Check here for more information on the various special parameters available for truck routing.

Regardless of the order in which we deliver our packages, we need to be back at the logistics hub at the end of our work day. This means we will also set the optional end parameter to get us back to where we started from. Our API call now looks like this:

If we feed this into the routing API, we get the following result:

Source: HERE

Much better. We get one clean route around town, with deliveries neatly clustered. Thank you, Waypoint Sequence API!

Of course, that’s not the whole story. When delivering packages there are many other constraints we may have to consider. For example:

• Some packages must be delivered before others.
• Some packages must be delivered within a specific time frame.
• Some packages must be delivered at a specific time.
• Delivering each package takes some time, which influences overall delivery times.
• Delivery drivers work hard and deserve some breaks. It’s not just a good idea, it’s often the law!

The Waypoint Sequence API supports all these constraints and can provide optimised routes and delivery times based on them.

Did you know that Grey Matter has a HERE specialist mapping team who can help you with API and platform licensing advice. Email: [email protected] or call them on +44 (0)1364 655133.

[This article by Richard Suselbeck was first published on the HERE Technologies developer blog and republished with permission.]