Flots entiers et multiflots fractionnaires couplés par une contrainte de capacité

Quilliot, Alain; Bendali, Fatiha; Mailfert, Jean

RAIRO - Operations Research - Recherche Opérationnelle, Tome 39 (2005) no. 3, pp. 185-224.

Nous modélisons ici plusieurs problèmes de Transport et de Gestion de Flux à l'aide d'un flot entier et d'un multiflot fractionnaire couplés par une contrainte de capacité. Pour le problème ainsi obtenu, nous proposons différents schémas de résolution par relaxation et décomposition, qui induisent la recherche d'un flot auxiliaire dont la partie entière supérieure doit minimiser un certain coût, et qui requièrent la mise en œuvre d'un processus d'agrégation. Nous en déduisons diverses heuristiques que nous testons.

We present here a Flow/Multicommodity Flow model for Transportation and Production Planning problems. We deal with this model through Lagrangean Relaxation and Hierarchical Decomposition techniques, which involve the resolution of a specific flow with least integral cost sub-problem, and which require the design of some agregation process. We deduce from this analysis several heuristic schemes, and we conclude by discussing numerical experiments.

Classification : 90C25
Mots clés : flots, multiflots, circuits négatifs, routage, transport

[1] R.K. Ahuja, J.B. Orlin and D. Sharma, Multiexchance neighbourhood structures for the capacitated minimum spanning tree problem. Math Programming 91 (2001) 71-97. | Zbl

[2] R.K. Ahuja, T.L. Magnanti, J.B. Orlin and M.R. Reddy, Applications of network optimization. Chapter 1 of Network Models, Handbook of Operation Research and Management Science 7 (1995)1-83. | Zbl

[3] R.V. Ahuja, T.L. Magnanti and J.B. Orlin, Network Flows$:$ Theory, Algorithms and Applications. Prentice hall, Englewood Cliffs, N.J. (1993). | MR

[4] J.E. Aronson, A survey on dynamic network flows. Ann. Oper. Res. 20 (1989) 1-66. | Zbl

[5] A. Assad, Multicommodity networks flows$:$ a survey. Networks 8 (1978) 37-91. | Zbl

[6] A. Balakrishnan, T. Magnanti and P. Mirchandani, Designing hierarchical survivable networks. Oper. Res. 46 (1998) 116-130. | Zbl

[7] A. Balakrishnan, T. Magnanti and P. Mirchandani, A dual based algorithm for multi level network design. Manage. Sci. 40 (1994) 567-580. | Zbl

[8] M. Balinski, Fixed cost transportation problems. Nov. Res. Log. Quart 8 (1961) 41-54. | Zbl

[9] F. Barahona, Network design using cut inequalities. SIAM J. Optim. 6 (1995) 822-837. | Zbl

[10] W. Ben Ameur, Constrained length connectivity and survivable networks. Networks 36 (2000) 1. | MR | Zbl

[11] A. Benchakroun, J. Ferland and V. Gascon, Benders decomposition for network design problems with underlying tree structure. Investigacion operativa 6 (1997) 165-180.

[12] J.F. Benders, Partitionning procedures for solving mixed variable programming problems. Num. Math. 4 (1962) 238-252. | EuDML | MR | Zbl

[13] D. Bertsimas and S. Stock Patterson, The air traffic flow problem with en route capacities. Oper. Res. 46-3 (1998) 406-422. | Zbl

[14] D. Bienstock and O. Unluk, Capacited network design$:$ polyedral structure and computation. Inform. J. Comput. 8 (1996) 243-259. | Zbl

[15] T. Boffey and A. Hinxman, Solving for optimal network problem. EJOR 3 (1979) 386-393. | MR | Zbl

[16] A. Caminada, J.K. Hao, J.L. Lutton and V. Martin, L'optimisation des réseaux de télécommunications. Recherche Opérationnelle et Réseaux : Méthodes d'Analyse Spatiale. Collection IGAT, Hermes, Chap. 7 (2002) 191-236.

[17] S.G. Chang and B. Gavish, Telecommunication network topological design and capacity expansion$:$ formulations and algorithms. Telecom. Syst. 1 (1993) 99-131.

