Navigation – Plan du site
1997
26

Morphologie du réseau de communication et localisations optimales d'activités. Quelle mesure pour exprimer la forme d'un réseau ?

The shape of the transportation network and the optimal location of facilities. How to measure the shape of a network ?

Hubert Beguin et Isabelle Thomas

Résumés

L'objectif du présent article est de poser succinctement les problèmes que soulèvent la caractérisation de la forme d'un réseau par un - ou plusieurs - paramètre(s). Une brève revue de la littérature est proposée; elle conduit à la conclusion qu'il n'existe pas aujourd'hui de critère unique et dépourvu d'ambiguïté permettant de distinguer deux graphes topologiquement distincts. Des perspectives sont discutées quant à la mesure de l'effet de la forme du réseau de communication sur les résultats d'un modèle de localisation optimale.

Haut de page

Texte intégral

Introduction

1Le modèle de la k-médiane vise à déterminer les localisations et les affectations qui minimisent la désutilité des déplacements entre la demande pour un bien (ou service) et l'offre correspondante. Bureaux de Poste, services d'urgence, services récréatifs sont autant d'exemples qui font des modèles de localisation-affectation un outil opérationnel d'aide à la décision. Dans la pratique, le milieu géographique est représenté par un ensemble de points qui symbolisent la demande et les sites potentiels d'offre; les déplacements de la demande vers l'offre (ou inversement) s'effectuent le long d'un réseau de transport représenté par des liens entre les noeuds. Les résultats de la résolution d'un problème tel que la k-médiane sont donc dépendants des caractéristiques du réseau de transport et notamment de la quantité de routes disponibles et de l'organisation spatiale de celles-ci.

2La forme du réseau de communication modifie les localisations et l'efficacité du système spatial mais aussi la répartition de la demande entre les k facilités, la taille des aires de marché et l'équité entre les demandeurs : Peeters et Thomas le démontrent de façon exploratoire en 1995 en introduisant des modifications de la forme d'un réseau théorique sur un lattis quadrangulaire de points, et en 1996 (Arnold, Peeters et Thomas) sur un lattis hexagonal. Leurs résultats indiquent que, même indépendamment de la connexité du réseau, la structure géographique du réseau exerce une nette influence sur divers aspects de la localisation d'une offre et l'affectation de la demande à cette offre. Les distances entre offre et demande, en termes d'efficacité et d'équité, ainsi que les localisations de l'offre et les aires de marché diffèrent selon la configuration spatiale du réseau. Empiriquement, Oppong (1996) montre dans quelle mesure les résultats optimaux dépendent du type de réseau, selon que l'étude de localisation optimale est conduite en saison sèche (réseau dense) ou en saison des pluies (communications malaisées).

3Mesurer l'effet de la forme du réseau de communication sur les résultats de la k-médiane signifie maîtriser les nombreux éléments caractérisant le réseau. L'objectif du présent article est de poser succinctement les problèmes que soulèvent actuellement encore la caractérisation de la forme d'un réseau par un - ou plusieurs - paramètre(s).

De la théorie des graphes à la géomorphométrie

4Soit un réseau de communication représenté par un graphe simple connexe valué, où e est le nombre d'arêtes et n et le nombre de sommets. Puisqu'une localisation optimale peut toujours être trouvée sur un noeud du réseau (Hakimi, 1964), ce dernier peut être représenté par un graphe connexe dont les noeuds sont à la fois les points de demande et les points d'offre potentiels, et dont les arêtes sont les routes du réseau de transport, les plus courts chemins entre points. A l'exclusion des cas triviaux de très petits réseaux, il existe généralement un très grand nombre de formes spatiales différentes susceptibles de relier les n points de demande aux k points d'offre de manière connexe (Read, 1979, p 409). Afin de mieux comprendre comment les résultats de la k-médiane peuvent dépendre des caractéristiques spatiales du réseau, il convient de contrôler le plus grand nombre possible de caractéristiques du réseau pour pouvoir examiner l'effet d'un petit nombre d'entre elles sur les résultats du modèle de localisation-affectation. Une des premières étapes de notre programme d'étude est donc de trouver des paramètres significatifs permettant de décrire un réseau et de départager les isomorphismes.

5Soit un espace géographique représenté par un ensemble de noeuds et de liens (graphe). Les caractéristiques spatiales de ce réseau sont multiples : (1) la taille et la forme du territoire étudié, c'est-à-dire les dimensions du graphe (étendue) et la forme de ses limites. La forme de l'enveloppe (exemple : une commune, un département, un pays, etc.) détermine l'importance des effets de frontière sur les résultats. (2) La représentation du contenu du territoire est résumée par un nombre de points (n ) qui représentent la demande et/ou l'offre. Ces points sont caractérisés par leur nombre, mais aussi par leur localisation géographique (coordonnées) et par un poids associé à chacun de ces points (quantité de demande). Enfin, (3), les liens entre ces noeuds constituent un dernier élément spatial décrivant la forme du réseau de communication. Ils sont caractérisés par leur nombre (e ), mais aussi par leur localisation spatiale (couples origine-destination), par leur longueur, par le flux de transport qui y est affecté et par leur capacité (flux maximum). La forme des liens dépend de la localisation des points de demande/d'offre.

