229

OPTIMALISATION DANS LES RI~SEAUX

Jean-Frangois L E G R O S IngOfieur des t616commuaications *

DES INVESTISSEMENTS TI~LI~PHONIQUES LOCAUX

par

Michel M I N O U X Alain O U S S E T Ancien El~ve Ingdnieur *

de l'dcole Polytechnique

R~SUMI~. - - Les rdseaux tdl@honiques locaux sont constituds par l'ensemble des sgst~mes d'abonnds (c'est-d-dire lignes et mat&Ms situ~s entre le poste tdl@honique et le centre local de rattachemenl). On ddcrit ici une mdlhode permettant de ddterminer une polilique optimale d'exlension d'un rdseau local minimalisant le bilan actualisd, sur une pdriode d'dlude considdrde, des inveslissements en cables, supports de cables (arl~res a&iennes, traneh&s, conduites... ) el concentrateurs de lignes d' abonnds. A l' aide de la thdorie des graphes el des riots, le probl~me est reprdsenld comme un programme mathdmatique non tin&ire & variables enti~res. Ce probl~me (comportant un lr~s grand nombre de variables) est rdsolu par une mdthode de recherche arborescente de type profondeur

d 'abord. Des rdsultats de son application sont prdsentds.

ABSTRACT. - - Local telephone networks are composed of cables and equipments used between the subscriber's pre- mises and his local exchange. This paper describes a method to determine an optimal extension policy for local networks, which minimizes the presenl worth of annual costs over a given study period, of investments of cables, supporting structures (poles, trenches, conduits...) and subscriber pair gain systems. Using graph and network flow theory, the problem is represented as a non linear integer mathematical program. This problem is solved using a depth first tree search method. Results obtained on a few typical examples are presented.

PLAN'. - - e 1 : Introduction. o 2 : Ddfinition du probl~me. �9 3 : Formulation du probl~me : Extension au moindre co~t d'un rdseau parcouru par des riots avec multiplicateurs. �9 4 : Eludes des propridtds du probl~me : Para-

mdtrisation. �9 5 : R&olution du probl~me P. �9 6 : Rdsultals. �9 7 : Conclusion.

i . I N T R O D U C T I O N

Les invest issements dans les rdseaux tdldphoniques

locaux t iennent ac tue l lement une place tr6s impor tan te

dans le budget annuel des tdldcommunicat ions (de

30 h 40 % environ) et les pr6visions laissent penser

que cet te par t ne fera qu 'augmenter .

En effet, darts ce type de rfseaux, les cofits de

raccordemcnt sont gdndralement 61evds, en raison des

distances entre abonnds et a u t o c o m m u t a t e u r de

r a t t achemen t , et des faibles densitds d'abonnds.

D 'au t re part , l 'u t i l isat ion de concentra teurs (le

lignes d 'abonnds (mat6riels raccordant un certain

hombre d 'abonnds par un nombre infdrieur de jonc-

tions) permet de rdaliser darts certains cas des 6co-

notates substantiel les dans le coflt de raccordement

des abonn6s susceptibles d 'y ~tre rattach6s.

Tout ceci justifie la recherche et la wise au point

d 'outi ls au tomat iques pe rme t t an t de choisir au mieux

les invest issements effect@s dans ces rdseaux locaux

(choix des taillcs et calibres des cables, dimension-

nement des infrastructures, d6terminat ion du hombre

et de l ' emplacement des concentrateurs) [1, 2].

Cet article est consacr~ au probl~me de la ddfinition

d 'une poli t ique opt imale d 'extens ion d 'un r6seau local

(partie t ransport) au sens du moindrc cofit actualisd,

sur un interval lc de temps donn6, cn t enan t compte

de la possibilit6 d 'ut i l isat ion (le concentra teurs de

ligne d 'abonnds .

2. D I ~ F I N I T I O N D U P R O B L ~ M E

Dans un rdseau t6 l@honique local, le r&eau de

transport est la part ie du r6seau qui relie les sous-

r@ar t i t ions h leur au tocom m uta t eu r de r a t t a chemen t (Fig. 1).

Dans le cas du rdseau fran~ais, un r6seau de t rans-

port peut ~tre d~crit, dans le langage de la th6orie

des graphes, comme un arbre orient6 ayan t l ' au to-

c o m m u t a t e u r comme racine [3]. Les autres nceuds

repr6sentent soit les points de sous- r@art i t ion (S.R.),

soit Ies nmuds de jonct ion (points de raccordement

des cables), et les arcs jo ignant ces nceuds sont consti-

t@s par les divers cables exis tant sur chaque tron~on

rel iant les points de sous-r@art i t ion et les nceuds de

jonct ion (Fig. 1). Les arcs sont orientals vers la racine.

On ne s 'occupe pas ici des invest issements darts le

rdseau de distr ibut ion (reliant les points de sous-

r@ar t i t ion aux points de concentra t ion d'abonn~s).

* A u CNET-Issy, groupement R ~ S n A U X ET CENTRES DE COMMUTATION, ddpartement ]~TUDES EN COMMUTATION ET RI~SEAUX.

1/10 ANN. TI~L~COMMUN1C., 31, n o" 7-8, 1976

230 J . - F . LEGROS. -- O P T I M A L I S A T I O N DES I N V E S T I S S E M E N T S DANS LES RI~SEAUX TI~LI~PHO~'IQUES LOCAUX

Pattie distribution

Partie transport

. . . . . . .

Y

Autocommutateur ]

F:G. 1. ]-1~seau local.

point de sous-r@artition

, noeuds de jonction ;

points de concentration d'abonn6s (ou point de distribution).

E t a n t donn6 une p6riode d 'dtude et une demande pr6visionnelle de raccordement en chaque point de sous-r@art i t ion, ~ chaque ins tan t de la p6riode, le

probl6me est de d~terminer une politique optimale

d ' invest issements darts la part ie t ranspor t d ' un rdseau

local, c'est-h-dire de minimaliser la somme des cofits actualisfs des concentrateurs , des cables et des sup- ports de cable (poteaux t61@honiques, tranchdes, conduites...) n6cessaires pour satisfaire la demande

