Robust positioning of service units

Robust Positioning of Service Units J. Puerto 1, *and A. M. Rodrı ´guez-Chı ´a 2, * 1 Dept. Estadı ´stica e Investigacio ´n Operativa, Universidad de Sevilla, Fac. de Matema ´ticas, Sevilla, Spain 2 Dept. Estadı ´stica e Investigacio ´n Operativa, Universidad de Ca ´diz, Fac. de Ciencias del Mar, Polı ´gono Rı ´o San Pedro, Ca ´diz, Spain ABSTRACT In this paper, we address the problem of locating mobile service units to cover random incidents. The model does not assume complete knowledge of the probability distribution of the location of the incident to be covered. Instead, only the mean value of that distribution is known. We propose the minimization of the maximum expected response time as an effectiveness measure for the model. Thus, the solution obtained is robust with respect to any probability distribution. The cases of one and two service units under the nearest allocation rule are studied in the paper. For both problems, the optimal solutions are shown to be degenerate distributions for the servers. Key Words: Location theory; Stochastic problems. 1. INTRODUCTION In distribution systems and in continuous location models, a common problem is to find the optimal placement of one or more servers minimizing the distances to a given set of points. All the models considered so far in the literature assume that the positions of 125 DOI: 10.1081/STM-120018142 1532-6349 (Print); 1532-4214 (Online) Copyright q2003 by Marcel Dekker, Inc. www.dekker.com *Correspondence: J. Puerto, Dept. Estadı ´stica e Investigacio ´n Operativa, Universidad de Sevilla, Fac. de Matema ´ticas, C/Tarfia s/n, 41012 Sevilla, Spain; E-mail: [email protected]. A. M. Rodrı ´guezChı ´a, Dept. Estadı ´stica e Investigacio ´n Operativa, Universidad de Ca ´diz, Fac. de Ciencias del Mar, Polı ´gono Rı ´o San Pedro, 11510 Puerto Real, Ca ´diz, Spain; E-mail: [email protected]. 120018142_STM_019_001_R1_X0.ald 8/2/2003—KALYAN—59071 STOCHASTIC MODELS Vol. 19, No. 1, pp. 125–147, 2003 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 these points are either deterministic or distributed according to a known probability distribution on the family of Borel sets in R n(see for instance Anderson and Fontenot, [1] Carrizosa, Mun ˜oz-Ma ´rquez and Puerto, [2] Larson and Odoni, [5] Levine, [6] De Palma, Liu and Thisse, [7] among others). However, it is easy to find situations in the real-world where the hypothesis of complete knowledge of this probability distribution is unrealistic. In this paper, we propose a more general model where only the mean value of this distribution is known. This assumption is not really restrictive because we can obtain good estimates of the unknown mean value by sampling. Although more information can be obtained from the sample, our model only needs the estimation of the mean value, which is a very wellsolved problem in mathematical statistics. A real-world application of such models is, for instance, the problem of locating a read/write head of a computer hard-disk to easily access the stored data. Similarly, our framework includes the problem of positioning police-cars that must cover incidents where the law is being broken, and positioning idle elevators to minimize response time(see Vickson, Gerchak and Rotem [10] or Smith [9] for a different analyses assuming that the distribution of the data is known). Indeed, in these cases, usually the distribution of the places where the law will be broken, the data are stored, or the elevator is needed is not known. Nevertheless, it would be less restrictive to assume that either we know the mean value for these distributions or we may estimate it by means of an empirical study. When the probability distribution of the position of the incident is unknown, the classical minimization of the expected distances is not possible. Therefore, alternative approaches have to be considered. In this paper, we propose a robust alternative consisting of minimizing the maximum expected distance within the whole family of probability measures which model the incident (see Gallego [4] and Puerto and Ferna ´ndez [8] for similar analyses applied to different problems in Operations Research). Let F( l ) and G( m ) be the families of random variables (r.v.) (given by their cumulative distribution functions (c.d.f.) defined on the n-dimensional hypercube [0,1] n with mean values l [ R nfor F( l ) and m [ R nfor G( m ), that is, Fð l Þ¼{X:r:v:on ½0;1nwith c:d:f:FX;Z½0;1n xdF XðxÞ¼ l }; Gð m Þ¼{A:r:v:on ½0;1nwith c:d:f:GA;Z½0;1n adG AðaÞ¼ m }: Define F:¼ l [½0;1n <Fð l Þ: The families Fand G( m ) are the sets of random variables which model the position of the server and the incident, respectively. It is worth noting that we have defined these random variables in the n-dimensional hypercube [0,1] n , but they can be extended to any hyperrectangle by a linear transformation. As previously mentioned, some authors have studied the problem of minimizing the expected distance to the random incident, i.e., X[F min Z½0;1nZ½0;1n dðx;aÞdGAðaÞdFXðxÞ; 120018142_STM_019_001_R1_X0.ald 8/2/2003—KALYAN—59071 Puerto and Rodrı ´guez-Chı ´a126 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 where dis a measure of distance, Xis a r.v. with c.d.f. F X , representing the position of the server, and Ais a r.v. with c.d.f. G A , representing the position of the incident. Our model does not assume any a priori knowledge about the probability distribution of the incident apart from its mean value. That is to say, we have almost complete uncertainty about where the incident will take place, and we search for the policy that an emergency unit, X, has to follow to minimize the maximum expected distance to any random incident. Therefore, the problem is X[F min A[Gð m Þ max Z½0;1nZ½0;1nkx2ak1dGAðaÞdFXðxÞ;ð1Þ where k·k 1 is the l 1 -norm in R n, so that, for x¼(x 1 ,...,x n )[ R n we have that kxk1¼X n i¼1jxij: The readers should note that there are essentially two kinds of factors that influence the formulation of the problem: 1) the dimension nof the space where the incidents occur; and 2) the number of service units to be located. It is also worth noting that this problem formulation can be used to model the above mentioned real-world situations because: a) we do not need to know the distribution of the incident; and b) the read/write head only admits displacements following the directions of the coordinate axes; and both the highway and the trajectory of the elevator can be considered like line segments where displacements are linear. Thus, the l 1 -norm is an appropriate measure of distance. Finally, the formulation (1) gives us a new interpretation of the solutions obtained in terms of statistics. As we shall show in the paper, the optimal probability distributions for our problem are degenerate random variables. Since principal points of probability distributions are those points optimizing some effectiveness measure (see Flury [3] ), we can see our solutions as a generalization of the principal points, but now we are optimizing over a family of distributions with a fixed mean rather than the values of a single probability distribution. The paper is organized as follows. In Section 2, we consider the problem of locating a single facility; we first study the problem considering the service unit as a degenerate random variable and then we extend these results to the general case with any random variable. In Section 3, we consider the two-facility problem under the nearest allocation rule and we follow a scheme similar to that followed in Section 2. In Section 4, we include some concluding remarks and possible extensions to the considered model. Finally, in the Appendix, we include, for the sake of readability, several technical results that have been used in the paper. 2. THE SINGLE FACILITY PROBLEM We begin this section by considering the one-dimensional case, then we proceed to the n-dimensional single facility problem. Let F 1 ( l ) and G 1 ( m ) be, respectively, the families of random variables F( l ) and G( m ) in the 1-dimensional case. For ease of 120018142_STM_019_001_R1_X0.ald 8/2/2003—KALYAN—59071 Robust Positioning of Service Units 127 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 understanding, we distinguish two cases. In the first case, the server is not allowed to patrol, i.e., we model the location of the server with a degenerate random variable. In the second case, the server is allowed to patrol, which means that it is any random variable in F 1 . For the first case, the mathematical formulation of the problem is: x[½0;1 min A[G1ð m Þ max Z½0;1jx2ajdGAðaÞ:ð2Þ Theorem 2.1 The optimal positioning policy in the hypothesis of Problem (2) is x*¼ 0if m ¼0:5 yfor any y[½0;1if m ¼0:5 1if m .0:5: 8 > > < > > : ð3Þ Remark 2.1 This result states that the optimal location for a fixed service unit when only the mean value m of the distribution of the incident is known, is on an extreme point of the interval of feasible locations for the incident. Further, when m ¼0:5 any point on the interval is an optimal location of the server. Proof: By Lemma A.2 in the Appendix we have that x[½0;1 min A[G1ð m Þ max Z½0;1jx2ajdGAðaÞ¼ x[½0;1 min A[G1ð m Þ max 2Zx 0 GAðaÞda 2xþ m  :ð4Þ Hence, we prove that the maximum in the last expression is reached at the random variable A*with the following c.d.f. GA*ðaÞ¼ 0ifa,0 12 m if 0 #a,1 1ifa$1: 8 > > < > > : Indeed, since xand m are constants for the inner maximum in the right hand side of (4), we have to prove the following inequality Zx 0 GAðaÞda 2ð12 m Þx#0;;x[½0;1;;A[G1ð m Þ:ð5Þ But, since R1 0GAðaÞda ¼12 m (Lemma A.2) and G A (·) is a distribution function, we are under the hypotheses of Lemma A.1 which proves the inequality (5). Therefore, the minimization Problem (2) reduces to the following problem: x[½0;1 min xð122 m Þþ m : Hence, depending on the relative values of m , we obtain that the optimal positioning x* satisfies equation (3). A 120018142_STM_019_001_R1_X0.ald 8/2/2003—KALYAN—59071 Puerto and Rodrı ´guez-Chı ´a128 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 In the second case, the service unit is also allowed to patrol. Initially, we permit the service unit to be distributed on the interval according to a random variable with the only condition that its mean value is fixed to l . Then, we solve the case when l is not fixed. For the first case, the problem is X[F1ð l Þ min A[G1ð m Þ max Z½0;1Z½0;1jx2ajdGAðaÞdFXðxÞ:ð6Þ Theorem 2.2 Any random variable X [F1ð l Þconstitutes an optimal policy for Problem (6). Proof: By Lemma A.4, we have that Z½0;1Z½0;1jx2ajdGAðaÞdFXðxÞ¼212Z1 0 GAðyÞFXðyÞdy  2 l 2 m : Therefore, using that l and m are fixed,we can solve Problem (6) by solving the equivalent problem X[F1ð l Þ max A[G1ð m Þ min Z1 0 GAðyÞFXðyÞdy: In order to do this, we are going to prove that the inner minimum is achieved by the random variable A* such that P(A*¼0) ¼1m and P(A*¼1) ¼ m . IA;X:¼Z1 0 FXðyÞGAðyÞdy 2Z1 0 FXðyÞð12 m Þdy $0: Considering t0:¼t0ðAÞ[ð0;1Þsuch that t0¼inf{t[R:GAðtÞ$12 m } we have the following inequalities: IA;X¼Zt0 0 FXðyÞðGAðyÞ2ð12 m ÞÞdy þZ1 t0 FXðyÞðGAðyÞ2ð12 m Þdy $Zt0 0 FXðt0ÞðGAðyÞ2ð12 m ÞÞdy þZ1 t0 FXðt0ÞðGAðyÞ2ð12 m ÞÞdy ¼FXðt0ÞZ1 0ðGAðyÞ2ð12 m ÞÞdy  ¼0; by Lemma A.2. Similarly, Lema A.2 implies that A[G1ð m Þ min Z1 0 GAðyÞFXðyÞdy þa[ð0;1Þ XaP½A¼aP½X¼a¼Z1 0 FXðyÞð12 m Þdy ¼ð12 l Þð12 m Þ; regardless of the choice of X[F1ð l Þ;and the result follows. A 120018142_STM_019_001_R1_X0.ald 8/2/2003—KALYAN—59071 Robust Positioning of Service Units 129 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 Let us consider in the following that no assumptions are made on the mean value, l ,of the random variable modelling the service unit. In this situation, the problem is X[F1 min A[G1ð m Þ max Z½0;1Z½0;1jx2ajdGAðaÞdFXðxÞ:ð7Þ Corollary 2.1 An optimal positioning policy of Problem (7) is the random variable X* such that P½X*¼x*¼1where x*was defined in (3). Proof: Note that X[F1 min A[G1ð m Þ max Z½0;1Z½0;1jx2ajdGAðaÞdFXðxÞ ¼ l [½0;1 min X[F1ð l Þ min A[G1ð m Þ max Z½0;1Z½0;1jx2ajdGAðaÞdFXðxÞ: Let Hð l Þ¼ X[F1ð l Þ min A[G1ð m Þ max R½0;1R½0;1jx2ajdGAðaÞdFXðxÞ: For each l [½0;1;by the proof of Theorem 2.2 we have that Hð l Þ¼2ð12ð12 l Þð12 m ÞÞ2 l 2 m ¼ð122 m Þ l þ m : Thus, if we look for the minimum in l we obtain arg l [½0;1 min Hð l Þ¼ {0} if m ,0:5 yfor any y[½0;1if m ¼0:5 {1} if m .0:5; 8 > > < > > : and the result follows. A This corollary shows that it is optimal to park the service unit when no hypotheses are made on the distribution of the service unit and only the mean value of the incident is known. Thus, although patrolling may be good for other reasons such as crime prevention, etc., it is not necessary in order to minimize the maximum expected distance to any random incident. Finally, we also solve the n-dimensional problem. Indeed, let us consider the problem: X[F min A[Gð m Þ max Z½0;1nZ½0;1nX n i¼1jxi2aijdGAðaÞdFXðxÞ;ð8Þ where m ¼ð m 1;...; m nÞ;x¼ðx1;...;xnÞand a¼ða1;...;anÞ:Problem (8) can be written equivalently as follows: X[F min A[Gð m Þ max X n i¼1Z½0;1Z½0;1jxi2aijdGAiðaiÞdFXiðxiÞ # X[F min X n i¼1Ai[G1ð m iÞ max Z½0;1Z½0;1jxi2aijdGAiðaiÞdFXiðxiÞ;ð9Þ 120018142_STM_019_001_R1_X0.ald 8/2/2003—KALYAN—59071 Puerto and Rodrı ´guez-Chı ´a130 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 where G A i and F X i are the marginal distributions of G A and F X respectively. Let A* 1;...;A* nbe the 1-dimensional random variables attaining the inner maxima and GA* 1;...;GA* ntheir respective cumulative distribution functions. Consider dGA*¼ dGA* 1 £...£dGA* n;the measure in the product space generated by the measures dGA* 1;...;dGA* n;and let A*be a n-dimensional random variable with cumulative distribution G A* . That means, A*is a random vector whose components are independent random variables. Since A*is feasible for the former maximum in (8), we have that (9) holds with equality. By a similar argument, we get X[F min A[Gð m Þ max Z½0;1nZ½0;1nX n i¼1jxi2aijdGAðaÞdFXðxÞ ¼X n i¼1Xi[F1 min Ai[G1ð m iÞ max Z½0;1Z½0;1jxi2aijdGAiðaiÞdFXiðxiÞ: Thus, we have obtained that the n-dimensional problem can be solved by solving n different 1-dimensional problems. This reduction allows the resolution of Problem (8) by Corollary 2.1. In particular, the results in this section show that if the l 1 -norm is used, the optimal policy is to park (to fix) the service unit at some vertex of the region where the random incident takes place. 3. THE TWO-FACILITY PROBLEM In the previous section, we considered the problem of locating only one facility to cover a random incident. However, often more than one service unit is necessary, especially if the coverage region is large. In this section, we consider the case where two service facilities cover a random incident under the usual nearest allocation rule: the random incident is covered by the closest service unit. This allocation rule leads to the following formulation: X1;X2[F1 min A[G1ð m Þ max Z½0;12Z½0;1 min jx12aj;jx22aj fg dGAðaÞdF1;2ðx1;x2Þ;ð10Þ where F 1 ,G 1 ( m ) were defined in Section 2, G A (·) is the c.d.f. of the random variable Aand F 1,2 (·,·) is the joint c.d.f. of the random variables X 1 and X 2 . It is worth noting that this is a non-trivial problem: 1) it is a minmax problem, and 2) the decision space is a functional space of random vectors. This formulation allows us to model different real-world situations where there are two-service units to cover a random incident. This is for example the case of highways with two patrolling vehicles so that each one covers the closest incident. In order to solve this problem, first we consider the case where the servers are not allowed to patrol, that is, X 1 and X 2 are degenerate random variables. After that, we deal with the general case: X 1 and X 2 are any random variables belonging to F 1 . 120018142_STM_019_001_R1_X0.ald 8/2/2003—KALYAN—59071 Robust Positioning of Service Units 131 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 The formulation of Problem (10) for the first case is given by the following expression x1;x2[½0;1 min A[G1ð m Þ max Z½0;1 min jx12aj;jx22aj fg dGAðaÞ:ð11Þ Remark 3.1 Without loss of generality we can assume that x1#x2: Before we proceed to obtain the solution of Problem (11), we define the following functions:  dðx1;x2;AÞ:¼2Zx1 0 GAðaÞda þZx2 x1þx2 2 GAðaÞda ! þ m 2x2;ð12Þ Cðx1;x2;p1Þ:¼2ð12 m Þx1þx2 22p1x12x1þx2 2  2 ! ! 2x2þ m ;ð13Þ and the set Tðx1;x2Þ:¼{p¼ðp0;p1;p2Þ$0:p0þp1þp2¼1 and p1 x1þx2 2þp2¼ m };ð14Þ where Ais a random variable in G 1 ( m ) with distribution function G A and x1;x2[½0;1: Theorem 3.1 The optimal positioning policy in the hypothesis of Problem (11) is x1¼ m 2and x2¼2 m 2 m 2: Proof: First, by Lemma A.5 and A.7, we have that 0#x1#x2#1 min A[G1ð m Þ max Z½0;1 min{jx12aj;jx22aj}dGAðaÞ¼ 0#x1#x2#1 min p[Tðx1;x2Þ max Cðx1;x2;p1Þ; where Cand T(x 1 ,x 2 ) were defined in (13) and (14), respectively. By Lemma A.8 the optimal solution of this problem is x1¼ m 2and x2¼2 m 2 m 2and the proof is concluded. A Once we have studied the problem of locating two deterministic service units, we consider the general problem where the service units are random vectors. In this case we consider the original Problem (10). Theorem 3.2 The optimal positioning policy of Problem (10) are the random variables X* 1and X* 2such that P X* 1¼ m 2  ¼1and P X* 2¼2 m 2 m 2  ¼1: 120018142_STM_019_001_R1_X0.ald 8/2/2003—KALYAN—59071 Puerto and Rodrı ´guez-Chı ´a132 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 Proof: Using Lemma A.5, we can bound the expression in (10) as follows (recall that d ¯ was defined in (12)): A[G1ð m Þ max Z½0;12Z½0;1 min{jx12aj;jx22aj}dGAðaÞdF1;2ðx1;x2Þ ¼A[G1ð m Þ max Z½0;x2£½0;1  dðx1;x2;AÞdF1;2ðx1;x2ÞþZðx2;1£½0;1  dðx2;x1;AÞdF1;2ðx1;x2Þ  #Z½0;x2£½0;1A[G1ð m Þ max  dðx1;x2;AÞdF1;2ðx1;x2Þ þZðx2;1£½0;1A[G1ð m Þ max  dðx2;x1;AÞdF1;2ðx1;x2Þ: ð15Þ Define S1¼{ðx1;x2Þ[ R 2:0#x1#x2#1}; S2¼{ðx1;x2Þ[ R 2:0#x2,x1#1}; and let X S j (·) denote the indicator function of the set S j for j¼1;2:Now, Lemma A.7 allows to write the integrands in (15) as A[G1ð m Þ max  dðx1;x2;AÞ¼ p[Tðx1;x2Þ max Cðx1;x2;p1Þfor ðx1;x2Þ[S1;ð16Þ A[G1ð m Þ max  dðx2;x1;AÞ¼ p[Tðx1;x2Þ max Cðx2;x1;p1Þfor ðx1;x2Þ[S2:ð17Þ Combining (16) and (17) we can rewrite the expression (15) as Z½0;12p[Tðx1;x2Þ max ½Cðx1;x2;p1ÞXS1ðx1;x2ÞþCðx2;x1;p1ÞXS2ðx1;x2ÞdF1;2ðx1;x2Þ: Let p*ðx1;x2Þ¼ðp* 0ðx1;x2Þ;p* 1ðx1;x2Þ;p* 2ðx1;x2ÞÞ [Tðx1;x2Þbe the function where the expression above reaches its inner maximum. Notice that the expression of p*(x 1 ,x 2 ) can be obtained from the proof of Lemma A.8, and it is defined in a different way depending on the region that (x 1 ,x 2 ) belongs to. Now, for all ðx1;x2Þ[½0;12;let A*(x 1 ,x 2 ) be a random variable independent of (X 1 ,X 2 ), whose probability distribution is dG A*(x 1 ,x 2 ), defined by dGA*ðx1;x2ÞðaÞ¼ p* 0ðx1;x2Þif a¼0 p* 1ðx1;x2Þif a¼x1þx2 2 p* 2ðx1;x2Þif a¼1: 8 > > < > > : ð18Þ Notice that, for a fixed x 1 and x 2 belonging to the interval [0,1], A*(x 1 ,x 2 ) is a discrete random variable taking the values 0, x1þx2 2and 1 with probabilities p* 0ðx1;x2Þ;p* 1ðx1;x2Þand 120018142_STM_019_001_R1_X0.ald 8/2/2003—KALYAN—59071 Robust Positioning of Service Units 133 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 Since, at zero the integrants of the first part of the equalities above are null, we have that Z½0;1 yGAðyÞdFXðyÞþZ½0;1 yFXðyÞdGAðyÞ¼1þxi[D XxiP½A¼xiP½X¼xi 2Z1 0 GAðyÞFXðyÞdy; and the result follows. A Lemma A.4 For any X [F1ð l Þand A[G1ð m Þwith c.d.f’s F X (·) and G A (·), respectively, we have that Z½0;1Z½0;1jx2ajdGAðaÞdFXðxÞ¼212Z1 0 GAðyÞFXðyÞdy  2 l 2 m : Proof: We have that Z½0;1Z½0;1jx–ajdGAðaÞdFXðxÞ ¼Z½0;1Z½0;x xdG AðaÞdFXðxÞ2Z½0;1Z½0;x adG AðaÞdFXðxÞ þZ½0;1Zðx;1 adG AðaÞdFXðxÞ2Z½0;1Zðx;1 xdG AðaÞdFXðxÞ ¼Z½0;1 xGAðxÞdFXðxÞ2Z½0;1Z½0;x adG AðaÞdFXðxÞ þZ½0;1Zðx;1 adG AðaÞdFXðxÞ2Z½0;1 xð12GAðxÞÞdFXðxÞ ¼2Z½0;1 xGAðxÞdFXðxÞ2 l 2Z½0;1Z½0;x adG AðaÞdFXðxÞ þZ½0;1ð m 2Z½0;x adG AðaÞÞdFXðxÞ¼2Z½0;1 xGAðxÞdFXðxÞ 22Z½0;1Z½0;x adGAðaÞdFXðxÞ2 l þ m ¼2Z½0;1 xGAðxÞdFXðxÞ 22Z½0;1 aZ½a;1 dFXðxÞdGAðaÞ2 l þ m ¼2Z½0;1 xGAðxÞdFXðxÞ 22Z½0;1 aZða;1 dFXðxÞdGAðaÞ22Z½0;1 aP½X¼adGAðaÞ2 l þ m : 120018142_STM_019_001_R1_X0.ald 8/2/2003—KALYAN—59071 Puerto and Rodrı ´guez-Chı ´a140 691 692 693 694 695 696 697 698 699 700 701 702 703 704 705 706 707 708 709 710 711 712 713 714 715 716 717 718 719 720 721 722 723 724 725 726 727 728 729 730 731 732 733 734 735 736 Denote by Dthe denumerable number of discontinuity points of F X or G A union with {0,1}. Then, we rewrite the expression above as 2Z½0;1 xGAðxÞdFXðxÞ22 m þ2Z½0;1 aFXðaÞdGAðaÞ22 y[D XyP½X¼yP½A¼y2 l þ m ¼2Z½0;1 yGAðyÞdFXðyÞþZ½0;1 yFXðyÞdGAðyÞ  22 y[D XyP½X¼yP½A¼y2 l 2 m : ð22Þ Now, using Lemma A.3 we have that ð22Þ¼212Z1 0 GAðyÞFXðyÞdy  2 l 2 m ; and the result follows. A Lemma A.5 For any A [G1ð m Þwith c.d.f. G A (·), the function d ¯defined in (12) admits the following representation.  dðx1;x2;AÞ¼Z½0;1 min jx12aj;jx22aj fg dGAðaÞ;x1#x2[½0;1: Proof: We have the following equalities: Z½0;1 min {jx12aj;jx22aj}dGAðaÞ¼Z½0;x1þx2 2jx12ajdGAðaÞþZðx1þx2 2;1jx22ajdGAðaÞ ¼Z½0;x1ðx12aÞdGAðaÞþZðx1;x1þx2 2ða2x1ÞdGAðaÞ þZðx1þx2 2;x2ðx22aÞdGAðaÞþZðx2;1ða2x2ÞdGAðaÞ ¼2x1GAðx1Þ2GA x1þx2 2  ðx1þx2Þþ2x2GAðx2Þ 2x22Z½0;x1 adGAðaÞþZðx1;x1þx2 2 adG AðaÞ 2Zðx1þx2 2;x2 adG AðaÞþZðx2;1 adG AðaÞ ¼2x1GAðx1Þð 2Z½0;x1 adG AðaÞþx2GAðx2Þ 120018142_STM_019_001_R1_X0.ald 8/2/2003—KALYAN—59071 Robust Positioning of Service Units 141 737 738 739 740 741 742 743 744 745 746 747 748 749 750 751 752 753 754 755 756 757 758 759 760 761 762 763 764 765 766 767 768 769 770 771 772 773 774 775 776 777 778 779 780 781 782 2GA x1þx2 2  x1þx2 22Zðx1þx2 2;x2 adG AðaÞ! þ m 2x2¼2Zx1 0 GAðaÞda þZx2 x1þx2 2 GAðaÞda ! þ m 2x2¼ dðx1;x2;AÞ; and the result is proved. A Lemma A.6 For each random variable A [G1ð m Þwith distribution function G A (·) and each 0#x1#x2#1;there exists a discrete random variable  A[G1ð m Þdefined by P½ A¼a¼ p0if a¼0 p1if a¼x1þx2 2 p2if a¼1; 8 > > < > > : where( p 0 ,p 1 ,p 2 ) satisfies that p0þp1þp2¼1  dðx1;x2;AÞ# dðx1;x2; AÞ Zx1þx2 2 0 GAðaÞda ¼p0 x1þx2 2ð23Þ Z1 x1þx2 2 GAðaÞda ¼ðp0þp1Þ12x1þx2 2  :ð24Þ Remark A.1 It should be noted that from this result and part i) of Lemma A.2, one obtains that for each 0 #x1#x2#1;the maxA[G1ð m Þ dðx1;x2;AÞis attained in a discrete random variable with mean value m and defined only on the values 0, x1þx2 2and 1. Moreover, p¼ðp0;p1;p2Þ[Tðx1;x2Þ(where Twas defined in (14)). Proof: First, we note that  A[G1ð m Þ;see Remark A.1. Second, in order to complete the proof of the lemma it suffices to prove: i) Rx1 0GAðaÞda 2p0x1#0 ii) Rx2 x1þx2 2 GAðaÞda 2ðp0þp1Þx22x1þx2 2  #0: To this end, we apply Lemma A..1. Since (23) and (24) hold and G A (·) is a probability distribution function, we are under hypotheses of Lemma A.1 and thus, i) and ii) are proved. A 120018142_STM_019_001_R1_X0.ald 8/2/2003—KALYAN—59071 Puerto and Rodrı ´guez-Chı ´a142 783 784 785 786 787 788 789 790 791 792 793 794 795 796 797 798 799 800 801 802 803 804 805 806 807 808 809 810 811 812 813 814 815 816 817 818 819 820 821 822 823 824 825 826 827 828 Lemma A.7 If x 1 ,x 2 [[0,1], x 1 #x 2 , then A[G1ð m Þ max  dðx1;x2;AÞ¼ p[Tðx1;x2Þ max Cðx1;x2;p1Þ; where d ¯, C, and T were defined in (12), (13), and (14), respectively. Proof: We have, by the definition of d ¯in (12) and Lemma A.6, that; A[G1ð m Þ max  dðx1;x2;AÞ¼ A[G1ð m Þ max 2 Zx1 0 GAðaÞda þZx2 x1þx2 2 GAðaÞda ! þ m 2x2 ¼ p[Tðx1;x2Þ max 2 p0x1þðp0þp1Þx22x1þx2 2  þ m 2x2: Using that p[Tðx1;x2Þ;(i.e., p0þp1þp2¼1 and x1þx2 2p1þp2¼ m ) we have that p[Tðx1;x2Þ max 2 p0x1þðp0þp1Þx22x1þx2 2  þ m 2x2 ¼ p[Tðx1;x2Þ max m 2x2þ2ð12 m þp1ðx1þx2 221ÞÞx1  þð12 m þp1 x1þx2 2Þðx22x1þx2 2Þ ¼ p[Tðx1;x2Þ max m 2x2þ2ð12 m Þx1þx2 22p1x12x1þx2 2  2 ! ! ¼ p[Tðx1;x2Þ max Cðx1;x2;p1Þ; which proves the result. A Lemma A.8 The optimal solution for the problem 0#x1#x2#1 min p[Tðx1;x2Þ max Cðx1;x2;p1Þð25Þ is x1¼ m 2and x2¼2 m 2 m 2;where C and T were defined in (13) and (14), respectively. Proof: Since C(x 1 ,x 2 ,p 1 ) is linear with respect to p 1 , we analyze the cases where the coefficient that multiplies p 1 is positive or negative separately. 120018142_STM_019_001_R1_X0.ald 8/2/2003—KALYAN—59071 Robust Positioning of Service Units 143 829 830 831 832 833 834 835 836 837 838 839 840 841 842 843 844 845 846 847 848 849 850 851 852 853 854 855 856 857 858 859 860 861 862 863 864 865 866 867 868 869 870 871 872 873 874 Case 1: x1$x1þx2 2  2 In this case, the function Cðx1;x2;p1Þis decreasing in p 1 , thus the maximum is reached at p1¼0:That means that p 0 ¼1m and p 2 ¼ m . Therefore, the expression that we have to consider is the following: 0#x1#x2#1 min C1ðx1;x2Þ:¼2ð12 m Þx1þx2 2  2x2þ m ð26Þ s:t:x1$x1þx2 2  2 : It is clear that: › C1ðx1;x2Þ › x1¼12 m $0: Since the function C 1 (x 1 ,x 2 ) is increasing in x 1 and x1$x1þx2 2  2we have that C1ðx1;x2Þ$C1ðt;x2Þ; where t¼tþx2 2  2:Thus, since x2$0;this implies that x2¼2ffiffit p2t(notice that 2 ffiffit p2 t$tfor all t$0).Therefore, solving (26) is equivalent to solving the following problem; x1[½0;1 min 2ð12 m Þffiffiffiffiffi x1 p22ffiffiffiffiffi x1 pþx1þ m ¼x1[½0;1 min x1þð122ffiffiffiffiffi x1 pÞ m ; and this problem reaches its minimum at the point x1¼ m 2:Hence, x2¼2 m 2 m 2and the minimum objective value is m 2 m 2 .A Case 2: x1#x1þx2 2  2 Notice that in Case 1, we have already studied the points (0,0) and (1,1). Therefore, in what follows, we can assume without loss of generality that (x 1 ,x 2 ) is neither (0,0) nor (1,1). In this case, the function C(x 1 ,x 2 ,p 1 ) is increasing in p 1 . Since p[Tðx1;x2Þwe have that p0¼12 m þp1ðx1þx2 221Þ;p2¼ m 2p1x1þx2 2;0#p0#1 and 0 #p2#1 then, we have that, a) 0 #ð12 m Þ2p1ð12x1þx2 2Þ#1;that is, 2 m 12x1þx2 2 #p1#12 m 12x1þx2 2 if ðx1;x2Þ– ð1;1Þ: b) 0 # m 2p1x1þx2 2#1;that is, 212 m x1þx2 2 #p1# m x1þx2 2 if ðx1;x2Þ–ð0;0Þ: Using that p1$0;2 m 12x1þx2 2 #0 and 212 m x1þx2 2 #0 the previous conditions reduce to; a) p1#12 m 12x1þx2 2 b) p1# m x1þx2 2 : Hence, p1#min 12 m 12x1þx2 2 ; m x1þx2 2  and to study this minimum we distinguish two cases; 120018142_STM_019_001_R1_X0.ald 8/2/2003—KALYAN—59071 Puerto and Rodrı ´guez-Chı ´a144 875 876 877 878 879 880 881 882 883 884 885 886 887 888 889 890 891 892 893 894 895 896 897 898 899 900 901 902 903 904 905 906 907 908 909 910 911 912 913 914 915 916 917 918 919 920 .Case 2.1: If x1þx2 2$ m then 12 m 12x1þx2 2 $ m x1þx2 2 ;thus p1# m x1þx2 2 : .Case 2.2: If x1þx2 2# m then 12 m 12x1þx2 2 # m x1þx2 2 ;thus, p1#12 m 12x1þx2 2 : Since the function C(x 1 ,x 2 ,p 1 ) is increasing in p 1 , in Case 2.1. its maximum in p 1 is reached at p1¼ m x1þx2 2 and in Case 2.2 at p1¼12 m 12x1þx2 2 : Hence, to find the maximum of the function C(x 1 ,x 2 ,p 1 ) we have the following two cases: .Case 2.1: p1¼ m x1þx2 2 : .Case 2.2: p1¼12 m 12x1þx2 2 : Case 2.1: p1¼ m x1þx2 2 In this case, Problem (25) reduces to the following optimization problem 0#x1#x2#1 min C2ðx1;x2Þ:¼x1122 m x1þx2 2 ! þ m s:t::x1#x1þx2 2  2 m #x1þx2 2: We obtain that › C2ðx1;x2Þ › x2¼ m x1 x1þx2 2  2$0: Therefore, C 2 (x 1 ,x 2 ) is a increasing function in x 2 . Since in this case, (x 1 ,x 2 ) satisfies that x2$2 m 2x1and x2$2ffiffiffiffiffi x1 p2x1we have that C2ðx1;x2Þ$C2ðx1;tÞ where .t¼2 m 2x1if x1# m 2 .t¼2ffiffiffiffiffi x1 p2x1if x1$ m 2: Thus, a) If x1# m 2we have that x1;x2[½0;1 min C2ðx1;x2Þ¼ x1[½0;1 min m 2x1: b) If x1$ m 2we have that x1;x2[½0;1 min C2ðx1;x2Þ¼ x1[½0;1 min x1122 m ffiffiffiffiffi x1 p  þ m : 120018142_STM_019_001_R1_X0.ald 8/2/2003—KALYAN—59071 Robust Positioning of Service Units 145 921 922 923 924 925 926 927 928 929 930 931 932 933 934 935 936 937 938 939 940 941 942 943 944 945 946 947 948 949 950 951 952 953 954 955 956 957 958 959 960 961 962 963 964 965 966 Both cases give us the same optimal solution x1¼ m 2and x2¼2 m 2 m 2and its objective value is m - m 2 . Case 2.2: p1¼12 m 12x1þx2 2 In this case, Problem (25) reduces to the following optimization problem 0#x1#x2#1 min C3ðx1;x2Þ:¼ x1;x2[½0;1 min x2 12 m 12x1þx2 2 21 ! 2x1 12 m 12x1þx2 2þ m s:t:x1#x1þx2 2  2 m $x1þx2 2: We obtain that, › C3ðx1;x2Þ › x1¼ð12 m Þðx221Þ ð12x1þx2 2Þ2#0: That means that C 3 (x 1 ,x 2 ) is a decreasing function in x 1 . Since, in this case, (x 1 ,x 2 ) satisfies that x1#x1þx2 2  2and m $x1þx2 2;we have that x1# m 2then C3ðx1;x2Þ$C3ð m 2;x2Þ: Thus, taking x 1 ¼ m 2 we have that m $ m 2þx2 2and m 2# m 2þx2 2  2;that is, x2#2 m 2 m 2 and x2$2 m 2 m 2:(Notice that we do not have to consider the other solution x2$ 22 m 2 m 2since 22 m 2 m 2#0 and x2$0). Therefore, x2¼2 m 2 m 2: Since, all the cases give us the same optimal solution, the optimal solution to Problem (25) is x1¼ m 2and x2¼2 m 2 m 2: ACKNOWLEDGMENTS The authors would like to thank the suggestions made by two anonymous referees and the editor who have improved the readability and the final presentation of the paper. This research has been partially financed by Spanish research grants BFM2001-2378 and BFM2001-4028. REFERENCES 1. Anderson, L.R.; Fontenot, R.A. Optimal positioning of service units along a coordinate line. Transportation Sci. 1992,26 (4), 346–351. 120018142_STM_019_001_R1_X0.ald 8/2/2003—KALYAN—59071 Puerto and Rodrı ´guez-Chı ´a146 967 968 969 970 971 972 973 974 975 976 977 978 979 980 981 982 983 984 985 986 987 988 989 990 991 992 993 994 995 996 997 998 999 1000 1001 1002 1003 1004 1005 1006 1007 1008 1009 1010 1011 1012 2. Carrizosa, E.; Mun ˜oz-Ma ´rquez, M.; Puerto, J. A note on the optimal positioning of service units. Oper. Res. 1998,46 (1), 155–156. 3. Flury, B.A. Principal points. Biometrika 1990,77 (1), 33–41. 4. Gallego, G. A minmax distribution free procedure for the (Q,R) inventory model. Oper. Res. Lett. 1992,11, 55–60. 5. Larson, R.; Odoni, A. Urban Operations Research; Prentice-Hall Englewood Cliffs: New Jersey, 1981. 6. Levine, A. A patrol problem. Math. Mag. 1986,59, 159–166. 7. De Palma, A.; Liu, Q.; Thisse, J.F. Optimal location on a line with random utilities. Transportation Sci. 1994,28 (1), 63–69. 8. Puerto, J.; Ferna ´ndez, F.R. Pareto-optimality in classical inventory problems. Naval Res. Logistic 1998,45, 83–98. 9. Smith, D.K. Police patrol policies on motorways with unequal patrol lengths. J. Oper. Res. Soc. 1997,48, 996–1000. 10. Vickson, R.G.; Gerchak, Y.; Rotem, D. Optimal positioning of read/write head in mirrored disks. Location Sci. 1995,3(2), 125–132. Received April 20, 1999 Revised April 18, 2000 Accepted October 1, 2002 120018142_STM_019_001_R1_X0.ald 8/2/2003—KALYAN—59071 Robust Positioning of Service Units 147 1013 1014 1015 1016 1017 1018 1019 1020 1021 1022 1023 1024 1025 1026 1027 1028 1029 1030 1031 1032 1033 1034 1035 1036 1037 1038 1039 1040 1041 1042 1043 1044 1045 1046 1047 1048 1049 1050 1051 1052 1053 1054 1055 1056 1057 1058