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.  Zbl1051.90019
  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.  Zbl0833.90116
  3. R.V. Ahuja, T.L. Magnanti and J.B. Orlin, Network Flows: Theory, Algorithms and Applications. Prentice hall, Englewood Cliffs, N.J. (1993).  Zbl1201.90001
  4. J.E. Aronson, A survey on dynamic network flows. Ann. Oper. Res.20 (1989) 1–66.  Zbl0704.90028
  5. A. Assad, Multicommodity networks flows: a survey. Networks8 (1978) 37–91.  Zbl0381.90040
  6. A. Balakrishnan, T. Magnanti and P. Mirchandani, Designing hierarchical survivable networks. Oper. Res.46 (1998) 116–130.  Zbl0987.90517
  7. A. Balakrishnan, T. Magnanti and P. Mirchandani, A dual based algorithm for multi level network design. Manage. Sci.40 (1994) 567–580.  Zbl0826.90117
  8. M. Balinski, Fixed cost transportation problems. Nov. Res. Log. Quart8 (1961) 41–54.  Zbl0106.34801
  9. F. Barahona, Network design using cut inequalities. SIAM J. Optim.6 (1995) 822–837.  Zbl0856.90112
  10. W. Ben Ameur, Constrained length connectivity and survivable networks. Networks36 (2000) 1.  Zbl0971.90010
  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.  Zbl0109.38302
  13. D. Bertsimas and S. Stock Patterson, The air traffic flow problem with en route capacities. Oper. Res.46-3 (1998) 406–422.  Zbl0996.90010
  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.  Zbl0424.90074
  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.  Zbl0864.90073
  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.  Zbl0821.90124
  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.  Zbl0987.90507
  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.  Zbl1040.90506
  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.  Zbl1026.90010
  26. G. Dahl and M. Stoer, A polyedral approach to multicommodity survivable network design. Numer. Math.68 (1994) 149–167.  Zbl0809.65068
  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.  Zbl0397.94024
  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.  Zbl0767.90006
  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.  Zbl0591.90092
  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.  Zbl0523.90087
  36. B. Gavish, Topological design of telecommunication networks: local access design methods. Ann. Oper. Res.33 (1991) 17–71.  Zbl0736.90030
  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.  Zbl0229.90024
  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.  Zbl0697.68063
  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.  Zbl0472.90068
  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.  Zbl0641.90036
  43. F.K. Hwang, D.S. Richards and P. Winter, The Steiner Tree Problem. North Holland (1992).  Zbl0774.05001
  44. P. Jaillet, G. Song and G. Yu, Airline network design and hub location problems. Location Science4 (1997) 195–212.  Zbl0929.90048
  45. D. Johnson, J. Lenstra, A. RInnoy-Khan, The complexity of the Network Design Problem. Networks8 (1978) 279–285.  Zbl0395.94048
  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.  Zbl0802.90039
  47. J.L. Kennington and R.V. Helgason, Algorithms for network programming. Wiley N.Y. (1980).  Zbl0502.90056
  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.  Zbl0890.90058
  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.  Zbl0987.90509
  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.  Zbl1002.90082
  56. A. Marin and J. Salmeron, Tactical design of rail freight networks: part 1- exact and heuristic methods. EJOR90 (1996) 26–44.  Zbl0916.90096
  57. M. Minoux, Network synthesis and optimum network design problems: models, solution methods and application. Networks19 (1989) 313–360.  Zbl0666.90032
  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.  Zbl0469.90080
  59. P.B. Mirchandani and L.R. Francis, Discrete Location Theory. John Wiley Eds, N.Y. (1990).  Zbl0718.00021
  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.  Zbl1231.90110
  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.  Zbl0874.90122
  65. P.A. Steenbrink, Optimization of transport networks. Wiley, N.Y. (1974).  Zbl0329.14007
  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.  Zbl0692.49025
  67. R. Vijay, A. Kanda and P. Vrat, Multiperiod capacity expansion of road networks: formulation and algorithms. Oper. Res.30 (1993) 117–140.  Zbl0795.90020
  68. R.T. Wong, Worst case analysis of network design problem heuristics. SIAM J. Alg. Disc.Meth.1 (1980) 51–63.  Zbl0498.90032

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.