Journal of Applied Mathematics and Decision Sciences
Volume 7 (2003), Issue 4, Pages 207-228
doi:10.1155/S117391260300018X
Genetic algorithm for network cost minimization using threshold based discounting
1Computer Science Department, Southern Connecticut State University, New Haven 06515, CT, USA
2W.A. Harriman School for Management and Policy, State University of New York at Stony Brook, Stony Brook 11794-3775, NY , USA
Copyright © 2003 Hrvoje Podnar and Jadranka Skorin-Kapov. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
Abstract
We present a genetic algorithm for heuristically solving a cost minimization problem applied to communication networks with threshold based discounting. The network model assumes that every two nodes can communicate and offers incentives to combine flow from different sources. Namely, there is a prescribed threshold on every link, and if the total flow on a link is greater than the threshold, the cost of this flow is discounted by a factor α. A heuristic algorithm based on genetic strategy is developed and applied to a benchmark set of problems. The results are compared with former branch and bound results using the CPLEX® solver. For larger data instances we were able to obtain improved solutions using less CPU time, confirming the effectiveness of our heuristic approach.