A composite algorithm for a concave-cost network flow problem. (English) Zbl 0673.90034

Balakrishnan, Anantaram; Graves, Stephen C.

Networks 19, No. 2, 175-202 (1989).

Summary: We consider the problem of routing multiple commodities between various origin-destination pairs in a network, at minimum total cost. Economies of scale in arc flow costs are modeled using piecewise linear, concave total-cost functions for each arc. This model applies to a variety of medium- and long-term planning contexts including transportation planning, design of communication networks, plant location and capacity expansion planning, production planning, and water resource management. We formulate the general problem as a mixed-integer program and develop a composite algorithm to generate both good lower bounds and heuristic solutions. We also report on computational results for several randomly generated general networks (with up to 40 nodes, 359 arcs, and 60 commodities) and layered networks (with up to 60 nodes, 372 arcs, and 60 commodities). These tests demonstrate that even for relatively large problems, the composite algorithm is very effective in generating solutions with small gaps between the upper and lower bounds (1.7% on average for general networks, and 0.4% on average for layered networks); for 19 out of the 25 layered network problems, the method generated and verified the optimal solution.

MSC:

90B10	Deterministic network models in operations research
90C11	Mixed integer programming
65K05	Numerical mathematical programming methods
90B05	Inventory, storage, reservoirs
90C90	Applications of mathematical programming
90B30	Production models
90C35	Programming involving graphs or networks

Keywords:

routing multiple commodities; origin-destination pairs; minimum total cost; Economies of scale in arc flow costs; transportation planning; design of communication networks; plant location; capacity expansion; lower bounds; heuristic; computational results

References:

[1]	Valid Inequalities and Algorithms for the Network Design Problem with an Application to LTL Consolidation. Doctoral dissertation, Sloan School Management, Massachusetts Institute of Technology, Cambridge, MA (1984).
[2]	Crowder, Symp. Math. 19 pp 357– (1976)
[3]	Dijkstra, Numerische Math. 1 pp 269– (1959)
[4]	Erickson, Math. Oper. Res. 12 pp 634– (1987)
[5]	Fisher, Management Sci. 27 pp 1– (1981)
[6]	Gallo, Eur. J. Oper. Res. 3 pp 239– (1979)
[7]	Geofffion, Math. Programming Study 2 pp 82– (1974)
[8]	Johnson, Netwoprks 8 pp 279– (1978)
[9]	Less-Than-Truckload freight consolidation and routing strategies: A mathematical programming procedure. Project report no. CTS/IU-83.2, Center for Transportation Studies, Massachusetts Institute of Technology, Cambridge, MA (1983).
[10]	, and , Bounding procedures for fixed charge, multicommodity network design problems. Working paper, Department of Civil Engineering, Massachusetts Institute of Technology, Cambridge, MA (1984).
[11]	Magnanti, Trans. Sci. 18 pp 1– (1984)
[12]	A local improvement heuristic for the design of less-than-truckload motor carrier networks. Working paper EES-85-3, Princeton University, Princeton, NJ (1985).
[13]	Powell, Trans. Res. 17A pp 471– (1983)
[14]	Soland, Oper. Res. 22 pp 373– (1974)
[15]	Zangwill, Management Sci. 14 pp 429– (1968)