chaque ins tan t de la pdriode.

2.1 . Les c o n t r a i n t e s :

C 3. I1 faut aussi tenir compte de contraintes techniques de raccordement. Pour chaque n(eud, la liaison 6lectrique dolt satisfaire h des contraintes de r6sistance, d 'affaiblissement et de distorsiou. Nous supposons ici la donnde d ' un plan de normalisat iou optimal, pe rme t t an t de d6terminer le calibre de rac- cordement d 'un point de sous-rdpart i t ion en fonction de la distance entre l ' au tocommuta t eu r et le point de concentrat ion d 'abonnds le plus dloign6 [4]. Par suite, ~ chaque ins tant , eu chaque nceud, la demande

se diffdrencie par calibre.

2.2 . Les h y p o t h S s e s .

H 1. On n 'envisage pas la modificat ion du r6seau exis taut au cours de la p6riode d'dtude. Par aillenrs, h chaque ins tan t de la pdriode d'dtude, on supposera qu 'on ne remet pas en cause les invest issements ddcidds antdrieurement .

H 2. L ' implan ta t ion des concentrateurs ne peut se faire qu ' aux emplacements des sous-r@arti t ions.

D 'aut re part , les hypotheses suivantes ont unique- men t pour but de simplifier la prdsentat ion de cet article (mais ne sont nu l lement indispensables h la r6solution du probl6me).

H 3. Chaque nceud est raccord6 ~ l ' au tocommu- ta teur par des cables de m~me calibre.

H4. Soit k (k < 1) le rapport de concentra t ion (nombre de paires sortantes sur nombre de paires entrantes) des concentra teurs utilisds dans le rdseau. Le nombre de paires ndcessaires pour raccorder

N abonnds desservis par des concentrateurs est une

fonction en escalier de N. On fera une approximat ion

de cette fonction par la fonction lindaire k x N.

3. F O R M U L A T I O N D U P B O B L ~ M E : E x t e n s i o n a u m o i n d r o corot d ' u n r 6 s e a u

p a r c o u r u p a r d e s r iots a v e c m u l t i p l i c a t e u r s

C 1. Le trafic issu d 'un point de concentra t ion d 'abonnds et p rovenan t d 'abonnds concentrables ne peut ~tre concentrd qu 'une fois au plus entre la sous-

r6part i t ion et l ' au tocommuta teur .

C2. I1 existe des contraintes techniques pour l ' implan ta t ion des concentrateurs. Considdrons une demande en paires issue des points de concentrat ion d 'abonn6s reli6s h une sous-r~partit ion A ; l a possi-

bilitd de concentrer cette demande en une sous-

r@ar t i t ion B ddpend de la distance entre l 'auto- commuta teu r et la sous-r6parti t ion B d 'une part , et de la distance entre la sous-rdpartit ion B e t le point de concentra t ion d 'abonnds le plus ~loign~ de A (origine d 'une part ie de cette demande) d 'au t re part.

Nous utiliserons ici le langage de la thdorie des graphes et la terIninologie employde est celle de

Berge [5]. Consid6rons l 'arbre G = IX, U] reprdsentatif du

rdseau dtudi~, off (Fig. 2) :

r X est l 'ensemble des nceuds (points de sous- r6part i t ion ou de jonct ion des cables principaux),

�9 U est l 'ensemble des arcs (repr6sentant les diffd-

rents trongons de cables avec leurs supports),

�9 a G X est le nceud repr6sentant l ' au tocommu-

tateur.

L 'arbrc G est orients des nceuds pendan ts (nceuds de degr6 1) vers a (autocommutateur) .

ANr~. T~LI~COMMUN1C., 31, n ~ 7-8, 1976 2 / 1 0

J . - F . L E G R O S . -- O P T I M A L I S A T I O N D E S I N V E S T I S S E M E N T S D A N S L E S R E S E A U X T E L I E P H O N I Q U E S L O C A U X 231

o

x

FIG. 2. - - G = ( X , U ) , riot sur Fare u : ~u = ~u, + ~u~.

3.1. Les donn6es de base :

On n o t e T = {0, 1, 2, . . . , T m a x } la pd r iode d ' d t u d e ,

f r a c t i o n n ~ e en i n t e r v a l l e s ( p a r e x e m p l e d ' u n e a n n i e )

�9 dlx(/) n o m b r e t o t a l d ' a b o n n d s n o r m a u x h l ' i n s -

t a n t t,

�9 d2x(/)= n o m b r e t o t a l d ' a b o n n d s sp~c i aux h F ins -

t a n t t.

3.2. D6finition du graphe G'.

E n l ' a b s e n c e des c o n c e n t r a t e u r s , on p o u r r a i t cons i -

d~rer l ' e n s e m b l e des d e m a n d e s de r a c c o r d e m e n t en

pa i res c o m m e 6 t a n t u n r iot su r G d ' e x t r ~ m i t ~ a ( e t

v d r i f i a n t les lois de c o n s e r v a t i o n de K i r c h o f f a u x

noeuds) .

L ' u t i l i s a t i o n de c o n c e n t r a t e u r s de l ignes d ' a b o n n 6 s

v a n d c e s s i t e r la m o d i f i c a t i o n des lois de c o n s e r v a t i o n

p a r l ' i n t r o d u c t i o n de f a c t e n r s m u l t i p l i c a t e u r s .

P o u r r e n d r e c o m p t e e n t e r m e s de f lots des diff6-

r e n t e s h y p o t h 6 s e s (en p a r t i c u l i e r ( H 2 ) ) , c o n s t r n i s o n s

le g r a p h e G ' - - [X ' , U ' ] , off (Fig. 3) :

Ul

a = al = a , = a 3

d u4

V 3 I

v, y, w,- . . . ,.2.X '

2 ) Z, dy

w ! ,

z$

w2

2 z~

Fro. 3. - - G' = ( X ' , U'), riot sur Fare u~ : q~u~ avec ~x = ~Pu~.

e t de du rde Tmax .

D e u x t y p e s d ' a b o n n 6 s a p p a r a i s s e n t au n i v e a u de

c h a q u e p o i n t de s o u s - r 6 p a r t i t i o n :

