Spatially Distributed Queues II M/G/1 2 Servers N servers Approximations M/G/1 Ambulance (0,0) (0,Y 0 ) Directions Of Travel X A Y A (X 0 ,0) Two-Server “Hypercube” Queueing Model aDistinguishable servers aDifferent workloads (due to geography) aCan appear with or without queueing `With -- usually FCFS `Without -- usually means a backup contract service is in place Poisson Arrivals from any sub-region A A B-A λ(A)=λ 1 λ(B-A)=λ 2 B = “Service Region” λ = λ 1 + λ 2 Balance of Flow Equations 1,0 λ 2 μ 0,0 0,1 λ 1,1 λ μ μ λ 1 μ Balance of Flow Equations P 00 (λ 1 + λ 2 ) = P 01 μ + P 10 μ P 01 (λ + μ) = P 11 μ + P 00 λ 1 Etc. P 00 +P 10 +P 01 +P 11 = 1 Workload and Imbalances aρ 1 = W 1 = P 01 + P 11 aρ 2 = W 2 = P 10 + P 11 aWorkload Imbalance = ?W = |W 1 -W 2 | Average System-Wide Travel Time T(A)=f 11 T 1 (A) + f 22 T 2 (B-A) +f 12 T 1 (B-A) + f 21 T 2 (A) Queueing Average System-Wide Travel Time T(A)=f 11 T 1 (A) + f 22 T 2 (B-A) +f 12 T 1 (B-A) + f 21 T 2 (A) Geometry How do we obtain the f nj ’s? aConsider a long time interval T af 12 =(# requests that assign unit 1 to area 2)/ (total # requests answered)aTotal # requests answered = (1-P 11 )λT aAverage # requests that are “server 1 to area 2” is λ 2 TP 10 . Why? aTherefore f 12 =(λ 2 TP 10 / [1-P 11 ]λT) = {λ 2 /(1-P 11 )λ)} P 10 x y -1 +1 x=-0.25 x=0.75 * w 1-w High Demand Area: 50% workload Rectangular City Example Equal travel time Boundary line Optimal Districting a“Dispatch the closest available server’ is often not optimal, where ‘optimal’ implies minimizing mean travel time aMay not be good for reducing workload imbalance either aWith numerical example in book, the optimal boundary line is shifted to the right by 10/126 miles. x y -1 +1 x=-0.25 x=0.75 * Equal travel time Boundary line w*=53/1261-w*=73/126 High Demand Area: 50% workload Optimal Boundary Line 10/126 Rectangular City Example Boundary Line Comparison aEqual travel time boundary line `T(A w=1/2 )=0.46246 `?W = 0.05236 aOptimal boundary line `T(A w* )=0.46166 `?W = 0.04405 Two server Loss Model: Boundary Line Result aTo minimize mean city-wide mean travel time: aThe optimal partitioning consists of a set of points within the region that is a constant travel time s 0 closer to facility 1 than to facility 2. (Carter, Chaiken, Ignall, 1972) aDoes our rectangular city example work for this? S 0 : Optimal Partitioning α ≡ λ /2μ μ 1 = μ 2 S 0 = [2α /(2α +1)]{T 2 (B) ? T 1 (B)} Directions Of Travel 1 2 Directions Of Travel 1 2 Equal travel time boundary line Directions Of Travel 1 2 S 0 growing larger Directions Of Travel 1 2 The S 0 result is general aWorks for discrete grid aOne way streets aGeneral transportation network aRick Jarvis, in an MIT Ph.D. thesis, generalized this to N servers Switch now to N Servers "Hypercube Queueing Model" Setup: Hypercube Queueing Model aRegion comprised of geographical atoms or nodes aEach node j is an independent Poisson generator, with rate λ j aTravel times: τ il = travel time from node i to node j aN servers aServer locations are random: l nj Setup: Hypercube Queueing Model - con't. aServer assignment: one assigned aState dependent dispatching aService times: mean = 1/μ n ; negative exponential density aService time dependence on travel time aWe allow a queue (FCFS, infinite capacity) Fixed Preference Dispatch Policies for the Model aIdea: for each atom, say Atom 12, there exists a vector of length N that is the preference-ordered list of servers to assign to a customer from that atom aExample: {3,1,7,5,6,4,2}, for N=7. aDispatcher always will assign the most preferred available server to the customer aUsually order this list in terms of some travel time criterion. Customer in square marked X. Place an asterisk in each square that could have the closest server. Assume each server is available and is located 'somewhere' in his/her square "police beat." X X* * ** * * * * * X* * * * * * * * * * * * * * * * * * * * * Example Dispatch Policies aSCM: Strict Center of Mass `Place server at its center of mass `Place customer at its center of mass `Estimate travel times: center of mass to center of mass aMCM: Modified Center of Mass `Place server at its center of mass `Keep customer at centroid of atom `Estimate travel times: center of mass to centroid of atom Example Dispatch Policies aEMCM: Expected Modified Center of Mass `Do the conditional expected travel time calculation correctly, conditioned on the centroid of the atom containing the customer Are fixed preference policies optimal? aAVL: Automatic Vehicle Location: dispatch the real time nearest server `This can be incorporated into the Hypercube framework, but very carefully! `Consider two servers: RA1 X Customer RA2 What to know about the Hypercube Queueing Miodel aKnow the 2-server setup aBe able to work with a 3-server model `Read in the text the formulas to apply aForget the cases for N>3 servers. Square Root Laws (approximations) In Chapter 3 we found E[D] = C A N 0 Area of service region Number of mobile servers depended on distance metric and location strategy Assumes all N 0 servers are available or free (not busy) Now consider N to be a R.V. Might we expect the following to be true? E[D | N = k] = C A k k = 1,2,..., N 0 What if the locations of servers were determined by a homogenous spatial Poisson process, with busy servers selected by "random erasers"? Getting to Expected Travel Distance E[D] = P 0 D 0 + P k k =1 N 0 ∑ C A k From M/M/N 0 queueing model where P k = Probability of k servers available (M/M/N 0 ) Moving to E[D] Since P 0 0, we can write? E[D] ? CAE states of M / M / N 0 [1 / N ] We now apply "B-" probability reasoning, to get E[D] ? C A E[N] (Jensen's Inequality shows that this Eq. is a lower bound to true E[D].) Finishing E[N] ≈ N 0 ? N 0 ρ = N 0 (1 ? ρ) E[D] ≈ C A N 0 (1 ? ρ) E[T] ≈ C v A N 0 (1 ? ρ) + v a Acceleration term Great results in practice Jensen's Inequality 0 0.2 0.4 0.6 0.8 1 1.2 12345678910 Series1 N 1/ N Jensen's Inequality 0 0.2 0.4 0.6 0.8 1 1.2 12345678910 Series1 50% of probability mass here 50% of probability mass here True mean "B-" mean N 1/ N Jensen's Inequality If g(X) is a convex function over the region of non-zero probability, then E[g(X )] ≥ g(E[X]) (Problem 5.5 explores this further.)