OPSI Systems Develops Improved Method for National Planning Scenarios
Johannesburg, South Arica, February 22, 2005:
OPSI Systems, in working with new clients in the USA, had the need to develop improved national planning scenarios due to the USA's vast road network.
OPSI systems completed a feasibility study for Atlanta Bread, a US-based bakery with a national delivery scope based in Atlanta, Georgia. The study presented a challenge to the current method of calculating shortest paths in a road network used in South Africa.
The South African road network used by OPSI contains approximately 10 000 nodes and 18 000 edges. It is broken up into 53 “mapsets” each having anywhere from 100 to 800 nodes. FLO users load only the needed mapsets for their deliveries. The current algorithm calculates all possible shortest paths between any two nodes in each mapset (“Floyds algorithm”). FLO users typically wait a minute or so upon opening as this calculation is executed, longer if more mapsets are needed.
The difficulty arises because Floyd's algorithm is cubic in network size. This means that doubling the number of nodes multiplies the calculation time by 2*2*2 = 8. This is fine for a relatively small network such as South Africa, but impossible in the US, where even a single small state could have 50 000 nodes or more if taken down to street level. This would make FLO open 2 500 times slower or more, taking us into months, years, perhaps lifetimes.
The new algorithm used to get around this problem is the “A*” (A Star) search. Its advantage is that it doesn't calculate all possible shortest paths, only those between customers currently in the schedule, instead of between all possible road network points, even those with no customers. On a day with 100 customers, this time savings can be 10 000 times or more depending on the road network size, making A* the clear winner.
A* has the added advantage of eliminating the notion of a mapset. The entire road network is loaded at once. This is a necessity for national planning scenarios.
Below is a new map set of the USA showing southern states around Atlanta, Georgia used for the feasibility study.
Below is illustrated the highway-level road network of Atlanta, Georgia and the surrounding southern states used in the study.
For more information, please contact:
OPSI Systems
David Lubinsky
Tel: +27 11 8807951
Email: david.lubinsky@opsi.co.za
About OPSI Systems
OPSI Systems is a software development and consulting house based in Johannesburg, South Africa. We focus exclusively on tools and services related to the supply chain, with a specific focus on vehicle logistics and demand prediction. We supply off-the-shelf routing and scheduling tools but also welcome work on custom projects for individual clients.
Key customers:
Barloworld Logistics, ABI (Coca Cola), Unitrans, UPS Logistics, Value Logistics, Tibbet and Britten, SAB Miller, and Reckitt Benkeiser.
About FLO™ (Fleet Logistics Optimiser)
The flagship of our product line is FLO (Fleet Logistics Optimizer). FLO is a multi-drop fleet routing and scheduling tool with many unique features. These include the ability to model a rich set of real world constraints including delivery windows, vehicle exclusions, product exclusions, multiple shifts, individual working hours by vehicle, multiple-container vehicles, trailer and associated constraints, as well as many others. FLO also features deep integration with GPS tracking to learns travel and stop times, to give updated ETA’s, and to detect unauthorized stops. On the accounting side, FLO has strong stop cost calculations and a complete delivery de-brief module this means that complete delivery contracts can be run using only FLO to handle all aspects of the planning and execution of the delivery .
OPSI Systems® and FLO ™ are trademarks of OPSI Systems CC. All other trademarks and registered trademarks referenced in this document are the property of their respective owners.
