Article ID: | iaor20032038 |
Country: | United Kingdom |
Volume: | 53 |
Issue: | 10 |
Start Page Number: | 1133 |
End Page Number: | 1141 |
Publication Date: | Oct 2002 |
Journal: | Journal of the Operational Research Society |
Authors: | Wackrill P. |
The out-of-kilter algorithm finds a minimum cost assignment of flows to a network defined in terms of one-way arcs, each with upper and lower bounds on flow, and a cost. It is a mathematical programming algorithm which exploits the network structure of the data. The objective function, being the sum taken over all the arcs of the products, cost × flow, is linear. The algorithm is applied in a new way to minimise a series of linear functions in a heuristic method to reduce the value of a non-convex quadratic function which is a measure of traffic congestion. The coefficients in these linear functions are chosen in a way which avoids one of the pitfalls occurring when Beale's method is applied to such a quadratic function. The method does not guarantee optimality but has produced optimal results with networks small enough for an integer linear programming method to be feasible.