Modelisation et Recherche Operationnelle : Reseaux d'ecarts

Exemple de la methode du chemin amplificateur de flot

Problême fictif

Les villages de Salmbach et de Mothern fête le jumelage de leurs 2 villages. La fête a lieu à Mothern et on s'attend à voir beaucoup de monde sur les routes. Pour éviter des embouteillages, le maire de Salmbach donne des conseils d'itinéraires différents à suivre à chaque habitant. Il faut également minimiser le coût du parcours global.

Ici la capacité est la vitesse conseillée. Le coût est la distance. 

[mist@savage carte]$ ls
carte2.grh  carte.dia  carte.dia~  carte.grh  carte.png
[mist@savage carte]$ display carte.png

[mist@savage carte]$ cat carte2.grh
 1  <?xml version="1.0" encoding="UTF-8"?>
 2  <graph xmlns:dia="http://www.lysator.liu.se/~alla/dia/">
 3    <vertex id="Lauterbourg" x="10" y="5"/>
 4    <vertex id="Scheibenhard" x="-2" y="0"/>
 5    <vertex id="SINK" x="9" y="14"/>
 6    <vertex id="Munchausen" x="5" y="22"/>
 7    <arc from="Lauterbourg" to="SINK" flow="0" capacity="90" cost="7"/>
 8    <arc from="Munchausen" to="SINK" flow="0" capacity="90" cost="3"/>
 9    <arc from="J1" to="Lauterbourg" flow="0" capacity="90" cost="1"/>
10    <vertex id="Neewiller" x="-6" y="10"/>
11    <arc from="Neewiller" to="SINK" flow="0" capacity="70" cost="4"/>
12    <vertex id="J1" x="4" y="6"/>
13    <arc from="Scheibenhard" to="J1" flow="0" capacity="90" cost="2"/>
14    <arc from="Wintzenbach" to="Neewiller" flow="0" capacity="90" cost="4"/>
15    <vertex id="Wintzenbach" x="-9.5145" y="19.4855"/>
16    <vertex id="Oberlauterbach" x="-21.4169" y="14.5831"/>
17    <arc from="Oberlauterbach" to="Wintzenbach" flow="0" capacity="80" cost="5"/>
18    <vertex id="Niderlauterbach" x="-16.0213" y="2.97871"/>
19    <arc from="Niderlauterbach" to="Neewiller" flow="0" capacity="80" cost="3"/>
20    <arc from="Niderlauterbach" to="Scheibenhard" flow="0" capacity="90" cost="3"/>
21    <arc from="Schaffouse" to="Wintzenbach" flow="0" capacity="90" cost="4"/>
22    <vertex id="Schaffouse" x="-15" y="27"/>
23    <vertex id="Seltz" x="-8" y="31"/>
24    <arc from="Seltz" to="Munchausen" flow="0" capacity="90" cost="5"/>
25    <arc from="Schaffouse" to="Seltz" flow="0" capacity="90" cost="2"/>
26    <vertex id="SOURCE" x="-26" y="6"/>
27    <arc from="SOURCE" to="Niderlauterbach" flow="0" capacity="90" cost="3"/>
28    <arc from="SOURCE" to="Oberlauterbach" flow="0" capacity="90" cost="3"/>
29    <arc from="Wintzenbach" to="Munchausen" flow="0" capacity="70" cost="3"/>
30    <arc from="Seltz" to="J1" flow="0" capacity="130" cost="10"/>
31    <arc from="Oberlauterbach" to="J2" flow="0" capacity="90" cost="5"/>
32    <vertex id="J2" x="-24" y="25"/>
33    <arc from="J2" to="Schaffouse" flow="0" capacity="90" cost="5"/>
34  </graph>
[mist@savage carte]$ python ../bff.py carte2.grh out.grh
[..]
finding way
Way :
->  Neewiller
->  Niderlauterbach
->  SOURCE
Continuing ...
exhibFoundWay
[..]
[..]
[mist@savage carte]$ cp ../grh2dia.xsl .
[mist@savage carte]$ ../serial.sh
                                                                                                                                                  
** (process:3217): WARNING **: No attribute type ((nil)) or no data((nil)) in this attribute
serial_0.dia --> serial_0.png
 
** (process:3222): WARNING **: No attribute type ((nil)) or no data((nil)) in this attribute
serial_1.dia --> serial_1.png
 
** (process:3227): WARNING **: No attribute type ((nil)) or no data((nil)) in this attribute
serial_2.dia --> serial_2.png
 
** (process:3232): WARNING **: No attribute type ((nil)) or no data((nil)) in this attribute
serial_3.dia --> serial_3.png
 
** (process:3237): WARNING **: No attribute type ((nil)) or no data((nil)) in this attribute
serial_4.dia --> serial_4.png
 
** (process:3242): WARNING **: No attribute type ((nil)) or no data((nil)) in this attribute
serial_5.dia --> serial_5.png
[mist@savage carte]$

Le problême de routage résolu



Résultats

Itinéraires à utiliser par les participants

Commentaire