6Notre problème est d'associer à chaque réseau un (ou plusieurs) indicateur(s) de description, et de départager ainsi les réseaux en catégories exclusives. Quels réseaux se ressemblent et selon quels critères ? Quels réseaux sont topologiquement identiques ? La littérature relative à ce problème est vaste mais souvent ancienne (années 60 et 70) et relève de différents domaines de la science; nous tenterons de résumer l'état de nos connaissances dans les quelques paragraphes qui suivent et dans le tableau repris ci-dessous.

7De nombreuses mesures sont issues directement de la théorie des graphes (Berge, 1963; Busacker et Saaty, 1965). Kansky (1963) utilise plusieurs indices exprimant la centralité, la connexité (la continuité du réseau), la connectivité (le maillage plus ou moins complet), la nodalité (les relations plus ou moins nombreuses et directes entre chaque point du réseau et tous les autres). Certains indices sont dits globaux (ex.: nombre cyclomatique, , , ), d'autres locaux (ex.: le diamètre, l'indice de Shimbel, l'accessibilité)(Dupuy, Stransky, 1996; Berry, Marble, 1968). En général, ces indices sont aisément calculables mais ils ne prennent pas en compte la longueur des liens, ni la qualité des communications (Smith, 1975) et discriminent mal des réseaux de tailles identiques (Cliff, Haggett, Ord, 1979; James e.a., 1970) puisqu'essentiellement basés sur le nombre de liens (e ) et/ou de noeuds (n ). Pour un nombre donné de liens et de noeuds, il est dès lors très aisé de trouver deux réseaux topologiquement différents mais caractérisés par des indices identiques (James e.a., 1970; Arnold, Peeters, Thomas, 1996).

8Ord propose en 1967 les indices S et I pour caractériser et classifier les réseaux de transport : S et I sont basées sur l'analyse des distributions de fréquences de la matrice des plus courts chemins associée au graphe; S et I dépendent des moments d'ordre 1 à 3. La comparaison des réseaux passe par un graphique croisant les valeurs de S et de I; selon leur position sur le graphique bidimensionnel, une conclusion est tirée quant à la distribution théorique des fréquences des plus courtes distances de chacun des réseaux étudiés. Les graphes planaires relèvent le plus souvent d'une distribution beta-binomiale, les graphes non-planaires sont hypergéométriques. Lorsque le nombre d'arcs augmente, I tend vers zéro et S vers -1. Des pondérations peuvent être considérées. Ces indices sont cependant toujours insuffisants pour départager deux formes de réseaux : deux paires de valeurs S-I identiques peuvent correspondre à des réseaux différents (Cliff, Haggett, Ord, 1979).

9Une troisième catégorie d'indicateurs provient de la géomorphométrie, de l'analyse topologique des réseaux dentritiques (drainage, rivières). Les rivières sont vues comme des graphes planaires faits de sources, fourches ou bifurcations, et d'une embouchure (lien terminal). Limitée aux arbres directionnels (les rivières coulent dans un seul sens, de la source vers l'embouchure), ces indicateurs sont principalement basés sur la notion d'ordre. Plusieurs définitions de l'ordre existent; elles dépendent de leur auteur et de la nature de la mesure (nominale, ordinale, cardinale) (voir par exemple Horton, 1932, Strahler, 1952, Scheidegger, 1965, Schreve, 1966, 1967). A côté de ces notions topologiques, certains géomorphologues tiennent compte de la notion de longueur et de distance entre la source et l'embouchure (exemple : Werner, Smart, 1976; Jarvis 1972; Liao, Scheidegger, 1968). Une multitude d'indicateurs descriptifs simples existent, tous basés sur l'ordre, les bifurcations et la longueur de la rivière. Werner et Smart (1973), Jarvis (1977) et Jarvis et Werrity (1975) proposent une classification multivariée des rivières selon un choix de critères topologiques. Aucune des méthodes d'ordonancement n'est cependant extrapolable à des réseaux de communications puisque par définition le trafic est bidirectionnel et se déroule tant sur des circuits que des arbres. Aucun indice pris isolément ou en combinaison avec d'autres ne permet de tenir compte des formes sous-jacentes : deux réseaux non-isomorphes peuvent avoir des indicateurs dont les valeurs sont identiques. Des réseaux géométriquement différents dans le plan euclidien peuvent être topologiquement identiques et des réseaux ayant un nombre de sources identique ont une complexité topologique comparable mais sont topologiquement différents !

