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,
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,
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.
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.
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.