Multiple routing strategies in a labelled network

J. Maublanc; D. Peyrton; A. Quilliot

RAIRO - Operations Research - Recherche Opérationnelle (2001)

  • Volume: 35, Issue: 1, page 85-106
  • ISSN: 0399-0559

Abstract

top
We present here models and algorithms for the construction of efficient path systems, robust to possible variations of the characteristics of the network. We propose some interpretations of these models and proceed to numerical experimentations of the related algorithms. We conclude with a discussion of the way those concepts may be applied to the design of a Public Transportation System.

How to cite

top

Maublanc, J., Peyrton, D., and Quilliot, A.. "Multiple routing strategies in a labelled network." RAIRO - Operations Research - Recherche Opérationnelle 35.1 (2001): 85-106. <http://eudml.org/doc/105239>.

@article{Maublanc2001,
abstract = {We present here models and algorithms for the construction of efficient path systems, robust to possible variations of the characteristics of the network. We propose some interpretations of these models and proceed to numerical experimentations of the related algorithms. We conclude with a discussion of the way those concepts may be applied to the design of a Public Transportation System.},
author = {Maublanc, J., Peyrton, D., Quilliot, A.},
journal = {RAIRO - Operations Research - Recherche Opérationnelle},
keywords = {shortest paths; network design; routing},
language = {eng},
number = {1},
pages = {85-106},
publisher = {EDP-Sciences},
title = {Multiple routing strategies in a labelled network},
url = {http://eudml.org/doc/105239},
volume = {35},
year = {2001},
}

TY - JOUR
AU - Maublanc, J.
AU - Peyrton, D.
AU - Quilliot, A.
TI - Multiple routing strategies in a labelled network
JO - RAIRO - Operations Research - Recherche Opérationnelle
PY - 2001
PB - EDP-Sciences
VL - 35
IS - 1
SP - 85
EP - 106
AB - We present here models and algorithms for the construction of efficient path systems, robust to possible variations of the characteristics of the network. We propose some interpretations of these models and proceed to numerical experimentations of the related algorithms. We conclude with a discussion of the way those concepts may be applied to the design of a Public Transportation System.
LA - eng
KW - shortest paths; network design; routing
UR - http://eudml.org/doc/105239
ER -

References

top
  1. [1] F. Bendali and A. Quilliot, Réseaux stochastiques. RAIRO Oper. Res. 24 (1990) 167-190. Zbl0699.90033MR1065533
  2. [2] T.H. Cormen, C.H. Leiserson and R.L. Rivest, Introduction to algorithms. MIT Press, Cambridge, Mass (1980). Zbl1047.68161
  3. [3] E. Dijkstra, A note with two problems in connection with graphs. Numer. Math. I (1959) 269-271. Zbl0092.16002MR107609
  4. [4] R. Dionne and M. Florian, Exact and approximate algorithms for optimal network design. Network 9 (1979) 37-59. Zbl0397.94024MR525452
  5. [5] A. Farley, Minimum broadcast networks. Networks 10 (1980) 59-70. Zbl0432.90030MR565325
  6. [6] M. Florian, No linear cost models in transportation analysis. Math. Programming Study 26 (1986) 167-196. Zbl0607.90029MR830490
  7. [7] P. Fraigniaud and E. Lazard, Methods and problems of communication in usual networks. Discrete Appl. Math. 53 (1994) 79-133. Zbl0818.94029MR1291003
  8. [8] M. Gondran and M. Minoux, Graphes et algorithmes. Ed. Eyrolles (1979). Zbl0497.05023MR615739
  9. [9] R.M. Karp and J.B. Orlin, Parametric shortest path algorithms with application to cyclic staffing. Discrete Appl. Math. 3 (1981) 37-45. Zbl0453.68032MR604264
  10. [10] J. Lauriere, Intelligence Artificielle. Eyrolles (1987). 
  11. [11] E. Lawler, A procedure for computing the k best solutions to discrete optimization problems and its application to the shortest path problem. Management Sci. 18 (1972) 401-405. Zbl0234.90050MR292489
  12. [12] E. Minieka, Optimization algorithms for networks and graphs. Marcel Dekker Inc. (1978). Zbl0427.90058MR517268
  13. [13] M. Minoux, Network synthesis and optimum network design problems: Models, solution methods and applications". Network 19 (1989) 313-360. Zbl0666.90032MR996586
  14. [14] N. Nilsson, Problem solving methods in A.I. Mac Graw Hill (1971). 
  15. [15] A. Quilliot, A retraction problem in graph theory. Discrete Math. 54 (1985) 61-71. Zbl0588.05043MR787493
  16. [16] A. Quilliot, Algorithmes de cheminements pour des réseaux d’actions à effets non déterministes. Math. Appl. 12 (1991) 25-44. Zbl0743.68140
  17. [17] M. Sakarovitch, Chemins, flots, ordonnancements dans les réseaux. Hermann, Paris (1984). 
  18. [18] M. Sakarovitch, The k shortest routes and k-shortest chains in a graph. Report ORC, Operation Research Center, University of California, Berkeley (1966) 66-32. 
  19. [19] D.R. Shier, On algorithms for finding the k shortest pathes in a network. Networks 9 (1979) 195-214. Zbl0414.68034MR546997
  20. [20] J. Wardrop, Some theoretical aspects of road traffic research. Proc. Inst. Civil Engrg. II (1952) 325-378. 
  21. [21] B. Yaged, Minimum cost routing for dynamic network models. Network 3 (1973) 315-331. Zbl0266.90057

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.