10Enfin, les valeurs et vecteurs propres des matrices d'adjacence des graphes-réseaux constituent une dernière famille de descripteurs. Kendal (1957) et Cliff et Ord (1981) décrivent un algorithme pour obtenir les valeurs propres et vecteurs propres de ces matrices. A l'époque, ils concluaient d'une part qu'un réseau fortement connecté génère de larges valeurs propres, et d'autre part, qu'au plus élevée est la valence d'un lien, au plus grand est le vecteur propre. Cette interprétation a été discutée (Hay, 1975; Tinkler, 1972; Boots, 1982, 1984; Boots, Royle, 1991; Griffith, Jones, 1980) car - tout comme en analyse factorielle - des vecteurs propres différents ne conduisent pas toujours à une interprétation dépourvue d'ambiguïtés. Cette méthode reste cependant un regard intuitif et tâtonnant, très empirique sur les graphes. Elle n'a pas abouti à l'identification certaine d'un indicateur clair de structure spatiale d'un graphe.

11A côté de ces quatre pistes d'investigations, peu de progrès significatifs ont été faits à notre connaissance, cela malgré l'émergence de nouvelles méthodes telles les fractales ou les réseaux neuronaux. A l'heure actuelle, il est encore bien malaisé de caractériser un réseau de communications par un indicateur de forme.

Conclusions

12En conclusion, la littérature géographique s'avère encore actuellement relativement pauvre en mesures efficaces de la forme des réseaux de communications. La plupart des progrès datent des années 60-70 et se sont arrêtés là. Aucun indicateur ou groupe d'indicateurs ne permet de caractériser avec certitude une forme de réseau de communication, de départager deux réseaux de façon non ambigüe. Or, il y a tout lieu de penser que certains réseaux tendent vers la concentration d'acitivtés, d'autres vers la dispersion.

13Vu la nature de la revue CYBERGEO, nous nous permettons de terminer cet article par trois questions :

  • Avons-nous omis des articles fondamentaux en matière de descripteurs de graphes ? Dans l'affirmative, lesquels ?

  • Quel(s) critère(s) utiliser pour départager des graphes isomorphes ?

  • Et, quel(s) critère(s) pourrait-on imaginer pour opérer une partition de l'ensemble des graphes en classes qui conduirait à une typologie qui soit utile du point de vue de la k-médiane, qui conduirait à minimiser la diversité interne des classes quant aux résultats de la k-médiane ?

Haut de page

Bibliographie

Arnold P., Peeters D., Thomas I. (1996) Network configuration and p-median results : the case of the hexagonal spatial structure. Sistemi Urbani (à paraître).

Berge C. (1958, 2e edn. 1963) Théorie des graphes et ses applications. Dunod, Paris.

Berry B., Marble D. (1968) Spatial analysis. A reader in statistical geography. Prentice-Hall, New Jersey.

Boots B. (1984) Evaluating principal eigenvalues as measures of network structure. Geographical Analysis, 16:3, 270-275.

Boots B. (1985) Size effects in the spatial patterning of nonprincipal vectors of planar networks. Geographical Analysis, 17:1, 74-81.

Boots B., Royle G. (1991) A conjecture on the maximum value of the principal eigenvalue of a planar graph. Geographical analysis, 23:3, 276-282.

Busacker R., Saaty T. (1965) Finite graphs and networks : an introduction with applications. McGraw-Hill, New York.

Cliff A., Ord J. (1981) Spatial processes. Pion, London.

Cliff A., Haggett P., Ord J., Bassett K., Davies R. (1975) Elements of spatial structure. A quantitative approach. Cambridge University Press.

Cliff A., Haggett P., Ord K. (1979) Graph theory and geography. in Wilson R., Beineke L. (Eds) Applications of graph theory. Academic Press, London.

Dupuy G., Stransky V. (1996) Cities and highway networks in Europe. Journal of Transport Geography, 107-119.

Ferguson R. (1975) Network elongation and the bifurcation ratio. Area 7, 121-124.

Garrison W., Marble D. (1965) A prolegomenon to the forecasting of transportation development. U.S. Army Technical Report, Northwestern University.

Gould P. (1967) On the geographical interpretation of eigenvalues? Institute of British Geog. Publ., 42, 63-92.

Griffith D., Jones K. (1980) Explorations into the relationship between spatial structure and spatial interaction. Environment and Planning A, 12, 187-201.

Haggett P, Cliff A., Frey A. (1977), Locational Analysis in Human Geography. Arnold, London.

Haggett P., Chorley R. (1972) Network analysis in geography. Arnold, London.

Hakimi L. (1965) Optimum distribution of switching centers in a communication network and some related graph theoretic problems. Operations Research 13, 462-465.