- - les a b o n n d s n o r m a u x ( s u s c e p t i b l e s d ' e t r e c o n c e n -

t r6s) ,

- - l e s a b o n n 6 s s p 6 c i a u x (he p o u v a n t pa s ~t re

des se rv i s p a r c o n e e n t r a t e u r e t d e v a n t ~t re relids en

d i rec t ) . P a r e x e m p l e , a b o n n d s h f o r t t r a f i c , si les

c o n c e n t r a t e u r s o n t des c o n t r a i n t e s m a x i m a l e s en

t r a f i c a d m i s s i b l e .

Les d e m a n d e s de r a c c o r d e m e n t (en n o m b r e d ' a b o n -

n6s) s o n t d o n n d e s en c h a q u e nceud x de G p a r les

f o n c t i o n s ( suppos6es n o n ddc r o i s s an t e s ) du t e m p s :

3 / lO

�9 X ' , e n s e m b l e des nceuds de G', es t o b t e n u en

a s s o c i a n t h c h a q u e nceud x E X de G t ro i s noeuds

no t6s x l , x2 , x a . On o b t i e n t a ins i u n e p a r t i t i o n de

X ' : X ' = X 1 to X 2 tO X a , off X l = { x ~ / x c X }

( i - - 1 , 2 , 3 ) .

P o u r a ~ X , on c o n s i d d r e r a que les t r o i s nceuds

a l , a2 , a a s o n t c o n f o n d u s en u n seul nceud n o t d a.

�9 U' , e n s e m b l e des a rcs de G', es t de la f o r m e :

U ' - - U I tO U 2 tO U a U U 4, avee

U 1 = { / l l = ( x l , gl)]( x, Y) e U} ,

U 2 = {u 2 = ( x 2 , g2 ) / ( x , g) E U } ,

U 3 = {u 3 - ( x 1 , x a ) / x e X } ,

U4 = {u4 = (x3, x ~ ) / x ~ X } .

ANN. TI~LI~'COMMUNIC.~ 31, n ~ 7-8, 1976

232 J . - F . L :EGi lOS . -- O P T I M A L I S A T I O N D E S I N N r E S T I S S I ~ M E N T S D A N S L E S R I ~ S E A U X T I ~ L I ~ P H O N I Q U E S L O C A U X

