Integral Flows and Aggregated Multicommodity Flows

Alain Quilliot; Fatiha Bendali; Jean Mailfert

RAIRO - Operations Research (2006)

  • Volume: 39, Issue: 3, page 185-224
  • ISSN: 0399-0559

Abstract

top
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.

How to cite

top

Quilliot, Alain, Bendali, Fatiha, and Mailfert, Jean. "Flots entiers et multiflots fractionnaires couplés par une contrainte de capacité." RAIRO - Operations Research 39.3 (2006): 185-224. <http://eudml.org/doc/105330>.

@article{Quilliot2006,
abstract = { 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. },
author = {Quilliot, Alain, Bendali, Fatiha, Mailfert, Jean},
journal = {RAIRO - Operations Research},
keywords = {Flots; Multiflots; Circuits Négatifs; Routage; Transport.; transportation and production planning problems; heuristic},
language = {fre},
month = {1},
number = {3},
pages = {185-224},
publisher = {EDP Sciences},
title = {Flots entiers et multiflots fractionnaires couplés par une contrainte de capacité},
url = {http://eudml.org/doc/105330},
volume = {39},
year = {2006},
}

TY - JOUR
AU - Quilliot, Alain
AU - Bendali, Fatiha
AU - Mailfert, Jean
TI - Flots entiers et multiflots fractionnaires couplés par une contrainte de capacité
JO - RAIRO - Operations Research
DA - 2006/1//
PB - EDP Sciences
VL - 39
IS - 3
SP - 185
EP - 224
AB - 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.
LA - fre
KW - Flots; Multiflots; Circuits Négatifs; Routage; Transport.; transportation and production planning problems; heuristic
UR - http://eudml.org/doc/105330
ER -

References

top
  1. R.K. Ahuja, J.B. Orlin and D. Sharma, Multiexchance neighbourhood structures for the capacitated minimum spanning tree problem. Math Programming91 (2001) 71–97.  
  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 Science7 (1995)1–83.  
  3. R.V. Ahuja, T.L. Magnanti and J.B. Orlin, Network Flows: Theory, Algorithms and Applications. Prentice hall, Englewood Cliffs, N.J. (1993).  
  4. J.E. Aronson, A survey on dynamic network flows. Ann. Oper. Res.20 (1989) 1–66.  
  5. A. Assad, Multicommodity networks flows: a survey. Networks8 (1978) 37–91.  
  6. A. Balakrishnan, T. Magnanti and P. Mirchandani, Designing hierarchical survivable networks. Oper. Res.46 (1998) 116–130.  
  7. A. Balakrishnan, T. Magnanti and P. Mirchandani, A dual based algorithm for multi level network design. Manage. Sci.40 (1994) 567–580.  
  8. M. Balinski, Fixed cost transportation problems. Nov. Res. Log. Quart8 (1961) 41–54.  
  9. F. Barahona, Network design using cut inequalities. SIAM J. Optim.6 (1995) 822–837.  
  10. W. Ben Ameur, Constrained length connectivity and survivable networks. Networks36 (2000) 1.  
  11. A. Benchakroun, J. Ferland and V. Gascon, Benders decomposition for network design problems with underlying tree structure. Investigacion operativa6 (1997) 165–180.  
  12. J.F. Benders, Partitionning procedures for solving mixed variable programming problems. Num. Math. 4 (1962) 238–252.  
  13. D. Bertsimas and S. Stock Patterson, The air traffic flow problem with en route capacities. Oper. Res.46-3 (1998) 406–422.  
  14. D. Bienstock and O. Unluk, Capacited network design: polyedral structure and computation. Inform. J. Comput.8 (1996) 243–259.  
  15. T. Boffey and A. Hinxman, Solving for optimal network problem. EJOR3 (1979) 386–393.  
  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. Networks28 (1996) 117–124.  
  19. J. Chifflet, A. Lisser and P. Tolla, Interior point methods for multicommodity netflow problems. Perquisa Operacional15 (1994) 1.  
  20. S. Chopra and M. Rao, The Steiner tree problem I: formulations, composition and extension of facets. Math Programming64 (1994) 209–229.  
  21. N. Christophides, C.A. Whitlock, Network synthesis with connectivity constraint: a survey. Oper. Res. (1981) 705–723.  
  22. J.P. Cordeau, P. Toth and D. Vigo, A survey of optimization models for train routing and scheduling. Transportation Science32 (1998) 380–404.  
  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.  
  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 B20 (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.  
  26. G. Dahl and M. Stoer, A polyedral approach to multicommodity survivable network design. Numer. Math.68 (1994) 149–167.  
  27. P. Dejax and T. Crainic, A review of empty flow and fleet management models in freight transportation. Transportation Science21 (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.  
  29. A. Dionne and M. Florian, Exact and approximate algorithms for optimal network design. Networks9 (1979) 37–59.  
  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 Sciences27 (1993) 44–54.  
  32. V. Ferreira Filho and J. Galvao, A survey of computer network design problems. Investigacion Operativa4 (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.  
  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.  
  35. G. Gallo, Lower planes for the network design problem. Networks13 (1983) 411–426.  
  36. B. Gavish, Topological design of telecommunication networks: local access design methods. Ann. Oper. Res.33 (1991) 17–71.  
  37. A. Geoffrion, Lagrangean relaxation and its uses in integer programming. Math. Prog. Study2 (1974) 82–114.  
  38. A. Geoffrion, Generalized Benders decomposition. J. Optim. Theory Appl.10 (1972) 237–260.  
  39. A. Girard and B. Liau, Dimensioning of adaptatively routed networks. IEE/ACM Trans. Networking1-4 (1993) 460–468.  
  40. A. Golberg and R. Tarjan, Finding minimum cost circulation by cancelling negative cycles, JACM36 (1989) 873–886.  
  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.  
  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.  
  43. F.K. Hwang, D.S. Richards and P. Winter, The Steiner Tree Problem. North Holland (1992).  
  44. P. Jaillet, G. Song and G. Yu, Airline network design and hub location problems. Location Science4 (1997) 195–212.  
  45. D. Johnson, J. Lenstra, A. RInnoy-Khan, The complexity of the Network Design Problem. Networks8 (1978) 279–285.  
  46. K.L. Jones, I.J. Lustig, J.M. Farvolden and W.B. Powel, Multicommodity network flows: the impact of formulation on decomposition. Math. Programming62 (1993) 95–117.  
  47. J.L. Kennington and R.V. Helgason, Algorithms for network programming. Wiley N.Y. (1980).  
  48. B.M. Khumalala, Warehouse location problem efficient branch and bound algorithm. Manage. Sciences B18 (1972) 718–731.  
  49. J.G. Klincewicz and M.B. Rosenwein, Planning and consolidating shipments from a warehouse. J. Operat. Res. Soc. 48 (1997) 241–246.  
  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.  
  52. J. Mac Gregor Smith and P. Winter, Topological Network Design. Ann. Oper. Res.33 (1991).  
  53. T. Magnanti, Combinatorial optimization and vehicle fleet planning: perspectives and prospects. Networks11 (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.  
  56. A. Marin and J. Salmeron, Tactical design of rail freight networks: part 1- exact and heuristic methods. EJOR90 (1996) 26–44.  
  57. M. Minoux, Network synthesis and optimum network design problems: models, solution methods and application. Networks19 (1989) 313–360.  
  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.  
  59. P.B. Mirchandani and L.R. Francis, Discrete Location Theory. John Wiley Eds, N.Y. (1990).  
  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. Science46 (2000) 126–147.  
  62. P.M. Pardalos and D.Z. Du, Network design: connectivity and facility location. DIMACS Series40, N.Y., American Math Society (1998).  
  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. ITOR3 (1996) 243–253.  
  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.  
  67. R. Vijay, A. Kanda and P. Vrat, Multiperiod capacity expansion of road networks: formulation and algorithms. Oper. Res.30 (1993) 117–140.  
  68. R.T. Wong, Worst case analysis of network design problem heuristics. SIAM J. Alg. Disc.Meth.1 (1980) 51–63.  

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.