Hostname: page-component-586b7cd67f-dlnhk Total loading time: 0 Render date: 2024-11-24T07:54:20.727Z Has data issue: false hasContentIssue false
  • English
  • Français

Multiple Routing Strategies in a Labelled Network

Published online by Cambridge University Press:  15 August 2002

J. Maublanc ,
D. Peyrton  and
A. Quilliot
J. Maublanc
Affiliation:
CERTU, Lyon, France.
D. Peyrton
Affiliation:
CERTU, Lyon, France.
A. Quilliot
Affiliation:
ISIMA, Campus des Cézeaux, Université Blaise Pascal, BP. 125, 63173 Aubière, France.
Get access

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.

Keywords

Shortest pathsnetwork designrouting.
Type
Research Article
Information
RAIRO - Operations Research , Volume 35 , Issue 1 , January 2001 , pp. 85 - 106
Copyright
© EDP Sciences, 2001

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Bendali, F. and Quilliot, A., Réseaux stochastiques. RAIRO Oper. Res. 24 (1990) 167-190. CrossRef
T.H. Cormen, C.H. Leiserson and R.L. Rivest, Introduction to algorithms. MIT Press, Cambridge, Mass (1980).
E. Dijkstra, A note with two problems in connection with graphs. Numer. Math. I (1959) 269-271.
Dionne, R. and Florian, M., Exact and approximate algorithms for optimal network design. Network 9 (1979) 37-59. CrossRef
Farley, A., Minimum broadcast networks. Networks 10 (1980) 59-70. CrossRef
Florian, M., No linear cost models in transportation analysis. Math. Programming Study 26 (1986) 167-196. CrossRef
Fraigniaud, P. and Lazard, E., Methods and problems of communication in usual networks. Discrete Appl. Math. 53 (1994) 79-133. CrossRef
M. Gondran and M. Minoux, Graphes et algorithmes. Ed. Eyrolles (1979).
Karp, R.M. and Orlin, J.B., Parametric shortest path algorithms with application to cyclic staffing. Discrete Appl. Math. 3 (1981) 37-45. CrossRef
J. Lauriere, Intelligence Artificielle. Eyrolles (1987).
Lawler, E., 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. CrossRef
E. Minieka, Optimization algorithms for networks and graphs. Marcel Dekker Inc. (1978).
Minoux, M., Network synthesis and optimum network design problems: Models, solution methods and applications". Network 19 (1989) 313-360. CrossRef
N. Nilsson, Problem solving methods in A.I. Mac Graw Hill (1971).
Quilliot, A., A retraction problem in graph theory. Discrete Math. 54 (1985) 61-71. CrossRef
Quilliot, A., Algorithmes de cheminements pour des réseaux d'actions à effets non déterministes. Math. Appl. 12 (1991) 25-44.
M. Sakarovitch, Chemins, flots, ordonnancements dans les réseaux. Hermann, Paris (1984).
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.
Shier, D.R., On algorithms for finding the k shortest pathes in a network. Networks 9 (1979) 195-214. CrossRef
J. Wardrop, Some theoretical aspects of road traffic research. Proc. Inst. Civil Engrg. II (1952) 325-378.
Yaged, B., Minimum cost routing for dynamic network models. Network 3 (1973) 315-331. CrossRef