Compendium of Lab. Assignments

For the following multicommodity network: 1--> 2 is required to transport g1 =400 flow units of commodity 1 and 3 --> 4 g2= 400 flow units of commodity 2. (t0 = per unit transportation cost ) -->EDIT .dat file b) Using the corresponding AMPL model and using solver Gurobi solve the problem (it is necessary first to edit the parameters file); c.1) No joint capacity limits at links. c.2) Modify the AMPL model so that joint capacity constratints enter into play. Define the value of these joint capacities so that the solution found in c.1) is no longer feasible at least at a link. c.3) For the solution with capacity constraints, print the solution and the dual variables N for the balance constraints and the dual variable for for the joint capacity constraint that has been added in c.2). Check that the following relationships hold : Ni= - , and c) Asume now that there is only a single commodity in the network and that it is necessary to transport 400 & 400 from 1,3 to 2,4 (no capacity limits) d.1) solve the problem using AMPL and compare the solutions with those obtained in c.1). a) Solve the problem coded in Mincost.mod with data in Mincost.dat using different solvers: MINOS, Gurobi and Cplex. Print the solution (flows on links) as well the values in Node for each of the solvers. Check the correspondence between the values in Node and the dual variables of the solution. Check the complementarity between reduced costs and solution flows. d) Assignment 0. Using AMPL and the KKT conditions Notes and recommendations to follow for Introductory Assignment 0 As regards to step a) the evaluation of dual variables and reduced costs for a simple MinCost problem is required. The example follows that of the class notes, summarized in this picture: In the previous example, dual variables appear calculated taking node 6 as root node (i.e. that with a 0 dual variable). If node 4 had been taken as root node, the dual variables would have been: When solving the problem using AMPL with Gurobi as solver: ampl: model mincost.mod; ampl: data mincost.dat; ampl: ampl: option solver gurobi; ampl: solve; Gurobi 9.1.1: optimal solution; objective 73 1 simplex iterations ampl: display Nodo; # dual v. for Nodo constraints are displayed Nodo [*] := C1 2 C2 4 C3 5 C4 0 C5 5 C6 -3 ; Notice that the dual variables reported are those in the previous figure, but changed in sign! This is SOLVER dependent. Notice also that the dual variables are those corresponding to the basic solution (red links in the figure). In order to know which flows are basic and which are non-basic, display the .sstatus suffix: ampl: display enlace.sstatus; enlace.sstatus := C1 C2 bas # basic variable C2 C3 bas C2 C4 low # non-basic variable C2 C5 bas C2 C6 low C3 C4 low C4 C6 low C5 C4 low C6 C1 bas C6 C4 bas ; AMPL displays those variables in the basic set IB with the label “bas”. Those in IN appear with “low” Sometimes, after solving a problem some variables appear marked as “none”. In this case the dual variables associated to nodes for links marked with “none” may be not calculated by the SOLVER. Then, previously to use dual variables in any calculation: a) The user must know whether or not the SOLVER changes its sign. Since only differences in dual variables may be required, which node is taken as root node is usually not relevant. b) It must be known whether a complete identification of basic and non-basic indexes has been done by the SOLVER, i.e. no flow appears marked with .sstatus of “none” As an exercise change link (5,4) by its opposite (4,5) also with a cost of 20 and run again AMPL for solving the problem with Gurobi. Then, display the dual variables and the .sstatus of the variable enlace and notice that the negative of dual variable of node 5 has an error. ampl: display Nodo; Nodo [*] := C1 5 C2 7 C3 8 C4 3 C5 0 C6 0 ; The same (although with different values) would occur with CPLEX and MINOS ampl: display enlace.sstatus; enlace.sstatus := C1 C2 bas C2 C3 bas C2 C4 low C2 C5 none C2 C6 low C3 C4 low C4 C5 none C4 C6 low C6 C1 bas C6 C4 bas ; As regards to step b) In order to display a floating point value (for instance, the objective function value Vg) with more figures use: ampl: printf " funcion objetivo f=%f \n",Vg; funcion objetivo f=1232.000000 As regards to step c) It is expected that imposing a capacity limitation on one or more links, the rerouting of flows is forced so that the objective function must necessarily increase. It may happen however that despite the rerouting, the objective function value does not decrease, but remains the same. (In order to make sure that the objective function value changes, it is better to use the ‘printf’ command as shown in order to unveil small changes that would otherwise, remain hidden with the ‘display’ command). If the objective function does not decrease, even though the upper bounds have been strengthened, then the dual variable for the corresponding upper bound constraint is zero. Although it has not been stated in the course, it is known that the dual variables of a constraint of the type x <= u1 have a dual variable y1 for the value u1 of the right hand side given by: y1= - lim u2  u1 (f(u2) – f(u1))/(u2-u1) being f(u1) the objective function value of the optimization problem when the right hand side of the constraint is u1. Example. Assume that in the Mincm2.mod model the following upper bound constraints on flows have been added: subject to capac{(i,j) in links}: v[i,j] <= gamma[i,j]; and that: a) bounds 100 on links (5,6) and (8,6) have been added (it can be shown that they are effective and that rerouting takes place). Check that objective function is 1232, just as when no upper bounds were added. b) a bound of 100 is added on link (5,9) instead. Now objective function increases to 1412. Displaying the dual variables the following is obtained: Gurobi 9.1.1: optimal solution; objective 1232 6 simplex iterations ampl: printf " funcion objetivo f=%f \n",Vg; funcion objetivo f=1232.000000 ampl: display capac; capac := 1 5 0 3 8 0 5 6 0 5 8 0 5 9 0 6 7 0 7 2 0 7 9 0 8 5 0 8 6 0 9 4 0 9 7 0 ; CASE A) ampl: display capac; capac := 1 5 0 3 8 0 5 6 0 5 8 0 5 9 -0.6 #(Notice that (1412-1232)/300 = 0.6 ) 6 7 0 7 2 0 7 9 0 8 5 0 8 6 0 9 4 0 9 7 0 ; CASE B) Notice that dual variables are given changed in sign !! Assignment 1. Introduction. Network Design. Consider the problem consisting in deciding which links in a transportation or in a data communications network are necessary by balancing investment costs and reductions in exploitation costs. Assume that initially the network presentes a configuration given by G′= (N, A′) and that there exists the possibility of increasing the number of network links taking the candidate links from a pre-specified set ˆ A, so that the final network may become G= (N, A) with A=A′∪ˆ A. The question is then which links in ˆ Aare suitable to be added so that the total cost (investment+exploitation) is the minimum possible. The cost will be made up by two components: a) on the one hand, adding each new link a∈ˆ Apresents a fix cost fa(purchase+instalation). b) when in service, a link a∈ˆ Awill have a cost per each unit of flow crossing that link during a given amortization period. Assume is addition, that these cost per unit depend on the starting origin (origin) of the trip. In this way, if Kdenotes the set of origins in the network, the cost throughout the amortization period can be formulated as: total cost =∑ ℓ∈K∑ a∈A cℓ axℓ a+∑ a∈ˆ A faya being ya= 1 if link a∈ˆ Ais added to the network and 0 otherwise. The problem will be now formulated using matrix notation. Let Bthe node-link incidence matrix of the network, xℓthe vector of flows originating at ℓ∈K. Assume that gℓis the total flow outgoing from origin ℓ∈Kand that if D(ℓ) is the set of destinations corresponding to origin ℓ, then gℓ,j is the flow arriving at j∈D(ℓ), in such a way that: gℓ=∑ j∈D(ℓ) gℓ,j Let vector tℓhave so many components as nodes in the network. Component tℓ icorresponding to node i∈Nis: tℓ i=−gℓ,i if i=ℓitℓ i=gℓif node iis precisely the origin ℓ. Then xℓobey to the following relationships: Bxℓ=tℓ, xℓ≥0 (See a complete example in the ending page). The problem of network design can be formulated : Min x,y ∑ℓ∈Kcℓ⊤xℓ+f⊤y (A)Bxℓ=tℓ, ℓ ∈K (B)xℓ a≤ρ ya, ℓ ∈K, a ∈ˆ A (C)xℓ≥0 y∈ {0,1}|ˆ A| (1) and in scalar notation: Min x,y ∑ℓ∈K∑a∈Acℓ axℓ a+∑a∈ˆ Afaya ∑r∈I(i)xℓ r,i −∑s∈E(i)xℓ i,s =tℓ i, i ∈N, ℓ ∈K xℓ a≤ρ ya, a ∈ˆ A, ℓ ∈K xℓ a≥0, a ∈A, ℓ ∈K ya∈ {0,1}, a ∈ˆ A ASSIGNMENT 1. The network design and fleet dimensioning problem The following design problem on a multicommodity network flow problem must be solved. m´ın x,w,N,y α(gN +f>y) + (1 −α)X `∈{O,D} c`>x`(1) s.t. :Bx`=p`, ` ∈ {O, D}(2) x`≥0 (3) Bw = 0 (w≥0) (4) X `∈{O,D} x` ≤ Kw(5) t>w≤N(6) X `∈{O,D} x` i,j ≤Myi,j,(i, j)∈ˆ A(7) wi,j ≤Myi,j,(i, j)∈ˆ A(8) yi,j ∈ {0,1}, N ∈Z+(9) The problem consists in finding which of the links (i, j) ∈ Aˆ must be built and how many vehicles must be purchased (or rented) in order to minimize a given objective function. Below a sample network is shown where graphically, the set of links in Aˆ appears in red. Node O will play the role of origin of flows of products of type 1 and node D will play the role of destination for products of type 2. Nodes in double color (red-blue) will play the role of destinations of product 1 (20 units of flow of product 1 must be delivered at each red-blue node) and origin of product 2 (20 units of flow of product 2 originate at each red-blue node). Each student will have its own instance in a graphic file specifying the values for parameters fand c(investment and costs per link and transportation cost of unit of product flow. For simplicity, consider that both product types have the sqame transportation cost: cO ij =cD ij ). Each link has a travel time given by tij = 750((xi−xj)2+(yi−yj)2)1 2. Consider transportation vehicles with a unit cost that keep this relationship with investment costs: g= 0,1×m´ın (i,j)∈ˆ A {fij} 1 1. Implement i n the AMPL model provided (netdes.mod) the appropriate additional constraints, variables and parameters i n order to run the model. Check your . dat file accordingly to your network. 2. Solve the problem when no additional link is added to the network (i.e., y = 0) and report the solution. 3. Solve the problem when all the candidate links have been added to the network and report the solution. 4. Solve i nitially the problem as f ormulated previously by simply using the netdes.mod file (complete i t properly) and report the solution. 5. Affect both terms of the objective f unction (investments, exploitation costs) by a parameter α, 0 ≤ α ≤ 1. Carry out a mutiobjective analysis of the problem by obtaining the corresponding Pareto optimality f rontier. - Obtain the trade-off table f or both objective f unctions - Plot the Pareto optimal frontier for 30 points of the a parameter. 6. Consider the case with y = 1 and leave the decision variables out of the objective function - Report f or the values a = 0 and a = 1, the flows of empty vehicles running on the network l inks. (Set a suitable value for transportation vehicles capacity K) 2 ASSIGNMENT 2. Optimization Models for Transport (MOT) Implement the diagonalization method for the network that will be indicated to you (NET 1, 2 or 3). Use the files .mod and .run contained in the file asass.zip and edit them conveniently adding the corresponding definitions of additional variables, parameters etc. if so required To illustrate the data structures following network example will be provided with g1= g1,2 =400 viatges, g2=g3,4= 400 trips. In the arcs of the network the following function VDF will apply:         − += ∑∈),(),( , , ,, 1)( jiPRIOnm nm ji jiji v c v t v d α where PRIO (i, j) is the set of arcs that have priority over the (i, j), α = 30 c = 1000. At each node with at least one inceident arc (i, j), choose by yourselves the a set PRIO(i, j) that have priority over the (i, j), with 0 <| PRIO (i, j) | <3. Suitably alter the parameters c and α so that, at least 5 iterations are made by the method of diagonalization. In the report, display for each iteration a) the iteration number, b) the relative gap value for the current iteration at v(k given by: - s(v(k)T(u(k - v(k )/ s(v(k)Tv(k, where u(k are the link flows obtained by loading the o-d matrix on the shortest paths for each o-d pair with costs on the network links given by the link-cost vector s(v(k). Report also the solution flows at the final iteration and upload in ATENEA the AMPL files (.run, .mod, .dat) used in the exercise. Diagonalization method: NET 4 Orígens Destinacions 2 3 4 5 1 100 300 50 100 6 150 100 600 200 2 8 1 7 12 6 9 3 10 4 11 5 15 14 13 NET 5 Orígens Destinacions 5 6 7 8 2 400 1000 600 2500 3 - 200 0 150 1 9 6 10 13 14 21 22 5 8 7 2 4 11 17 18 12 15 16 20 19 3 NET 6 Orígens Destinacions 5 6 7 8 2 400 700 350 25 3 - 200 4000 150 1 9 6 10 13 14 21 22 5 8 7 2 4 11 17 18 12 15 16 20 19 3 NET 7 Orígens Destinacions 2 3 4 5 1 190 - 500 100 6 150 400 - 200 2 8 1 7 12 6 9 3 10 4 11 5 15 14 13 NET 8 Orígens Destinacions 3 4 1 800 350 2 620 350 1 5 6 12 2 7 3 10 9 8 11 13 4 NET 9 Orígens Destinacions 3 4 1 480 1250 2 1600 900 1 5 6 12 2 7 3 10 9 8 11 13 4 NET 10 Orígens Destinacions 3 4 1 325 1274 2 617 1630 1 5 6 12 2 7 3 10 9 8 11 13 4 ASSIGNMENT 3. Pigou taxes on markets The foundation of network analysis from the point of view of spatial market equilibrium can be found in the center of virtual courses and seminars for supernets: http://supernet.isenberg.umass.edu/ Goal programming can be used to formulate spatial market equilibrium problems in which there is an external intervention (usually an administration) to establish subsidies or otherwise, production taxes on certain firms so that this production may fit, as much as possible, to some given and convenient quantities ɵ, which are considered as goals to achieve. The aim is that, in the event that a product generates "negative externalities", a contribution might be payed by the firm (taxes on production), which is fixed by the administration to alleviate the effects of these externalities. Typical examples are taxes on alcoholic beverages. Then, these taxes affect the final price for the consumers, resulting in lower consumption. Equally, the same policy may be applied in the case of activities that generate pollutants or greenhouse gases etc. This is known as Pigou’s effect. Conversely, in the case of beneficial products, if companies can not produce sufficient quantities at a price affordable enough, then the production subsidies help the producers to bring in the markets larger quantities of product at lower prices, thus encouraging consumption. The model formulated in the next page is an extension of the spatial market equilibrium model and reproduces Pigou’s effect. In the model, now weights Mi or Ni appear, as fixed costs for flow variables σ+ and σ- . These σ+, σrepresent the amounts of excess/lack of production as regards to objective ɵi. All other variables have the same meaning that in the case of elastic demand model already described. Notice that the 0 node now receives an injection that balances the total flows on the network. Usually the difference will be positive as the sum of upper bounds on consumption will exceed the sum of the production targets. Remember that in the market equilibrium model, the difference between multipliers corresponding to market nodes and the source node 0 has the physical meaning of minimum selling prices at that markets (Accumulated production + transport). In this case, the difference between multipliers of additional nodes and the origin or 0 node has the meaning of increase / decrease of the production cost caused by the tax / subsidy respectively. If νi is this increase / decrease of cost of production at factory i, then it is verified that: - Ni ≤ νi ≤ Mi, being Ni, Mi weights on variables σ+ and σin the objective function. These weights must be set so that goals ɵi are approximately achieved. The spatial market’s equilibrium problem with taxes/subsidies Tasks in the assignment An AMPL model that has been provided to you reproduces the problem of spatial price equilibrium of markets with elastic demand, so far discussed in class of theory and is described in the following slides. The data file corresponds with two centres of production and three markets. 0) Load in the AMPL system the model and the data (in .dat file) that has been provided to you and check that the model executes properly. Report this solution (flow variables, objective function value and final prices at markets). 1) Add one more market to the file of data and another production center, updating accordingly the sets MERC, ARCTR, ARCH_EXC and the files of parameters, CTRANS, a, b, alfa, beta, dtotal, dmax. Report this solution (flow variables, objective function value and final prices at markets). 2) Load the new set of data and resolve the problem. Report its solution, describing which centres sell to which markets and the prices at the markets. 3) Add a limitation of capacity in some link xij corresponding to a transportation channel actively used to feed a market. (updating the .mod and .dat accordingly). Check that the limitation of capacity actually will be active taking into account the solution given in step 2) 4) Eliminate any upper bound on the flows on the model’s definition set in previous step 3). Modify conveniently the AMPL files provided to you for reproducing the market equilibrium model in order to reproduce the taxes / subsidies model on the production described previously. Fix goal values of production ɵi different from the ones obtained for the elastic demand market equilibrium in step 2). Then try to solve the model with different values of the weights Ni, Mi and report the solutions obtained (flows and final prices at markets) As a checking of the proper functioning of the model, an example with three production centers to five consumption centers will be solved (set by yourself the required parameter values). It is recommended to properly expand the data set attached to the case market equilibrium with inelastic demand. In each case the following must be reported: -Flow solution on the links of the model, the value of the cost functions and final prices at markets. -Extra productions σ+ and σdue to Subsidies/taxes (variables νi) and subsidies/taxes νi -Prices of products in the markets and production costs. 4/ 9 Single Depot Vehicle Scheduling Each service of a line is a task to be performed. In the graph of tasks, a task will be a link (i, j) σi, σj=scheduled starting and ending clock time of the task (i, j) θi=a variable for actual clock time for node ion the graph of tasks. A tolerance may be fixed to accommodate scheduled time σiand θi: σi−≤θi≤σi+ τij = time required to carry out task (i, j). It can be a fixed parameter or a variable subject to upper and lower bounds: τij ≤τij ≤ˆτij, v= number of vehicles (buses) Given the set of scheduled times σj, only tasks complying with the consistency condition: ˆτij ≤σj−σi−2,j6= 0, make sense to exist in the graph of tasks. 5/ 9 Single Depot Vehicle Scheduling and recourse constraints - Typically, a family of recourse constraints will apply for the clock time variables θjat nodes j6= 0 in the graph of tasks. - Assuming unlimited autonomy of the buses, the solution would be made up by vsubtours, each one of them for each bus. - If autonomy of the units is limited, because of fuel, battery, driving time or other reason, each of these reasons gives rise to a new family of recourse constraints. The charging point will be always node 0. - The charging time, when non-negligible, will added to the trip time of tasks (0, i) - Assume BatteryT ime as the maximum autonomy time for electrical buses. Then, new variables γjare needed. -γj=battery time consumed by the unit when reaching node j. Notice that in general γj6=σj - Now fleet size ≤v=number of total round trips made by bus units to the depot (node 0). 6/ 9 Subsequences of tasks with recourse constraints Min x,v,θ,τ,γ X (i,j)∈A cijxij +ρv X j∈E[i] xij =X j∈I[i] xji i= 0,1,2, ...n X j∈E[0] x0j≤v, X j∈E[i] xij = 1 i= 1,2, ...n RC.1θj≥θi+τij −M(1 −xij),(i, j)∈A, j 6= 0 σj−≤θj≤σj+, j 6= 0, τij ≤τij ≤ˆτij,(i, j)∈A θ0= 0, RC.2γj≥γi+τij −M(1 −xij),(i, j)∈A, j 6= 0 γk+τk0≤BatteryT ime −ε, (k, 0) ∈A γ0= 0, xij ∈ {0,1} 7/ 9 Single Depot Vehicle + Driver Scheduling. Formulation as IP Drivers can only be on duty a maximum of ˆ θminutes on duty. G= (N, A)graph for buses; GD= (ND, AD)graph for drivers. Two Cases: 1Driver replacement can take place only at the end of the line service. 2Drives replament can take place at any bus stop. -τij =tij +dj−ai≥0,∀(i, j)∈A 8/ 9 Single Depot Vehicle + Driver Scheduling. Formulation as IP MinxX (i,j)∈A cijxij +X i∈N c0ix0i+X (i,j)∈AD γijyij +X i∈ND γ0iy0i X i∈N x0i≤vX i∈ND y0i≤sd X j∈E[i] xij =X j∈I[i] xji, i ∈NX j∈ED[i] yij =X j∈ID[i] yji, i ∈ND X j∈E[i] xij = 1, i ∈NX j∈ED[i] yij = 1 i∈ND θj≥θi+τij +M(1 −yij), j 6= 0,∀(i, j)∈AD, θ0= 0 xij ≤yij,∀(i, j)∈AD∩A, i, j, 6= 0 0≤θj≤ˆ θ, j ∈ND xij, yij ∈ {0,1} 9/ 9 Multiple Depot Vehicle Scheduling. Formulation as IP Each depot has its own graph Gk= (Nk, Ak) Nk=N∪ {n+k}, Ak=A∪ {{n+k} × N}∪{N× {n+k}} MinxX k X (i,j)∈AN cijxk ij +X k X i∈Nk c0ixk 0i X j∈N xk n+k,j ≤vkk∈K X i∈Nk xk ij =X i∈Nk xk ji 0≤i≤n X k X j∈Nk xk ij = 1 i∈N xk ij ∈ {0,1} If costs cn+k,j =cn+k0,j,∀k, k0, then the problem is polynomial and reduces to a single commodity network flow. As before, aj< di+tij −→ xk ij = 0 Assignment 4. Case Study concerningtransitmodels 1) Solveatransitassignmentproblem for the following network: Prof. Esteve Codina Example: 1234 amin 7 min b min 4 min 4 min Line Frequency (uncongested): X each hour Line Frequency (uncongested): Y each hour Line Frequency (uncongested): Z each hour Assumeademanduniformly distributed on time: e*1000tripsfrom1to4ande*400tripsfrom2to4. Valuesforwill be X=6s/h, Y=4s/h,Z=6s/h,a=24min,b=5min. e is an augmenting factor of the demand, initially taken as e=1, although the student may change it in case of difficulties. 1) Write a report in which you show the solution of the previous problem by running the AMPL material provided (trass.mod) showing: a) the objective function value, b) link flows per destination and total link flows, c) the values for the w variables in the Spiess' LP model, d) the o-d trip times on your network 2) Solve for the lines previously specified, a vehicle scheduling problem over a time horizon of H=3 hours. Assume that electrical buses will be used with an autonomy of h=2 hours and a constant recharging time of r=15min and that units always recharge on depot if they return to it. 3) Report (<=15 pages) : a) The code developed for implementing the scheduling model. b) Accordingly to the frequencies specified for your case, set the different services that have to be run on each line, along with its starting time, ending time and possible connections between services accordingly to the returning times. These will be assumed (in min) 4-->1 = 30, 4-->2 =25, 3-->1 = 15, 3-->2 = 15min in all cases. c) The solutions obtained specifying: b.1) the total number of buses needed to carry out all the services. b.2) the services assigned to each bus. d) Assuming that buses can have a capacity of 30, 45, 60, 75 or 100 passengers choose the appropriate bus capacity. 1 A worked example for the Spiess' Algorithm (25, ∞) (7, ∞)(6,∞) (4, ∞)(4, ∞) (0,1/6) (0,1/6) (0, ∞) (0, ∞)(0,1/6) (0,1/15) 1234 (0, ∞) (10, ∞) (0, 1/3) Headway=12min; av.waiting time=6 min = 1/10 h eff.freq=1/6 min-1 10 rides each our Headway=12min; av.waiting time=6 min = 1/10 h eff.freq=1/6 min-1 10 rides each our Headway=30min; av.waiting time=15 min = 1/4 h eff.freq=1/15 min-1 4 rides each our Headway=6min; av.waiting time=3 min = 1/20 h eff.freq=1/3 min-1 20 rides each our 2 Example f=0 u=∞ f=0 u=∞ f=0 u=∞ f=0 u=∞ f=0 u=∞ (25,1/6) (10,1/3) (0,1/6) (0,∞)(0,1/15)(0,∞) f=0 u= 0  H. Spiess and M. Florian, "Optimal strategies: a new assignment model for transit networks", Transportation Research Part B 23 (2) 83-102 (1989) S Ā A\(SUĀ) Step 0 3 Example f=0 u=∞ f=0 u=∞ f=∞ u=4 f=0 u=∞ f=0 u=∞ (25,1/6) (0,1/6) (0,∞)(0,1/15)(0,∞) f=0 u= 0  2 (10,1/3) S Ā A\(SUĀ) Step 1 10 Example f=0 u=∞ f= ∞ u= 35/2 f=0 u=4 f=7/30 u=19’07 f=1/15 u=19 (25,1/6) (0,1/6) (0,∞)(0,1/15)(0,∞) f=0 u= 0  (10,1/3) f=2/5 u=23/2 f=1/15 u=23 S Ā A\(SUĀ) Step 8 (Null Step) 11 Example f=1/6 u=61/2 f= ∞ u= 35/2 f=∞ u=4 f=7/30 u=19’07 f=1/15 u=19 (25,1/6) (0,1/6) (0,∞)(0,1/15)(0,∞) f=0 u= 0  (10,1/3) f=2/5 u=23/2 f=1/15 u=23 f=0 u=∞ S Ā A\(SUĀ) Step 9 12 Example f=1/3 u=111/4 f= ∞ u= 35/2 f=∞ u=4 f=7/30 u=19’07 f=1/15 u=19 (25,1/6) (0,1/6) (0,∞)(0,1/15)(0,∞) f=0 u= 0  (10,1/3) f=2/5 u=23/2 f=1/15 u=23 f=0 u=∞ S Ā A\(SUĀ) Step 10 13 Flows for the optimal strategy • Line 1 • Line 2 • Line 3 • Line 4 Optimal strategy - Expected travel time 27.75 min V=.5 V=.5 V=0 V=.42 V=.5 V=.5