Probabilistic local search algorithms for concave cost transportation network problems

In practice concave cost transportation problems are characterized as NP-hard, therefore cost functions are usually simplified as linear in order to facilitate problem solving. However, linear cost functions may not reflect actual operations, which generally results in decreased operational performance. This research employs the techniques of simulated annealing and threshold accepting to develop several heuristics that would efficiently solve these concave cost transportation network problems. A network generator has also been designed to generate many instances on an HP workstation to test the heuristics. The preliminary results show that these heuristics are potentially useful.