[N. B. Les arcs (a~, as) et ( as , a~) n ' i n t e r v i e n n e n t

pas dans le p rob lbme ct nous supposerons qu ' i l s ne

f igurent pas darts U'.]

3.3. D6f in i t ion d 'un riot avec mul t ip l i ca teur sur G'.

Sur G ' , fa isons c i rcu le r h c h a q u e i n s t a n t t u n riot

o(t) = [~u(t) l~ 'eU' te l que :

- - la lot de c o n s e r v a t i o n de K i r chhof f est vdrifide

en c h a q u e nceud de X 1 U X ~ ,

- - en c h a q u e nceud de X a , le riot s o r t a n t est ~gal

h k fois le riot e n t r a n t (k ~ 1 est le r a p p o r t de

concen t r a t i on ) ,

- - le nceud a~ = a~ = a a = a est le nceud put ts ,

- - les naeuds x~ ~ X 1 et x~ e X~ son t des sources

de riot, la v a l e u r du r o t e n t r a n t d t an t r e s p e c t i v e m e n t

d'z(t), d~x(t).

Le riot q~(t) est un riot a v e c m u l t i p l i e a t e u r sur G' [6]

et il vdrif ie le sys t~me d ' d q u a t i o n s l indaires :

[AI [q~(t)]= [D( I ) ] , ( u T ) ,

off [A] est une m a t r i e e IX ' l • I u ' l qu i se d~dui t de

la m a t r i e e d ' i ne idenee (ares-nceuds) [A'] de G' de la

man i~re s u i v a n t e :

[A(xa , us) ] = k [ A ' ( x 3 , us)] V x a e X a , V u a e U a

[A(x, u)] = [A'(x, u)] , s iuon.

E t d ' a u t r e pa r t , [D(t)] est ddfinie pa r :

t Dx~(t) = d~(t) , Vx~ e X~ - - {a}, Dx~(/) = d~x(t) , V x 2 ~ X~ - - {a},

Dxa(t ) - - 0 , V x 3 ~ X 3 - - {a} .

L ' i n t e r p r d t a t i o n des ~ui(l) est la s u i v a n t e :

~u~(t) r ep r6sen te la d e m a n d e en pai res non con-

cent rdes c i r c u l a n t sur l ' a r c u de G h l ' i n s t a n t t.

�9 Opus(t) r ep rdsen te la d e m a n d e en pai res concen-

tr6es c i r cu lan t sur l ' a r c u de G h l ' i n s t a n t t,

�9 ~u(t) = ~ux(t) + ~u~(t) repr~sen te la d e m a n d e

to t a l e en paires sur l ' a r c u de G.

Si ua = (x~ , xa) , ~x(t) = ~ua(t) repr~sen te le n o m b r e

d ' abonnds eoneert tr6s au nceud x de G h l ' i u s t a n t t.

�9 S i u a = (xa, x z ) , ~u,(t) reprdsen te le n o m b r e de

pai res n~eessaires p o u r r a c c o r d e r les abormds eoncen-

tr~s au neeud x de G h l ' i n s t a n t t.

sur Fare u. P o u r f(t) donn6e, la v a l e u r de qb u sur un

t r ongon u q u e l c o n q u e p e u t ~tre o b t e n u e de mani+re

e x a c t e p a r la p r o g r a m m a t i o n d y n a m i q u e [7]. Cepen-

dan t , ce calcul d e v a n t se fa i re un tr~s g r and h o m b r e

de lois, le t e m p s de rdso lu t ion est d ~ t e r m i n a n t ; nous

avons donc mis an po in t une m ~ t h o d e heu r i s t i que

d o n n a n t r a p i d e m e n t une b o n n e so lu t ion approchde.

Consid~rons de m ~ m e un nceud x 6 X et supposons

que la fonc t ion g ( t ) , t E T repr~sen te le n o m b r e

d ' abonnds d e v a n t ~tre concen t rds en ce nceud au

cours de la p~riode d '6 tude . On n o t e r a tFx(g ) le coflt

ac tual i sd de la po l i t i que o p t i m a l e d ' i n s t a l l a t i o n de

c o n c e n t r a t e u r s au noeud x p e r m e t t a n t de c o n c e n t r e r

g(t) abonn~s h c h a q u e i n s t a n t de la pdr iode d 'd tude .

Si on ddfini t p o u r les fonc t ions de R T ( * ) la r e l a t ion

d ' o rd re pa r t i e l (notde __~) :

f o ( f ' ~ V l ~ T , f(t) ~ I ' ( t ) ,

alors V(x, u) E X • U, les fonc t ions (I)u e t tF x vdr i f i en t

la p ropr i6 t6 f o n d a m e n t a l e s u i v a n t e (mono ton ic i t 6

g6n6ralis6e) :

f or f ' :~ On(f) ~ O~( f ' ) , g ~___ g' ~ Wx(g) ~ t F x ( g ' ) .

3.5. Le problSme.

D d t e r m i n e r une po l i t i que o p t i m a l e d ' e x t e n s i o n du

rdseau G r e v i e n t alors h rdsoudre le p rob l~me P

s u i v a n t :

Min z = Z Ou((pu) + Z t F x ( ~ x ) , uEU x ~ X

sous les c o n t r a i n t e s

(1) (P) [A] [ ~ ( t ) ] = [D(t)] , u T,

(2) ~u(t) = ~u~(t) + ~%(t) , u u) ~ T • U,

(3) (ox(t) = Tu~(t) , V(t, x) E T • X . a v e c u 3 = (x I , xa)

�9 . ~ T U D E D E S P I ~ O P R I ~ . T ~ S D U PBOBLi~.ME : P A R A M I ~ T B I S A T I O N

4.1. P a r a m 6 t r i s a t i o n des var iables de d6cis ion re lat ives a u x c o n c e n t r a t e u r s .

3.4. F o n c t i o n s de cofit sur les arcs et dans les noeuds .

Considdrons un a rc u ~ U de G sur leque l la d e m a n d e

to t a l e en pai res au eours de la pdr iode d '~ tude est

reprdsent~e p a r la f o n c t i o n f i t ) , t ~ T. On n o t e r a r le cofit ac tual i s6 de la po l i t i que

o p t i m a l e d ' i n v e s t i s s e m e n t s en cfibles et suppor t s de

cfibles p e r m e t t a n t de sa t i s fa i re la d e m a n d e f(t) , t E T

T o u t e po l i t i que d ' i n s t a l l a t i o n de c o n c e n t r a t e u r s sur

le g r aphe G est d6finic p a r la donn6e, h c h a q u e ins-

t a n t t, du n o m b r e K(x, t) de c o n c e n t r a t e u r s instal l6s

au noeud x ~ X h l ' i n s t a n t t.

Si C O d6signe la capac i t6 de c o n c e n t r a t i o n d ' u n

c o n c e n t r a t e u r (ca n o m b r e de paires) , alors, pour

K = [K(x, l)] donn6, le n o m b r e de pai res p o u v a n t

(*) I t "r est l 'ensemble des fonctions de T h valeur clans It.

ANN. TI~L~COMMUNIC., 31, n ~ 7-8, 1976 4/10

J . - F . LEGROS. -- O P T I M A L I S A T I O N DES I N V E S T I S S E M E N T S D A N S LES RI~SEAUX TI~LI~PHONIQUES L O C A U X 233

fitre concent rdes en x G X h l ' i n s t a n t I G T est :

c~(t) c o K ( x , t ) .

On no te K ~ (NI X] 17 ' I ) l ' ensemble des pol i t iques poss ib l e s ; il est facile de m o n t r e r que K est un ensemble fini (en t o u t uoeud x, et h chaque i n s t a n t l, le n o m b r e K(x, t) est born6).

P o u r K = [K(x, t)] donnd, le deuxi6me t e rme

tF(K) ~_~ tFz(Cx) de la fouct ion objec t ive de (P) xGX

est fix6.

Consid6rons alors le p rob l6me :

Miu ~ Ou@u), u~U

P(K) sous les co n t r a i n t e s (1), (2), (3) et

(p~(t) ~< CoK(x, t) V (x, t) ~ X • T.

No tons (I)*(K) la va leu r op t ima le de la fonc t ion objec t i f de P(K) .

R6soudre le p robl6me (P) r ev i en t alors h chercher K * = [K*(x , t)] tel que l ' on ai t :

qb*(K*) + ~F(K*) -- Min {qb*(U) + tF (K)} . KSK

E v i d e m m e n t , cet te approche n ' e s t in tdressau te que si les probl~mes P (K) ne son t pus t rop difficiles h r6soudre. C'est ce po in t que nous al lons e x a m i n e r m a i n t e n a n t .

4 . 2 . R 6 s o l u t i o n d e s p r o b l b m e s P ( K ) .

P o u r K = [ K ( x , t ) ] ~ K et V t ~ T, d6finissons les problbmes :

I Min Y, ~u(t), uGU

P ( K , t ) [A] [~(t)] = [D(t)] ,

I u(t) %~(t) + %~(t) , V u ~ U, ~x(t) = %~(t) <~ CoK(x, t ) .

On r e m a r q u e que les P (K, t) son t des p r o g r a m m e s lindaires. On p e u t d tabl i r les r6su l ta t s su ivan t s :

Propridtd 1.

Toute so lu t ion

(4) ~x*(l) = Min

op t imale q~*(t) de P (K , t) v6rifie V x :

; * l , {CoK(x , t) d~(/) + Z q)ul( )} uEPred(x)

Off pour x r X, P red (x) no te l ' en semble des arcs de G a y a n t x pou r ex t r6mi td :

P red (x) {u ~ U/u (g, x)}.

Ddmonstralion de la propridtd 1.

Mont rous que s'il existe u n riot ne v~r i f ian t pas (4) il n ' e s t pas so lu t ion op t ima le de P (K , t).

Soit u n flot rdal isable (~(t), c 'es t -h-dire qu ' i l v6rifie

les 6qua t ions [A] [~0(t)] = [D(t)] et ~ua(t ) <~ CoK(x , t), ne v6r i f iau t pas (4) au nceud m E X associ6 h l ' a rc

w ~ U [ w = (re, x ) ] , c 'es t -h-dire tel que l ' on ai t :

~m(l) < Miu {C o • K(m, t) ; d~m(t) + ~] q~ut(t)} �9 u ~ P r e d ( m )

Soit M + l ' en semble des arcs de U c o n s t i t u a n t le chemin de m h a et M - le c o m p l 6 m e n t a i r e de 3 I +

dans U.

Cons t ru i sons le r o t ~(t) sur G', ~(t) = [,~u'(t)]u'GU', de la mani6re s u i v a n t e :

- - Vu E M- ,~u i ( t ) - epu~(t) pour i = 1 h 4,

- - V u ~ M + , ~ua(t ) v6rifie (4).

C 'es t -h-dirc que l ' on d6bute pa r le nceud m :

~wa(/) est dd te rmin6 pa r l 'dgali t6 (4), puis +Wl(/), ~bw2(t ) et +w4(t ) sont fix6s par les con t r a in t e s de rdalisabil i td.

E t e n s u r e , on cons t ru i t de la m~me man i6 re pa r r6currence +u(t) pour les aut res arcs du chemin M +.

Au nceud m, ce n o u v e a u riot vdrifie : "~m(t) > ~m(t) et donc ~w(l) < ~w(t),

=~ Z q~u(t) < Z ~u(t) et Z ~u(t) < E ~Ou(t). u ~ M + u@M + u E U u E U

q)(t) n ' e s t doric pas so lu t ion op t ima le de P(K, t) pu i squ ' i l existe u n riot ~(l) d o n n a n t une v a l e u r mei l leure h la fonc t ion objectif .

