Question 1

IEOR 4601 Assignment 9

1. In class we considered a network problem with two resources and three itineraries, with two fares per itinerary and illustrated a variety of heuristics for that problem. Here we will consider an expanded model with the same three itineraries but with five fares per itinerary. Itinerary one, consumes one unit of resource one and has five fares: 185, 160, 150, 130, 100. Itinerary two, consumes one unit of resource two and has five fares: 130, 110, 95, 80, 75. Itinerary three, consumes one unit of each resource and has five fares: 260, 240, 220, 190, 170. Using the single index model the incidence matrix A is given by

A = (

1 1 1 1 1 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1

) and the fare vector by

p = ( 185 160 150 130 100 130 110 95 80 75 260 240 220 190 170 ) .

Assume a discrete time model with T = 1, 000 periods and time varying arrival rates given by

λt = ( .00 .00 .015 .036 .054 .00 .00 .015 .04 .06 .00 .00 .01 .03 .03 )

for 501 ≤ t ≤ 1000 and

λt = ( .02 .04 .015 .00 .00 .03 0.04 .015 .00 .00 .04 .02 .01 .00 .00 )

for 1 ≤ t ≤ 500. The initial vector of capacities is c = ( 100, 120 ) . All vectors should be interpreted as column vectors (although for convenience we write them as row vectors).

a) Find the aggregate arrival rate ΛTj = ∫ T 0 λtjdt,j = 1, . . . , 15 for the 15 ODFs.

b) Write the corresponding Deterministic Linear Program (dual of the ADP formula- tion) to determine how much capacity y should be allocated to each ODF.

1

c) Use Excel solver or any other linear programming solver to determine an optimal capacity allocation ȳj,j = 1, . . . , 15 and use the sensitivity report to obtain the dual or shadow prices z̄ = z(T,u) for the two resources. Describe how you would implement the unmodified bid-price heuristic?

d) Partition the 15 ODFs into sets F = {j : ȳj = ΛTj}, P = {j : 0 < ȳj < ΛTj} and R = {j : ȳj = 0}. Describe how you would handle the ODFs in set P under the PAC heuristic.

e) Use the vector of bid-prices obtained in part c) to obtain the net contribution of the fares to each resource. For example, for ODF 12, p1,12(z̄) = 240 − z̄2 and p2,12(z̄) = 240− z̄1. Then map all ODFs for each resource into one of three buckets: bucket 1 for net fares that are at least 120, bucket two for net fares between 70 and 120, and bucket 3 for net fares below 70. Once the buckets are assigned, compute the weighted average fare and the aggregate demand for each bucket for each leg. Finally, for each leg, apply the EMSR-b heuristic to obtain protection levels for the higher fare buckets.

2

e) Estimate the performance of the heuristics of parts c, d and e. Report the approx- imate expected revenues and the standard error of your simulations.

3