[18] P. Chardaire, M.C. Costa and A. Sutter, Solving the dynamic facility location problem. Networks 28 (1996) 117-124. | MR | Zbl

[19] J. Chifflet, A. Lisser and P. Tolla, Interior point methods for multicommodity netflow problems. Perquisa Operacional 15 (1994) 1.

[20] S. Chopra and M. Rao, The Steiner tree problem I: formulations, composition and extension of facets. Math Programming 64 (1994) 209-229. | MR | Zbl

[21] N. Christophides, C.A. Whitlock, Network synthesis with connectivity constraint$:$ a survey. Oper. Res. (1981) 705-723. | Zbl

[22] J.P. Cordeau, P. Toth and D. Vigo, A survey of optimization models for train routing and scheduling. Transportation Science 32 (1998) 380-404. | Zbl

[23] T. Crainic, M. Gendreau and J.M. Farvolden, A simplex based tabu search method for capacitated network design. Inform. J. Comput. 12 (2000) 223-236. | Zbl

[24] T. Crainic and J.M. Rousseau, Multicommodity, multimode freight transportation$:$ a general modeling and algorithmic framework for the service network design problem. Transport Research B 20 (1988) 290-297.

[25] T. Crainic, A. Frangioni and B. Gendron, Bundle based relaxation methods for multicommodity capacitated fixed charge network design. Discrete Appl. Math. 112 (2001) 73-99. | Zbl

[26] G. Dahl and M. Stoer, A polyedral approach to multicommodity survivable network design. Numer. Math. 68 (1994) 149-167. | Zbl

[27] P. Dejax and T. Crainic, A review of empty flow and fleet management models in freight transportation. Transportation Science 21 (1987) 227-247.

[28] D. De Wolf and Y. Smeers, Optimal dimensionning of pipe networks with application to gas transmission networks. Oper. Res. 44-4 (1996) 596-608. | Zbl

[29] A. Dionne and M. Florian, Exact and approximate algorithms for optimal network design. Networks 9 (1979) 37-59. | Zbl

[30] Z. Drezner and T. Drezner, Applied location theory models, in Modern Methods for Business Research, edited by Lawrence Erlbaum Mahwa, N.J. (1998) 79-120.

[31] H.A. Eiselt, G. Laporte and J.F. Thisse, Competitive location models$:$ a framework and bibliography. Transportation Sciences 27 (1993) 44-54. | Zbl

[32] V. Ferreira Filho and J. Galvao, A survey of computer network design problems. Investigacion Operativa 4 (1994) 183-211.

[33] M. Florian, An introduction to network models used in transportation planning, in Transp. Plann. Models, edited by M. Florian, North Holland, Amsterdam (1984) 137-152. | Zbl

[34] J.M. Forvalden, W.B. Powell and I. Lustig, A primal partitionning solution for the arc chain formulation of a multicommodity network flow problem. Oper. Res. 41 (1993) 669-693. | Zbl

[35] G. Gallo, Lower planes for the network design problem. Networks 13 (1983) 411-426. | Zbl

[36] B. Gavish, Topological design of telecommunication networks$:$ local access design methods. Ann. Oper. Res. 33 (1991) 17-71. | Zbl

[37] A. Geoffrion, Lagrangean relaxation and its uses in integer programming. Math. Prog. Study 2 (1974) 82-114. | Zbl

[38] A. Geoffrion, Generalized Benders decomposition. J. Optim. Theory Appl. 10 (1972) 237-260. | Zbl

[39] A. Girard and B. Liau, Dimensioning of adaptatively routed networks. IEE/ACM Trans. Networking 1-4 (1993) 460-468.

[40] A. Golberg and R. Tarjan, Finding minimum cost circulation by cancelling negative cycles, JACM 36 (1989) 873-886. | Zbl

[41] H. Hoang, Topological optimization of networks$:$ a non linear mixed model employing generalized Benders decomposition. IEEE Trans. Automat. Control. AC-27 (1982) 164-169. | Zbl

[42] P.A. Hossein, D.P. Bertsekas and P. Tseng, Relaxation methods for network problems with convex arc costs. SIAM J. Control Optim. 5 (1987) 1219-1243. | Zbl