La propri6t~ 1 p e r m e t de r6soudre chaque pro- b l6me P(K, l) sans avoi r recours h la p r o g r a m m a t i o n liadaire. E n effet, on r e m a r q u e que le riot op t ima l ~0*(t) p e u t ~tre calcul6 h l ' a ide de la re la t ion (4) pa r rdcurrence sur les nceuds, en p a r t a n t des nceuds pen- dan t s de G (nceuds de degr6 1).

Propridtd 2.

Soit ~*(t) une so lu t ion op t ima le de P (K , t). Tou t e

so lu t ion rdal isable q)(l) de P (K, t) vdrifie :

(5) ~ ( t ) ~< ~ ( t ) V u ~ u.

A u t r e m e u t dit , (~*( t )= [~u*(t)]ucU est une solu- t ion m in im a le , composan t e pa r composan te , dans l ' ensemble des ~ ( t ) = [~u(t)] r~alisables.

Ddmonstralion.

Elle rdsul te de la propr id t6 1.

Supposons en effet la propr idt6 2 n o n v6rifi6e, c 'es t -h-dire que pou r les riots q~*(t) op t ima l et q~(t) rdal isable, il existe u n arc w e t u n nceud m associ6s tels que :

- - l ' indgat i td (5) est v6rifi6e en t o u t arc u ~ P r e d (m),

- - elle n ' e s t pus v6rifi6e en m : ~w*(t) > ~w(t).

Or q)*(t) 6 t an t op t imal , il v6rifie la re la t ion (4) d 'aprbs la propr id t6 1 ; et les riots q~*(t) et q0(t) d t an t rdalisables, on a b o u t i t h une con t rad ic t ion .

E n f i u la propr i6 t6 s u i v a n t e p e r m e t de r a m e n e r la

rdsolut ion du p rob lbme P (K) h la rdsolu t ion des pro- blbmes P ( K , I ) , V t ~ T.

Propridld 3.

P o u r t o u t t ~ T, soit q~*(l) une so lu t ion op t ima le de P (K , t).

Alors q~*= [~*(t)]t~T est so lu t ion op t ima le du p rob l6me P(K) .

5 / 1 0 ANN. TI~LI~COMMUN1C., 31, n ~ 7-8, 1976

234 J . - F . L E G R O S . -- O P T I M A L I S A T I O N D E S I N V E S T I S S E M E N T S D A N S L E S R I ~ S E A U X T ] ~ L E P H O N I Q U E S L O C A U X

Ceci rdsulte d i rec tement de la min imal i t6 de r h chaque ins tan t t ~ T (propri6t~ 2) et de la propri~t6 de monotonici t~ (g6n6ralis6e) des fonctions (I)u.

Ddmonstralion.

Considdrons donc q~*= [(p*(l)]t~T avee q~*(t) solu- t ion op t imale de P(K, t) et supposons que q~* n 'es t pas solut ion op t imale de P(K). C'est-h-dire qu ' i l existe un flot ~, r6alisable pour P(K) et tel que la va leur de la fonct ion object i f de P(K) soit meil leure pour ~ que celle pour q~*. D o n c :

Z Cu(~*) > Z ~ ( ~ , ) �9 uEU uEU

Or d 'apr~s la propri6t6 de monotonic i t6 des fonc- t ions r on en d6dui t :

~ w ~ X et l ~ T tels que ~*(l) > ~w(t),

ce qui est en cont rad ic t ion avee la propridt6 2 appli- qu6e h T*(t) solut ion op t imale de P(K, t).

5. I : t ~ S O L U T I O N D U P R O B L ~ M E (P)

Cette r6solution consiste h 6numfrer un certain nombre de poli t iques d ' ins ta l l a t ion de concentra teurs K s K. Comme l ' ensemble K est fini, mais tr~s grand, l '6num6rat ion exhaus t ive est impossible. La m6thode que nous proposons consiste h explorer une par t ie seulement de K selon une proc6dure de recherche arborescente d6rivde d 'une m6thode de t y p e profon- deur d'abord [8].

. . . . . . . . . . . . . . . . .

t I

annees 0 = 1 ...... TMAX

I

I f

calcul de+* (KO) + ~ (KO) I

1 (

L__ ( fin boucle ann6es 1

I K* = K TMAx ~ I

noeudsy~X

I catcul de 3' (Y, h) et 3" (Y, h)

pour 1~ h< hy

] fin boucle noeuds )

�9 O U I ~ NON

OUI

I I I

1 __ . J

D I d6termination

de ~'et I~

I

! implantation d6finitive d'un concentrateur en ~ ~ 0

K 0 ( ~ , t ) = K 0 ( ~ , t ) + l , V t ~ >

I IP

FIG. 4. - - D6termiaation de K* (configuration optimale en concentrateurs de lignes d'abonn6s).

ANN. T~L~COMMUNIC., 31, n ~ 7-8, 1976 6/10

J.-F. LEGROS. -- OPTIMALISATION DES INVESTISSEMENTS DANS LES RI~SEAUX T15,LI~PHONIQUES LOCAUX 235

Pour 0 G T, on suppose que l 'on a d6termin6 une solut ion sub-opt imale K ~ = [K~ t)] pour la pdriode

0 ,1 . . . . . 0.

On a done K~ 0) - -K~ 0 + 1 ) . . . . . K~ Tmax).

