Solving transportation problems with nonlinear side constraints with tabu search

An algorithm based on tabu search ideas is developed to solve transportation problems with nonlinear side constraints. The authors show how to superimpose the tabu search (TS) framework conveniently on basis exchange (or ‘pivoting’) operations specialized to the transportation network context, and thereby to guide these operations to overcome the limitations of local optimality. Using an exact algorithm as a benchmark, the present computational study demonstrates the effectiveness of the procedure, and suggests the relevance of similar TS applications for solving other optimization problems that can be formulated as network problems with complicated nonlinear side constraints.