Multiple routing strategies in a labelled network
RAIRO - Operations Research - Recherche Opérationnelle, Volume 35 (2001) no. 1, p. 85-106

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.

Keywords: shortest paths, network design, routing
@article{RO_2001__35_1_85_0,
     author = {Maublanc, J. and Peyrton, D. and Quilliot, A.},
     title = {Multiple routing strategies in a labelled network},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     publisher = {EDP-Sciences},
     volume = {35},
     number = {1},
     year = {2001},
     pages = {85-106},
     zbl = {0993.90015},
     mrnumber = {1841815},
     language = {en},
     url = {http://www.numdam.org/item/RO_2001__35_1_85_0}
}
Maublanc, J.; Peyrton, D.; Quilliot, A. Multiple routing strategies in a labelled network. RAIRO - Operations Research - Recherche Opérationnelle, Volume 35 (2001) no. 1, pp. 85-106. http://www.numdam.org/item/RO_2001__35_1_85_0/

[1] F. Bendali and A. Quilliot, Réseaux stochastiques. RAIRO Oper. Res. 24 (1990) 167-190. | Numdam | MR 1065533 | Zbl 0699.90033

[2] T.H. Cormen, C.H. Leiserson and R.L. Rivest, Introduction to algorithms. MIT Press, Cambridge, Mass (1980). | Zbl 1047.68161

[3] E. Dijkstra, A note with two problems in connection with graphs. Numer. Math. I (1959) 269-271. | MR 107609 | Zbl 0092.16002

[4] R. Dionne and M. Florian, Exact and approximate algorithms for optimal network design. Network 9 (1979) 37-59. | MR 525452 | Zbl 0397.94024

[5] A. Farley, Minimum broadcast networks. Networks 10 (1980) 59-70. | MR 565325 | Zbl 0432.90030

[6] M. Florian, No linear cost models in transportation analysis. Math. Programming Study 26 (1986) 167-196. | MR 830490 | Zbl 0607.90029

[7] P. Fraigniaud and E. Lazard, Methods and problems of communication in usual networks. Discrete Appl. Math. 53 (1994) 79-133. | MR 1291003 | Zbl 0818.94029

[8] M. Gondran and M. Minoux, Graphes et algorithmes. Ed. Eyrolles (1979). | MR 615739 | Zbl 0497.05023

[9] R.M. Karp and J.B. Orlin, Parametric shortest path algorithms with application to cyclic staffing. Discrete Appl. Math. 3 (1981) 37-45. | MR 604264 | Zbl 0453.68032

[10] J. Lauriere, Intelligence Artificielle. Eyrolles (1987).

[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. | MR 292489 | Zbl 0234.90050

[12] E. Minieka, Optimization algorithms for networks and graphs. Marcel Dekker Inc. (1978). | MR 517268 | Zbl 0427.90058

[13] M. Minoux, Network synthesis and optimum network design problems: Models, solution methods and applications". Network 19 (1989) 313-360. | MR 996586 | Zbl 0666.90032

[14] N. Nilsson, Problem solving methods in A.I. Mac Graw Hill (1971).

[15] A. Quilliot, A retraction problem in graph theory. Discrete Math. 54 (1985) 61-71. | MR 787493 | Zbl 0588.05043

[16] A. Quilliot, Algorithmes de cheminements pour des réseaux d'actions à effets non déterministes. Math. Appl. 12 (1991) 25-44. | Zbl 0743.68140

[17] M. Sakarovitch, Chemins, flots, ordonnancements dans les réseaux. Hermann, Paris (1984).

[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] D.R. Shier, On algorithms for finding the k shortest pathes in a network. Networks 9 (1979) 195-214. | MR 546997 | Zbl 0414.68034

[20] J. Wardrop, Some theoretical aspects of road traffic research. Proc. Inst. Civil Engrg. II (1952) 325-378.

[21] B. Yaged, Minimum cost routing for dynamic network models. Network 3 (1973) 315-331. | Zbl 0266.90057