Pour 0 = 0, K ~ -- [K~ t)] est la conf igurat ion de concent ra teurs exis tante .

V0 E T, K ~ est alors d~fini ~ pa r t i r de K ~ de la mani6re su ivante (Fig. 4) :

a) au d~but K ~ K ~

b) ensuite, pour ehaque nceud g ~ X successive- ment , on regarde quelle est l ' influence, sur le coflt to ta l du r~seau, de i ' impIan ta t ion de 1, 2, ..., hy con- cen t ra teurs en g h l ' i n s t an t 0 (la va leur de hy d6pend du hombre max ima l d 'abonn~s p o u v a n t 8tre eoncen- tr~s en g ~ l ' i n s t an t 0 ; g~n~ralement hy est un ent ier de faible valeur, h g = 2 ou 3).

Soit K = [K(x, t)] d~fini pa r :

K ( x , t ) = K~ Vx #: g, V t ~ T,

K(y, t ) - - K~ t) V I < 0,

K ( g , t ) = K ~ h V t >~ 0,1 <~ h ~ h u.

On note y(g, h) = r + tF(K), le eofit t o t a l du r~seau (coflt calcul6 sur tou te la p~riode d '6 tude) dans l 'hypoth+se off l 'on implan te h eoneent ra teurs sup- pl~mentaires au nceud g ~ l ' i n s tan t 0.

On consid~re d ' au t re pa r t K ' = [K'(x, t)] d6fini pa r

K ' ( x , t ) - - K~ Vx vr g, V t E T,

K'(g, t) = K~ t) V t ~ 0,

K ' ( y , I ) = K ~ h pour l ~ 0 + 1, l ~ h ~ h y ,

et on note y ' (g, h) = (I)*(K') + tF (K ' )

(off K ' est la configurat ion K dans laquelle la ddci- sion d ' i m p l a n t e r h concent ra teurs en g a dt6 diffdr~e d 'un in terval le d 'd tude)

c) soit alors l ' ensemble F ddfini pa r :

F = {(g, h)/y(g, h) < y'(g, h)}.

Si l ' ensemble F est non-vide, consid6rons g e t }i tels que y(g, h ) = Miu y(g, h) .

(y,h)@F [En effet, si y'(g, h) ~ y(g, h ) , il est plus dcono-

mique de repor te r l ' inves t i s sement de h concentra- teurs en g h l ' i n s t an t su ivant 0 + l . ]

�9 Si l ' ensemble pr@ddent F est vide ou si

T(Y, h) ~ O*(K~ + t F ( K ~

alors, si 0 < Tma. , on passe fi l ' i n s t an t su ivant en posant 0 = 0 + 1 et l'or~ re tourne en a).

[En effet cela signifie qu 'on ne peu t pas amdliorer le cofit du r6seau en imp lan t an t de nouveaux concen- t r a t eu r s ~ l ' i n s t an t 0].

Si l ' o n a 0 : Tmax, on s 'arr~te et pose K * = K Tmax .

�9 Si y(~, h) < O*(K ~ + i F ( K ~ alors on d6cide d ' ins ta l le r effect ivement un concen t ra teur en ~ l ' i n s t an t 0.

On posera doric :

K ~ K ~ I V t ~ 0 ,

et l 'on re tourne en b) pour examiner si d ' au t res eoneent ra teurs ne peuven t pas ~tre encore install~s

l ' i n s t an t 0.

6. A P P L I C A T I O N S E T I:t~ .SULTATS

6.1. G6n6ral isat ion de la f o r m u l a t i o n .

La formula t ion prdc~dente t ena i t compte de cer- ta ines hypotheses suppl~mentaires (H 3 et H 4 par exemple) pour simplifier l 'expos~.

Parc~ ~ St George=

28 A6

Bill6

28A6 Combourtill~

Javi~ 56A8

56A6

112A6

///~/ '/112 C6 224 C ~ SR 07

112C6 448C4 ~ S R 0 8

Autocommutateur ]

FIG. 5. - - R6seau de Foug~res h l'ann6e z6ro. (N) : nombre d'abonn6s raccord6s h l'ann6e l.

Support des efibles : A : a6rien, T : tranch6e, C : conduite. Ex : 56A 6, c~ble 56 paires a6rien de calibre 0,6 ram.

/ ~ fil ~ fil (direct),

/ ~ 1 concentrateur,

~ 2 concentrateurs.

7/10 AN~. TEL]~COMMUNIC., 3 1 , n ~ 7-8, 1976

236 J . -F . LEGROS. -- OPTIMALISATION DES INVESTISSEMENTS DANS LES RI~SEAUX TI~L]~PHONIQUES LOCAUX

E n rdal i t~ d a n s la p r a t i q u e on n ' u t i l i s e pa s u n seul

ca l ib re u n i f o r m d m e n t . P o u r en t e n i r c o m p t e , on p e u t

i n t r o d u i r e au n i v e a u de c h a q u e a rc de G u n m u l t i -

r iot (h t r o i s c o m p o s a n t e s d u n s le cas de r d s e a u x

f ran~ais ) . C h a q u e c o m p o s a n t e r e p r ~ s e n t e la d e m a n d e

en pa i r e s d u n s F u n des ca l ib res .

On p e n t auss i s ' a f f r a n c h i r de c e r t a i n e s a u t r e s h y p o -

t h e s e s ( p a r e x e m p l e n o n - p r o p o r t i o n n a l i t d du n o m b r e

de j o n c t i o n s r e l i a n t u n c o n c e n t r a t e u r au n o m b r e

d ' a b o n n d s r a c c o r d d s su r celui-ci) .

6.2. R6sultats.

Jav~ne (71~

/•3 Parc5

81

28A6 I

/ Combourtill6

Bill(~ 28A6 ~ ) (188 A

,56A6

56A6

~28 28 A6 A6

S t Georges ; (54)

L a m d t h o d e qu i v i e n t d ' e t r e exposde a ~td p ro -

g r a m m ~ e (*). L ' d v a l u a t i o n des cofl ts s u r les a rcs

(w 3.4) a dt~ a b o r d d e en e s s a y a n t de t c n i r c o m p t e

au m i e u x des p r o b l ~ m e s de s u p p o r t s e t de l eu r dvo-

l u t i o n lors d ' u n e s a t u r a t i o n .

U n c e r t a i n n o m b r e de c o n t r a i n t e s t e c h n i q u e s

d o i v e n t ~t re p r i ses en c o m p t e ( p a r e x e m p l e p o u r

c e r t a i n s s y s t ~ m e s de c o n c e n t r a t e u r s d ' a b o n n d s (MIC) ,

28 A6

6ili~ (12;

Parc~ ~ , , , , , St Ge36~rges (32)

Combourtille 28 A6 [ ~

56A6 28A6

56A6

112A6/ /56T6

/ 224 C4

S r

112 C6 -~/ C6

/ 224 C4

FIG. 6. - - E t a t du r~seau & l 'ann~e 1. On pose un 224 paires 0,4 mm en eonduite entre la SR07

et l ' autoeommutateur ; un 28 paires 0,6 mm a~rien, 56 paires 0,6 mm en traneh~e, 56 paires 0,6 mm en eonduite entre Bill~ et l ' autoeommutateur , un eoneentrateur & BillC

112A II,,T 6

/ / / / / / / / / / / /

/ 112C6

/ / 56 C6

224 C 4

224 C 4

FIG. 7. - - E t a t du rdseau h l 'annde 4. Oll pose un 28 paires 0,6 mm a~rien entre Bil]~ et le nceud

de jonction Bill~-Jav~ne ; un concentrateur h BillC

on es t l im i td en n o m b r e de j o n c t i o n s ( d e s s e r v a n t u n

c o n c e n t r a t e u r ) su r u n c&ble donnd) .

Le t a b l e a u I d o n n e des e x e m p l e s de r d s u l t a t s . A

t i t r e c o m p a r a t i f on in ( l ique le h o m b r e de v a r i a b l e s

du p r o b l ~ m e en h o m b r e s e n t i e r s d q u i v a l e n t . Les

t e m p s de ca lcn l d d p e n d e n t b e a n c o u p de l ' d t a t exis-

r a n t du rdseau e t de sa s t r u c t u r e .

L ' e x e m p l e 1 c o r r e s p o n d au r d s e a u de Foug~res ,

d o n t on p e u t s u i v r e l ' d v o l u t i o n c o r r e s p o n d a n t a u x

p r e m i e r e s a n n d e s de la pd r iode d ' d t u d e su r les f igures 5

h 9. A u d d p a r t , u n e p a r t i e du r d s e a u es t en adr ien , le

r e s t e en c o n d u i t e h 7 a lvdoles . Des e x t e n s i o n s se f o n t

en c&bles ou c o n c e n t r a t e u r s d ' a b o n n d s (*) (60 a b o n n d s

r a c c o r d d s p a r 13 j o n c t i o n s ) a u x a n n ~ e s 1, 4, 6 e t 7

p o u r s a t i s f a i r e la d e m a n d e en r a c c o r d e m e n t j u s q u ' h

l ' a n n ~ e 11. On p e u t vo i r qu ' i l n ' y a pus de n o u v e l

i n v e s t i s s e m e n t en c o n d u i t e r d s u l t a n t d ' u n b o n r e m -

p l i s sage des d i s p o n i b i l i t d s e x i s t a n t e s .

Les r d s u l t a t s o b t e n u s c o n f i r m e n t l ' i n t ~ r ~ t dcono-

m i q u e des t e c h n i q u e s de r a c c o r d e m e n t u t i l i s a n t des

c o n c e n t r a t e u r s de l ignes d ' a b o n u d s .

Su r les e x e m p l e s que n o u s a v o n s t r a i t~ s , l ' ~ c o n o m i e

c o n c e r n a n t les i n v e s t i s s e m e n t s d u n s la p a t t i e t r a n s p o r t

(*) Sur calculateur GE 6080. (*) De type TELIC.

ANN. T~L~COMMUNIC., 31, n ~ 7-8, 1976 8 / 1 0

J . - F . LEGROS. -- OPTIMALISATION D E S INVESTISS:EMENTS b A N S LES R E S E A U X TI~LEPHONIQUES LOCAUX 237

TABLEAU I

Exemple 1

Exemple 2

Exemple 3

Nombre de nceuds

8

15

22

Nombre de pdriodes

i3

15

15

Nombre d' 6valuation

Cu(f)

1 800

2 700

3 050

Economie par rapport h la solution

sans concentrateur

50 %

60 %

50 %

Temps processeur

(en 1/1 000 h)

46

85

95

Encombrement de la mdmoire

26 K

29 K

33 K

Nombre de variables du probl~me en nombres

entiers

4 200

9 000

13 200

Jav~ne ~ 1 ~ (04)

, & Parc~ S t Georges ~ (461 172)

Combourtill~

56A6 28 A 6 - - 28 A6

56 A6

1 56 T6

224 C4

/ / 2 2 4 0 4 + [ ~ sR 07 (736)

112C6~

//// 448C4 ~ [ ~ \

"~i 2=4c4 Lq~-' I E" 896C4- ] ~ l f ~

FIG. 8. - - Eta t du rdseau h l 'annde 6. On pose : un concentrateur h Saint-Georges; un coneen-

t ra teur h Bill~ ; un 448 paires 0,4 mm en conduite entre ]a SR 07 et la SR 08 ; un 896 paires 0,4 mm en conduite entre la SR 08 et l 'autocommutateur .

Jav(}ne (108)

! 28 A6

Bille (286)

56A6 28 A6 - - 28 A6

56 A6

Parce r ~ S t / ~ (83)

k (53) Georges

Combourtille 28 A6 > 2 5 )

k _

112T6

5616 112T6

/

/ S / / / /

112C6 -~

~ / SR 07 (809) 224 C4

224 C4 224 C4 448 C4

\

SR 08 (272) 224 C4

448 C4 l 896 C4 224 C4

2C6

Fro. 9. - - E t a t du r6seau h l 'ann6e 7. On pose un concentrateur & Jav~ne; un 112 paires 0,6 mm

en tranch~e, puis conduite, entre Bill~ et l 'autoeommutateur . Les besoins de la r~gion sont eouverts jusqu'& l 'annde 11.

es t de 50 % en m o y e n n e p a r r a p p o r t h u n e so lu t ion

tout cdble, c ' e s t - h - d i r e sans u t i l i s a t i o n de c o n e e n t r a -

t e u r s .

7 . G O N G L U S I O N

L a m 6 t h o d e qu i v i e n t d ' e t r e expos~e p e r m e t de

dd f in i r des p o l i t i q u e s de d 6 v e l o p p e m e n t o p t i m a l e s ou

quas i o p t i m a l e s p o u r la p a r t i e t r a n s p o r t des

r 6 s e a u x locaux . Les r 6 s u l t a t s o b t e n u s c o n f i r m e n t

l ' i n t d r ~ t 6 c o n o m i q u e des c o n c e n t r a t e u r s de l ignes

d ' a b o n n 6 s , c o n n u d e p u i s l o n g t e m p s des se rv ices

d ' e x p l o i t a t i o n . D u f a r de son c a r a c t 6 r e a u t o m a t i q u e

e t de sa r ap id i t 6 , elle p e r m e t d ' e x p l o r e r de f agon

b e a u c o u p p lus s y s t 6 m a t i q u e que p a r les m 6 t h o d e s

m a n u e l l e s l ' e n s e m b l e des s o l u t i o n s poss ib les et , p a r

c o n s 6 q u e n t , de rddu i re , d a n s le c a d r e des h y p o t h e s e s

r e t e n u e s , les cof l ts d ' i n v e s t i s s e m e n t .

I n d d p e n d a m m e n t de l ' a i d e i m m 6 d i a t e q u ' e l l e f o u r n i t

9 /10 Ar~. TELECOMMUNIC., 31, n ~ 7-8, |976

238 J . - F . LEGROS. -- O P T I M A L I S A T I O N DES I N V E S T I S S E M E N T S DANS LES RI~SEAUX TI~L]~PHONIQUES L O C A U X

pour le choix du volume et des dates des nouveaux invest issements , elle appor t e des 61dments de rdponses h u n cer ta in nombre de probl~mes technico-dcono- miques. Pa r exemple , elle peu t ~tre utilisde pour effectuer, sur un rdseau donnd, des comparaisons de cofit sur les diffdrents types de concent ra teurs de lignes d 'abonn~s proposals pa r les const ructeurs et conduire ainsi h une pol i t ique d 'u t i l i sa t ion cohdrente de tou te la gamme des mater ie ls ex is tan t actuel lement .

Pa r ailleurs, elle p e r m e t d 'envisager le t r a i t e m e n t sys tdmat ique d 'un grand nombre de rdseaux et pour ra donc ~tre utilisde pour va l ider des r~gles simples (bas~es pa r exemple sur des considdrat ions de cofit moyen) & i m p l a n t a t i o n de concentra teurs . Ces r6gles, appl icables in situ, dvi tera ient darts les cas les plus simples le recours h l ' o rd ina t eu r et la collecte de donndes nombreuses.

Manuscri l re~u le 29 avril 1976.

BIBLIOGRAPHIE

[1] GUENTHER (R. D.), DAUGHERTY (T. H.). Introduction of subscriber pair-gain systems (Utilisation de concer~- trateurs de lignes d'abonnds). International symposium

on subscriber loops and services. Proceedings, Ottawa, Canada (20-23 mai 1974), pp. 4.4.1 fi 5.

[2] WARREN KOONTZ (L. G.). Optimal temporary deferral of reinforcements in an exchange cable network (Diff6rement temporaire optimal des extensions dans un rdseau de c~bles), International symposium on sus- criber loops and services, Proceedings, Ottawa, Canada (20-23 mai 1974), pp. 1.5.1 ~ 6.

[3] DAMLAMIAN (Z. J . ) , DE BoYssoN (H.). Le programme Pentagone : un outil pour la planification de l 'auto- matisation des groupements tdldphoniques. Ann. Tdldcommunic., Fr. (1970), 25, n ~ 5-6, pp. 167-184.

[4] ROUSSEAUX (A.), LE RIDANT (J. V.). Considdrations technico-dconomiques sur l 'emploi de concentrateurs d'abonnds, International symposium on suscriber loops and services. Proceedings, Ottawa, Canada (20-23 mai 1974), pp. 3.4.1 h 13.

[5] BEnOE (C.). Graphes et hypergraphes, Dunod, Paris (1970), 502 p.

[6] RoY (B.). - - Algebre moderne et thdorie des graphes, Dunod, Paris (1970), t. II , 753 p.

[7] BELLMAN (R. E.). Dynamic programming (Program- mation dynamique), Princeton University Press, New- Jersey (1957), 3~2 p.

[8] MiNoux (M.). Recherche de la configuration optimale d'un rdseau de t61dcommunications, Ann. Tdldcom- munic., Fr. (1974), 29, n ~ I-2, pp. 25-42 et 29, no 3-4, pp. 139-171.

ANN. T~L~COMMUNIC., 31, n ~ 7-8, 1976 1 0 / 1 0