[43] F.K. Hwang, D.S. Richards and P. Winter, The Steiner Tree Problem. North Holland (1992). | MR | Zbl

[44] P. Jaillet, G. Song and G. Yu, Airline network design and hub location problems. Location Science 4 (1997) 195-212. | Zbl

[45] D. Johnson, J. Lenstra, A. RInnoy-Khan, The complexity of the Network Design Problem. Networks 8 (1978) 279-285. | Zbl

[46] K.L. Jones, I.J. Lustig, J.M. Farvolden and W.B. Powel, Multicommodity network flows$:$ the impact of formulation on decomposition. Math. Programming 62 (1993) 95-117. | Zbl

[47] J.L. Kennington and R.V. Helgason, Algorithms for network programming. Wiley N.Y. (1980). | MR | Zbl

[48] B.M. Khumalala, Warehouse location problem efficient branch and bound algorithm. Manage. Sciences B 18 (1972) 718-731. | Zbl

[49] J.G. Klincewicz and M.B. Rosenwein, Planning and consolidating shipments from a warehouse. J. Operat. Res. Soc. 48 (1997) 241-246. | Zbl

[50] L.J. Leblanc, An algorithm for discrete network design. Trans. Sci. 9 (1975) 283-287.

[51] P.J. Lederer and R.S. Nambimadom, Airline network design. Oper. Res. 46-6 (1998) 785-804. | Zbl

[52] J. Mac Gregor Smith and P. Winter, Topological Network Design. Ann. Oper. Res. 33 (1991). | MR

[53] T. Magnanti, Combinatorial optimization and vehicle fleet planning$:$ perspectives and prospects. Networks 11 (1981) 179-214.

[54] T. Magnanti and R.T. Wong, Network design and transportation planning models and algorithms. Trans. Sci. 18 (1984) 1-5.

[55] P. Mahey, A. Benchakroun and F. Boyer, Capacity and flow assignment of data networks by generalized Benders decomposition. J. Global Optim. 20 (2001) 173-193. | Zbl

[56] A. Marin and J. Salmeron, Tactical design of rail freight networks$:$ part 1- exact and heuristic methods. EJOR 90 (1996) 26-44. | Zbl

[57] M. Minoux, Network synthesis and optimum network design problems$:$ models, solution methods and application. Networks 19 (1989) 313-360. | Zbl

[58] M. Minoux, Optimum synthesis of a network with non simultaneous multicommodity flow requirements, Studies on graphs and Discrete Programming, Annals of Disc. Math., edited by P. Hansen, North Holland 11 (1981) 269-277. | Zbl

[59] P.B. Mirchandani and L.R. Francis, Discrete Location Theory. John Wiley Eds, N.Y. (1990). | MR | Zbl

[60] I. Norenkov, Y. Yevstifeyev and V. Manichev, A method for an accelerated analysis of multiperiod electronic circuits. Telecom Radio Engin. 42 (1987) 123-126.

[61] A. Ouorou, P. Mahey and J.P. Vial, A survey of algorithms for convex multicommodity flow problems. Manage. Science 46 (2000) 126-147.

[62] P.M. Pardalos and D.Z. Du, Network design$:$ connectivity and facility location. DIMACS Series 40, N.Y., American Math Society (1998). | MR

[63] R. Rebai, Optimisation de réseaux de télécommunications avec sécurisation. Thèse Paris-Dauphine (2000).

[64] T. Scott and E. Read, Modelling hydroreservoir operation in a deregulated electricity market. ITOR 3 (1996) 243-253. | Zbl

[65] P.A. Steenbrink, Optimization of transport networks. Wiley, N.Y. (1974).

[66] P. Tseng, Dual Ascent methods for problems with strictly convex costs and linear constraints$:$ a unified approach. SIAM J. Control Optim. 28 (1990) 214-242. | Zbl

[67] R. Vijay, A. Kanda and P. Vrat, Multiperiod capacity expansion of road networks$:$ formulation and algorithms. Oper. Res. 30 (1993) 117-140. | Zbl

[68] R.T. Wong, Worst case analysis of network design problem heuristics. SIAM J. Alg. Disc. Meth. 1 (1980) 51-63. | MR | Zbl