Simple Vehicle Routings Simulator

Saving heuristic method is proposed by Clarks and Wright (1963) to solve vehicle routing problems. Most of the time this method helps to find the optimal route for the vehicle with given payload.

To understand the saving heuristic method first takes the following scenario,

Headquarters and customer setup

Headquarters and customer setup

The above figure represents the headquarters of the company (Hq) and it’s 2 customers A and B. When consider the distances Hq to A had 10km and Hq to B had 12 km. Both A and B located with 8km of distance. When Hq release some new stock delivery vehicle of Hq moves as follows,

Standard delivery vehicle's route

Standard delivery vehicle's route

When consider the above tour, total distance traveled by the delivery vehicle is,

Total distance travelled between Hq and A = 2 x 10 km = 20 km
Total distance travelled between Hq and B = 2 x 12 km = 24 km
Total distance travelled by the delivery vehicle (dt1) = 44 km

Saving heuristic model eliminate some of these unwanted distances as illustrated in following figure.

Saving heuristic model for delivery route

Saving heuristic model for delivery route

If delivery vehicle has enough capacity this tour plan had total distance as follows,

Distance travelled between Hq and A = 10 km
Distance travelled between A and B = 8 km
Distance travelled between B and Hq = 12 km
Total distance travelled by the delivery vehicle (dt2) = 30 km

So difference between total distances is Δ(dt1 – dt2) = 14 km.

Formulate total distance

Formulate total distance

So general formulation to get the distance difference is,

Total distance when using the standard tour = 2DA + 2DB
Total distance when using the saving heuristic = DA + DB + DAB
Distance difference = ( 2DA + 2DB ) – ( DA + DB + DAB ) = DA + DB – DAB

Simple Vehicle routings simulator is completely based on above described technique to seek the optimal delivery route. This sample application is developed using Borland Delphi 7 and JEDI JCL libraries. To download the simulator with the complete source code and sample data please visit the download section of elect.wikispaces.com.

%d bloggers like this: