Heuristic Method for Costs Minimization

The above figure shows a problem of assigning 35 units between nodes a and f at minimum cost.

• Identify all possible paths between nodes having a transport demand (all paths between a and f). Order these paths by their cost, from the least to the most expensive (1).
• Take the least expensive path and assign all the traffic that the link having the weakest capacity can support (2).  Subtract this number to the capacity of every link of the path. This subtraction cannot be lower than 0. The result of this subtraction is the remaining capacity of each link of the path (2).
• Repeat by increasing order of path cost until all the demand is assigned (3 and 4). If all the demand can not be assigned, the problem cannot be solved.

Home | Contents | Media | Glossary | Links | About | Contact | Purchase

Copyright © 1998-2012, Dr. Jean-Paul Rodrigue, Dept. of Global Studies & Geography, Hofstra University, New York, USA.
This material (including graphics) cannot be copied or redistributed, in whole or in part, in ANY FORM (printed or electronic) and on ANY MEDIA. For specific uses permission MUST be requested and the material must be cited.