From: FAROUK AMINU <f.aminu_at_lancaster.ac.uk>

Date: Wed 25 Oct 2000 09:13:34 PM GMT

Message-ID: <Pine.GSO.4.21.0010252025500.27436-100000@unixb.lancs.ac.uk>

Date: Wed 25 Oct 2000 09:13:34 PM GMT

Message-ID: <Pine.GSO.4.21.0010252025500.27436-100000@unixb.lancs.ac.uk>

Dear Warwick, The problem is that of finding an Euler tour in a graph. Let's take the directed version for the moment. I have five nodes and seven links (Arcs), I have formulated the problem of determining the Euler tour and that of determining the shortest path in the graph. My main concern at the moment is to fromulate the problem to find exactly at which time each arc is traversed. The graph has two junctions (from node 3 to 4 or 3 to 5 and from node 5 to 2 or 5 to 1). I decided to number the arcs as arc1 to arc7. My reason for doing it this way is to generalise the model so as to accomodate all situations. Looking at the graph one can pick the arcs by eye and thus say that T1 is the time to traverse arc1 and T2 for arc2,.., T7 for arc7. arc1 is the starting arc and the finishing arc. One can write the total accumulated time as Tot #= t1 + t2 + t3 + t4 + t5 + t6 + t7, if the best way to traverse the arcs is starting with arc1 then arc2 up to arc7 in this sequence. It is evident that this would not work on computer as a general model. I thus decided to write the program in such a way that after traversing the first arc it is left to the optimisation function to chose which arc to traverse next, this will automatically set the directed sequence and decide at the junctions, which way to go. I made a pre-processing of the shortest times between the arcs, thus my Tij's are the times between the end of arc1 to the begining of arcj. Thus to go to arcj from arci, the time Tj should be Ti + Tij + tj. Thus T2 #= T1 + T12 + t2 if arc2 id traversed after arc1 and so on. >From my formulation, I used the element constraint to set the ti's, thus if A1 #= 2, then the value t2 will be assigned to C1, this is clear from the code: element(A1, [2, 3, 5, 5, 1, 2, 5], C1), element(A2, [2, 3, 5, 5, 1, 2, 5], C2), element(A3, [2, 3, 5, 5, 1, 2, 5], C3), element(A4, [2, 3, 5, 5, 1, 2, 5], C4), element(A5, [2, 3, 5, 5, 1, 2, 5], C5), element(A6, [2, 3, 5, 5, 1, 2, 5], C6), element(A7, [2, 3, 5, 5, 1, 2, 5], C7), The links in my graph are([1,2],[2,3],[3,4/3,5],[4,1],[5,2/5,1] with times 2,3,5/1,5,2/5). Links [1,2 = arc1], [2,3 = arc2], [3,4 = arc3], [4,1 = arc4], [3,5 =arc5], [5,2 =arc6], [5,1 = arc7]. The Tij's are added knowing that in determining an Euler tour an arc must be traversed exactly once (but after balancing some of the arcs are going to be duplicated which means you can traverse an arc at least once). I used the matrix to select the Tij's based on which arc is traversed after which and assigned the values to the Vi's. Thus, if arc2 is traversed after arc1 then, the subscript should be [row1,col2] which will pick T12, if arc7 is traversed after arc2, then the subscript is [row2,col7], which will pick T27 and so on. The sequence will thus be 2,7,...,1. I have constrained A7 to take value 1 so that arc1 is the final arc to traverse, the issue now is left to the solver to select from which arc to go back to arc1 (due to optimisation). There is no harm to this as the shortest paths solutions have taken care of coming back to arc1 through either arc7 or arc4 and is captured in the Tij's. It can be understood that if I have sequence like: 2,3,4,5,6,7,1 this means that I will go to arc2 from arc1, arc3 from arc2, arc4 from 3, 5 from 4, 6 from 5, 7 from 6 and 1 from 7. I used T8 to take care of the time to get back to arc1, but since the general formular takes into account the times to come from arci to arcj and the time to service arcj then I subtracted the time to service arc1 from the total because it is going to be counted twice. You can see in my code that I used T1 #= 2, then I continued accumulating the values of the Ti's. Now because of my sequence, I can write T2 #= T1 + V1 (which is T12 in this case) + C1 (which is the time to traverse arc2), T3 #= T2 + V2 (which is T23 in this case) + C2 (which is the time to traverse arc3), ...., T8 #= T7 + V7(which is T71 in this case) + C1( which is the time to service arc1) - 2 (which is the time to service arc1). This does what I want but you can see that it is not general. My aim is to constrain the Ti's to go with the values of the Ai's as in the above case. That is if the sequence is 4,5,6,1,3,7,2, the sequece for the Ti's should be T4,T5,T6,T1,T3,T7,T2. You can see that from my formulation the Ci's and the Vi's will not change, that is, T1 #= 2, T4 #= T1 + V1 (which is T14) + C1 (which is t4), T5 #= T4 + V2 (which is T45) + C2 (which is t5), T6 #= T5 + V3 (which is T56) + C3 (which is t6), T1 #= T6 + V4 (T61) + C4 (t1), T3 #= T1 + V5 (T13) + C5 (t3), T7 #= T3 + V6 (T37) + C6 (t7), T2 #= T7 + V7 (T72) + C7 (t2), T8 #= T2 - 2 (t1), You can make the above using if then else constraint, that is, if A1=2,A2 =3,A3=4,A4=5,A5=6,A6=7,A7=1, => T1=2,T2=T1+(COST1),T3=T2+COST2,...; A1=3,A2=4,A3=5,A4=6,A5=7,A6=2,A7=1 => T1 =2,T3=T1+COST1,T4=T3+COST2,...,T2=T7+COST6,T1=T2+COST7, and so on. But then this will be dependent on the number of arcs available and if the number is too large then it is going to be impossible to write all the constraints. My weakness is my inability to match the Ti's with values assigned to the Ai's during optimisation of the total time. Your earlier formulation constrain C1 to go with A1, C2 with A2 and C3 with A3, but my problem is to constrain T1 to go with value 1 it does not matter which of the Ai's is given that value. Thus T2 goes with value 2, T3 goes with value 3 and so on. Finally, T8 sums up the whole times and is then optimised. I am really grateful for your interest in this problem and hope this information sheds more light to the problem. Thanking you, with best regards, Farouk =============================================================================== UMARU FAROUK AMINU DEPARTMENT OF MANAGEMENT SCIENCE LANCASTER UNIVERSITY LANCASTER LA1 4YX U.K. +44 (0)1524 593865 (School) +44 (0)1524 383619 (Home) +44 (0)1524 844885 (Fax)Received on Wed Oct 25 22:15:49 2000

*
This archive was generated by hypermail 2.1.8
: Wed 16 Nov 2005 06:07:06 PM GMT GMT
*