Overview
The aim of an effective vehicle routing system is relatively simple; deliver as many parcels as possible with minimal cost. Achieving this goal, however, is an extremely complex mathematical problem (see
Combinatorial Optimization
). For any problem encountered in the real world, it is impossible to find the absolute best solution in reasonable time but we can use heuristic approaches to find near-optimal solutions. That's what
is demonstrated on this page.
The top priority for this particular heuristic is to ensure the delivery of all parcels, above all financial costs. This means that it will use as many vehicles from the available fleet as is necessary, even when this may result in one delivery van carrying
only a single item. Items must be delivered within their selected time slot. Once all parcels are delivered, the following costs are minimised:
- Fixed costs. Every vehicle deployed in the solution will add a fixed cost of £100. This is to try minimise the number of vehicles used.
- Cost per km. The algorithm considers a flat cost of £0.12/km (based on 30 miles/gallon and £1.25/litre of petrol).
- Cost per driving time. The algorithm considers a flat driver wage cost of £0.17/min (based on £10/hr).
- Cost per waiting time. Recall that all deliveries must be delivered in their alloted time window. This could mean that drivers are forced into situations where they have to wait for a time slot to open to continue
deliveries - but they're still being paid!
Testing it Out
Clicking on the "Create Routing Problem" will generate a random problem based on your specified criteria. Whilst you may see repeated customer names (I just use a pool of 200 names), all of the latitude/longitude pairs are random in the Greater Manchester
area - no two problems should be the same and no problems are pre-solved. This means it's impossible to know what a solution will look like a priori and some may end up looking very unusual.
However, the biggest impact you should see is in the effect of the delivery time window. Customers are demanding ever-smaller time slots for delivery (nobody likes waiting in all day for something to arrive), which is at odds with operational efficiency.
Narrowing the time slots tends to:
- cause drivers to have to criss-cross the city more often, increasing the overall mileage
- increase the likelihood of having to deploy more vehicles
- increase waiting time across all vehicles in the fleet
- decrease vehicle utilisation. Vehicles will be more likely to be deployed carrying fewer items, meaning that they may return to the depot even before they get to lunch time
Why is Lunch Optional?
This is a bit tongue-in-cheek. When I first started using this algorithm, there was no way to factor in lunch breaks in routes. I worked with the library owner to make this a feature, for which I was
listed as a contributor
. Hopefully that made things a little easier on the drivers!
What else can it do?
This is just a demo, which only covers a small portion of what a full vehicle routing system needs to do. The full-blown version handles:
- pickups from customers; sometimes things need to be returned
- 1-1 transfers. Items can be picked up somewhere in a route and delivered elsewhere later on
- different vehicle capacities and running costs. Fleets might have vans and trucks that carry different things and cost different amounts to run
- vehicle requirements. For example, some items may need to be carried in refrigerated vehicles
- soft time windows. Maybe it's better to be late if there's no other way to cope, rather than just fail to make 100% of deliveries
- dynamic issues, such as orders being placed after the vehicle fleet is dispatched, or customers rescheduling on the same date
It's a huge undertaking to implement vehicle routing systems and beyond the scope of this demo.