3.7.144. Metro

A constraint that can be used for modelling the metro problem, i.e.,Β finding the shortest distance from a given metro station to all other stations of the network.

Given an undirected graph G=(V,E), with a non -negative distance attached to each edge of E, a conjunction of πš•πšŽπšš_𝚌𝚜𝚝 constraints was used by H.Β Simonis in order to illustrate how propagation for such a conjunction simulates a naΓ―ve version of Dijsktra algorithm for computing the shortest distance from a given vertex v s of V to all other vertices. The potential source of inefficiency comes from the fact that, depending on the scheduling policy of the underlying constraint engine, an inequality constraint can be reconsidered several times before reaching the fixed point. The problem was modelled in the following way:

  • To each vertex v i ∈V we associate a distance variable D i , which represents the domain range of the distance between vertex v i and vertex v s .

  • To each edge (v i ,v j )∈E we impose two inequality constraints D i ≀D j +d i,j and D j ≀D i +d i,j , where d i,j corresponds to the distance attached to edge (v i ,v j ). This restricts the maximum difference between the distances variables associated with the two extremities of edge (v i ,v j ).

  • Finally, we set the distance variable attached to vertex v s to 0. Propagating the inequalities constraints by using arc-consistency enforces the maximum value of each distance variable D i to be equal to the shortest distance from vertex v i to v s when the fixed point is reached.

Figure 3.7.32. A metro map composed of four lines (a blue, a pink, a green and a yellow line) and the corresponding minimum and maximum values of the distance variables attached to each station, under the assumptions (1)Β that the distance attached to each connection is equal to 1 and (2)Β that we compute the shortest path from stationΒ i (in red); the font size used for displaying the bounds of a distance variable is inversely proportional to the length of the shortest path to station i.
ctrs/leq_cst1

FigureΒ 3.7.32 illustrates this problem on a metro map composed of four lines and 18 stations respectively labelled by a, b, ..., r. Its assumes that the distance associated with each connection is equal to 1. The figure displays the status (i.e.,Β the minimum and maximum values) of the distance variables under the assumption that we want to compute the shortest path from station i. The inequalities constraints between the distance variables D a ,D b ,...,D r corresponding to this metro map are:

  • (constraints attached to the connections of the blue metro line)

    • Β Β D a ≀D b +1,Β Β D b ≀D a +1,

    • Β Β D b ≀D c +1,Β Β D c ≀D b +1,

    • Β Β D c ≀D d +1,Β Β D d ≀D c +1,

    • Β Β D d ≀D e +1,Β Β D e ≀D d +1,

    • Β Β D e ≀D f +1,Β Β D f ≀D e +1,

    • Β Β D f ≀D a +1,Β Β D a ≀D f +1.

  • (constraints attached to the connections of the pink metro line)

    • Β Β D g ≀D f +1,Β Β D f ≀D g +1,

    • Β Β D f ≀D h +1,Β Β D h ≀D f +1,

    • Β Β D h ≀D c +1,Β Β D c ≀D h +1,

    • Β Β D c ≀D i +1,Β Β D i ≀D c +1,

    • Β Β D i ≀D j +1,Β Β D j ≀D i +1.

  • (constraints attached to the connections of the green metro line)

    • Β Β D p ≀D q +1,Β Β D q ≀D p +1,

    • Β Β D q ≀D r +1,Β Β D r ≀D q +1,

    • Β Β D r ≀D a +1,Β Β D a ≀D r +1,

    • Β Β D a ≀D h +1,Β Β D h ≀D a +1,

    • Β Β D h ≀D d +1,Β Β D d ≀D h +1.

  • (constraints attached to the connections of the yellow metro line)

    • Β Β D k ≀D l +1,Β Β D l ≀D k +1,

    • Β Β D l ≀D m +1,Β Β D m ≀D l +1,

    • Β Β D m ≀D a +1,Β Β D a ≀D m +1,

    • Β Β D a ≀D n +1,Β Β D n ≀D a +1,

    • Β Β D n ≀D o +1,Β Β D o ≀D n +1,

    • Β Β D o ≀D i +1,Β Β D i ≀D o +1.