Hay A. (1975) On the choice of methods in the factor analysis of connectivity matrices : a comment. Inst. Brit. Geog. Publ. 66, 163-167

Haynes V. (1977) The modification of valley patterns by ice-sheet activity. Geografiska Annaler A, 59, 195-207.

Horton R. (1945) Erosional development of streams and their drainage basins : hydrophysical approach to quantitative morphology. Bull. Geolog. Soc. America 56, 275-370.

James G., Cliff A., Haggett P., Ord J. (1970), Some discrete distributions for graphs with applications to regional transport networks. Geografiska Annaler B, 52, 14-21.

Jarvis R. (1977) Spatial variation in ordered tributary basins - a proposed classification. Geografiska AnnalerA, 241-251.

Jarvis R., Werrity A. (1975) Some mcomments on testing random topology stream network models. Water Resources Research 11, 309-318.

Kansky K. (1963) Stucture of transportation networks : relatoionshops between network geography and regional characteristics. University of Chicago, Department of Geography, Research Papers 84.

Kendal M (1957) Multivariate analysis. Griffin, London.

Laporte, Mesa, Ortega (1994) Assessing Topological Configurations for Rapid Transit Networks. Research Paper CRT-999 (Montréal), 16 p.

Liao K., Scheidegger A. (1968) A computer model of some branching-type phenomena in hydrology. Bull. Int. Ass. Sci. Hydrol. 13:1, 5-13.

Lowe J., Moryades S. (1975) The Ggeography of movement. Houghton Mifflon Company, Boston.

Musso A., Vuhic V. (1988) Characteristic of metro networks and methodology for their evaluation. Transportation Research Record 1162, 22-33.

Oppong J. (1996), Accomodating the Rainy Season in Third World Location-Allocation Applications. Socio-Economic Planning Science, 30-2, 121-137.

Ord J. (1967) On a system of discrete distributions? Biometrika, 54, 649-56.

Peeters D., Thomas I. (1995) The effect of spatial structure on p-median results. Transportation Science 29, 366-373.

Peuquet D. (1988) Representations of geographic space : toward a conceptual synthesis. Annals Assoc. Americ. Geog., 78:3, 375-394.

Pitts F. (1965) A graph theoretic approach to historical geography. Professional Geographer 17, 15-20.

Read R. (1979) Algortihms in graph theory. in Wilson R., Beineke L. (Eds) Applications of graph theory. Academic Press, London.

Scheidegger A. (1965) Statistical low of stream numbers. Jour. Geology, 74, 17-37.

Shreve R. (1966) Statistical low of stream numbers. Jour. Geology 74, 17-37.

Shreve R. (1967) Infinite topologically random channel networks. Journal of Geology, 178-186.

Smith D. (1975) Patterns in human geography. An introduction to numerical methods. New York, David & Charles Newton Abbot.

Strahler A. (1964) Quantitavie geomorphology of drainage basins and channel networks. in Chow V. (Ed.) Handbook of applied hydrology. McGraw-Hill, New York, 4.40-4.74.

Taafe E., Gauthier H. (1973) Geography of transportation. Prentice-Hall, Englewood Cliffs, New York.

Tinkler K. (1979) Graph theory. Progress in Human Geography, 3, 85-116.

Tinkler K. (1972) The physical interpretation of eigenvalues of dichotomous matrices. Inst. Brit. Geog. Publ. 55, 17-46.

Werner C., Smart J (1973) Some new methods of topologic classification of channel networks. Geographical Analysis, 5, 271-295.

Werrity A. (1967) The topology of stream networks. in Chorley R. (Ed.) Spatial analysis in geomorphology. Methuen, London, 167-196.

Haut de page

Document annexe

Haut de page

Table des illustrations

URL http://cybergeo.revues.org/docannexe/image/2189/img-1.png
Fichier image/png, 43k
Haut de page

Pour citer cet article

Référence électronique

Hubert Beguin et Isabelle Thomas, « Morphologie du réseau de communication et localisations optimales d'activités. Quelle mesure pour exprimer la forme d'un réseau ?  », Cybergeo : European Journal of Geography [En ligne], Systèmes, Modélisation, Géostatistiques, document 26, mis en ligne le 09 avril 1997, consulté le 25 juin 2017. URL : http://cybergeo.revues.org/2189 ; DOI : 10.4000/cybergeo.2189

Haut de page

Auteurs

Hubert Beguin

Département de Géographie, Université catholique de Louvain, Louvain-la-Neuve, Belgique. beguin@geog.ucl.ac.be

Isabelle Thomas

Département de Géographie, Université catholique de Louvain, Louvain-la-Neuve, Belgique. isabelle@geog.ucl.ac.be

Articles du même auteur

Haut de page

Droits d’auteur

© CNRS-UMR Géographie-cités 8504

Haut de page