×

A capacity scaling heuristic for the multicommodity capacitated network design problem. (English) Zbl 1178.90057

A capacity scaling heuristic using a column generation and row generation technique to address the multi-commodity capacitated network design problem is proposed. The capacity scaling heuristic is an approximate iterative solution method for capacitated network problems based on changing arc capacities, which depend on flow volumes on the arcs.

MSC:

90B10 Deterministic network models in operations research
90C35 Programming involving graphs or networks
94C30 Applications of design theory to circuits and networks
90C59 Approximation methods and heuristics in mathematical programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Magnanti, T. L.; Mireault, P.; Wong, R. T., Tailoring benders decomposition for uncapacitated network design, Mathematical Programming Study, 26, 112-155 (1986) · Zbl 0596.90098
[2] Magnanti, T. L.; Mirchandani, P.; Vachani, R., The convex hull of two core capacitated network design problems, Mathematical Programming, 60, 233-250 (1993) · Zbl 0788.90071
[3] Barahona, F., Network design using cut inequalities, SIAM Journal on Computing, 6, 823-837 (1996) · Zbl 0856.90112
[4] M. Chouman, T.G. Crainic, B. Gendron, A cutting-plane algorithm based on cutset inequalities for multicommodity capacitated fixed charge network design, Tech. Rep. CRT-2003-16, Centre de recherche sur les transports, Universite de Montreal, 2003; M. Chouman, T.G. Crainic, B. Gendron, A cutting-plane algorithm based on cutset inequalities for multicommodity capacitated fixed charge network design, Tech. Rep. CRT-2003-16, Centre de recherche sur les transports, Universite de Montreal, 2003
[5] Katayama, N.; Kasugai, H., A capacitated multi-commodity network design problem—a solution method for finding a lower bound using valid inequalities, Journal of Japan Industrial Management Association, 44, 164-175 (1993), (in Japanese)
[6] B. Gendron, T. Crainic, Relaxations for multicommodity capacitated network design problems, Tech. Rep. CRT-965, Centre de recherche sur les transports, Universite de Montreal, 1994; B. Gendron, T. Crainic, Relaxations for multicommodity capacitated network design problems, Tech. Rep. CRT-965, Centre de recherche sur les transports, Universite de Montreal, 1994
[7] B. Gendron, T. Crainic, Bounding procedures for multicommodity capacitated fixed charge network design problems, Tech. Rep. CRT-96-06, Centre de recherche sur les transports,Universite de Montreal, 1996; B. Gendron, T. Crainic, Bounding procedures for multicommodity capacitated fixed charge network design problems, Tech. Rep. CRT-96-06, Centre de recherche sur les transports,Universite de Montreal, 1996
[8] Crainic, T.; Frangioni, A.; Gendron, B., Bundle-based relaxation methods for multicommodity capacitated fixed charge network design, Discrete Applied Mathematics, 112, 73-99 (2001) · Zbl 1026.90010
[9] Holmberg, K.; Yuan, D., A lagrangian heuristic based branch-and-bound approach for the capacitated network design problem, Operations Research, 48, 461-481 (2000) · Zbl 1106.90381
[10] Herrmann, J.; Ioannou, G.; Minis, I.; Proth, J. M., A dual ascent approach to the fixed-charge capacitated network design problem, European Journal of Operational Research, 95, 476-490 (1996) · Zbl 0943.90501
[11] Crainic, T.; Gendreau, M.; Farvolden, J., A simplex-based tabu search for capacitated network design, INFORMS Journal on Computing, 12, 223-236 (2000) · Zbl 1040.90506
[12] N. Zaleta, A.M.A. Socarrás, Tabu search-based algorithm for capacitated multicommodity network design problems, 14th Int. Conference on Electronics, Communications and Computers, 2004, pp. 144-148; N. Zaleta, A.M.A. Socarrás, Tabu search-based algorithm for capacitated multicommodity network design problems, 14th Int. Conference on Electronics, Communications and Computers, 2004, pp. 144-148
[13] Ghamlouche, I.; Crainic, T.; Gendreau, M., Cycle-based neighbourhoods for fixed-charge capacitated multicommodity network design, Operations Research, 51, 655-667 (2003) · Zbl 1165.90360
[14] Ghamlouche, I.; Crainic, T. G.; Gendreau, M., Path relinking, cycle-based neighborhoods and capacitated multicommodity network design, Annals of Operations Research, 131, 109-134 (2004) · Zbl 1067.90014
[15] Alvarez, A. M.; González-Velarde, J. L.; De-Alba, K., Scatter search for network design problem, Annals of Operations Research, 138, 1, 159-178 (2005) · Zbl 1091.90006
[16] Crainic, T. G.; Gendron, B., Cooperative parallel tabu search for capacitated network design, Journal of Heuristics, 8, 601-627 (2002)
[17] Crainic, T. G.; Li, Y.; Toulouse, M., A first multilevel cooperative algorithm for capacitated multicommodity network design, Computers & Operations Research, 33, 2602-2622 (2006) · Zbl 1086.90009
[18] Crainic, T.; Gendron, B.; Hernu, G., A slope scaling/Lagrangean perturbation heuristic with long-term memory for multicommodity capacitated fixed-charge network design, Journal of Heuristics, 10, 525-545 (2004) · Zbl 1062.90009
[19] Pochet, Y.; Vyve, M., A general heuristic for production planning problems, Journal on Computing, 16, 316-327 (2004) · Zbl 1239.90043
[20] Farvolden, J.; Powell, W., A primal partitioning solution for the arc-chain formulation of a multicommodity network flow problem, Operations Research, 41, 669-693 (1993) · Zbl 0782.90032
[21] I. Ghamlouche, T. Crainic, M. Gendreau, Cycle-based neighbourhoods for fixed-charge capacitated multicommodity network design, Tech. Rep. CRT-2001-01, Centre de recherche sur les transports, Universite de Montreal, 2001; I. Ghamlouche, T. Crainic, M. Gendreau, Cycle-based neighbourhoods for fixed-charge capacitated multicommodity network design, Tech. Rep. CRT-2001-01, Centre de recherche sur les transports, Universite de Montreal, 2001 · Zbl 1165.90360
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.