1.203J Logistical and Transportation Planning Methods, Quiz #2 (Solutions)

1.203J / 6.281J / 13.665J / 15.073J / 16.76J / ESD.216J Logistical and Transportation Planning Methods Quiz #2 Solutions Problem 1 (35 points) a). Let the states be defined by (i, j, k) where: - i is the number of Type 1 customers (i = 0, 1, 2, or 3) - j is the number of Type 2 customers (j = 0, 1, 2, or 3) - k is the type of customer being served (k = 0, 1, 2) The total number of state is 13. The state transition diagram for the system is as follows: λ2 λ2 0,0,0 0,1,2 0,2,2 µ2 λ1 µ2 1,1,2 µ1 1,1,1 µ1 2,0,1 µ2 µ1 λ2 λ1 0,3,2 µ2 µ1 1,0,1 λ2 µ2 λ1 µ1 λ2 λ1 µ2 λ2 1,2,2 λ1 1,2,1 2,1,2 λ2 λ1 µ1 2,1,1 3,0,1 b). In the long run, this system treats Type 1 and Type 2 customers equally. Sometimes Type 1 customers have priority and sometimes Type 2 customers do. When λ1 = λ 2 and µ1 = µ 2 , the state transition diagram is perfectly symmetrical. Therefore, L1 = L2 under those conditions. c). The next customer to be served by the server is a Type 2 customers if no Type 1 customer arrives before the completion of the current service. The probability that a Type 1 customers arrives before the completion of the current service is given by: J 6 PA = Pr(next event occurs in [0, ε ] and is the arrival of one Type 1 customer ) Pr (next event occurs in [0, ε ]) PA = λ1 λ1 + λ 2 + µ1 Therefore, the probability that the next customer to be served is a Type 2 customer is given by: PA = 1 − PA = λ 2 + µ1 λ1 + λ 2 + µ1 d). We start with 2 people in the system: one Type 1 customer is being served and one Type 2 customer is waiting for service. • Let’s first consider that the next transition is due to an arrival of a Type 1 customer. This customer will be the next one to be served and we cannot reach the state described by the 3rd transition. • If a Type 2 customer arrives before service completion, the system is full, thus the following state transition can only be due to the end of Type 1 customer’s service. Type 2 customers are then given priority, and we end up in the desired state at the 3rd transition if and only if a 3rd Type 2 customer shows up before service completion • Let’s now consider that the next transition is due to a service completion. The Type 2 customer who was waiting is then served and there are two empty waiting seats. We end up in the desired state at the 3rd transition if and only if two Type 2 customers arrive before service completion. We have therefore identified exactly two cases: 1rst transition = Arrival: Type 2 (system is full) nd 2 transition = Service completion: Type 1 (automatic) 3rd transition = Arrival: Type 2 or 1rst transition = 2nd transition = 3rd transition = Service completion: Type 1 Arrival: Type 2 Arrival: Type 2 Thus, the answer is: λ2 λ2 µ1 λ2 λ2 ⋅1⋅ + ⋅ λ1 + λ 2 + µ1 λ1 + λ 2 + µ 2 λ1 + λ 2 + µ1 λ1 + λ 2 + µ 2 λ1 + λ 2 + µ 2 2 λ2 µ1 P= (1 + ) (λ1 + λ 2 + µ1 )(λ1 + λ 2 + µ 2 ) λ1 + λ 2 + µ 2 P= Problem 2 (35 points) a). We can use an aggregated birth-and-death process to compute the average workload. The equivalent system is an M/M/3 with no queueing space system. The associated state transition diagram is: J 6 λ 0 λ 1 2 µ Thus P1 = λ 2µ 3 3µ λ2 λ3 λ P0 ; P2 = P ; P = P0 . Since the sum of the probabilities is 1, we can 0 3 µ 2µ 2 6µ 3 16 24 18 9 , P1 = , P2 = and P3 = . 67 67 67 67 1 2 29 The average workload is: ρ = P1 + P2 + P3 = . 3 3 67 compute all of them: P0 = b). The calls lost for the system are the calls that arrive when all the cars are busy. This corresponds to state P3. Thus, fraction of calls for service that are lost to the system is 9 ≈ 13%. 67 c). In order for a call for service to be an intra-sector assignment, the car assigned to the corresponding sector should be free. Let (a,b,c) be the state of the system, where: - a describes the state of car A (0 if idle, 1 if busy) - b describes the state of car B (0 if idle, 1 if busy) - c describes the state of car C (0 if idle, 1 if busy) If a call originates from sector A, it is responded to by car A if and only if a=0. The corresponding states are: (0,0,0), (0,1,0), (0,0,1), (0,1,1). If a call originates from sector B, it is responded to by car B if and only if b=0. The corresponding states are: (0,0,0), (10,0), (0,0,1), (1,0,1). If a call originates from sector C, it is responded to by car C if and only if c=0. The corresponding states are: (0,0,0), (0,1,0), (1,0,0), (1,1,0). λ f int ra = 3 λ f int ra = 3 f int ra = (P000 + P010 + P001 + P011 ) λ (P000 + P100 + P001 + P101 ) λ (P000 + P010 + P100 + P110 ) λ (1 − P111 ) (3P0 + 2 P1 + P2 ) λ (1− P3 ) 19 29 d). P2 = 26.9% + 3 λ (1 − P111 ) + 3 λ (1 − P111 ) J 6 e). The police car B is closer to region A than C is and vice versa. Thus, the police car B gets assigned to another region more often than the two other cars. Current State Length covered by A (miles) 1 0 Average of 1.5 1 1+1+1 = 3 0 0 0 (0,0,0) (1,0,0) (0,1,0) (0,0,1) (0,1,1) (1,0,1) (1,1,0) (1,1,1) Length covered by B (miles) 1 1+1 = 2 0 1+1 = 2 0 3 0 0 Length covered by C (miles)1 1 1 Average of 1.5 0 0 0 3 0 From this table, we can draw a detail state transition diagram of the system and write the steady state equations. λ 3 µ µ 0,1,0 λ 3 λ 2 0,0,1 λ 2 λ 3 2λ 3 2λ 3 µ µ 1,1,0 λ 1,0,1 λ µ µ This gives us a set of six equations with 6 unknown. λ 3 P0 + µ (P101 + P110) µ µ 0,1,1 λ µ 1,1,1 (µ + λ ) P100 = µ λ 3 1,0,0 µ λ 3 0,0,0 µ J 6 (µ + λ ) P010 = λ (µ + λ ) P001 = λ 3 3 (2µ + λ ) P110 = P0 + µ (P011 + P101) P0 + µ (P101 + P101) µ P3 + (2µ + λ ) P101 = µ P3 + (2µ + λ ) P011 = µ P3 + λ 2 λ 3 λ 2 P010 + 2λ P100 3 (P001 + P100) P010 + 2λ P001 3 There is a symmetry between A and C that simplifies the system. It can be reduced to a set of 2 equations with 2 unknowns. We have: P001 = P100 = And P101 = 256 280 ; P010 = 2211 2211 158 218 ; P110 = P011 = 2211 2211 Therefore, the fraction of time B is busy is: f B = P010 + P110 + P011 + P111 = 1013 = 45.8% 2211 f). In order to for A to be called in service in sector B, we should be in the situation where a call originates from sector B whereas car B is busy and: - car C is busy but A is idle, which corresponds to state (0,1,1) - car C and car A are idle but A is closer, which corresponds to state (0,1,0) with A closer. Therefore, the answer is: λ 1λ P010 173 3 2 3 f A→ B = = ≈ 18% λ 957 (1 − P111 ) 3 P011 + g). Let’s first consider sector A. Let us define three distances yA, yB and x shown below: J 6 Car A Call yA Car B yB x We have YA ~ U(0,1) and YB ~ U(0,1). Let’s consider that x belongs to [0.5; 1], otherwise we know that car A is closer for sure. We are looking for P{car A closer | YB = yB, X = x > 0.5}. If car A is between the call and car B, i.e. yA > x, then car A is closer. That happens with probability 1-x. If car A is to the left of the call, then it is closer if and only if it is within a distance of 1-x+yB of the call. Thus, P(car A closer | YB = yB, X = x > 0.5) = 1-x + 1-x+yB = 2 (1-x) + yB. We should now consider a double integral to have P(car A closer ). The answer is P(car A closer ) = 3 . 4 To get this result, we had assumed that x > 0.5. Therefore, for a random incident from Sector A, the probability that car A will be closer to the call than car B is: P = 1× 1 3 1 7 + × = . 2 4 2 8 By symmetry, the result is indentical for C. And for Sector B, for one half of the cases, car A could be closer than B, and for the other half, car C could be closer. Thus, car B is the closest to a call originating from Sector B with the probability 3 1 3 1 3 × + × = . 4 2 4 2 4 Problem 3 (30 points) a). The solution to the CPP on an undirected graph uses a minimum-cost pairwise matching of the odd-degree nodes to identify the “dummy edges” that need to be added to the original graph to convert it into an Eulerian graph. But we have argued that the paths associated with a minimumcost pairwise matching cannot have overlapping edges (see pp. 393-394 of the textbook). That means, no edge will have more than one dummy edges added to it. Thus n(i, j) = 1 or 2 for all (i, j) in an optimal solution to the CPP. b). i). According to the Majority Theorem, µ is in (N - Nvi) implies that H (N - Nvi) ≥ H (Nvi). J 6 ii). However, all nodes have a positive weight, therefore H (Nvi) ≥ H (Nvi - N2). iii). Thus, H (N - Nvi) ≥ H (Nvi - N2). However, in order for µ1 to be in (Nvi - N2) and not in (N - Nvi), we must have: H (N - Nvi) ≤ H (Nvi - N2). This contradicts the original assumption of our logic. Therefore, the claim is not true.