Optimizing Routes with Time Constraints

Showing how vehicle routing can be optimized in the presence of delivery time constraints

Route planning & management relies heavily on time, but not always in the way you might think. Delivery planning software has to lower an entire fleet's overall cost to company - even if this means increasing the time and cost of individual vehicles for the greater good. As the old adage goes, "time is money" and saving it is not always straightforward.

Generally, there are two types of time constraint that go into route planning:

  • Schedule time limits: When, and for how long, your fleet can operate (i.e. 9 - 5 Monday to Friday).
  • Delivery/location time constraint: A pickup or drop-off must occur within at a specific time, or within a small time window (i.e. Mrs Smith needs her medicine delivered between 9am and 10am on Monday).

Optimizing routes are subject to these two types of time constraint on a regular basis, but solving them often leads to some very powerful results. For example, you might not even know whether or not it is possible to make all your deliveries in a single day. But an efficient optimization can easily reveal this information one way or another. This has an important knock on effect in the sense that you can avoid growing your fleet (and associated costs) by understanding whether or not your current business requirements are even possible with your current fleet resources.

In this sense, route optimizations using time constraints is vital for understanding and managing your fleet size correctly.

In addition, optimized routes give you a clear understand of where and when your vehicles will be ahead of time. So, after optimizing routes it is possible to notify contacts of your estimated arrival time at each and every location. This means that instead of telling clients something vague like "we'll be there sometime tomorrow" (infuriating for clients who have better things to do that sit around waiting) you can now say, according to our schedule we will be at your door at, say, 11:45am.

Schedule Time Limitations

To understand how overall time limitations can affect the way vehicles are utilized in an optimized solution, let's contrast two situations. The first will have plenty of time available for vehicles to complete their routes, the second will severely restrict the available time.

Continuing with our Paris examples, here's a schedule with 10 locations and two vehicles with a standard 9am - 5pm day:

Schedule for route optimization showing time constraints

For the purposes of this example I have set the vehicle costs of each vehicle used to be precisely the same (otherwise the optimization would favor the cheaper vehicle and skew the results). Optimizing this schedule gives the following:

Optimized route showing single vehicle solution

There are two salient points here. First, only one vehicle was required. while obvious in this example there is quite a powerful underlying message. Imagine you are running a schedule with 50 available vehicles only to find out that, say, 40 vehicles can do everything. What effect would that have on your transport costs assuming your fleet requirements in the long term?

The second point is that the total time this vehicle required to complete the entire route was 2 hours and 51 minutes.

But what if you prefer to utilize all your vehicles (if the company is paying for them anyway) and instead would rather finish earlier?

Restricted Schedule Times

In this instance we know that one vehicle can do the entire route in a touch under 3 hours. Would it be possible for both vehicles to perform the same deliveries in under 2 hours? Bear in mind that the depot, in this specific example, is quite some distance from all the stops so both vehicles have a bit of travelling away from the depot before they can begin visiting locations - they then have to return afterwards, all in under two hours.

Here's the new schedule:

Route optimization with restricted time limits

as yo8u ca see, the Start and End time are now set from 9am to 11am, giving us a total schedule time of 2 hours. In this case, we're not sure if it's even possible for the vehicles to physically achieve what we're asking. Only optimization will tell us:

Optimized route showing two vehicles used to solve restrictive time limitations

We did it. And with plenty of time to spare. The Red Pickup completed its route in 1 hour, 50 minutes. While the white Pickup only took 1 hour, 44 minutes.

However, here's something worth noting. The Total Time, in other words the time taken by all the vehicles together, was 3 hours, 35 minutes. This is higher than the single vehicle solution that took less than 3 hours in total. In addition because two vehicles are being used and have to travel in similar directions to make all their stops in the given time frame, the costs have increased to $93 - up from $71.

This tells us that using a single vehicle is cheaper than using both vehicles. However, if it is more important to complete a route within a given time frame (as is most often the case) then the lowest cost solution morphs from using less vehicles to using more. While the multi-vehicle solution is not the lowest cost, it is the lowest cost solution that meets the specified objectives of the business.

Location Time Constraints

What happens if a pickup or drop-off location has its own time constraint. For example, Mrs Smith needs her medication between 9am and 10am in the morning. In this instance its imperative to get a vehicle to that location within that time frame - even if it means changing from the optimal, low cost solution to the lowest cost solution that has a vehicle there on time.

Setting a Time Window for a specific location is easy. Here's an example showing one set for the location Alesia:

Setting a time window constraint on a location

I've specifically chosen Alesia because it is one of the furthest locations from the depot, hopefully making this constraint quite disruptive on the schedule so that the changes to the optimal solution are more obvious.

Can you guess what will happen? Here's the new solution:

Route optimization showing location time constraint being fulfilled

As you can see, the Red Pickup managed to arrive at Alesia at 9:39 AM, well within the time window specified. In addition, we've maintained the optimal solution.

Perhaps we can shake things up by making Mrs Smith a little more anxious for her medication. Let's modify the time window to 9AM - 9:30AM, that's much earlier than the solution we obtained here. Changing this time constraint and optimizing gives the following result:

Affect of restrictive location time constraint on optimized route

Notice something a bit different about this solution? Well, it seems like Mrs Smith got her delivery on time. The Red Pickup arrived there at 9:22AM, 8 minutes before the delivery time constraint was due to expire. It also had to go straight there without being able to visit any other locations first.

This change to the optimal route had a knock-on effect. The White Pickup had to pick up some slack because of the changes in the Red Pickup route. This meant that overall our solution was tagged as Qualified. Qualified means that all the locations were visited correctly but that, in this instance, Time constraints were violated. If you look closely at the White Pickup timeline you'll noticed that it completed its route in 2 hours, 5 minutes. Approximately 5 minutes over the schedule time limit of 2 hours.

In addition, the time window constraint also meant a deviation from the otherwise optimal route leading to an increase in total costs of about $3 (and possibly one slightly irate driver who needs to stay on the road an extra 5 minutes).

So time based restrictions can have a large impact on route optimizations. But, they can also reveal some powerful insights into how your fleet operates and meets its objectives. Time limitations can tell you whether a specific schedule is even possible before you attempt it. It can also shed light on the resources required to fulfil delivery and pickup obligations. Plus it can help you manage how resources are used - from taking a long time but using less vehicles, to taking less time but utilizing more vehicles.