University of California Transportation Center
UCTC Research Paper No. UCTC- 2010- 02
Reliable Facility Location Design under the Risk of Disruptions
Tingting Cui,
University of California, Berkeley,
Yanfeng Ouyang,
University of Illinois at Urbana- Champaign, and
Zuo- Jun Max Shen,
University of California, Berkeley
2010
S u b m i t t e d t o O p e r a t i o n s R e s e a r c h
R e l i a b l e F a c i l i t y L o c a t i o n D e s i g n u n d e r t h e R i s k o f
D i s r u p t i o n s
T i n g t i n g C u i
D e p a r t m e n t o f I n d u s t r i a l E n g i n e e r i n g a n d O p e r a t i o n s R e s e a r c h , U n i v e r s i t y o f C a l i f o r n i a , B e r k e l e y , C A 9 4 7 2 0
t i n g t i n g @ i e o r . b e r k e l e y . e d u
Y a n f e n g O u y a n g
D e p a r t m e n t o f C i v i l a n d E n v i r o n m e n t a l E n g i n e e r i n g , U n i v e r s i t y o f I l l i n o i s a t U r b a n a - C h a m p a i g n , U r b a n a , I L 6 1 8 0 1
y f o u y a n g @ i l l i n o i s . e d u
Z u o - J u n M a x S h e n
D e p a r t m e n t o f I n d u s t r i a l E n g i n e e r i n g a n d O p e r a t i o n s R e s e a r c h , U n i v e r s i t y o f C a l i f o r n i a , B e r k e l e y , C A 9 4 7 2 0
s h e n @ i e o r . b e r k e l e y . e d u
R e l i a b l e f a c i l i t y l o c a t i o n m o d e l s c o n s i d e r u n e x p e c t e d f a i l u r e s w i t h s i t e - d e p e n d e n t p r o b a b i l i t i e s , a s w e l l a s
p o s s i b l e c u s t o m e r r e a s s i g n m e n t . T h i s p a p e r p r o p o s e s a c o m p a c t m i x e d i n t e g e r p r o g r a m ( M I P ) f o r m u l a t i o n
a n d a c o n t i n u u m a p p r o x i m a t i o n ( C A ) m o d e l t o s t u d y t h e r e l i a b l e u n c a p a c i t a t e d ¯ x e d c h a r g e l o c a t i o n p r o b -
l e m ( R U F L ) w h i c h s e e k s t o m i n i m i z e i n i t i a l s e t u p c o s t s a n d e x p e c t e d t r a n s p o r t a t i o n c o s t s i n n o r m a l a n d
f a i l u r e s c e n a r i o s .
T h e M I P d e t e r m i n e s t h e o p t i m a l f a c i l i t y l o c a t i o n s a s w e l l a s t h e o p t i m a l c u s t o m e r a s s i g n m e n t s , a n d t h e
M I P i s s o l v e d u s i n g a c u s t o m - d e s i g n e d L a g r a n g i a n R e l a x a t i o n ( L R ) a l g o r i t h m . T h e C A m o d e l p r e d i c t s t h e
t o t a l s y s t e m c o s t w i t h o u t d e t a i l s a b o u t f a c i l i t y l o c a t i o n s a n d c u s t o m e r a s s i g n m e n t s , a n d i t p r o v i d e s a f a s t
h e u r i s t i c t o ¯ n d n e a r - o p t i m u m s o l u t i o n s . O u r c o m p u t a t i o n a l r e s u l t s s h o w t h a t t h e L R a l g o r i t h m i s e ± c i e n t
f o r m i d - s i z e d R U F L p r o b l e m s a n d t h a t t h e C A s o l u t i o n s a r e c l o s e t o o p t i m a l i n m o s t o f t h e t e s t i n s t a n c e s .
F o r l a r g e - s c a l e p r o b l e m s , t h e C A m e t h o d i s a g o o d a l t e r n a t i v e t o t h e L R a l g o r i t h m t h a t a v o i d s p r o h i b i t i v e l y
l o n g r u n n i n g t i m e s .
K e y w o r d s : f a c i l i t y l o c a t i o n , r e l i a b i l i t y , m i x e d i n t e g e r p r o g r a m , L a g r a n g i a n r e l a x a t i o n , h e u r i s t i c s ,
c o n t i n u u m a p p r o x i m a t i o n
1 . I n t r o d u c t i o n
T h e c l a s s i c u n c a p a c i t a t e d ¯ x e d c h a r g e l o c a t i o n p r o b l e m ( U F L ) s e l e c t s f a c i l i t y l o c a t i o n s a n d c u s -
t o m e r a s s i g n m e n t s i n o r d e r t o b a l a n c e t h e t r a d e - o ® b e t w e e n i n i t i a l s e t u p c o s t s a n d d a y - t o - d a y
t r a n s p o r t a t i o n c o s t s . H o w e v e r , s o m e o f t h e c o n s t r u c t e d f a c i l i t i e s m a y b e c o m e u n a v a i l a b l e d u e t o
d i s r u p t i o n s c a u s e d b y n a t u r a l d i s a s t e r s , t e r r o r i s t a t t a c k s o r l a b o r s t r i k e s . W h e n a f a c i l i t y f a i l u r e
1
C u i , O u y a n g , a n d S h e n : R e l i a b l e F a c i l i t y L o c a t i o n D e s i g n
2 A r t i c l e s u b m i t t e d t o O p e r a t i o n s R e s e a r c h ; m a n u s c r i p t n o . ( P l e a s e , p r o v i d e t h e m a n s u c r i p t n u m b e r ! )
F i g u r e 1 U F L s o l u t i o n t o 4 9 - d a t a s e t
o c c u r s , c u s t o m e r s m a y h a v e t o b e r e a s s i g n e d f r o m t h e i r o r i g i n a l f a c i l i t i e s t o o t h e r s t h a t r e q u i r e
h i g h e r t r a n s p o r t a t i o n c o s t s . I n t h i s p a p e r w e p r e s e n t f a c i l i t y l o c a t i o n m o d e l s t h a t m i n i m i z e n o r m a l
c o n s t r u c t i o n a n d t r a n s p o r t a t i o n c o s t s a s w e l l a s h e d g e a g a i n s t f a c i l i t y f a i l u r e s w i t h i n t h e s y s t e m .
T h e r e l i a b l e l o c a t i o n m o d e l w a s ¯ r s t i n t r o d u c e d b y S n y d e r a n d D a s k i n ( 3 7 ) t o h a n d l e f a c i l i t y
d i s r u p t i o n . T h e i r m o t i v a t i n g e x a m p l e i s a s f o l l o w s . C o n s i d e r a s u p p l y n e t w o r k t h a t s e r v e s 4 9 c i t i e s ,
c o n s i s t i n g o f a l l s t a t e c a p i t a l s o f t h e c o n t i n e n t a l U n i t e d S t a t e s a n d W a s h i n g t o n , D C . D e m a n d s a r e
p r o p o r t i o n a l t o t h e 1 9 9 0 s t a t e p o p u l a t i o n s a n d t h e ¯ x e d c o s t s a r e p r o p o r t i o n a l t o t h e m e d i a n h o u s e
p r i c e s . T h e o p t i m a l U F L s o l u t i o n f o r t h i s p r o b l e m i s s h o w n i n F i g u r e 1 . T h i s s o l u t i o n h a s a ¯ x e d
c o s t o f $ 3 4 8 , 0 0 0 a n d a t r a n s p o r t a t i o n c o s t o f $ 5 0 9 , 0 0 0 ( a t $ 0 . 0 0 0 0 1 p e r m i l e p e r u n i t o f d e m a n d ) .
H o w e v e r , i f t h e f a c i l i t y i n S a c r a m e n t o , C A f a i l e d , c u s t o m e r s f r o m t h e e n t i r e w e s t - c o a s t r e g i o n w o u l d
h a v e t o g e t s e r v i c e f r o m t h e f a c i l i t i e s i n S p r i n g ¯ e l d , I L a n d A u s t i n T X , w h i c h w o u l d i n c r e a s e t h e
t r a n s p o r t a t i o n c o s t t o $ 1 , 0 8 1 , 0 0 0 ( 1 1 2 % ) . T a b l e 1 l i s t s t h e \ f a i l u r e c o s t " , t h e t r a n s p o r t a t i o n c o s t
a s s o c i a t e d w i t h e a c h f a c i l i t y f a i l u r e .
L o c a t i o n F a i l u r e C o s t % I n c r e a s e
S a c r a m e n t o , C A 1 , 0 8 1 , 2 2 9 1 1 2 %
H a r r i s b u r g , P A 9 1 7 , 3 3 2 8 0 %
S p r i n g ¯ e l d , I L 6 9 6 , 9 4 7 3 7 %
M o n t g o m e r y , A L 6 3 9 , 6 3 1 2 6 %
A u s t i n , T X 6 3 6 , 8 5 8 2 5 %
T r a n s p . c o s t w / o f a i l u r e s 5 0 8 , 8 5 8 0 %
T a b l e 1 F a i l u r e c o s t s o f U F L s o l u t i o n
C u i , O u y a n g , a n d S h e n : R e l i a b l e F a c i l i t y L o c a t i o n D e s i g n
A r t i c l e s u b m i t t e d t o O p e r a t i o n s R e s e a r c h ; m a n u s c r i p t n o . ( P l e a s e , p r o v i d e t h e m a n s u c r i p t n u m b e r ! ) 3
F i g u r e 2 A m o r e r e l i a b l e s o l u t i o n
S n y d e r a n d D a s k i n ( 3 7 ) s u g g e s t e d t h a t l o c a t i n g f a c i l i t i e s i n t h e c a p i t a l s o f C A , N Y , T X , P A ,
O H , A L , O R , a n d I A ( F i g u r e 2 ) i s a m o r e r e l i a b l e s o l u t i o n . I n t h i s s o l u t i o n , t h e m a x i m u m f a i l u r e
c o s t i s r e d u c e d t o $ 5 0 0 , 2 1 6 , l e s s t h a n t h e s m a l l e s t f a i l u r e c o s t i n T a b l e 1 . H o w e v e r , t h r e e a d d i t i o n a l
f a c i l i t i e s a r e u s e d i n t h i s s o l u t i o n r e s u l t i n g i n a t o t a l l o c a t i o n a n d d a y - t o - d a y t r a n s p o r t a t i o n c o s t
o f $ 9 1 9 , 2 9 8 - a 7 . 2 5 % i n c r e a s e f r o m t h e U F L o p t i m a l s o l u t i o n .
R e a l i s t i c a l l y , n o c o m p a n y w o u l d a c c e p t a s u p p l y n e t w o r k w i t h h i g h n o r m a l o p e r a t i n g c o s t s j u s t
t o h e d g e a g a i n s t v e r y r a r e f a c i l i t y d i s r u p t i o n s . I n o r d e r t o b a l a n c e t h e t r a d e - o ® b e t w e e n n o r m a l
o p e r a t i n g c o s t s a n d f a i l u r e c o s t s , t h e n e t w o r k s t r u c t u r e s h o u l d d e p e n d o n h o w l i k e l y t h e c a n d i d a t e
s i t e s m a y g e t d i s r u p t e d , a s w e l l a s t h e i r c l o s e n e s s t o t h e p o t e n t i a l c u s t o m e r s . I n S n y d e r a n d D a s k i n
( 3 7 ) , a l l f a c i l i t y l o c a t i o n s a r e a s s u m e d t o h a v e i d e n t i c a l f a i l u r e p r o b a b i l i t i e s , w h i c h m i g h t n o t b e
v e r y r e p r e s e n t a t i v e o f p r a c t i c a l s i t u a t i o n s . L e t u s i l l u s t r a t e h o w s i t e - d e p e n d e n t f a i l u r e p r o b a b i l i t i e s
i m p a c t t h e c h o i c e o f f a c i l i t y l o c a t i o n s . S p e c i ¯ c a l l y , s u p p o s e t h a t t h e f a c i l i t i e s a r e v u l n e r a b l e t o
h u r r i c a n e r e l a t e d d i s a s t e r s . F a c i l i t i e s l o c a t e d i n t h e G u l f c o a s t a r e a ( T X , L A , M S , A L a n d F L ) a l l
h a v e a 1 0 % c h a n c e o f d i s r u p t i o n , w h i l e o t h e r p o t e n t i a l s i t e s h a v e a m u c h l o w e r f a i l u r e p r o b a b i l i t y
o f 0 . 1 % . I t i s c o s t e ± c i e n t h e r e t o h e d g e a g a i n s t d i s r u p t i o n b y l o c a t i n g f a c i l i t i e s i n t h e c a p i t a l s o f
C A , P A , I L , G A a n d O K ( F i g u r e 3 ) . I n t h i s s o l u t i o n , t h e t w o f a c i l i t i e s a l o n g t h e G u l f c o a s t ( T X
a n d A L ) a r e m o v e d t o a d j a c e n t \ s a f e r " l o c a t i o n s . A l t h o u g h t h e f a i l u r e c o s t s o f C A a n d P A a r e
h i g h , w e c h o o s e n o t t o b u i l d \ b a c k u p " f a c i l i t i e s f o r t h e m b e c a u s e t h e i r p r o b a b i l i t y o f d i s r u p t i o n
C u i , O u y a n g , a n d S h e n : R e l i a b l e F a c i l i t y L o c a t i o n D e s i g n
4 A r t i c l e s u b m i t t e d t o O p e r a t i o n s R e s e a r c h ; m a n u s c r i p t n o . ( P l e a s e , p r o v i d e t h e m a n s u c r i p t n u m b e r ! )
F i g u r e 3 A c o s t e ± c i e n t s o l u t i o n
i s s o s m a l l . T h e e x p e c t e d f a i l u r e c o s t i n t h i s s o l u t i o n i s a b o u t $ 4 , 0 0 0 , c o m p a r e d t o $ 1 3 0 , 3 4 4 i n
t h e U F L o p t i m a l s o l u t i o n i n F i g u r e 1 , a n d t h e l o c a t i o n a n d d a y - t o - d a y t r a n s p o r t a t i o n c o s t s a r e
i n c r e a s e d b y o n l y 3 . 6 % . T a b l e 2 c o m p a r e s t h e n o r m a l o p e r a t i n g c o s t s a n d t h e e x p e c t e d f a i l u r e c o s t s
o f t h e t h r e e s o l u t i o n s .
S o l u t i o n 1
L o c a t i o n F a i l u r e C o s t F a i l u r e P r o b a b i l i t y E x p e c t e d C o s t
S a c r a m e n t o , C A 1 , 0 8 1 , 2 2 9 0 . 0 0 1 1 , 0 8 1
H a r r i s b u r g , P A 9 1 7 , 3 3 2 0 . 0 0 1 9 1 7
S p r i n g ¯ e l d , I L 6 9 6 , 9 4 7 0 . 0 0 1 6 9 7
M o n t g o m e r y , A L 6 3 9 , 6 3 1 0 . 1 6 3 , 9 6 3
A u s t i n , T X 6 3 6 , 8 5 8 0 . 1 6 3 , 6 8 6
E x p e c t e d f a i l u r e c o s t 1 3 0 , 3 4 4
N o r m a l o p e r a t i n g c o s t 8 5 7 , 1 2 8
S o l u t i o n 2
L o c a t i o n F a i l u r e C o s t F a i l u r e P r o b a b i l i t y E x p e c t e d C o s t
S a c r a m e n t o , C A 5 0 0 , 2 1 6 0 . 0 0 1 5 0 0
A l b a n y , N Y 4 1 9 , 0 8 7 0 . 0 0 1 4 1 9
A u s t i n , T X 4 7 6 , 3 7 4 0 . 1 4 7 , 6 3 7
H a r r i s b u r g , P A 4 0 9 , 3 8 3 0 . 0 0 1 4 0 9
C o l u m b u s , O H 4 3 4 , 1 7 2 0 . 0 0 1 4 3 4
M o n t g o m e r y , A L 4 7 4 , 6 4 0 0 . 1 4 7 , 4 6 4
S a l e m , O R 3 8 9 , 4 8 4 0 . 0 0 1 3 8 9
D e s M o i n e s , I A 4 5 2 , 3 0 5 0 . 0 0 1 4 5 2
E x p e c t e d f a i l u r e c o s t 9 7 , 7 0 6
N o r m a l o p e r a t i n g c o s t 9 1 9 , 2 9 8
S o l u t i o n 3
L o c a t i o n F a i l u r e C o s t F a i l u r e P r o b a b i l i t y E x p e c t e d C o s t
S a c r a m e n t o , C A 1 , 0 5 8 , 2 2 6 0 . 0 0 1 1 , 0 5 8
H a r r i s b u r g , P A 9 0 8 , 6 7 2 0 . 0 0 1 9 0 9
S p r i n g ¯ e l d , I L 6 8 1 , 7 8 6 0 . 0 0 1 6 8 2
A t l a n t a , G A 6 7 9 , 0 2 2 0 . 0 0 1 6 7 9
O k l a h o m a C i t y , O K 6 6 0 , 9 8 5 0 . 0 0 1 6 6 1
E x p e c t e d f a i l u r e c o s t 3 , 9 8 9
N o r m a l o p e r a t i n g c o s t 8 8 8 , 0 0 9
T a b l e 2 C o m p a r i s o n s o f t h e n o r m a l o p e r a t i n g c o s t s a n d t h e e x p e c t e d f a i l u r e c o s t s
C u i , O u y a n g , a n d S h e n : R e l i a b l e F a c i l i t y L o c a t i o n D e s i g n
A r t i c l e s u b m i t t e d t o O p e r a t i o n s R e s e a r c h ; m a n u s c r i p t n o . ( P l e a s e , p r o v i d e t h e m a n s u c r i p t n u m b e r ! ) 5
I n t h i s p a p e r , w e s e e k t o d e s i g n s u p p l y n e t w o r k s t h a t a r e b o t h r e l i a b l e a n d c o s t e ± c i e n t . W e
m i n i m i z e t h e e x p e c t e d t r a n s p o r t a t i o n c o s t s i n b o t h t h e r e g u l a r a n d t h e f a i l u r e s c e n a r i o s ( p l u s t h e
¯ x e d c o n s t r u c t i o n c o s t s ) t o b a l a n c e t h e t r a d e - o ® b e t w e e n n o r m a l a n d e m e r g e n c y o p e r a t i n g c o s t s .
T h e f a i l u r e o f e a c h f a c i l i t y s i t e i s a s s u m e d t o b e i n d e p e n d e n t a n d t h e p r o b a b i l i t y i s t a k e n a s a
p r i o r . U n l i k e i n S n y d e r a n d D a s k i n ( 3 7 ) , t h e f a i l u r e p r o b a b i l i t i e s a r e a l l o w e d t o b e s i t e - d e p e n d e n t .
T h e f a c i l i t y l o c a t i o n d e c i s i o n s a n d c u s t o m e r a s s i g n m e n t s a r e m a d e a t t h e ¯ r s t s t a g e , b e f o r e a n y
f a i l u r e s o c c u r . E a c h c u s t o m e r c a n b e a s s i g n e d t o u p t o R ¸ 1 f a c i l i t i e s t o h e d g e a g a i n s t f a i l u r e s .
A f t e r a n y d i s r u p t i o n s o c c u r , e a c h c u s t o m e r i s s e r v e d b y h e r c l o s e s t a s s i g n e d o p e r a t i n g f a c i l i t y ; i f
a l l h e r a s s i g n e d f a c i l i t i e s h a v e f a i l e d t h e n a p e n a l t y c o s t i s c h a r g e d . W e f e e l t h a t i t i s r e a s o n a b l e
t o r e s t r i c t e a c h c u s t o m e r ' s f a c i l i t y a s s i g n m e n t s t o a p r e - d e t e r m i n e d s u b s e t o f a l l o p e n f a c i l i t i e s . I n
r e a l i t y a c u s t o m e r m a y n o t b e a b l e t o g e t s e r v i c e f r o m a l l f a c i l i t i e s d u e t o s y s t e m c o m p a t i b i l i t y ,
l i m i t e d c a p a c i t y , o r s i m p l y e x c e s s i v e t r a n s p o r t a t i o n c o s t s . O u r c o m p u t a t i o n a l r e s u l t s i n d i c a t e t h a t
t h e c h o i c e o f R h a s n o s i g n i ¯ c a n t i m p a c t o n t h e n e t w o r k s t r u c t u r e o f t h e o p t i m a l s o l u t i o n s .
I n t h e s e q u e l w e p r e s e n t t w o d i s t i n c t m o d e l s t o a d d r e s s t h e r e l i a b l e f a c i l i t y l o c a t i o n p r o b l e m {
o n e d i s c r e t e a n d t h e o t h e r c o n t i n u o u s . O u r d i s c r e t e m o d e l i s a l i n e a r m i x e d i n t e g e r p r o g r a m ( M I P )
t h a t c o m p u t e s t h e o p t i m a l f a c i l i t y l o c a t i o n s a n d c u s t o m e r a s s i g n m e n t s . U n l i k e m o s t s c e n a r i o - b a s e d
s t o c h a s t i c p r o g r a m m i n g f o r m u l a t i o n s t h a t r e q u i r e e x p o n e n t i a l l y m a n y v a r i a b l e a n d c o n s t r a i n t s ,
o u r M I P f o r m u l a t i o n i s p o l y n o m i a l i n t h e n u m b e r o f c a n d i d a t e s i t e s . T h e M I P i s s o l v e d e ± c i e n t l y
u s i n g a c u s t o m - d e s i g n e d L a g r a n g i a n R e l a x a t i o n ( L R ) a l g o r i t h m . H o w e v e r , d u e t o t h e c o m p l e x i t y
o f t h e u n d e r l y i n g p r o b l e m , t h e c o m p u t a t i o n a l c o s t o f t h i s m e t h o d f o r l a r g e p r o b l e m i n s t a n c e s c a n
b e e x c e s s i v e , a n d v e r y f e w i n s i g h t s c a n b e d r a w n f r o m t h e n u m e r i c a l s o l u t i o n s . T h u s , w e d e v e l o p a
c o n t i n u u m a p p r o x i m a t i o n ( C A ) m o d e l w h i c h p r e d i c t s t h e t o t a l s y s t e m c o s t w i t h o u t t h e d e t a i l s o f
f a c i l i t y l o c a t i o n s a n d c u s t o m e r a s s i g n m e n t s . M a n a g e r i a l i n s i g h t s ( e . g . , h o w t h e s o l u t i o n v a r i e s a s
k e y p a r a m e t e r s c h a n g e ) c a n b e d r a w n d i r e c t l y f r o m t h e C A m o d e l . I n a d d i t i o n , t h e C A a p p r o a c h
c a n b e u s e d a s a h e u r i s t i c t o ¯ n d n e a r - o p t i m a l s o l u t i o n s .
T h e r e m a i n d e r o f t h i s p a p e r i s o r g a n i z e d a s f o l l o w s . W e r e v i e w l i t e r a t u r e o n f a c i l i t y l o c a t i o n i n
S e c t i o n 2 . I n S e c t i o n 3 , w e f o r m u l a t e t h e r e l i a b l e f a c i l i t y l o c a t i o n p r o b l e m a s a l i n e a r m i x e d - i n t e g e r
C u i , O u y a n g , a n d S h e n : R e l i a b l e F a c i l i t y L o c a t i o n D e s i g n
6 A r t i c l e s u b m i t t e d t o O p e r a t i o n s R e s e a r c h ; m a n u s c r i p t n o . ( P l e a s e , p r o v i d e t h e m a n s u c r i p t n u m b e r ! )
p r o g r a m ( M I P ) a n d p r o v i d e a L a g r a n g i a n r e l a x a t i o n a l g o r i t h m . S e c t i o n 4 i n t r o d u c e s t h e c o n t i n u u m
a p p r o x i m a t i o n ( C A ) m o d e l . C o m p u t a t i o n a l r e s u l t s f o r b o t h t h e d i s c r e t e a n d t h e C A m o d e l s a r e
d i s c u s s e d i n S e c t i o n 5 . S e c t i o n 6 c o n c l u d e s t h e p a p e r a n d d i s c u s s e s f u t u r e r e s e a r c h .
2 . L i t e r a t u r e R e v i e w
T h e e x t e n s i v e l i t e r a t u r e o n f a c i l i t y l o c a t i o n d a t e s b a c k t o i t s o r i g i n a l f o r m u l a t i o n i n 1 9 0 9 a n d t h e
W e b e r p r o b l e m ( 3 9 ) . T r a d i t i o n a l l y , f a c i l i t y l o c a t i o n p r o b l e m s a r e m o d e l e d a s d i s c r e t e o p t i m i z a t i o n
p r o b l e m s a n d s o l v e d w i t h m a t h e m a t i c a l p r o g r a m m i n g t e c h n i q u e s . D a s k i n ( 1 5 ) a n d D r e z n e r ( 1 6 )
p r o v i d e g o o d i n t r o d u c t i o n s t o a n d s u r v e y s o f t h i s t o p i c .
R e c e n t l y , r e l i a b i l i t y i s s u e s i n s u p p l y c h a i n d e s i g n a r e o f p a r t i c u l a r i n t e r e s t . M o s t o f t h e e x i s t i n g
l i t e r a t u r e f o c u s e s o n f a c i l i t y c o n g e s t i o n s f r o m s t o c h a s t i c d e m a n d . D a s k i n ( 1 3 , 1 4 ) , B a l l a n d L i n
( 2 ) , R e V e l l e a n d H o g a n ( 3 5 ) , a n d B a t t a e t . a l . ( 3 ) a l l a t t e m p t e d t o i n c r e a s e t h e s y s t e m a v a i l a b i l i t y
t h r o u g h r e d u n d a n t c o v e r a g e .
F o c u s o n s y s t e m f a i l u r e s d u e t o f a c i l i t y d i s r u p t i o n s i n s u p p l y c h a i n d e s i g n i s g a i n i n g a t t e n t i o n
r e c e n t l y ( 3 3 , 3 4 ) . I n t h e t r a d i t i o n a l l o c a t i o n a l a n a l y s i s l i t e r a t u r e , S n y d e r a n d D a s k i n ( 3 7 ) p r o p o s e
a n i m p l i c i t f o r m u l a t i o n o f t h e s t o c h a s t i c P - m e d i a n a n d ¯ x e d - c h a r g e p r o b l e m s b a s e d o n l e v e l a s s i g n -
m e n t s , w h e r e t h e c a n d i d a t e s i t e s a r e s u b j e c t t o r a n d o m d i s r u p t i o n s w i t h e q u a l p r o b a b i l i t y . W o r k
b y Z h a n e t . a l . ( 4 0 ) a n d B e r m a n e t a l . ( 4 ) r e l a x t h e a s s u m p t i o n o f u n i f o r m f a i l u r e p r o b a b i l i t i e s .
Z h a n e t . a l . f o r m u l a t e t h e s t o c h a s t i c ¯ x e d - c h a r g e d p r o b l e m a s a n o n l i n e a r m i x e d i n t e g e r p r o g r a m
a n d p r o v i d e s s e v e r a l h e u r i s t i c s o l u t i o n a l g o r i t h m s . B e r m a n e t a l . f o c u s o n a n a s y m p t o t i c p r o p e r t y
o f t h e p r o b l e m . T h e y p r o v e t h a t t h e s o l u t i o n t o t h e s t o c h a s t i c P - m e d i a n p r o b l e m c o i n c i d e s w i t h
t h e d e t e r m i n i s t i c p r o b l e m a s t h e f a i l u r e p r o b a b i l i t i e s a p p r o a c h z e r o . T h e y a l s o p r o p o s e h e u r i s t i c s
w i t h b o u n d s o n t h e w o r s t - c a s e p e r f o r m a n c e .
A l l o f t h e a b o v e l i t e r a t u r e i s b a s e d o n d i s c r e t e o p t i m i z a t i o n . M o s t o f t h e d i s c r e t e l o c a t i o n m o d e l s
a r e N P - h a r d a n d t h u s i t i s d i ± c u l t t o o b t a i n g o o d s o l u t i o n s f o r l a r g e p r o b l e m i n s t a n c e s w i t h i n a
l i m i t e d t i m e f r a m e . T h i s f a c t m o t i v a t e s r e s e a r c h o n t h e c o n t i n u u m a p p r o x i m a t i o n ( C A ) m e t h o d
a s a n a l t e r n a t i v e t o s o l v i n g l a r g e - s c a l e f a c i l i t y l o c a t i o n p r o b l e m s . B u i l d i n g o n t h e e a r l i e r w o r k
C u i , O u y a n g , a n d S h e n : R e l i a b l e F a c i l i t y L o c a t i o n D e s i g n
A r t i c l e s u b m i t t e d t o O p e r a t i o n s R e s e a r c h ; m a n u s c r i p t n o . ( P l e a s e , p r o v i d e t h e m a n s u c r i p t n u m b e r ! ) 7
i n N e w e l l ( 2 8 , 2 9 ) a n d D a g a n z o ( 7 , 8 ) , D a g a n z o a n d N e w e l l ( 9 ) p r o p o s e a C A a p p r o a c h f o r t h e
t r a d i t i o n a l f a c i l i t y l o c a t i o n p r o b l e m . W h i l e c o n d i t i o n s a r e s l o w l y - v a r y i n g , t h e c o s t o f s e r v i n g t h e
d e m a n d n e a r a f a c i l i t y l o c a t i o n i s f o r m u l a t e d a s a f u n c t i o n o f a c o n t i n u o u s f a c i l i t y d e n s i t y ( n u m b e r
o f f a c i l i t i e s p e r u n i t a r e a ) t h a t c a n b e e ± c i e n t l y o p t i m i z e d i n a p o i n t - w i s e w a y . N o t e t h a t t h e
i n v e r s e o f f a c i l i t y d e n s i t y i s t h e i n ° u e n c e a r e a s i z e ( a r e a p e r f a c i l i t y ) . T h e o p t i m i z a t i o n y i e l d s t h e
d e s i r e d f a c i l i t y d e n s i t y a n d i n ° u e n c e a r e a s i z e n e a r e a c h c a n d i d a t e l o c a t i o n , w h i c h i n f o r m s t h e
d e s i g n o f d i s c r e t e f a c i l i t y l o c a t i o n s . I t i s s h o w n i n v a r i o u s c o n t e x t s t h a t t h e C A a p p r o a c h g i v e s
g o o d a p p r o x i m a t e s o l u t i o n s t o l a r g e - s c a l e l o g i s t i c s p r o b l e m s b y f o c u s i n g o n k e y p h y s i c a l i s s u e s
s u c h a s t h e f a c i l i t y s i z e a n d d e m a n d d i s t r i b u t i o n ( 2 1 , 2 2 , 2 3 , 5 , 6 , 1 0 , 1 2 ) . S e e L a n g e v i n e t a l .
( 2 6 ) a n d D a g a n z o ( 1 1 ) f o r r e v i e w s o f t h e C A m o d e l . O u y a n g a n d D a g a n z o ( 3 1 ) a n d O u y a n g ( 3 2 )
p r o p o s e m e t h o d s t o e ± c i e n t l y t r a n s f o r m o u t p u t f r o m t h e C A m o d e l i n t o d i s c r e t e d e s i g n s t r a t e g i e s .
T h e f o r m e r r e f e r e n c e a l s o a n a l y t i c a l l y v a l i d a t e s t h e C A m e t h o d f o r t h e t r a d i t i o n a l f a c i l i t y l o c a t i o n
p r o b l e m . R e c e n t l y , L i m e t a l . ( 2 7 ) p r o p o s e a r e l i a b i l i t y C A m o d e l f o r f a c i l i t y l o c a t i o n p r o b l e m s
w i t h u n i f o r m c u s t o m e r d e n s i t y . F o r s i m p l i ¯ c a t i o n , a s p e c i ¯ c t y p e o f f a i l u r e - p r o o f f a c i l i t y i s a s s u m e d
t o e x i s t ; a c u s t o m e r i s a l w a y s r e - a s s i g n e d t o a f a i l u r e - p r o o f f a c i l i t y a f t e r i t s n e a r e s t r e g u l a r f a c i l i t y
f a i l s , r e g a r d l e s s o f o t h e r ( a n d n e a r e r ) r e g u l a r f a c i l i t i e s . W e r e l a x t h e s e r a t h e r s t r o n g a s s u m p t i o n s
i n o u r w o r k .
3 . T h e D i s c r e t e M o d e l
I n t h i s s e c t i o n w e f o r m u l a t e t h e d i s c r e t e m o d e l t h a t m i n i m i z e s t h e s u m o f t h e n o r m a l o p e r a t i n g
c o s t a n d t h e e x p e c t e d f a i l u r e c o s t . W e ¯ r s t s h o w h o w t h i s p r o b l e m c a n b e f o r m u l a t e d a s a n M I P
a n d t h e n d e v e l o p a L a g r a n g i a n r e l a x a t i o n a l g o r i t h m t o e ± c i e n t l y s o l v e t h e p r o b l e m .
3 . 1 . F o r m u l a t i o n
D e ¯ n e I t o b e t h e s e t o f c u s t o m e r s , i n d e x e d b y i , a n d J t o b e t h e s e t o f c a n d i d a t e f a c i l i t y l o c a t i o n s ,
i n d e x e d b y j . F o r t h e e a s e o f n o t a t i o n , w e a l s o u s e I a n d J t o i n d i c a t e t h e c a r d i n a l i t i e s o f t h e s e t s .
E a c h c u s t o m e r i 2 I h a s a d e m a n d r a t e o f ¸ i . T h e c o s t t o s h i p a u n i t o f d e m a n d f r o m f a c i l i t y j 2 J
t o c u s t o m e r i 2 I i s d e n o t e d b y d i j . A s s o c i a t e d w i t h e a c h f a c i l i t y j 2 J a r e t h e ¯ x e d l o c a t i o n c o s t
C u i , O u y a n g , a n d S h e n : R e l i a b l e F a c i l i t y L o c a t i o n D e s i g n
8 A r t i c l e s u b m i t t e d t o O p e r a t i o n s R e s e a r c h ; m a n u s c r i p t n o . ( P l e a s e , p r o v i d e t h e m a n s u c r i p t n u m b e r ! )
f j a n d t h e p r o b a b i l i t y o f f a i l u r e 0 · q j < 1 . T h e e v e n t s o f f a c i l i t y d i s r u p t i o n s a r e a s s u m e d t o b e
i n d e p e n d e n t .
E a c h c u s t o m e r i s a s s i g n e d t o u p t o R ¸ 1 f a c i l i t i e s , a n d c a n b e s e r v i c e d b y t h e s e a n d o n l y t h e s e
f a c i l i t i e s . T h e r e i s a c o s t Á i a s s o c i a t e d w i t h e a c h c u s t o m e r i 2 I t h a t r e p r e s e n t s t h e p e n a l t y c o s t
o f n o t s e r v i n g t h e c u s t o m e r p e r u n i t o f m i s s e d d e m a n d . T h i s c o s t m a y b e i n c u r r e d e v e n i f s o m e o f
h e r a s s i g n e d f a c i l i t i e s a r e s t i l l o n l i n e , g i v e n t h a t Á i i s l e s s t h a n t h e c o s t o f s e r v i n g i v i a a n y o f t h e s e
f a c i l i t i e s . T h i s r u l e i s m o d e l e d u s i n g a n \ e m e r g e n c y " f a c i l i t y , i n d e x e d b y j = J , t h a t h a s ¯ x e d c o s t
f J = 0 , f a i l u r e p r o b a b i l i t y q J = 0 a n d t r a n s p o r t a t i o n c o s t d i J = Á i f o r c u s t o m e r i 2 I .
T h e v a r i a b l e s u s e d i n t h i s m o d e l a r e t h e l o c a t i o n v a r i a b l e s ( X ) , t h e a s s i g n m e n t v a r i a b l e s ( Y )
a n d t h e p r o b a b i l i t y v a r i a b l e s ( P ) :
X j = ½ 1 ; i f a f a c i l i t y j i s o p e n
0 ; o t h e r w i s e
Y i j r = ½ 1 ; i f f a c i l i t y j i s a s s i g n e d t o c u s t o m e r i a t l e v e l r
0 ; o t h e r w i s e
P i j r = p r o b a b i l i t y t h a t f a c i l i t y j s e r v e s c u s t o m e r i a t l e v e l r :
W e e m p l o y t h e m o d e l i n g t e c h n i q u e s i n t r o d u c e d b y S n y d e r a n d D a s k i n ( 3 7 ) f o r a s s i g n i n g c u s -
t o m e r s t o f a c i l i t i e s a t m u l t i p l e l e v e l s . A \ l e v e l - r " a s s i g n m e n t f o r a c u s t o m e r i 2 I w i l l s e r v e h e r i f
a n d o n l y i f a l l o f h e r a s s i g n e d f a c i l i t i e s a t l e v e l s 0 ; ¢ ¢ ¢ ; r ¡ 1 h a v e f a i l e d . A t o p t i m a l i t y , e a c h c u s t o m e r
i 2 I s h o u l d h a v e e x a c t l y R a s s i g n m e n t s , u n l e s s i i s a s s i g n e d t o t h e e m e r g e n c y f a c i l i t y a t c e r t a i n
l e v e l s < R . I f a c u s t o m e r i i s i n d e e d a s s i g n e d t o e x a c t l y R r e g u l a r f a c i l i t i e s a t l e v e l s 0 ; ¢ ¢ ¢ ; R ¡ 1 ,
s h e m u s t a l s o b e a s s i g n e d t o t h e e m e r g e n c y f a c i l i t y J a t l e v e l R t o c a p t u r e t h e p o s s i b i l i t y t h a t a l l
o f t h e R r e g u l a r f a c i l i t i e s m a y f a i l . F i n a l l y , P i j r i s t h e p r o b a b i l i t y t h a t f a c i l i t y j s e r v e s c u s t o m e r i
a t l e v e l r , g i v e n h e r o t h e r a s s i g n e d f a c i l i t i e s a t l e v e l s 0 t o r ¡ 1 .
T h e r e l i a b i l i t y U F L p r o b l e m ( R U F L ) i s f o r m u l a t e d a s :
( R U F L ) M i n
J ¡ 1 X j = 0
f j X j +
I ¡ 1 X i = 0
J X j = 0
R X r = 0
¸ i d i j P i j r Y i j r ( 1 a )
s . t .
J ¡ 1 X j = 0
Y i j r +
r ¡ 1 X s = 0
Y i J s = 1 8 0 · i · I ¡ 1 ; 0 · r · R ( 1 b )
C u i , O u y a n g , a n d S h e n : R e l i a b l e F a c i l i t y L o c a t i o n D e s i g n
A r t i c l e s u b m i t t e d t o O p e r a t i o n s R e s e a r c h ; m a n u s c r i p t n o . ( P l e a s e , p r o v i d e t h e m a n s u c r i p t n u m b e r ! ) 9
R ¡ 1 X r = 0
Y i j r · X j 8 0 · i · I ¡ 1 ; 0 · j · J ¡ 1 ( 1 c )
R X r = 0
Y i J r = 1 8 0 · i · I ¡ 1 ( 1 d )
P i j 0 = 1 ¡ q j 8 0 · i · I ¡ 1 ; 0 · j · J ( 1 e )
P i j r = ( 1 ¡ q j )
J ¡ 1 X k = 0
q k
1 ¡ q k
P i ; k ; r ¡ 1 Y i ; k ; r ¡ 1 8 0 · i · I ¡ 1 ; 0 · j · J ; 1 · r · R ( 1 f )
X j ; Y i j r 2 f 0 ; 1 g 8 0 · i · I ¡ 1 ; 0 · j · J ; 0 · r · R : ( 1 g )
T h e o b j e c t i v e f u n c t i o n ( 1 a ) i s t h e s u m o f t h e ¯ x e d c o s t s a n d t h e e x p e c t e d t r a n s p o r t a t i o n c o s t s .
C o n s t r a i n t s ( 1 b ) e n f o r c e t h a t f o r e a c h c u s t o m e r i a n d e a c h l e v e l r , e i t h e r i i s a s s i g n e d t o a r e g u l a r
f a c i l i t y a t l e v e l r o r s h e i s a s s i g n e d t o t h e e m e r g e n c y f a c i l i t y J a t c e r t a i n l e v e l s < r ( t a k i n g
P r ¡ 1
s = 0 Y i J s = 0 i f r = 0 ) . C o n s t r a i n t s ( 1 c ) l i m i t c u s t o m e r a s s i g n m e n t s t o o n l y t h e o p e n f a c i l i t i e s ,
w h i l e c o n s t r a i n t s ( 1 d ) r e q u i r e e a c h c u s t o m e r t o b e a s s i g n e d t o t h e e m e r g e n c y f a c i l i t y a t a c e r t a i n
l e v e l . ( 1 e ) - ( 1 f ) a r e t h e \ t r a n s i t i o n a l p r o b a b i l i t y " e q u a t i o n s . P i j r , t h e p r o b a b i l i t y t h a t f a c i l i t y j
s e r v e s c u s t o m e r i a t l e v e l r , i s j u s t t h e p r o b a b i l i t y t h a t j r e m a i n s o p e n i f r = 0 . F o r 1 · r · R , P i j r
i s e q u a l t o q k ( 1 ¡ q j )
1 ¡ q k
P i ; k ; r ¡ 1 g i v e n t h a t f a c i l i t y k s e r v e s c u s t o m e r i a t l e v e l r ¡ 1 . N o t e t h a t c o n s t r a i n t s
( 1 b ) i m p l y t h a t Y i ; k ; r ¡ 1 c a n e q u a l 1 f o r a t m o s t o n e k 2 J , w h i c h g u a r a n t e e s c o r r e c t n e s s o f t h e
t r a n s i t i o n a l p r o b a b i l i t i e s .
F o r m u l a t i o n ( 1 a ) - ( 1 g ) i s n o n l i n e a r . H o w e v e r , t h e o n l y n o n l i n e a r t e r m s a r e P i j r Y i j r ; 0 · i ·
I ¡ 1 ; 0 · j · J ; 0 · r · R , e a c h b e i n g a p r o d u c t o f a c o n t i n u o u s v a r i a b l e a n d a b i n a r y v a r i a b l e .
W e a p p l y t h e l i n e a r i z a t i o n t e c h n i q u e i n t r o d u c e d b y S h e r a l i a n d A l a m e d d i n e ( 3 6 ) b y r e p l a c i n g e a c h
P i j r Y i j r w i t h a n e w v a r i a b l e W i j r . F o r e a c h 0 · i · I ¡ 1 , 0 · j · J a n d 0 · r · R a s e t o f n e w
c o n s t r a i n t s i s a d d e d t o t h e f o r m u l a t i o n t o e n f o r c e W i j r = P i j r Y i j r :
W i j r · P i j r ( 2 a )
W i j r · Y i j r ( 2 b )
W i j r ¸ 0 ( 2 c )
W i j r ¸ P i j r + Y i j r ¡ 1 : ( 2 d )
C u i , O u y a n g , a n d S h e n : R e l i a b l e F a c i l i t y L o c a t i o n D e s i g n
1 0 A r t i c l e s u b m i t t e d t o O p e r a t i o n s R e s e a r c h ; m a n u s c r i p t n o . ( P l e a s e , p r o v i d e t h e m a n s u c r i p t n u m b e r ! )
T h e l i n e a r i z e d f o r m u l a t i o n ( L R U F L ) i s s t a t e d b e l o w :
( L R U F L ) M i n
J ¡ 1 X j = 0
f j X j +
I ¡ 1 X i = 0
J X j = 0
R X r = 0
¸ i d i j W i j r ( 3 a )
s . t . ( 1 b ) ¡ ( 1 d ) ( 3 b )
P i j r = ( 1 ¡ q j )
J ¡ 1 X k = 0
q k
1 ¡ q k
W i ; k ; r ¡ 1 8 0 · i · I ¡ 1 ; 0 · j · J ; 1 · r · R ( 3 c )
( 2 a ) ¡ ( 2 d ) 8 0 · i · I ¡ 1 ; 0 · j · J ; 1 · r · R ( 3 d )
X j ; Y i j r 2 f 0 ; 1 g 8 0 · i · I ¡ 1 ; 0 · j · J ; 0 · r · R : ( 3 e )
U n l i k e s c e n a r i o b a s e d s t o c h a s t i c p r o g r a m m i n g p r o b l e m s t h a t h a v e e x p o n e n t i a l l y m a n y v a r i a b l e s
a n d c o n s t r a i n t s , o u r f o r m u l a t i o n i s c o m p a c t a n d p o l y n o m i a l i n s i z e . P r o p o s i t i o n 1 s h o w s t h e e q u i v -
a l e n c e o f ( L R U F L ) t o t h e s c e n a r i o b a s e d f o r m u l a t i o n .
P r o p o s i t i o n 1 . I f R = J , t h e n f o r m u l a t i o n ( 1 a ) - ( 1 g ) i s e q u i v a l e n t t o t h e s t o c h a s t i c p r o g r a m m i n g
f o r m u l a t i o n t h a t c o v e r s a l l f a i l u r e s c e n a r i o s .
I n g e n e r a l , ( L R U F L ) i s n o t e q u i v a l e n t t o t h e s c e n a r i o b a s e d f o r m u l a t i o n i f R < J . H o w e v e r , o u r
c o m p u t a t i o n a l r e s u l t s s h o w t h a t t h e c h o i c e o f R h a s l i t t l e i m p a c t o n t h e o p t i m a l f a c i l i t y l o c a t i o n s .
S i m i l a r t o c l a s s i c f a c i l i t y l o c a t i o n p r o b l e m s , w e d o n o t e n f o r c e a c u s t o m e r t o b e s e r v e d b y h e r
c l o s e s t o p e n f a c i l i t y i n o u r f o r m u l a t i o n . I t i s p r o v e d i n S n y d e r a n d D a s k i n ( 3 7 ) t h a t t h e o p t i m a l
s o l u t i o n a l w a y s a s s i g n s a c u s t o m e r t o o p e n f a c i l i t i e s l e v e l b y l e v e l i n i n c r e a s i n g o r d e r o f d i s t a n c e ,
g i v e n t h a t a l l f a c i l i t i e s a r e e q u a l l y l i k e l y t o f a i l . T h e f o l l o w i n g p r o p o s i t i o n e x t e n d s t h i s r e s u l t t o
t h e c a s e w h e r e t h e f a c i l i t y f a i l u r e p r o b a b i l i t i e s a r e d i ® e r e n t a c r o s s s i t e s .
P r o p o s i t i o n 2 . I n a n y o p t i m a l s o l u t i o n ( X ; Y ; P ) o f ( R U F L ) , i f Y i j r = 1 a n d Y i k ; r + 1 = 1 , t h e n
d i j · d i k , f o r a l l 0 · i · I ¡ 1 ; 0 · j · J , a n d 0 · r · R .
P r o p o s i t i o n 2 t e l l s u s t h a t f o r a g i v e n s u b s e t o f f a c i l i t i e s a s s i g n e d t o a c u s t o m e r , t h e o p t i m a l
a s s i g n m e n t l e v e l s o n l y d e p e n d o n t h e d i s t a n c e s f r o m t h e c u s t o m e r t o t h e s e f a c i l i t i e s . H o w e v e r , i f
m o r e t h a n R f a c i l i t i e s a r e c o n s t r u c t e d , i t m a y b e s u b - o p t i m a l t o a s s i g n e a c h c u s t o m e r t o h e r R
c l o s e s t f a c i l i t i e s . A s t h e f o l l o w i n g e x a m p l e s h o w s , i t m a y b e o p t i m a l t o a s s i g n a c u s t o m e r t o a
f a c i l i t y t h a t i s f a r t h e r a w a y b u t l e s s l i k e l y t o f a i l .
C u i , O u y a n g , a n d S h e n : R e l i a b l e F a c i l i t y L o c a t i o n D e s i g n
A r t i c l e s u b m i t t e d t o O p e r a t i o n s R e s e a r c h ; m a n u s c r i p t n o . ( P l e a s e , p r o v i d e t h e m a n s u c r i p t n u m b e r ! ) 1 1
F i g u r e 4 F r a c t i o n o f a s u p p l y n e t w o r k
E x a m p l e 1 . C o n s i d e r a f r a c t i o n o f a s u p p l y n e t w o r k d e p i c t e d i n F i g u r e 4 . T h r e e f a c i l i t i e s a r e
c o n s t r u c t e d a r o u n d c u s t o m e r i . T h e d i s t a n c e s f r o m i t o t h e f a c i l i t i e s a r e d i 1 = d i 2 = 1 0 , a n d d i 3 = 2 0 .
T h e f a i l u r e p r o b a b i l i t i e s o f t h e t h r e e f a c i l i t i e s a r e q 1 = q 3 = 0 : 1 , a n d q 2 = 0 : 2 . T h e d e m a n d r a t e
a t i i s ¸ i = 1 a n d t h e p e n a l t y f o r n o t s e r v i n g a u n i t o f d e m a n d i s Á i = 1 0 0 0 . S u p p o s e t h a t e a c h
c u s t o m e r i s o n l y a l l o w e d o n e p r i m a r y a n d o n e b a c k - u p f a c i l i t y ( R = 2 ) . I f w e a s s i g n c u s t o m e r i t o
t h e t w o c l o s e s t f a c i l i t i e s 1 a n d 2 , t h e n t h e e x p e c t e d t r a n s p o r t a t i o n / p e n a l t y c o s t f o r t h i s c u s t o m e r
i s 2 9 . 8 . H o w e v e r , t h e o p t i m a l s t r a t e g y i s t o a s s i g n i t o f a c i l i t i e s 1 a n d 3 , w h i c h r e d u c e s t h e e x p e c t e d
t r a n s p o r t a t i o n c o s t t o 1 1 . 9 8 .
E x a m p l e 1 i m p l i e s t h a t e v e n w i t h ¯ x e d f a c i l i t y l o c a t i o n s , t h e c u s t o m e r a s s i g n m e n t p r o b l e m i s
c o m b i n a t o r i a l a n d r e q u i r e s m o r e s o p h i s t i c a t e d s o l u t i o n m e t h o d s . I n t h i s r e g a r d , o u r m o d e l i s h a r d e r
t h a n t h a t i n S n y d e r a n d D a s k i n ( 3 7 ) , i n w h i c h t h e c u s t o m e r a s s i g n m e n t p r o b l e m w i t h ¯ x e d f a c i l i t y
l o c a t i o n s c a n b e e a s i l y s o l v e d . W e d i s c u s s h o w t o d e c o m p o s e t h e c u s t o m e r a s s i g n m e n t p r o b l e m
u s i n g L a g r a n g i a n r e l a x a t i o n i n s e c t i o n 3 . 2 , a n d h o w t o e ± c i e n t l y s o l v e t h e i n d i v i d u a l c u s t o m e r
a s s i g n m e n t p r o b l e m i n s e c t i o n 3 . 3 .
3 . 2 . T h e L a g r a n g i a n R e l a x a t i o n A l g o r i t h m
T h e l i n e a r m i x e d - i n t e g e r p r o g r a m ( L R U F L ) c a n b e s o l v e d u s i n g c o m m e r c i a l s o f t w a r e p a c k a g e s l i k e
I L O G C P L E X , b u t g e n e r a l l y s u c h a n a p p r o a c h t a k e s a n e x c e s s i v e l y l o n g t i m e e v e n f o r m o d e r a t e l y
C u i , O u y a n g , a n d S h e n : R e l i a b l e F a c i l i t y L o c a t i o n D e s i g n
1 2 A r t i c l e s u b m i t t e d t o O p e r a t i o n s R e s e a r c h ; m a n u s c r i p t n o . ( P l e a s e , p r o v i d e t h e m a n s u c r i p t n u m b e r ! )
s i z e d p r o b l e m s . T h i s f a c t m o t i v a t e s t h e d e v e l o p m e n t o f a L a g r a n g i a n r e l a x a t i o n a l g o r i t h m . R e l a x i n g
c o n s t r a i n t s ( 1 c ) w i t h m u l t i p l i e r s ¹ y i e l d s t h e f o l l o w i n g o b j e c t i v e f u n c t i o n :
J ¡ 1 X j = 0
( f j ¡
I ¡ 1 X i = 0
¹ i j ) X j +
I ¡ 1 X i = 0
J X j = 0
R X r = 0
¸ i d i j W i j r +
I ¡ 1 X i = 0
J ¡ 1 X j = 0
R ¡ 1 X r = 0
¹ i j Y i j r :
F o r g i v e n v a l u e o f ¹ , t h e o p t i m a l v a l u e o f X c a n b e f o u n d e a s i l y :
X j = ½ 1 i f f j ¡ P I ¡ 1
i = 0 ¹ i j < 0
0 o t h e r w i s e .
T o ¯ n d t h e o p t i m a l Y , t h e c u s t o m e r a s s i g n m e n t d e c i s i o n , n o t e t h a t t h e p r o b l e m i s s e p a r a b l e
i n i . F o r g i v e n L a g r a n g i a n m u l t i p l i e r s ¹ a n i n d i v i d u a l c u s t o m e r ' s a s s i g n m e n t p r o b l e m i s r e f e r r e d
t o a s t h e r e l a x e d s u b p r o b l e m ( R S P ) . T h e c o m p l e x i t y o f R S P i s d e m o n s t r a t e d i n E x a m p l e 1 , i n
w h i c h t h e s i m p l e h e u r i s t i c l e a d s t o s u b o p t i m a l s o l u t i o n s . W e d i s c u s s e ± c i e n t a l g o r i t h m s f o r R S P
i n S e c t i o n 3 . 3 .
W e u s e s t a n d a r d s u b g r a d i e n t o p t i m i z a t i o n t e c h n i q u e t o u p d a t e t h e L a g r a n g i a n m u l t i p l i e r s ¹ ,
a s d e s c r i b e d i n F i s h e r ( 1 8 ) . I f t h e L a g r a n g i a n p r o c e s s f a i l s t o c o n v e r g e i n a c e r t a i n n u m b e r o f
i t e r a t i o n s , w e u s e b r a n c h - a n d - b o u n d t o c l o s e t h e g a p . A s a b e n c h m a r k , w e t e s t e d o u r a l g o r i t h m
o n t h e s a m e d a t a s e t s u s e d b y S n y d e r a n d D a s k i n ( 3 7 ) . T h e c o m p u t a t i o n a l r e s u l t s a r e d i s c u s s e d
i n S e c t i o n 5 . 1 .
3 . 3 . T h e R e l a x e d S u b p r o b l e m
B e l o w i s t h e M I P f o r m u l a t i o n o f t h e r e l a x e d s u b p r o b l e m w i t h r e s p e c t t o c u s t o m e r i ( R S P i ) . F o r
e a s e o f n o t a t i o n , w e o m i t t h e s u b s c r i p t i i n Y i j r , P i j r a n d W i j r .
( R S P i ) M i n © i =
J X j = 0
R X r = 0
¸ i d i j W j r +
J ¡ 1 X j = 0
R ¡ 1 X r = 0
¹ i j Y j r ( 4 a )
s . t .
J ¡ 1 X j = 0
Y j r +
r ¡ 1 X s = 0
Y J s = 1 8 0 · r · R ( 4 b )
R ¡ 1 X r = 0
Y j r · 1 8 0 · j · J ¡ 1 ( 4 c )
R X r = 0
Y J r = 1 ( 4 d )
C u i , O u y a n g , a n d S h e n : R e l i a b l e F a c i l i t y L o c a t i o n D e s i g n
A r t i c l e s u b m i t t e d t o O p e r a t i o n s R e s e a r c h ; m a n u s c r i p t n o . ( P l e a s e , p r o v i d e t h e m a n s u c r i p t n u m b e r ! ) 1 3
P j 0 = 1 ¡ q j 8 0 · j · J ( 4 e )
P j r = ( 1 ¡ q j )
J ¡ 1 X k = 0
q k
1 ¡ q k
W k ; r ¡ 1 8 0 · j · J ; 1 · r · R ( 4 f )
Y j r 2 f 0 ; 1 g 8 0 · j · J ; 0 · r · R ( 4 g )
( 2 a ) ¡ ( 2 d ) : ( 4 h )
W e p r o p o s e t w o m e t h o d s t o s o l v e t h e r e l a x e d s u b p r o b l e m : o n e e x a c t a l g o r i t h m t h a t ¯ n d s t h e
o p t i m a l c u s t o m e r a s s i g n m e n t , a n d o n e f a s t a p p r o x i m a t e a l g o r i t h m t h a t p r o v i d e s a n l o w e r b o u n d .
3 . 3 . 1 . A n E x a c t A l g o r i t h m F o l l o w i n g a s i m i l a r a r g u m e n t t o P r o p o s i t i o n 2 , g i v e n t h e s u b s e t
o f f a c i l i t i e s t h a t s e r v e a c e r t a i n c u s t o m e r , i t i s o p t i m a l t o a s s i g n t h i s c u s t o m e r t o t h e f a c i l i t i e s l e v e l
b y l e v e l i n i n c r e a s i n g o r d e r o f t h e d i s t a n c e s . T h e r e f o r e t h e o b j e c t i v e v a l u e o f ( R S P i ) o n l y d e p e n d s
o n t h e s e t o f f a c i l i t i e s t h a t s e r v e c u s t o m e r i . D e ¯ n e © i ( S ) t o b e t h e m i n i m u m c o s t t o s e r v e c u s t o m e r
i , u s i n g o n l y f a c i l i t i e s i n S ; i . e . ,
© i ( S ) = M i n
J X j = 0
R X r = 0
h i d i j W j r + X j 2 S
¹ i j ( 5 a )
s . t . ( 4 b ) ¡ ( 4 g ) ( 5 b )
R ¡ 1 X r = 0
Y j r = 0 8 j 2 f 1 ; ¢ ¢ ¢ ; J ¡ 1 g n S : ( 5 c )
I t i s c l e a r t h a t ( R S P i ) i s e q u i v a l e n t t o t h e f o l l o w i n g m i n i m i z a t i o n o f a s e t f u n c t i o n ( M S F i ) :
( M S F i ) M i n © i ( S ) ( 6 a )
s . t . S µ f 0 ; ¢ ¢ ¢ ; J ¡ 1 g ( 6 b )
j S j · R : ( 6 c )
W e s o l v e ( M S F ) u s i n g a s p e c i a l b r a n c h - a n d - b o u n d a l g o r i t h m , b a s e d o n s o m e u n i q u e p r o p e r t i e s o f
t h e s e t f u n c t i o n © , a s d e s c r i b e d i n P r o p o s i t i o n 3 .
P r o p o s i t i o n 3 . T h e s e t f u n c t i o n © i i s s u p e r m o d u l a r , f o r a l l i = 0 ; ¢ ¢ ¢ ; I ¡ 1 .
T h e m i n i m i z a t i o n o f a s u p e r m o d u l a r s e t f u n c t i o n c a n b e s o l v e d m o r e e ± c i e n t l y , u s i n g t h e b r a n c h -
a n d b o u n d a l g o r i t h m d e v e l o p e d b y G o l d e n g o r i n e t a l . ( 2 0 ) . T h e a l g o r i t h m k e e p s t r a c k o f A a n d
C u i , O u y a n g , a n d S h e n : R e l i a b l e F a c i l i t y L o c a t i o n D e s i g n
1 4 A r t i c l e s u b m i t t e d t o O p e r a t i o n s R e s e a r c h ; m a n u s c r i p t n o . ( P l e a s e , p r o v i d e t h e m a n s u c r i p t n u m b e r ! )
B , t h e s e t o f f a c i l i t i e s t h a t h a v e b e e n f o r c e d i n o r o u t f o r e a c h b r a n c h - a n d - b o u n d n o d e . T h e
s u p e r m o d u l a r i t y o f t h e o b j e c t i v e f u n c t i o n a l l o w s u s t o f o r c e o u t a f a c i l i t y i f i t s a d d i t i o n t o s e t A
d o e s n o t r e d u c e t h e t o t a l c o s t . I n a n u n c o n s t r a i n e d p r o b l e m , i t i s a l s o p o s s i b l e t o f o r c e i n a f a c i l i t y
i f i t s d e l e t i o n f r o m f 0 ; ¢ ¢ ¢ ; J ¡ 1 g n B i n c r e a s e s t h e t o t a l c o s t . H o w e v e r , s i n c e M S F i s s u b j e c t t o
t h e c a r d i n a l i t y c o n s t r a i n t ( 6 c ) , t h e s e c o n d o p t i o n d o e s n o t a p p l y h e r e .
3 . 3 . 2 . A n A p p r o x i m a t e S o l u t i o n A l t h o u g h t h e e x a c t a l g o r i t h m i n S e c t i o n 3 . 3 . 1 t a k e s
a d v a n t a g e o f s p e c i a l s t r u c t u r e o f t h e p r o b l e m , i t s w o r s t c a s e c o m p l e x i t y i s s t i l l e x p o n e n t i a l . I n
t h i s s e c t i o n w e p r o v i d e a f a s t a p p r o x i m a t e a l g o r i t h m t h a t ¯ n d s l o w e r b o u n d s f o r t h e L a g r a n g i a n
p r o c e d u r e .
I n o u r a p p r o x i m a t e s o l u t i o n , w e r e p l a c e t h e v a r i a b l e p r o b a b i l i t y P j r w i t h ¯ x e d n u m b e r s . L e t
j 0 ; j 1 ; ¢ ¢ ¢ ; j J ¡ 1 b e a n o r d e r i n g o f t h e f a c i l i t i e s s u c h t h a t q j 0 · q j 1 · ¢ ¢ ¢ · q J ¡ 1 . D e ¯ n e
® r = ( 1 ¡ q j r )
r ¡ 1 Y ` = 0
q j `
¯ r =
r ¡ 1 Y ` = 0
q j ` :
W e d e ¯ n e a r e f o r m u l a t i o n o f t h e r e l a x e d s u b p r o b l e m ( R R S P ) b y r e p l a c i n g P j r w i t h ® r i f 0 · j ·
J ¡ 1 , a n d r e p l a c i n g P J r w i t h ¯ r :
( R R S P i ) M i n
J ¡ 1 X j = 0
R ¡ 1 X r = 0
( ¸ i d i j ® r + ¹ i j ) Y j r +
R X r = 0
¸ i d i J ¯ r Y J r ( 7 a )
s . t .
J ¡ 1 X j = 0
Y j r +
r ¡ 1 X s = 0
Y J s = 1 8 0 · r · R ( 7 b )
R ¡ 1 X r = 0
Y j r · 1 8 0 · j · J ¡ 1 ( 7 c )
R X r = 0
Y J r = 1 ( 7 d )
Y j r 2 f 0 ; 1 g 8 0 · j · J ; 0 · r · R : ( 7 e )
T h e f o l l o w i n g p r o p o s i t i o n s t a t e s t h a t w e c a n s o l v e ( R R S P ) f o r a l o w e r b o u n d o f ( R S P ) .
P r o p o s i t i o n 4 . T h e ( R R S P ) f o r m u l a t i o n ( 7 a ) - ( 7 e ) y i e l d s a l o w e r b o u n d t o t h e r e l a x e d s u b p r o b l e m
( 4 a ) - ( 4 h ) .
C u i , O u y a n g , a n d S h e n : R e l i a b l e F a c i l i t y L o c a t i o n D e s i g n
A r t i c l e s u b m i t t e d t o O p e r a t i o n s R e s e a r c h ; m a n u s c r i p t n o . ( P l e a s e , p r o v i d e t h e m a n s u c r i p t n u m b e r ! ) 1 5
W e n o t e t h a t t h e ( R R S P ) f o r m u l a t i o n ( 7 a ) - ( 7 e ) l e a d s t o a c o m b i n a t o r i a l a s s i g n m e n t p r o b l e m ,
w h i c h c a n b e s o l v e d i n s t r o n g l y p o l y n o m i a l t i m e u s i n g t h e H u n g a r i a n a l g o r i t h m ( 2 5 ) . I n o u r
n u m e r i c a l t e s t s , w e u s e b o t h t h e e x a c t a n d t h e a p p r o x i m a t e a l g o r i t h m t o g e t t h e b e s t c o m b i n a t i o n
o f s p e e d a n d a c c u r a c y .
A l t h o u g h o u r c o m p a c t M I P f o r m u l a t i o n a n d t h e L a g r a n g i a n r e l a x a t i o n a l g o r i t h m a r e s i g n i ¯ c a n t
i m p r o v e m e n t s o v e r s c e n a r i o b a s e d s t o c h a s t i c p r o g r a m m i n g f o r m u l a t i o n s , t h e w o r s t c a s e c o m p l e x i t y
i s s t i l l e x p o n e n t i a l , d u e t o t h e N P - h a r d n e s s o f t h e u n d e r l y i n g p r o b l e m . F u r t h e r m o r e , b e c a u s e o n l y
n u m e r i c a l r e s u l t s a r e a v a i l a b l e f r o m t h e d i s c r e t e m o d e l , v e r y f e w m a n a g e r i a l i n s i g h t s c a n b e d r a w n
f r o m t h e o p t i m a l s o l u t i o n s . I n t h e n e x t s e c t i o n , w e o v e r c o m e t h e s e d i ± c u l t i e s b y i n t r o d u c i n g t h e
c o n t i n u u m a p p r o x i m a t i o n ( C A ) m o d e l .
4 . T h e C o n t i n u u m A p p r o x i m a t i o n M o d e l
I n t h i s s e c t i o n , w e r e s t r i c t o u r a t t e n t i o n t o t h e p l a n a r v e r s i o n o f t h e r e l i a b l e f a c i l i t y l o c a t i o n
p r o b l e m , d e ¯ n e d o v e r a l a r g e s e t o f c u s t o m e r s i n t h e c o n t i n u o u s m e t r i c s p a c e S µ R 2 , w h e r e t h e
d e m a n d r a t e ¸ , ¯ x e d c o s t f , f a i l u r e p r o b a b i l i t y q a n d t h e p e n a l t y c o s t Á a r e c o n t i n u o u s f u n c t i o n s
o f t h e l o c a t i o n x 2 S . A l l t h e s e s p a t i a l a t t r i b u t e s a r e a s s u m e d t o v a r y c o n t i n u o u s l y a n d s l o w l y i n
x . S u p p o s e t h a t t h e c o s t u n i t s a r e s e t s o t h a t t h e t r a n s p o r t a t i o n c o s t f o r s e r v i n g a u n i t d e m a n d
a t x b y a f a c i l i t y a t x j i s e q u a l t o t h e d i s t a n c e m e a s u r e d b y t h e E u c l i d e a n m e t r i c , k x ¡ x j k . I n
a d d i t i o n , w e a s s u m e t h a t Á ( x ) ¸ m a x f k x ¡ x j k : 8 x j 2 S g , f o r a l l x 2 S . U n d e r s u c h a s s u m p t i o n , a
c u s t o m e r s h a l l a l w a y s b e a s s i g n e d t o e x a c t l y R f a c i l i t i e s i f a v a i l a b l e .
4 . 1 . I n ¯ n i t e H o m o g e n e o u s P l a n e
W e ¯ r s t c o n s i d e r t h e c a s e w h e r e S = R 2 , a n d a l l p a r a m e t e r s , ¸ ; Á ; q ; f , a r e c o n s t a n t e v e r y w h e r e .
W e w i l l ¯ r s t i d e n t i f y o p t i m a l r e s u l t s f o r t h i s s i m p l e r c a s e a n d t h e n u s e t h e m a s b u i l d i n g b l o c k s t o
d e s i g n s o l u t i o n m e t h o d s f o r m o r e g e n e r a l c a s e s .
I t i s c l e a r t h a t o n a h o m o g e n e o u s p l a n e , g i v e n a n y s e t o f l o c a t i o n s x = f x 1 ; ¢ ¢ ¢ x n g , a c u s t o m e r
s h o u l d a l w a y s b e a s s i g n e d t o t h e R n e a r e s t f a c i l i t i e s . O t h e r w i s e w e c o u l d r e d u c e t h e c o s t b y s i m p l y
C u i , O u y a n g , a n d S h e n : R e l i a b l e F a c i l i t y L o c a t i o n D e s i g n
1 6 A r t i c l e s u b m i t t e d t o O p e r a t i o n s R e s e a r c h ; m a n u s c r i p t n o . ( P l e a s e , p r o v i d e t h e m a n s u c r i p t n u m b e r ! )
s w i t c h i n g t h i s c u s t o m e r o v e r t o a c l o s e r f a c i l i t y . T h u s , a n y d e s i g n x ( s u b j e c t t o f a i l u r e ) d e t e r m i n e s
t h e a s s i g n m e n t o f c u s t o m e r d e m a n d .
> F r o m t h e p e r s p e c t i v e o f a g e n e r i c f a c i l i t y j , i t w i l l s e r v e e v e r y c u s t o m e r o n t h e 2 - d p l a n e w i t h a
c e r t a i n p r o b a b i l i t y ( d e p e n d i n g o n i t s f a i l u r e p r o b a b i l i t y a n d t h a t o f o t h e r f a c i l i t i e s ) . T h e w h o l e a r e a
S c a n b e p a r t i t i o n e d i n t o n o n - o v e r l a p p i n g s u b a r e a s R j 0 ; R j 1 ; R j 2 ; ¢ ¢ ¢ , s u c h t h a t R j k ; 8 k , c o n t a i n s
t h e s u b s e t o f c u s t o m e r s f o r w h o m f a c i l i t y j i s t h e ( k + 1 ) t h n e a r e s t f a c i l i t y . W i t h t h i s d e ¯ n i t i o n , f o r
e v e r y j t h e r e i s a n o n - o v e r l a p p i n g p a r t i t i o n i f w e i g n o r e t h e b o u n d a r i e s o f t h e s e s u b a r e a s ,
[ k
R j k = S ; a n d R j k \ R j k 0 = ? ; 8 k 0 6 = k :
S i n c e e v e r y c u s t o m e r w i l l a l w a y s g o t o t h e n e a r e s t a v a i l a b l e f a c i l i t y , t h e c u s t o m e r a t x 2 R j k w i l l
g o t o f a c i l i t y j o n l y a f t e r a l l o f i t s k \ n e a r e s t " f a c i l i t i e s h a v e f a i l e d , a n d i f k + 1 · R . F a c i l i t y j w i l l
s e r v e c u s t o m e r s a t x w i t h t h e f o l l o w i n g s e r v i c e p r o b a b i l i t y :
P ( x ; x j j x ) = ( 1 ¡ q ) q k ; i f x 2 R j k ; ( 8 )
w h i c h d e c r e a s e s w i t h k .
P a r t i c u l a r l y , t h e i n i t i a l s e r v i c e a r e a R j 0 d e n o t e s t h e s u b a r e a o f S s e r v e d b y f a c i l i t y j b e f o r e a n y
f a i l u r e ; i . e . , R j 0 : = f x : k x ¡ x j k · k x ¡ x i k ; 8 i g µ S . F u r t h e r d e n o t i n g t h e s e t o f i n i t i a l s e r v i c e a r e a s
b y R : = f R 1 0 ; R 2 0 ; : : : ; R n 0 g , t h e y s h o u l d f o r m a n o t h e r a r e a p a r t i t i o n ( i g n o r i n g b o u n d a r i e s ) :
[ j
R j 0 = S a n d R j 0 \ R j 0 0 = ? ; 8 j 0 6 = j :
P r o p o s i t i o n 5 s h o w s t h a t t h e o p t i m a l f a c i l i t y d e s i g n o n a h o m o g e n e o u s p l a n e h a s t h e f o l l o w i n g
s p e c i a l s t r u c t u r e .
P r o p o s i t i o n 5 . I n a n i n ¯ n i t e h o m o g e n e o u s E u c l i d e a n p l a n e , t h e o p t i m a l i n i t i a l s e r v i c e a r e a s
s h o u l d f o r m a r e g u l a r h e x a g o n t e s s e l l a t i o n o f t h e p l a n e , w h i l e t h e f a c i l i t i e s a r e a t t h e c e n t r o i d s o f
t h e i n i t i a l s e r v i c e a r e a s ; s e e F i g u r e 5 ( a ) .
W i t h P r o p o s i t i o n 5 , w e c a n e s t i m a t e t h e e x p e c t e d c o s t i n c u r r e d b y o n e f a c i l i t y o n a n i n ¯ n i t e
h o m o g e n e o u s p l a n e . F i r s t o f a l l , t h e p r o b a b i l i t y t h a t a p a r t i c u l a r f a c i l i t y s e r v e s a c u s t o m e r d i m i n -
i s h e s a p p r o x i m a t e l y e x p o n e n t i a l l y w i t h t h e d i s t a n c e b e t w e e n t h e m . T h i s i s b e c a u s e t h e n u m b e r o f
C u i , O u y a n g , a n d S h e n : R e l i a b l e F a c i l i t y L o c a t i o n D e s i g n
A r t i c l e s u b m i t t e d t o O p e r a t i o n s R e s e a r c h ; m a n u s c r i p t n o . ( P l e a s e , p r o v i d e t h e m a n s u c r i p t n u m b e r ! ) 1 7
R j0
( a) ( b)
j j
R j1
R j1 R j2
R j3
R j0
R j1
R j1
R j1
R j1
R j2
R j2
R j2
R j2
R j2
R j3
R j3
R j3
R j3
R j3
F i g u r e 5 R e g u l a r h e x a g o n t e s s e l l a t i o n i n a n i n ¯ n i t e h o m o g e n e o u s 2 - d E u c l i d e a n p l a n e : ( a ) I n i t i a l s e r v i c e a r e a s ;
( b ) S e r v i c e s u b a r e a p a r t i t i o n f o r f a c i l i t y j
f a c i l i t i e s c l o s e r t o t h e c u s t o m e r ( i . e . , k ) , i s a p p r o x i m a t e l y p r o p o r t i o n a l t o t h e s q u a r e o f t h e d i s t a n c e ,
w h i l e t h e s e r v i c e p r o b a b i l i t y i n ( 8 ) d e c r e a s e s e x p o n e n t i a l l y w i t h k . F r o m t h e f a c i l i t y ' s p e r s p e c t i v e ,
t h e n u m b e r o f a v a i l a b l e c u s t o m e r s g r o w s o n l y p o l y n o m i a l l y w i t h t h e d i s t a n c e . H e n c e , t h e e x p e c t e d
s e r v i c e c o s t i n c u r r e d t o o n e f a c i l i t y o n a n i n ¯ n i t e h o m o g e n o u s p l a n e i s b o u n d e d f r o m a b o v e e v e n
w h e n R ! 1 .
T h e r e g u l a r h e x a g o n a l t e s s e l l a t i o n d e s i g n i n F i g u r e 5 ( a ) o b v i o u s l y l e a d s t o t h e s e r v i c e s u b a r e a
p a r t i t i o n i n F i g u r e 5 ( b ) . A n a r b i t r a r y f a c i l i t y j h a s a n i n i t i a l s e r v i c e a r e a s i z e A : = j R j 0 j a n d m a y
f a i l w i t h a p r o b a b i l i t y o f q . F o r t h i s f a c i l i t y t o s e r v e c u s t o m e r s t h a t o n l y g o t o R n e a r e s t f a c i l i t i e s ,
w e d e ¯ n e t h e f o l l o w i n g u s e f u l t e r m :
L : = Z x 2 S
k x ¡ x j k P ( x ; x j j x ) d x =
R ¡ 1 X k = 0 Z x 2 R j k k x ¡ x j k ( 1 ¡ q ) q k d x ; ( 9 )
w h e r e t h e s e c o n d e q u a l i t y h o l d s f r o m ( 8 ) .
N o t e t h a t ¸ L c a n b e t a k e n a s t h e e x p e c t e d t r a n s p o r t a t i o n c o s t o f a g e n e r i c f a c i l i t y t o s e r v e
a l l i t s p o t e n t i a l c u s t o m e r s , w h i l e t h e a v e r a g e t r a v e l e d d i s t a n c e o f a c u s t o m e r i s g i v e n b y L = ( R A ) .
A p p a r e n t l y , L < 1 ( s i n c e q < 1 ) a n d i t s v a l u e s h o u l d o n l y d e p e n d o n t h r e e f a c t o r s , A , R a n d q .
B y d i m e n s i o n a l a n a l y s i s a n d t h e B u c k i n g h a m - ¦ T h e o r e m ( 2 4 ) , t h e d i m e n s i o n l e s s q u a n t i t i e s ,
L = A 3
2 , R , a n d q , m u s t b e i n t e r d e p e n d e n t ; i . e . , t h e r e m u s t e x i s t a u n i q u e f u n c t i o n G s u c h t h a t
L = A
3
2 = G ( R ; q ) : ( 1 0 )
C u i , O u y a n g , a n d S h e n : R e l i a b l e F a c i l i t y L o c a t i o n D e s i g n
1 8 A r t i c l e s u b m i t t e d t o O p e r a t i o n s R e s e a r c h ; m a n u s c r i p t n o . ( P l e a s e , p r o v i d e t h e m a n s u c r i p t n u m b e r ! )
0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1
0
0.05
0.1
0.15
0.2
0.25
0.3
0.35
0.4
0.45
0.5
probability, q
R= 1
R= 2
R= 3
R= 7
R= 11
R= 5
* Simulated data
−− Fitted function
F i g u r e 6 S i m u l a t e d a n d ¯ t t e d L = ( R A ) 3 = 2 f o r E u c l i d e a n m e t r i c
W e n o t e t h a t G ( R ; q ) c a n b e i n t e r p r e t e d a s t h e e x p e c t e d t r a n s p o r t a t i o n c o s t f o r a g e n e r i c f a c i l i t y
t o s e r v e a l l i t s p o t e n t i a l c u s t o m e r s w h e n ¸ = 1 a n d A = 1 . T h e e x a c t f u n c t i o n a l f o r m o f G i s
u n k n o w n ; h o w e v e r i t o n l y d e p e n d s o n t h e d i s t a n c e m e t r i c a n d c a n b e e s t i m a t e d b y a s i m u l a t i o n .
F o r p u r p o s e o f o u r a n a l y s i s , w e h y p o t h e s i z e t h a t l n ( L = A 3 = 2 ) c a n b e a p p r o x i m a t e d b y a l i n e a r
f u n c t i o n o f a l i s t o f p o l y n o m i a l t e r m s o f R a n d q . F o r t h e E u c l i d e a n m e t r i c , l e a s t s q u a r e s r e g r e s s i o n
w i t h t h e s i m u l a t e d d a t a i n F i g u r e 6 ( w i t h 1 · R · 1 1 ; 0 · q · 0 : 9 5 ) y i e l d s
G ( R ; q ) ¼ e x p ( ¡ 0 : 9 3 0 ¡ 0 : 2 2 3 q + 4 : 1 3 3 q 2 ¡ 2 : 9 0 6 q 3 ¡ 1 : 5 4 2 ¼ q 2 = R ) ; ( 1 1 )
T h e R - s q u a r e v a l u e f o r t h e a b o v e r e g r e s s i o n e q u a l s 0 : 9 6 , i n d i c a t i n g a v e r y g o o d ¯ t , e s p e c i a l l y f o r
R ¸ 2 a n d q · 0 : 5 ( t h e r e a l i s t i c r a n g e o f p a r a m e t e r s f o r t h e r e l i a b i l i t y p r o b l e m ) . I n t h e n u m e r i c a l
e x a m p l e , w e w i l l u s e ( 1 1 ) t o a p p r o x i m a t e G ( R ; q ) . I t s h o u l d b e n o t e d , h o w e v e r , t h a t ( 1 1 ) i s b y
n o m e a n s t h e o n l y w a y t o e s t i m a t e G ( R ; q ) ; r a t h e r , i t i s a p l a u s i b l e a n d s i m p l e c h o i c e . T h e C A
a p p r o a c h p r e s e n t e d i n t h i s p a p e r c a n s t i l l b e a p p l i e d w i t h a n y a l t e r n a t i v e s o f ( 1 1 ) .
F o l l o w i n g f r o m ( 1 0 ) , w e d e ¯ n e t h e a v e r a g e p e r u n i t a r e a c o s t o f t h e s y s t e m t o b e
z ( A ) : = ( f + ¸ L ) = A + ¸ Á q R = f = A + ¸ G ( R ; q ) p A + ¸ Á q R ; ( 1 2 )
w h e r e f = A i s t h e ¯ x e d c o s t p e r u n i t a r e a ( s i n c e e a c h i n i t i a l s e r v i c e a r e a c o n s i s t s o f a s i n g l e f a c i l i t y ) ,
a n d ¸ Á q R i s t h e e x p e c t e d p e n a l t y c o s t p e r u n i t a r e a f o r f a i l u r e t o s e r v e t h e c u s t o m e r s .
C u i , O u y a n g , a n d S h e n : R e l i a b l e F a c i l i t y L o c a t i o n D e s i g n
A r t i c l e s u b m i t t e d t o O p e r a t i o n s R e s e a r c h ; m a n u s c r i p t n o . ( P l e a s e , p r o v i d e t h e m a n s u c r i p t n u m b e r ! ) 1 9
T h e o p t i m a l s i z e o f t h e i n i t i a l s e r v i c e a r e a , a n d t h u s t h e m i n i m u m s y s t e m c o s t c a n b e o b t a i n e d
b y m i n i m i z i n g t h e a v e r a g e c o s t p e r u n i t a r e a ; i . e . ,
m i n
A > 0
z ( A ) :
4 . 2 . H e t e r o g e n e o u s P l a n e
T o h a n d l e m o r e r e a l i s t i c c a s e s , w e a l l o w t h e p a r a m e t e r s ¸ ; Á ; q ; f t o b e v a r y i n g f u n c t i o n s o f t h e
l o c a t i o n x i n a b o u n d e d a r e a S i n t h i s s e c t i o n . S i m i l a r t o t h e h o m o g e n e o u s c a s e , w e l o o k f o r a
c o n t i n u o u s f u n c t i o n , A ( x ) 2 R + ; x 2 S , t h a t a p p r o x i m a t e s t h e i n i t i a l s e r v i c e a r e a s i z e o f a f a c i l i t y
n e a r x .
W e a s s u m e t h a t S i s f a r l a r g e r t h a n A ( x ) ; i . e . a p p r o x i m a t e l y i n ¯ n i t e ; a n d a l l p a r a m e t e r s , f ( x ) ,
¸ ( x ) , q ( x ) a n d Á ( x ) a r e s l o w l y v a r y i n g ; i . e . a p p r o x i m a t e l y c o n s t a n t . W h e n t h e p a r a m e t e r s a r e
a p p r o x i m a t e l y c o n s t a n t o v e r a r e g i o n c o m p a r a b l e t o t h e s i z e o f s e v e r a l i n ° u e n c e a r e a s , t h e i n ° u e n c e
a r e a s i z e A ( x ) s h o u l d a l s o b e a p p r o x i m a t e l y c o n s t a n t o n t h a t s c a l e . I n t h i s c a s e , w e d e ¯ n e z ( A ( x ) ; x )
t o b e t h e c o s t o f s e r v i n g a u n i t a r e a n e a r x w h e n t h e i n ° u e n c e a r e a s i z e i s a p p r o x i m a t e l y A ( x ) ; i . e . ,
z ( A ( x ) ; x ) : = f ( x ) = A ( x ) + ¸ ( x ) G ( R ; q ( x ) ) p A ( x ) + ¸ ( x ) Á ( x ) q ( x ) R : ( 1 3 )
T h e t o t a l s y s t e m c o s t c a n b e a p p r o x i m a t e d b y i n t e g r a t i n g Z ( A ( x ) ; x ) o v e r t h e s e r v i c e a r e a S :
Z x 2 S
z ( A ( x ) ; x ) d x : ( 1 4 )
T h e o p t i m a l s y s t e m c o s t c a n b e a p p r o x i m a t e d b y s o l v i n g a p o i n t - w i s e o p t i m i z a t i o n p r o b l e m f o r
e a c h x 2 S :
m i n
A ( x ) > 0
z ( A ( x ) ; x ) : ( 1 5 )
4 . 3 . F e a s i b l e D i s c r e t e L o c a t i o n D e s i g n
F o r m u l a ( 1 4 ) y i e l d s a n e s t i m a t e o f t h e t o t a l s y s t e m c o s t w i t h o u t p r o v i d i n g a d i s c r e t e f a c i l i t y d e s i g n .
H o w e v e r , t h e o p t i m a l i n i t i a l s e r v i c e a r e a s i z e s , A ¤ ( x ) ; 8 x 2 S , c a n b e u s e d a s g u i d e l i n e s t o o b t a i n
f e a s i b l e d i s c r e t e l o c a t i o n d e s i g n s .
C u i , O u y a n g , a n d S h e n : R e l i a b l e F a c i l i t y L o c a t i o n D e s i g n
2 0 A r t i c l e s u b m i t t e d t o O p e r a t i o n s R e s e a r c h ; m a n u s c r i p t n o . ( P l e a s e , p r o v i d e t h e m a n s u c r i p t n u m b e r ! )
T h e o p t i m a l n u m b e r o f i n i t i a l s e r v i c e a r e a s , n ¤ , i s a p p r o x i m a t e l y g i v e n b y
n ¤ : = Z S
[ A ¤ ( x ) ] ¡ 1 d x :
T h e d i s k m o d e l b y O u y a n g a n d D a g a n z o ( 3 1 ) s e a r c h e s f o r a s e t o f n n o n - o v e r l a p p i n g d i s k s , e a c h
h a v i n g a r o u n d s h a p e ( i . e . , a p p r o x i m a t i n g h e x a g o n s ) a n d a p r o p e r s i z e , t h a t c o v e r m o s t o f S . A
d i s k c e n t e r e d a t x w i l l h a v e s i z e ® A ¤ ( x ) , w h e r e t h e s c a l i n g p a r a m e t e r ® i s s l i g h t l y s m a l l e r t h a n 1
t o e n s u r e t h a t t h e r o u n d d i s k s c a n j o i n t l y c o v e r m o s t o f S w i t h o u t l e a v i n g t h e r e g i o n .
T h e d i s k s m o v e w i t h i n S i n s e a r c h o f a n o n - o v e r l a p p i n g d i s t r i b u t i o n p a t t e r n . T o a u t o m a t e t h e
s l i d i n g p r o c e d u r e , r e p u l s i v e f o r c e s a c t i n g o n t h e c e n t e r s o f t h e d i s k s a r e i m p o s e d o n a n y o v e r l a p p i n g
d i s k s a n d o n a n y d i s k s t h a t l i e o u t s i d e o f S . T h e d i s k s t h e n m o v e u n d e r t h e s e f o r c e s i n s m a l l s t e p s ,
a n d t h e d i s k s i z e s a n d f o r c e s a r e u p d a t e d s i m u l t a n e o u s l y . O u y a n g a n d D a g a n z o ( 3 1 ) a n d O u y a n g
( 3 2 ) p r o v i d e d e t a i l e d d i s c u s s i o n s o n h o w t o c h o o s e s t e p s i z e s , h o w t o i n t r o d u c e n e c e s s a r y r a n d o m
p e r t u r b a t i o n s , a n d h o w t o d e c r e a s e ® i n c r e m e n t a l l y u n t i l a l l f o r c e s v a n i s h ( i . e . , w h e n a d e s i r e d
n o n - o v e r l a p p i n g p a t t e r n i s f o u n d ) . T h e n , t h e d i s k c e n t e r s w i l l b e u s e d a s t h e f a c i l i t y l o c a t i o n s a n d
t h e c u s t o m e r d e m a n d s w i l l b e a s s i g n e d a c c o r d i n g l y . T h i s p r o c e d u r e w i l l g i v e a n e a r - o p t i m a l f e a s i b l e
s o l u t i o n t o t h e p l a n a r p r o b l e m .
4 . 4 . R e m a r k s o n t h e C A M o d e l
T h e p o i n t - w i s e o p t i m i z a t i o n p r o b l e m ( 1 5 ) c a n b e s o l v e d i n c l o s e d - f o r m t o p r o v i d e m a n a g e r i a l
i n s i g h t s . S e c t i o n 5 . 3 s h o w s a s i m p l e e x a m p l e o f s e n s i t i v i t y a n a l y s i s b a s e d o n t h e C A f o r m u l a .
I t s h o u l d b e n o t e d t h a t t h e i m p l e m e n t a t i o n f r a m e w o r k o f t h e C A m o d e l d o e s n o t r e l y d i r e c t l y
o n t h e s p e c i ¯ c f u n c t i o n f o r m o f G ( R ; q ) . O t h e r f o r m s o f G ( R ; q ) ( e . g . , t h o s e p r o v i d i n g c l e a r e r
m a n a g e r i a l i n s i g h t s o r b e t t e r r e g r e s s i o n ¯ t ) c a n b e e a s i l y a p p l i e d .
T h e r e a r e s e v e r a l p o t e n t i a l s o u r c e s o f i n a c c u r a c y i n t h e C A m o d e l . F i r s t , t h e C A m o d e l i s
e x p e c t e d t o p e r f o r m w e l l f o r l a r g e - s c a l e s y s t e m s w i t h s l o w - v a r y i n g c o n d i t i o n s . T h i s i s b e c a u s e w e
h a v e a s s u m e d c o n s t a n t c o n d i t i o n s i n a f a i r l y l a r g e a r e a ( w i t h s i z e ¼ R A ) . I f , i n c e r t a i n c a s e s ,
s y s t e m p a r a m e t e r v a l u e s c h a n g e r a p i d l y w i t h x , t h e C A m o d e l m a y n o t y i e l d v e r y a c c u r a t e r e s u l t s .
C u i , O u y a n g , a n d S h e n : R e l i a b l e F a c i l i t y L o c a t i o n D e s i g n
A r t i c l e s u b m i t t e d t o O p e r a t i o n s R e s e a r c h ; m a n u s c r i p t n o . ( P l e a s e , p r o v i d e t h e m a n s u c r i p t n u m b e r ! ) 2 1
H o w e v e r , m u c h l i k e t h e t r a d i t i o n a l C A m e t h o d , t h e e r r o r h e r e i s l i k e l y t o c a n c e l o u t a c r o s s d i ® e r e n t
c u s t o m e r s d u e t o t h e l a w o f l a r g e n u m b e r s . S e c t i o n 5 w i l l u s e n u m e r i c a l e x a m p l e s t o s h o w t h a t t h e
c o n t i n u u m a p p r o x i m a t i o n m o d e l y i e l d s n e a r - o p t i m a l r e s u l t s d e s p i t e v i o l a t i o n s t o t h e a s s u m p t i o n
o n s l o w - v a r y i n g c o n d i t i o n s .
S e c o n d , w e i g n o r e t h e b o u n d a r y o f S w h i l e d e v e l o p i n g P ( ¢ ) . S u c h s i m p l i ¯ c a t i o n , h o w e v e r , i s n o t
l i k e l y t o i n t r o d u c e s e v e r e e r r o r s b e c a u s e t h e p r o b a b i l i t y t h a t a f a c i l i t y s e r v e s a p a r t i c u l a r c u s t o m e r
d i m i n i s h e s g e o m e t r i c a l l y ( r a p i d l y f o r s m a l l q ) w i t h t h e d i s t a n c e b e t w e e n t h e m . T h e r e f o r e , t h e
i n ° u e n c e o f t h e b o u n d a r y f o r l a r g e - s c a l e p r o b l e m s ( i . e . , n À 1 ) i s l i k e l y t o b e s m a l l . A l s o , G e r s h o
( 1 9 ) s h o w e d t h a t e v e n f o r ¯ n i t e ( b u t l a r g e ) t w o - d i m e n s i o n a l p l a n e s , t h e i n ° u e n c e w i l l o n l y b e
s i g n i ¯ c a n t f o r i n i t i a l s e r v i c e a r e a s d i r e c t l y t o u c h i n g t h e p e r i p h e r y o f S , a n d h e n c e s m a l l .
N e v e r t h e l e s s , t h e i n ° u e n c e o f t h e b o u n d a r y w i l l c a u s e r e m a r k a b l e e r r o r s i n c e r t a i n i l l - p o s e d
s i t u a t i o n s . N o t e t h a t i n t h e d e r i v a t i o n s i n S e c t i o n 4 . 1 , w e a s s u m e t h a t n ¸ R . I n e x t r e m e c a s e s
( e . g . , f a c i l i t y s e t - u p c o s t s f a r e v e r y h i g h c o m p a r e d w i t h c u s t o m e r p e n a l t i e s Á ) , t h e i d e a l f a c i l i t y
d e n s i t y s h a l l b e v e r y l o w ( i . e . , A ! 1 ) . W h e n t h e c u s t o m e r a r e a j S j i s ¯ n i t e , i t i s p o s s i b l e t h a t
t h e n u m b e r o f t o t a l f a c i l i t i e s n < R ( o r e v e n n ! 0 ) . I n s u c h c a s e s , i t i s n o t p o s s i b l e t o f o r c e e v e r y
c u s t o m e r t o c o n s i d e r R f a c i l i t i e s | t h e a s s u m p t i o n u s e d t o d e r i v e c o s t f o r m u l a ( 9 ) i s v i o l a t e d . H e n c e ,
s o m e t i m e s i t i s n o t r e a s o n a b l e t o s p e c i f y t h a t e v e r y c u s t o m e r s h a l l c o n s i d e r a t m o s t R f a c i l i t i e s .
A l t e r n a t i v e l y , w e m a y p o s t u l a t e t h a t a c u s t o m e r , i f s e r v e d a t a l l , s h a l l o n l y b e s e r v e d b y a f a c i l i t y
w i t h i n a m a x i m u m s e r v i c e d i s t a n c e . A p p e n d i x B p r o v i d e s d i s c u s s i o n s o n s u c h f o r m u l a t i o n s .
5 . C o m p u t a t i o n a l R e s u l t s
W e c o n d u c t e d a s e r i e s o f c o m p u t a t i o n a l e x p e r i m e n t s t o t e s t t h e p e r f o r m a n c e o f t h e d i s c r e t e a n d
t h e C A m o d e l . W e a l s o d e m o n s t r a t e t h e u s e o f C A f o r s e n s i t i v i t y a n a l y s i s .
5 . 1 . D i s c r e t e M o d e l R e s u l t s
T h e d i s c r e t e m o d e l w a s t e s t e d o n t w o t y p e s o f n e t w o r k s - t h e \ r e a l " n e t w o r k b a s e d o n t h e U S m a p
w i t h 4 9 o r 8 8 n o d e s a n d t h e \ r a n d o m " n e t w o r k g e n e r a t e d o n a u n i t s q u a r e r e g i o n w i t h 5 0 o r 1 0 0
n o d e s ( t h e d a t a s e t w a s k i n d l y p r o v i d e d b y L . S n y d e r a n d i s a v a i l a b l e f r o m h i s w e b s i t e ( 3 8 ) ) . T h e
C u i , O u y a n g , a n d S h e n : R e l i a b l e F a c i l i t y L o c a t i o n D e s i g n
2 2 A r t i c l e s u b m i t t e d t o O p e r a t i o n s R e s e a r c h ; m a n u s c r i p t n o . ( P l e a s e , p r o v i d e t h e m a n s u c r i p t n u m b e r ! )
f a i l u r e p r o b a b i l i t i e s q j i n t h e r e a l n e t w o r k s a r e c a l c u l a t e d u s i n g q j = 0 : 1 e ¡ D j = 4 0 0 , i n w h i c h D j i s t h e
g r e a t c y c l e d i s t a n c e ( i n m i l e s ) b e t w e e n l o c a t i o n j a n d N e w O r l e a n s , L A . I n t h e r a n d o m n e t w o r k s ,
q j a r e r a n d o m l y g e n e r a t e d f r o m a u n i f o r m d i s t r i b u t i o n b e t w e e n 0 a n d 0 . 2 . F o r e a c h d a t a s e t , w e
t e s t o u r a l g o r i t h m f o r R = 2 , 3 a n d 4 . T h e L a g r a n g i a n r e l a x a t i o n / b r a n c h - a n d - b o u n d p r o c e d u r e i s
e x e c u t e d t o a t o l e r a n c e o f 0 . 5 % , o r u p t o 3 6 0 0 s e c o n d s ( 6 0 m i n u t e s ) i n C P U t i m e . T h e a l g o r i t h m
w a s c o d e d i n C + + a n d t e s t e d o n a n I n t e l P e n t i u m 4 3 . 2 0 G H z p r o c e s s o r w i t h 1 . 0 G B R A M u n d e r
L i n u x . P a r a m e t e r v a l u e s f o r t h e L a g r a n g i a n r e l a x a t i o n a l g o r i t h m c a n b e f o u n d i n T a b l e 3 , a n d t h e
a l g o r i t h m p e r f o r m a n c e i s s u m m a r i z e d i n T a b l e 4 .
P a r a m e t e r V a l u e
O p t i m a l t o l e r a n c e 0 . 0 0 5
M a x i m u m n u m b e r o f a p p r o x i m a t e i t e r a t i o n s a t r o o t n o d e 1 0 0 0
M a x i m u m n u m b e r o f e x a c t i t e r a t i o n s a t r o o t n o d e 5 0 0
M a x i m u m n u m b e r o f a p p r o x i m a t e i t e r a t i o n s a t c h i l d n o d e s 2 0 0
M a x i m u m n u m b e r o f e x a c t i t e r a t i o n s a t c h i l d n o d e s 1 0 0
I n i t i a l v a l u e f o r ¹ i j o p t i m a l d u a l o f L P r e l a x a t i o n
T a b l e 3 P a r a m e t e r v a l u e s f o r t h e L a g r a n g i a n r e l a x a t i o n
N o d e s R e - a s s i g n m e n t l e v e l R o o t L B R o o t U B R o o t g a p ( % ) O v e r a l l U B O v e r a l l g a p ( % ) C P U t i m e ( s e c . )
4 9 2 8 7 8 , 8 5 6 8 8 0 , 0 9 8 0 . 1 4 1 8 8 0 , 0 9 8 0 . 1 4 1 9
4 9 3 8 7 0 , 2 2 9 8 7 4 , 4 2 3 0 . 4 8 2 8 7 4 , 4 2 3 0 . 4 8 2 1 9
4 9 4 8 7 0 , 1 4 3 8 7 4 , 3 2 3 0 . 4 8 1 8 7 4 , 3 2 3 0 . 4 8 1 5 0
8 8 2 1 , 2 3 0 , 1 2 0 1 , 2 3 4 , 8 6 0 0 . 3 8 5 1 , 2 3 4 , 8 6 0 0 . 3 8 5 6 6
8 8 3 1 , 2 1 7 , 6 5 0 1 , 2 2 3 , 6 1 0 0 . 4 8 9 1 , 2 2 3 , 6 1 0 0 . 4 8 9 4 5 8
8 8 4 1 , 2 1 7 , 2 7 0 1 , 2 2 3 , 2 9 0 0 . 4 9 4 1 , 2 2 3 , 2 9 0 0 . 4 9 4 8 8 3
5 0 2 6 , 3 3 6 6 , 3 6 3 0 . 4 1 5 6 , 3 6 3 0 . 4 1 5 1
5 0 3 6 , 3 3 1 6 , 3 6 3 0 . 4 9 6 6 , 3 6 3 0 . 4 9 6 3
5 0 4 6 , 3 3 1 6 , 3 6 3 0 . 4 9 6 6 , 3 6 3 0 . 4 9 6 4
1 0 0 2 1 1 , 9 2 2 1 1 , 9 8 1 0 . 4 9 4 1 1 , 9 8 1 0 . 4 9 4 2 2
1 0 0 3 1 1 , 9 2 1 1 1 , 9 8 0 0 . 4 9 9 1 1 , 9 8 0 0 . 4 9 9 3 5
1 0 0 4 1 1 , 9 1 1 1 1 , 9 7 0 0 . 4 8 9 1 1 , 9 7 0 0 . 4 8 9 2 1
T a b l e 4 L R A l g o r i t h m P e r f o r m a n c e
W e n o t i c e t h a t t h e m a x i m u m r e - a s s i g n m e n t l e v e l R d o e s n o t a ® e c t t h e o p t i m a l f a c i l i t y l o c a t i o n s
i n a l l o f o u r t e s t i n s t a n c e s , a l t h o u g h a h i g h e r R i n g e n e r a l h e l p s t o r e d u c e t h e o p t i m a l c o s t . F i g u r e 7
a n d 8 i l l u s t r a t e t h e o p t i m a l f a c i l i t y l o c a t i o n s f o r t h e 4 9 - n o d e a n d t h e 8 8 - n o d e p r o b l e m r e s p e c t i v e l y .
T a b l e 5 a n d 6 l i s t t h e p e r c e n t a g e o f c o v e r e d d e m a n d , ¯ x e d c o s t , a n d f a i l u r e p r o b a b i l i t y a t e a c h
o p t i m a l f a c i l i t y l o c a t i o n i n t h e t w o p r o b l e m i n s t a n c e s . I n b o t h c a s e s , t h e o p t i m a l s o l u t i o n s a v o i d
h i g h l y r i s k y a r e a s s u c h a s L A a n d M S . I n a r e a s w i t h m o d e r a t e r i s k , c l u s t e r s o f f a c i l i t i e s a r e f o r m e d
C u i , O u y a n g , a n d S h e n : R e l i a b l e F a c i l i t y L o c a t i o n D e s i g n
A r t i c l e s u b m i t t e d t o O p e r a t i o n s R e s e a r c h ; m a n u s c r i p t n o . ( P l e a s e , p r o v i d e t h e m a n s u c r i p t n u m b e r ! ) 2 3
t o h e d g e a g a i n s t p o s s i b l e d i s r u p t i o n s . I n a r e a s w i t h l o w r i s k ( O R , C A a n d A Z ) , f a c i l i t i e s a r e l o c a t e d
r e l a t i v e l y s p a r s e l y .
F i g u r e 7 O p t i m a l S o l u t i o n t o t h e 4 9 - N o d e P r o b l e m F i g u r e 8 O p t i m a l S o l u t i o n t o t h e 8 8 - N o d e P r o b l e m
L o c a t i o n D e m a n d C o v e r e d F i x e d C o s t F a i l u r e P r o b a b i l i t y
S a c r a m e n t o , C A 1 9 % 1 1 5 , 8 0 0 0 . 0 0 1
A u s t i n , T X 9 % 7 2 , 6 0 0 0 . 0 4 3
H a r r i s b u r g , P A 2 9 % 3 8 , 4 0 0 0 . 0 1 2
L a n s i n g , M I 1 2 % 4 8 , 4 0 0 0 . 0 1 3
M o n t g o m e r y , A L 1 7 % 6 2 , 2 0 0 0 . 0 5 3
D e s M o i n e s , I A 1 5 % 4 9 , 5 0 0 0 . 0 1 4
T a b l e 5 O p t i m a l L o c a t i o n s f o r t h e 4 9 - N o d e P r o b l e m
L o c a t i o n D e m a n d C o v e r e d F i x e d C o s t F a i l u r e P r o b a b i l i t y
H o u s t o n , T X 1 0 % 5 8 , 0 0 0 0 . 0 4 3
P h i l a d e l p h i a , P A 2 7 % 4 9 , 4 0 0 0 . 0 1 2
D e t r o i t , M I 1 0 % 2 5 , 6 0 0 0 . 0 1 3
M i l w a u k e e , W I 1 0 % 5 3 , 5 0 0 0 . 0 1 4
P o r t l a n d , O R 3 % 5 9 , 2 0 0 0 . 0 0 1
T u c s o n , A Z 5 % 6 6 , 8 0 0 0 . 0 0 1
F r e s n o , C A 1 7 % 8 0 , 3 0 0 0 . 0 0 1
M o n t g o m e r y , A L 9 % 6 2 , 2 0 0 0 . 0 5 3
T o p e k a , K S 8 % 4 8 , 8 0 0 0 . 0 2 4
T a b l e 6 O p t i m a l L o c a t i o n s f o r t h e 8 8 - N o d e P r o b l e m
O u r a l g o r i t h m a p p e a r s t o h a v e p e r f o r m e d e ± c i e n t l y o n t h e r a n d o m t e s t i n s t a n c e s . H o w e v e r ,
t h e a l g o r i t h m c o n v e r g e n c e i s s l o w f o r s o m e o f t h e r e a l t e s t i n s t a n c e s . D u e t o t h e c o m p u t a t i o n a l
c o m p l e x i t y o f ¯ n d i n g e x a c t s o l u t i o n s f o r t h e r e l a x e d s u b p r o b l e m s ( R S P ) , w e c a n o n l y a ® o r d t o r u n
t h e e x a c t a l g o r i t h m f o r a v e r y l i m i t e d n u m b e r o f i t e r a t i o n s ( 1 0 0 a t e a c h B & B n o d e a s c o m p a r e d
t o 2 0 0 0 i n S n y d e r a n d D a s k i n ( 3 7 ) ) , T h e a p p r o x i m a t e a l g o r i t h m f o r R S P i s f a s t , b u t t h e b o u n d i t
p r o v i d e s c a n b e l a x i n s o m e c i r c u m s t a n c e s . F o r ¯ x e d - c h a r g e l o c a t i o n p r o b l e m s , i t i s g e n e r a l l y m o r e
C u i , O u y a n g , a n d S h e n : R e l i a b l e F a c i l i t y L o c a t i o n D e s i g n
2 4 A r t i c l e s u b m i t t e d t o O p e r a t i o n s R e s e a r c h ; m a n u s c r i p t n o . ( P l e a s e , p r o v i d e t h e m a n s u c r i p t n u m b e r ! )
e ± c i e n t t o r e l a x t h e a s s i g n m e n t c o n s t r a i n t ( 1 b ) i n s t e a d o f t h e l i n k i n g c o n s t r a i n t ( 1 c ) . H o w e v e r , i n
o u r c a s e r e l a x i n g ( 1 c ) a l l o w s u s t o d e c o m p o s e t h e c u s t o m e r a s s i g n m e n t p r o b l e m , a k e y s t e p i n t h e
a l g o r i t h m d e v e l o p m e n t . T o i m p r o v e t h e e ± c i e n c y o f t h e a l g o r i t h m , w e n e e d t o ¯ n d w a y s t o s o l v e
t h e r e l a x e d s u b p r o b l e m s m o r e q u i c k l y a n d b e t t e r d e c o m p o s i i t i o n m e c h a n i s m s w i t h t i g h t e r b o u n d s .
T h e s e g o a l s w i l l b e p u r s u e d i n o u r f u t u r e r e s e a r c h .
5 . 2 . C A M o d e l R e s u t l s
T o t e s t t h e p e r f o r m a n c e o f t h e C A a p p r o a c h , w e c o n s i d e r a [ 0 ; 1 ] £ [ 0 ; 1 ] u n i t s q u a r e , w h e r e c u s t o m e r
d e m a n d s a r e d i s t r i b u t e d a c c o r d i n g t o a d e n s i t y f u n c t i o n ¸ ( x ) . A f a c i l i t y b u i l t a t l o c a t i o n x i n c u r s
a c o s t o f f ( x ) a n d m a y f a i l w i t h p r o b a b i l i t y q ( x ) . A s a b e n c h m a r k , w e a l s o c o n s t r u c t a n d s o l v e
a n a l o g o u s d i s c r e t e t e s t i n s t a n c e s b y p a r t i t i o n i n g t h e u n i t s q u a r e i n t o 7 £ 7 = 4 9 i d e n t i c a l s q u a r e
c e l l s ; t h e c e n t e r o f e a c h c e l l r e p r e s e n t s a c a n d i d a t e f a c i l i t y l o c a t i o n a s w e l l a s t h e c o n s o l i d a t i o n
p o i n t o f t h e c u s t o m e r d e m a n d f r o m t h a t c e l l .
W e g r o u p o u r t e s t i n s t a n c e s i n t o t w o c a t e g o r i e s : t h e h o m o g e n e o u s c a s e a n d t h e h e t e r o g e n e o u s
c a s e . I n t h e h o m o g e n e o u s c a s e , a l l s y s t e m p a r a m e t e r s a r e c o n s t a n t o v e r s p a c e ; i . e . , ¸ ( x ) = ¸ ; f ( x ) =
f , a n d q ( x ) = q 8 x . W e g e n e r a t e 1 6 t e s t i n s t a n c e s w i t h k e y p a r a m e t e r s t a k i n g v a l u e s f r o m q 2
f 0 : 0 5 ; 0 : 1 0 ; 0 : 1 5 ; 0 : 2 0 g , ¸ 2 f 5 0 0 0 0 ; 1 0 0 0 0 0 ; 1 5 0 0 0 0 ; 5 0 0 0 0 0 g . T h e ¯ x e d c o s t i s f = 1 0 0 0 f o r a l l 1 6
i n s t a n c e s .
I n t h e h e t e r o g e n e o u s c a s e , w e l e t t h e k e y p a r a m e t e r s b e c o n t i n u o u s f u n c t i o n s t h a t c a n v a r y
a c r o s s s p a c e , d e ¯ n e d a s f o l l o w s :
¸ ( x ) = ¸ ( 1 + ¢ ¸ c o s ( ¼ x [ 2 ] ) ) ; f ( x ) = f e ¡ k x k ; q ( x ) = q [ 1 + ¢ q c o s ( ¼ k x k ) ] ; 8 x ;
w h e r e k x k i s t h e E u c l i d e a n d i s t a n c e f r o m x t o t h e o r i g i n , a n d x [ 2 ] i s t h e s e c o n d c o o r d i n a t e o f x .
N o t e t h a t q a n d ¸ c o n t r o l t h e a v e r a g e m a g n i t u d e o f f a i l u r e p r o b a b i l i t i e s a n d d e m a n d d e n s i t i e s ,
w h i l e ¢ q a n d ¢ ¸ c o n t r o l t h e v a r i a b i l i t y o f t h e s e p a r a m e t e r s . W e g e n e r a t e 2 0 t e s t i n s t a n c e s i n t o t a l ,
w i t h q a n d ¢ q d r a w n f r o m q 2 f 0 : 1 ; 0 : 2 g a n d ¢ q 2 f 0 : 1 ; 0 : 2 ; 0 : 3 ; 0 : 4 ; 0 : 5 g , a n d ¢ ¸ t a k i n g v a l u e s f r o m
¢ ¸ 2 f 0 : 0 ; 1 : 0 g . T h e a v e r a g e d e m a n d d e n s i t y i s s e t t o b e ¸ = 1 0 0 0 0 0 a n d t h e a v e r a g e ¯ x e d c o s t i s
s e t t o f = 1 0 0 0 f o r a l l 2 0 i n s t a n c e s .
C u i , O u y a n g , a n d S h e n : R e l i a b l e F a c i l i t y L o c a t i o n D e s i g n
A r t i c l e s u b m i t t e d t o O p e r a t i o n s R e s e a r c h ; m a n u s c r i p t n o . ( P l e a s e , p r o v i d e t h e m a n s u c r i p t n u m b e r ! ) 2 5
T h e p e n a l t y c o s t i s ¯ x e d a t Á ( x ) = p 2 , a n d t h e r e a s s i g n m e n t l e v e l i s s e t t o R = 2 f o r a l l 3 6 t e s t
i n s t a n c e s i n b o t h c a t e g o r i e s .
F o r e a c h t e s t i n s t a n c e , w e l i s t t h e C A p r e d i c t e d c o s t Z C A , t h e f e a s i b l e d i s c r e t e s o l u t i o n f o u n d
b y t h e d i s k a l g o r i t h m Z D
C A , a n d t h e o p t i m a l s o l u t i o n f o u n d b y t h e L a g r a n g i a n a l g o r i t h m Z D
L R . T h e
s u p e r s c r i p t ` D ' h e r e s t a n d s f o r d i s c r e t e c u s t o m e r d e m a n d ( i . e . , a s s u m i n g t h e c o n t i n u o u s d e m a n d
d i s t r i b u t i o n a s a n a p p r o x i m a t i o n ) . T h e n u m b e r o f f a c i l i t i e s c o n s t r u c t e d i n t h e C A a n d t h e d i s c r e t e
m o d e l s o l u t i o n s a r e a l s o l i s t e d r e s p e c t i v e l y u n d e r n ¤ C A a n d n ¤ L R . F o r c o m p a r i s o n , w e c a l c u l a t e " D ,
t h e g a p b e t w e e n Z D
C A a n d Z D
L R f o r e a c h t e s t i n s t a n c e . T h e r e s u l t s a r e s u m m a r i z e d i n T a b l e 7 f o r t h e
h o m o g e n e o u s c a s e s a n d i n T a b l e 8 f o r t h e h e t e r o g e n e o u s c a s e s . W e a r e a l s o i n t e r e s t e d i n c o m p a r i n g
t h e m o d e l r e s u l t s a s s u m i n g c o n t i n u o u s d e m a n d ( i . e . , c o n s i d e r i n g t h e a g g r e g a t e d d i s c r e t e d e m a n d
a s a n a p p r o x i m a t i o n ) , a n d t h o s e r e s u l t s a r e l i s t e d i n A p p e n d i x C .
T a b l e 7 C A c o s t e s t i m a t e s , f e a s i b l e s o l u t i o n s , a n d L R s o l u t i o n s f o r t h e h o m o g e n e o u s c a s e s
q ¸ ( 1 0 4 ) Z C A Z D
C A Z D
L R n ¤ C A n ¤ L R " D ( % )
0 . 0 5 5 1 3 9 0 8 . 5 1 4 6 9 4 . 1 1 4 2 8 1 . 1 5 5 2 . 8 9
0 . 1 5 1 4 4 3 0 . 9 1 5 6 0 0 . 1 1 5 1 3 4 . 1 5 5 3 . 0 8
0 . 1 5 5 1 5 3 4 5 . 4 1 6 7 6 2 . 3 1 6 2 5 1 . 5 5 5 3 . 1 4
0 . 2 5 1 6 6 3 2 . 0 1 8 1 8 0 . 6 1 7 6 3 3 . 4 5 5 3 . 1
0 . 0 5 1 0 2 2 1 5 1 . 2 2 2 8 9 5 . 4 2 2 6 0 7 . 4 7 7 1 . 2 7
0 . 1 1 0 2 3 1 9 9 . 4 2 4 4 7 0 . 8 2 4 2 8 1 . 5 7 8 0 . 7 8
0 . 1 5 1 0 2 5 0 1 5 . 7 2 6 6 0 5 . 3 2 4 2 8 1 . 5 7 8 0 . 7 4
0 . 2 1 0 2 7 5 6 8 . 7 2 9 2 9 8 . 8 2 8 9 5 4 . 8 7 9 1 . 1 9
0 . 0 5 1 5 2 8 7 0 4 . 7 3 0 5 3 8 . 9 2 9 4 6 0 . 2 1 0 1 0 3 . 6 6
0 . 1 1 5 2 9 3 0 9 . 9 3 2 7 0 2 . 9 3 1 8 0 7 . 3 1 0 1 0 2 . 8 2
0 . 1 5 1 5 3 0 6 6 7 . 5 3 5 7 9 0 . 7 3 4 9 8 8 . 7 1 0 1 1 2 . 2 9
0 . 2 1 5 3 2 8 8 0 . 6 3 9 5 4 6 . 5 3 8 9 4 5 . 2 1 0 1 0 1 . 5 4
0 . 0 5 5 0 6 5 5 0 4 . 6 6 5 5 8 6 . 0 5 4 1 6 4 . 0 2 1 4 9 2 1 . 0 9
0 . 1 5 0 7 0 7 7 1 . 4 7 2 5 5 1 . 7 6 2 5 0 6 . 1 2 1 4 9 1 6 . 0 7
0 . 1 5 5 0 7 9 7 5 2 . 2 8 3 8 8 5 . 3 7 4 0 2 6 . 1 2 1 4 9 1 3 . 3 2
0 . 2 5 0 9 2 3 5 4 . 9 9 5 8 6 1 . 2 8 8 7 2 4 . 3 2 1 4 9 8 . 0 4
O u r t e s t r e s u l t s s h o w t h a t t h e C A m e t h o d i s a p r o m i s i n g t o o l f o r ¯ n d i n g n e a r o p t i m a l s o l u t i o n s .
E v e n u n d e r t h e d i s c r e t e d e m a n d d i s t r i b u t i o n ( i . e . , c o n s i d e r i n g t h e c o n t i n u o u s d e m a n d d i s t r i b u t i o n
a s a n a p p r o x i m a t i o n ) , t h e o p t i m a l i t y g a p i s b e l o w 4 % i n m o s t t e s t i n s t a n c e s . P a r t i c u l a r l y , e v e n
w h e n t h e d e m a n d d i s t r i b u t i o n i s s i g n i ¯ c a n t l y v a r i a b l e a c r o s s s p a c e ( ¸ ( x ) v a r y i n g f r o m 0 t o 2 ¸ ) ,
t h e g a p s i s m o s t l y w i t h i n 4 ¡ 7 % .
W e n o t e t h a t u n d e r v e r y h i g h d e m a n d d e n s i t y ¸ = 5 0 0 ; 0 0 0 , t h e d i s c r e p a n c y b e t w e e n t h e C A
a n d t h e L R s o l u t i o n s i s m o r e s i g n i ¯ c a n t i n t e r m s o f b o t h t h e n u m b e r o f c o n s t r u c t e d f a c i l i t i e s a n d
C u i , O u y a n g , a n d S h e n : R e l i a b l e F a c i l i t y L o c a t i o n D e s i g n
2 6 A r t i c l e s u b m i t t e d t o O p e r a t i o n s R e s e a r c h ; m a n u s c r i p t n o . ( P l e a s e , p r o v i d e t h e m a n s u c r i p t n u m b e r ! )
T a b l e 8 C A c o s t e s t i m a t e s , f e a s i b l e s o l u t i o n s , a n d L R s o l u t i o n s f o r t h e h e t e r o g e n e o u s c a s e
q ¢ q ¢ ¸ Z C A Z D
C A Z D
L R n ¤ C A n ¤ L R " D ( % )
0 . 1 0 . 1 0 1 8 2 3 5 1 9 5 6 3 1 8 9 7 1 . 1 1 2 1 5 3 . 1 2
0 . 1 0 . 2 0 1 8 1 1 5 . 3 1 9 4 0 5 . 5 1 8 7 2 6 . 6 1 2 1 4 3 . 6 3
0 . 1 0 . 3 0 1 8 0 1 2 . 8 1 9 2 4 5 . 2 1 8 6 3 1 . 9 1 2 1 5 3 . 2 9
0 . 1 0 . 4 0 1 7 9 2 7 . 5 1 9 4 6 4 . 7 1 8 3 6 6 . 3 1 2 1 5 5 . 9 8
0 . 1 0 . 5 0 1 7 8 5 9 . 4 1 8 8 0 7 . 9 1 8 3 4 9 . 6 1 2 1 4 2 . 5
0 . 2 0 . 1 0 2 2 1 5 8 . 7 2 3 8 2 7 . 9 2 3 0 7 4 . 8 1 2 1 4 3 . 2 6
0 . 2 0 . 2 0 2 1 6 6 8 . 7 2 3 1 2 6 . 6 2 2 6 6 5 . 4 1 2 1 5 2 . 0 3
0 . 2 0 . 3 0 2 1 2 4 3 . 6 2 2 6 2 1 . 5 2 2 0 7 6 . 7 1 2 1 7 2 . 4 7
0 . 2 0 . 4 0 2 0 8 8 4 . 0 2 2 0 4 4 . 2 2 1 4 2 6 . 4 1 2 1 6 2 . 8 8
0 . 2 0 . 5 0 2 0 5 9 0 . 4 2 1 4 6 2 . 3 2 0 9 7 8 . 2 1 2 1 4 2 . 3 1
0 . 1 0 . 1 1 1 6 6 6 7 . 8 1 8 5 7 3 . 0 1 7 6 7 0 . 0 1 1 1 4 5 . 1 1
0 . 1 0 . 2 1 1 6 6 4 6 . 7 1 8 5 0 5 . 9 1 7 5 2 9 . 8 1 1 1 4 5 . 5 7
0 . 1 0 . 3 1 1 6 6 3 4 . 4 1 8 4 1 1 . 5 1 7 4 3 5 . 3 1 1 1 6 5 . 6
0 . 1 0 . 4 1 1 6 6 3 0 . 7 1 8 3 5 4 . 0 1 7 2 9 3 . 5 1 1 1 3 6 . 1 3
0 . 1 0 . 5 1 1 6 6 3 5 . 4 1 8 5 4 1 . 6 1 7 1 7 7 . 7 1 1 1 3 7 . 9 4
0 . 2 0 . 1 1 1 8 8 6 4 . 4 2 2 9 3 2 . 2 2 2 0 2 9 . 6 1 1 1 3 4 . 1
0 . 2 0 . 2 1 1 8 7 4 0 . 0 2 2 5 4 8 . 1 2 1 7 7 0 . 8 1 1 1 3 3 . 5 7
0 . 2 0 . 3 1 1 8 6 5 9 . 9 2 2 2 8 4 . 3 2 1 3 6 9 . 5 1 1 1 4 4 . 2 8
0 . 2 0 . 4 1 1 8 6 2 3 . 1 2 2 1 5 7 . 3 2 1 1 7 4 . 1 1 1 1 6 4 . 6 4
0 . 2 0 . 5 1 1 8 6 2 8 . 6 2 1 9 3 6 . 2 2 0 7 3 1 . 1 1 1 1 4 5 . 8 1
t h e t o t a l s y s t e m c o s t . T h i s d i s c o v e r y i s n o t s u r p r i s i n g . W i t h h i g h d e m a n d d e n s i t y , t h e d i ® e r e n c e o f
d e m a n d d i s t r i b u t i o n u s e d i n t h e C A a n d t h e d i s c r e t e m o d e l i s m a g n i ¯ e d . I n g e n e r a l , t h e m a r g i n a l
b e n e ¯ t o f b u i l d i n g a n a d d i t i o n a l f a c i l i t y i s l o w e r i n t h e C A m o d e l t h a n i n t h e d i s c r e t e m o d e l , s i n c e
d e m a n d i s d i s t r i b u t e d t h r o u g h o u t t h e a r e a i n t h e f o r m e r , a n d a g g r e g a t e d a t t h e c e l l c e n t e r s i n t h e
l a t t e r . H e n c e , t h e C A m o d e l t e n d s t o b u i l d f e w e r f a c i l i t i e s w h e n t h e c u s t o m e r d e m a n d i s e x t r e m e l y
d e n s e . W e a n t i c i p a t e t h a t t h e d i s c r e p a n c i e s w o u l d d e c r e a s e i f t h e i n p u t t o t h e d i s c r e t e m o d e l h a s
¯ n e r r e s o l u t i o n ( i . e . , m o r e d e m a n d a g g r e g a t i o n n o d e s ) .
T o v e r i f y o u r h y p o t h e s i s , w e f u r t h e r d i v i d e t h e u n i t s q u a r e t o 1 0 £ 1 0 i d e n t i c a l c e l l s a n d a g g r e g a t e
d e m a n d t o t h e 1 0 0 c e l l c e n t e r s . W e t e s t a l l 4 i n s t a n c e s w i t h h i g h d e m a n d d e n s i t y ¸ = 5 0 0 ; 0 0 0 i n
t h e 1 0 0 - n o d e n e t w o r k . T h e r e s u l t s a r e l i s t e d i n T a b l e 1 0 .
T a b l e 9 C A c o s t e s t i m a t e , f e a s i b l e s o l u t i o n s , a n d L R s o l u t i o n s i n t h e 1 0 0 - n o d e n e t w o r k
q ¸ ( 1 0 4 ) Z C A Z D
C A Z L R n ¤ C A n ¤ L R " ( % )
0 . 0 5 5 0 6 5 5 0 4 . 6 6 8 2 6 3 . 3 6 6 1 7 3 . 5 2 1 2 2 3 . 1 6
0 . 1 0 5 0 7 0 7 7 1 . 4 7 4 4 9 1 . 9 7 3 5 2 8 . 5 2 1 2 4 1 . 3 1
0 . 1 5 5 0 7 9 7 5 2 . 2 8 4 2 0 7 . 7 8 3 1 1 4 . 6 2 1 2 3 1 . 3 2
0 . 2 0 5 0 9 2 3 5 4 . 9 9 7 0 4 5 . 5 9 5 8 3 7 . 4 2 2 2 5 1 . 2 6
T h e r e s u l t s i n T a b l e 1 0 i n d i c a t e t h a t t h e C A s o l u t i o n s a r e m o r e c o n s i s t e n t w i t h t h e d i s c r e t e
m o d e l s o l u t i o n s w i t h m o r e d e m a n d a g g r e g a t i o n n o d e s . T h i s i m p l i e s t h a t t h e C A m o d e l s h o u l d
m a t c h t h e d i s c r e t e m o d e l b e s t w h e n t h e r e a r e a l a r g e n u m b e r o f c a n d i d a t e l o c a t i o n s ( w h e n t h e
C u i , O u y a n g , a n d S h e n : R e l i a b l e F a c i l i t y L o c a t i o n D e s i g n
A r t i c l e s u b m i t t e d t o O p e r a t i o n s R e s e a r c h ; m a n u s c r i p t n o . ( P l e a s e , p r o v i d e t h e m a n s u c r i p t n u m b e r ! ) 2 7
d i s c r e t e m o d e l w o u l d i n c u r t h e m o s t c o m p u t a t i o n a l d i ± c u l t y ) . I n t h i s s e n s e , t h e L R a n d t h e C A
m e t h o d s c a n s e r v e a s t h e c o m p l e m e n t o f e a c h o t h e r .
5 . 3 . S e n s i t i v i t y A n a l y s i s w i t h C A
T h e s y s t e m c o s t p r e d i c t e d b y t h e C A m o d e l i s c o n t i n u o u s i n a l l p a r a m e t e r s , a n d i s t h u s a u s e f u l
t o o l f o r s e n s i t i v i t y a n a l y s i s . I n t h i s s e c t i o n , w e d e m o n s t r a t e h o w t o u s e C A t o s t u d y t h e i m p a c t o f
t h e k e y p a r a m e t e r s o n t h e s t r u c t u r e o f t h e o p t i m a l s y s t e m d e s i g n . I n p a r t i c u l a r , w e a r e i n t e r e s t e d
i n k n o w i n g h o w t h e d e g r e e o f d e m a n d a g g r e g a t i o n a ® e c t s t h e s y s t e m c o s t . I n o t h e r w o r d s , a l l o t h e r
t h i n g s b e i n g e q u a l , i s i t p r e f e r a b l e t o h a v e e v e n l y d i s t r i b u t e d d e m a n d o r a g g r e g a t e d d e m a n d ?
T h e C A m o d e l s u g g e s t s t h a t t h e t o t a l c o s t i s d e t e r m i n e d b y ( 1 4 ) . I t i s e a s y t o v e r i f y t h a t
Z ( A ( x ) ; x ) i s m o d u l a r i n A a n d t h a t t h e p o i n t - w i s e o p t i m a l i n i t i a l s e r v i c e a r e a c a n b e d e t e r m i n e d
b y
A ¤ ( x ) = (
2 f ( x )
¸ ( x ) G ( R ; q )
) 2
3 :
P l u g g i n g A ¤ ( x ) b a c k i n ( 1 3 ) g i v e s u s t h e c o s t \ d e n s i t y " n e a r p o i n t x
z ( x ) ´ z ( A ¤ ( x ) ; x ) = ( 2 ¡ 2
3 + 2 1
3 ) f ( x ) 1
3 ¸ ( x ) 2
3 G
2
3 ( R ; q ( x ) ) + Á ( x ) ¸ ( x ) q ( x ) R : ( 1 6 )
C l e a r l y , z ( x ) i s c o n c a v e i n ¸ . F r o m J e n s e n ' s i n e q u a l i t y , w e k n o w t h a t t h e t o t a l c o s t d e c r e a s e s a s
t h e d e g r e e o f d e m a n d a g g r e g a t i o n i n c r e a s e s .
T o v e r i f y o u r ¯ n d i n g s , w e d e s i g n e d n u m e r i c a l t e s t s u s i n g t h e L R a l g o r i t h m . T h e k e y p a r a m e t e r s
a r e d e t e r m i n e d b y
¸ ( x ) = ¸ ( 1 + ¢ ¸ c o s ( ¼ x [ 2 ] ) ) ; f ( x ) = 1 0 0 0 ; q ( x ) = 0 : 2 ; Á ( x ) = p 2 8 x :
W e g e n e r a t e d 3 0 t e s t i n s t a n c e s , 1 0 e a c h f o r t h r e e d i ® e r e n t l e v e l s o f a v e r a g e d e m a n d ¸ a t 5 0 0 0 0 ,
1 0 0 0 0 0 o r 1 5 0 0 0 0 . T h e d e m a n d v a r i a t i o n ¢ ¸ r a n g e s f r o m 0 t o 0 . 9 . L i k e t h e p r e v i o u s t e s t s , w e
a g g r e g a t e d e m a n d t o 4 9 d i s c r e t e p o i n t s . E a c h t e s t i n s t a n c e i s s o l v e d b y t h e L a g r a n g i a n a l g o r i t h m ,
a n d t h e n t h e p e r c e n t a g e c h a n g e i n t h e o p t i m a l c o s t i s c a l c u l a t e d , u s i n g t h e c a s e ¢ ¸ = 0 a s t h e
b e n c h m a r k . T h e t e s t r e s u l t s a r e i l l u s t r a t e d i n F i g u r e 9 .
C u i , O u y a n g , a n d S h e n : R e l i a b l e F a c i l i t y L o c a t i o n D e s i g n
2 8 A r t i c l e s u b m i t t e d t o O p e r a t i o n s R e s e a r c h ; m a n u s c r i p t n o . ( P l e a s e , p r o v i d e t h e m a n s u c r i p t n u m b e r ! )
F i g u r e 9 O p t i m a l C o s t v . s . d e m a n d v a r i a b i l i t y
C l e a r l y , t h e t e s t r e s u l t s f r o m t h e d i s c r e t e m o d e l v e r i f y t h e p r e d i c t i o n s m a d e b y t h e C A m o d e l ,
w i t h t h e t o t a l c o s t d e c r e a s i n g b y u p t o 7 % a s t h e d e m a n d v a r i a t i o n i n c r e a s e s f r o m 0 t o 0 . 9 . T h i s
r e s u l t i m p l i e s t h a t i t i s b e n e ¯ c i a l t o a g g r e g a t e d e m a n d . I n r e a l i t y , t h i s p r i n c i p l e i s c o m m o n l y
i m p l e m e n t e d t h r o u g h t h e u s e o f w a r e h o u s e s a n d d i s t r i b u t i o n c e n t e r s w h i c h s e r v e a s p o i n t s f o r
d e m a n d a g g r e g a t i o n .
6 . C o n c l u s i o n s
S u p p l y c h a i n s a r e v u l n e r a b l e t o d i s r u p t i o n s c a u s e d b y n a t u r a l d i s a s t e r s , t e r r o r i s t a t t a c k s o r m a n -
m a d e d e f e c t i o n s . T h e c o n s e q u e n c e s o f d i s r u p t i o n s a r e o f t e n d i s a s t r o u s d e s p i t e t h e i r r a r e o c c u r r e n c e .
H o w e v e r , t h e e m e r g e n c y c o s t c a n b e s i g n i ¯ c a n t l y r e d u c e d t h r o u g h a p r o a c t i v e a p p r o a c h d u r i n g
t h e d e s i g n p h a s e . W e p r e s e n t t w o d i s t i n c t m o d e l s t o ¯ n d f a c i l i t y l o c a t i o n s o l u t i o n s t h a t a r e b o t h
r e l i a b l e a n d c o s t e ± c i e n t . O u r d i s c r e t e m o d e l i s a m i x e d i n t e g e r l i n e a r p r o g r a m . W i t h o u r c u s t o m -
d e s i g n e d L a g r a n g i a n r e l a x a t i o n a l g o r i t h m , i t e ± c i e n t l y c o m p u t e s t h e g l o b a l o p t i m a l s o l u t i o n s f o r
s m a l l o r m e d i u m s i z e d p r o b l e m s . O u r c o n t i n u u m a p p r o x i m a t i o n m o d e l o m i t s d e t a i l s o f t h e f a c i l i t y
l o c a t i o n s a n d c u s t o m e r a s s i g n m e n t s , b u t p r o v i d e s m a n a g e r i a l i n s i g h t s a n d s e r v e s a s a v a l u a b l e t o o l
f o r s e n s i t i v i t y a n a l y s i s . I t c a n a l s o b e u s e d a s a n e ± c i e n t h e u r i s t i c t o ¯ n d n e a r - o p t i m a l s o l u t i o n s
f o r l a r g e p r o b l e m i n s t a n c e s .
C u i , O u y a n g , a n d S h e n : R e l i a b l e F a c i l i t y L o c a t i o n D e s i g n
A r t i c l e s u b m i t t e d t o O p e r a t i o n s R e s e a r c h ; m a n u s c r i p t n o . ( P l e a s e , p r o v i d e t h e m a n s u c r i p t n u m b e r ! ) 2 9
O u r ¯ n d i n g s a l s o b r i n g u p n e w q u e s t i o n s f o r f u t u r e r e s e a r c h . F i r s t , w e p l a n t o i n t r o d u c e c a p a c i t y
l i m i t s i n t o t h e m o d e l , a s o p p o s e d t o t h e u n c a p a c i a t e d c a s e i n t h i s s t u d y . A l t h o u g h e x o g e n o u s
f a c i l i t y c a p a c i t i e s w i l l n o t s i g n i ¯ c a n t l y i n c r e a s e t h e c o m p l e x i t y o f t h e m o d e l s a n d t h e s o l u t i o n
a l g o r i t h m s , i t i s a l s o p o s s i b l e t o l e t t h e s y s t e m e n d o g e n o u s l y d e t e r m i n e t h e c a p a c i t y l e v e l f o r e a c h
f a c i l i t y , a t a c e r t a i n r e s e r v a t i o n c o s t . S e c o n d , o n l y s t a t i c d e c i s i o n r u l e s a r e c o n s i d e r e d i n t h i s s t u d y ,
i g n o r i n g t h e d u r a t i o n a n d t h e f r e q u e n c y o f t h e f a c i l i t y d i s r u p t i o n s . I n c o r p o r a t i n g t h e s e f a c t o r s i n t o
o u r m o d e l w i l l a l l o w u s t o e x a m i n e o p t i m a l d e c i s i o n r u l e s i n a d y n a m i c e n v i r o n m e n t . R e g a r d i n g t h e
C A a p p r o a c h , w e a r e p a r t i c u l a r l y i n t e r e s t e d i n d e v e l o p i n g e ® e c t i v e p r o c e d u r e s t o m a p d i s c r e t e d a t a
i n t o t h e c o n t i n u o u s s e t t i n g s o t h a t t h e C A m o d e l c a n b e u s e d t o s o l v e e x i s t i n g d i s c r e t e p r o b l e m s
i n t h e l i t e r a t u r e . W e a r e a l s o i n t e r e s t e d i n s e e k i n g b e t t e r u n d e r s t a n d i n g o r e s t i m a t e s o f f u n c t i o n
G ( R ; q ) s o a s t o p o t e n t i a l l y i m p r o v e t h e p e r f o r m a n c e o f t h e C A m o d e l . F i n a l l y , w e w o u l d e x p l o r e
o t h e r a p p l i c a t i o n s o f t h e C A m o d e l , e s p e c i a l l y i n t h e ¯ e l d o f i n t e g r a t e d s u p p l y c h a i n d e s i g n .
R e f e r e n c e s
[ 1 ] B a l l , W . W . R . a n d C o x e t e r , H . S . M . ( 1 9 8 7 ) M a t h e m a t i c a l R e c r e a t i o n s a n d E s s a y s ( 1 3 t h E d i t i o n ) .
N e w Y o r k : D o v e r .
[ 2 ] B a l l , M . O . a n d L i n , F . L . ( 1 9 9 3 ) A r e l i a b i l i t y m o d e l a p p l i e d t o e m e r g e n c y s e r v i c e v e h i c l e l o c a t i o n .
O p e r a t i o n s R e s e a r c h 4 1 ( 1 ) : 1 8 - 3 6 .
[ 3 ] B a t t a , R . , D o l a n , J . M . a n d K r i s h n a m u r t h y , N . N . ( 1 9 8 9 ) T h e m a x i m a l e x p e c t e d c o v e r i n g l o c a t i o n
p r o b l e m - r e v i s i t e d . T r a n s p o r t a i o n S c i e n c e 2 3 ( 4 ) : 2 7 7 - 2 8 7 .
[ 4 ] B e r m a n , O . , K r a s s , D . a n d M e n e z e s , M . B . C . ( 2 0 0 7 ) F a c i l i t y r e l i a b i l i t y i s s u e s i n n e t w o r k P - m e d i a n
p r o b l e m s : s t r a t e g i c c e n t r a l i z a t i o n a n d c o - l o c a t i o n e ® e c t s . O p e r a t i o n s R e s e a r c h 5 5 : 3 3 2 - 3 5 0 .
[ 5 ] C a m p b e l l , J . F . ( 1 9 9 3 a ) C o n t i n u o u s a n d d i s c r e t e d e m a n d h u b l o c a t i o n p r o b l e m s . T r a n s p o r t a t i o n
R e s e a r c h P a r t B , 2 7 : 4 7 3 - 4 8 2 .
[ 6 ] C a m p b e l l , J . F . ( 1 9 9 3 b ) O n e - t o - m a n y d i s t r i b u t i o n w i t h t r a n s s h i p m e n t s : A n a n a l y t i c m o d e l .
T r a n s p o r t a t i o n S c i e n c e , 2 7 : 3 3 0 - 3 4 0 .
[ 7 ] D a g a n z o , C . F . ( 1 9 8 4 a ) T h e l e n g t h o f t o u r s i n z o n e s o f d i ® e r e n t s h a p e s . T r a n s p o r t a t i o n R e s e a r c h
P a r t B , 1 8 ( 2 ) , 1 3 5 - 1 4 6 .
C u i , O u y a n g , a n d S h e n : R e l i a b l e F a c i l i t y L o c a t i o n D e s i g n
3 0 A r t i c l e s u b m i t t e d t o O p e r a t i o n s R e s e a r c h ; m a n u s c r i p t n o . ( P l e a s e , p r o v i d e t h e m a n s u c r i p t n u m b e r ! )
[ 8 ] D a g a n z o , C . F . ( 1 9 8 4 b ) T h e d i s t a n c e t r a v e l e d t o v i s i t N p o i n t s w i t h a m a x i m u m o f C s t o p s p e r
p o i n t : A m a n u a l t o u r - b u i l d i n g s t r a t e g y a n d c a s e s t u d y . T r a n s p o r t a t i o n S c i e n c e , 1 8 , 3 3 1 - 3 5 0 .
[ 9 ] D a g a n z o , C . F . a n d N e w e l l , G . F . ( 1 9 8 6 ) C o n ¯ g u r a t i o n o f p h y s i c a l d i s t r i b u t i o n n e t w o r k s . N e t w o r k s
1 6 : 1 1 3 - 1 3 2 .
[ 1 0 ] D a g a n z o , C . F . a n d E r e r a , A . L . ( 1 9 9 9 ) O n p l a n n i n g a n d d e s i g n o f l o g i s t i c s s y s t e m s f o r u n c e r t a i n
e n v i r o n m e n t s . I n : N e w T r e n d s i n D i s t r i b u t i o n L o g i s t i c s . S p r i n g e r , B e r l i n , G e r m a n y , 3 - 2 1 .
[ 1 1 ] D a g a n z o , C . F . ( 1 9 9 2 ) L o g i s t i c s S y s t e m s A n a l y s i s ( 1 s t E d i t i o n ) , S p r i n g e r , B e r l i n , G e r m a n y .
[ 1 2 ] D a s c i , A . a n d V e r t e r , V . ( 2 0 0 1 ) A c o n t i n u o u s m o d e l f o r p r o d u c t i o n - d i s t r i b u t i o n s y s t e m d e s i g n .
E u r o p e a n J o u r n a l o f O p e r a t i o n a l R e s e a r c h 1 2 9 : 2 8 7 - 2 9 8 .
[ 1 3 ] D a s k i n , M . S . ( 1 9 8 2 ) A p p l i c a t i o n o f a n e x p e c t e d c o v e r i n g m o d e l t o e m e r g e n c y m e d i c a l s e r v i c e
s y s t e m d e s i g n . D e c i s i o n S c i e n c e 1 3 ( 3 ) : 4 1 6 - 4 3 9 .
[ 1 4 ] D a s k i n , M . S . ( 1 9 8 3 ) A m a x i m u m e x p e c t e d c o v e r i n g l o c a t i o n m o d e l : F o r m u l a t i o n , p r o p e r t i e s a n d
h e u r i s t i c s o l u t i o n . T r a n s p o r t a t i o n S c i e n c e 1 7 ( 1 ) : 4 8 - 7 0 .
[ 1 5 ] D a s k i n , M . S . ( 1 9 9 5 ) N e t w o r k a n d D i s c r e t e L o c a t i o n : M o d e l s , A l g o r i t h m s , a n d A p p l i c a t i o n s . J o h n
W i l e y , N e w Y o r k , 1 9 9 5 .
[ 1 6 ] D r e z n e r , Z . , e d i t o r . ( 1 9 9 5 ) F a c i l i t y L o c a t i o n : A S u r v e y o f A p p l i c a t i o n s a n d M e t h o d s . S p r i n g e r ,
N e w Y o r k , 1 9 9 5 .
[ 1 7 ] F e j e s T o t h , L . ( 1 9 5 9 ) S u r l a r e p r e s e n t a t i o n d ' u n e p o p u l a t i o n i n ¯ n i e p a r u n n o m b r e ¯ n i
d ' d l e m e n t s . A c t a M a t h , A c a d e m y o f S c i e n c e o f H u n g a r y , 1 0 : 2 9 9 - 3 0 4 .
[ 1 8 ] F i s h e r , M . L . ( 1 9 8 1 ) T h e L a g r a n g i a n r e l a x a t i o n m e t h o d f o r s o l v i n g i n t e g e r p r o g r a m m i n g p r o b -
l e m s . M a n a g e m e n t S c i e n c e 2 7 : 1 - 1 8 .
[ 1 9 ] G e r s h o , A . ( 1 9 7 9 ) A s y m p t o t i c a l l y o p t i m a l b l o c k q u a n t i z a t i o n , I E E E T r a n s a c t i o n s o n I n f o r m a -
t i o n T h e o r y I T - 2 5 ( 4 ) : 3 7 3 - 3 8 0 .
[ 2 0 ] B . G o l d e n g o r i n , G . S i e r k s m a , G . A . T i j s s e n a n d T s o , M . ( 1 9 9 9 ) T h e d a t a - c o r r e c t i n g a l g o r i t h m
f o r t h e m i n i m i z a t i o n o f s u p e r m o d u l a r f u n c t i o n s . M a n a g e m e n t S c i e n c e 4 5 : 1 5 3 9 - 1 5 5 1 .
[ 2 1 ] H a l l , R . W . ( 1 9 8 4 ) T r a v e l d i s t a n c e t h r o u g h t r a n s p o r t a t i o n t e r m i n a l s o n a r e c t a n g u l a r g r i d . J o u r -
n a l o f t h e O p e r a t i o n a l R e s e a r c h S o c i e t y 3 5 ( 1 2 ) : 1 0 6 7 - 1 0 7 8 .
C u i , O u y a n g , a n d S h e n : R e l i a b l e F a c i l i t y L o c a t i o n D e s i g n
A r t i c l e s u b m i t t e d t o O p e r a t i o n s R e s e a r c h ; m a n u s c r i p t n o . ( P l e a s e , p r o v i d e t h e m a n s u c r i p t n u m b e r ! ) 3 1
[ 2 2 ] H a l l , R . W . ( 1 9 8 6 ) D i s c r e t e m o d e l s / c o n t i n u o u s m o d e l s . O M E G A - I n t e r n a t i o n a l J o u r n a l o f M a n -
a g e m e n t S c i e n c e 1 4 ( 3 ) : 2 1 3 - 2 2 0 .
[ 2 3 ] H a l l , R . W . ( 1 9 8 9 ) C o n ¯ g u r a t i o n o f a n o v e r n i g h t p a c k a g e a i r n e t w o r k . T r a n s p o r t a t i o n R e s e a r c h
A 2 3 A ( 2 ) : 1 3 9 - 1 4 9
[ 2 4 ] J o h n s o n , W . ( 1 9 4 4 ) M a t h . a n d P h y s i c a l P r i n c i p l e s o f E n g i n e e r i n g A n a l y s i s , M c G r a w H i l l .
[ 2 5 ] K u h n , H . W . ( 1 9 5 5 ) T h e H u n g a r i a n M e t h o d f o r t h e a s s i g n m e n t p r o b l e m . N a v a l R e s e a r c h L o g i s t i c s
Q u a r t e r l y 2 : 8 3 C 9 7 .
[ 2 6 ] L a n g e v i n , A . , M b a r a g a , P . a n d C a m p b e l l , J . F . ( 1 9 9 6 ) C o n t i n u o u s a p p r o x i m a t i o n m o d e l s i n
f r e i g h t d i s t r i b u t i o n : A n o v e r v i e w . T r a n s p o r t a t i o n R e s e a r c h P a r t B 3 0 : 1 6 3 - 1 8 8 .
[ 2 7 ] L i m , M . , D a s k i n , M . , C h o p r a , S . , a n d B a s s a m b o o , A . ( 2 0 0 7 ) M a n a g i n g r i s k s o f f a c i l i t y d i s r u p -
t i o n s , W o r k i n g P a p e r , N o r t h w e s t e r n U n i v e r s i t y .
[ 2 8 ] N e w e l l , G . F . ( 1 9 7 1 ) D i s p a t c h i n g p o l i c i e s f o r a t r a n s p o r t a t i o n r o u t e , T r a n s p o r t a t i o n S c i e n c e 5 :
9 1 - 1 0 5 .
[ 2 9 ] N e w e l l , G . F . ( 1 9 7 3 ) S c h e d u l i n g , l o c a t i o n , t r a n s p o r t a t i o n a n d c o n t i n u u m m e c h a n i c s : s o m e s i m p l e
a p p r o x i m a t i o n s t o o p t i m i z a t i o n p r o b l e m s , S I A M J . A p p l . M a t h . 2 5 ( 3 ) : 3 4 6 - 3 6 0 .
[ 3 0 ] O k a b e , A . , B o o t s , B . a n d S u g i h a r a , K . ( 1 9 9 2 ) S p a t i a l T e s s e l l a t i o n s : C o n c e p t s a n d A p p l i c a t i o n s
o f V o r o n o i D i a g r a m s . W i l e y , C h i c h e s t e r , U K .
[ 3 1 ] O u y a n g , Y . a n d D a g a n z o , C . F . ( 2 0 0 6 ) D i s c r e t i z a t i o n a n d v a l i d a t i o n o f t h e c o n t i n u u m a p p r o x i -
m a t i o n s c h e m e f o r t e r m i n a l s y s t e m d e s i g n , T r a n s p o r t a t i o n S c i e n c e 4 0 ( 1 ) : 8 9 - 9 8 .
[ 3 2 ] O u y a n g , Y . ( 2 0 0 7 ) D e s i g n o f v e h i c l e r o u t i n g z o n e s f o r l a r g e - s c a l e d i s t r i b u t i o n s y s t e m s . T r a n s -
p o r t a t i o n R e s e a r c h P a r t B 4 1 ( 1 0 ) : 1 0 7 9 - 1 0 9 3 .
[ 3 3 ] Q i , L . a n d S h e n , Z . - J . M . ( 2 0 0 7 ) A s u p p l y c h a i n d e s i g n m o d e l w i t h u n r e l i a b l e s u p p l y . N a v a l
R e s e a r c h L o g i s t i c s 5 4 : 8 2 9 - 8 4 4 .
[ 3 4 ] Q i , L . , S h e n , Z . - J . M . , a n d S n y d e r , L . V . ( 2 0 0 8 ) T h e e ® e c t o f s u p p l y d i s r u p t i o n s o n s u p p l y c h a i n
n e t w o r k d e s i g n . S u b m i t t e d f o r p u b l i c a t i o n .
[ 3 5 ] R e v e l l e , C . a n d H o g a n , K . ( 1 9 8 9 ) T h e m a x i m u m a v a i l a b i l i t y l o c a t i o n p r o b l e m . T r a n s p o r t a t i o n
S c i e n c e 2 3 ( 3 ) : 1 9 2 - 2 0 0 .
C u i , O u y a n g , a n d S h e n : R e l i a b l e F a c i l i t y L o c a t i o n D e s i g n
3 2 A r t i c l e s u b m i t t e d t o O p e r a t i o n s R e s e a r c h ; m a n u s c r i p t n o . ( P l e a s e , p r o v i d e t h e m a n s u c r i p t n u m b e r ! )
[ 3 6 ] S h e r a l i , H . D . a n d A l a m e d d i n e , A . ( 1 9 9 2 ) A n e w r e f o r m u l a t i o n - l i n e a r i z a t i o n t e c h n i q u e f o r b i l i n e a r
p r o g r a m m i n g p r o b l e m s . J o u r n a l o f G l o b a l O p t i m i z a t i o n 2 ( 4 ) : 3 7 9 - 4 1 0 .
[ 3 7 ] S n y d e r , L . V . a n d D a s k i n M . S . ( 2 0 0 5 ) R e l i a b i l i t y m o d e l s f o r f a c i l i t y l o c a t i o n : t h e e x p e c t e d f a i l u r e
c o s t c a s e . T r a n s p o r t a t i o n S c i e n c e 3 9 ( 3 ) : 4 0 0 - 4 1 6 .
[ 3 8 ] h t t p : / / w w w . l e h i g h . e d u / l v s 2
[ 3 9 ] W e b e r , A . ( 1 9 5 7 ) T h e o r y o f t h e L o c a t i o n o f I n d u s t r i e s . U n i v e r s i t y o f C h i c a g o P r e s s , I L , 1 9 5 7 .
[ 4 0 ] Z h a n , R . L . , S h e n , Z . - J . M . , D a s k i n , M . S . ( 2 0 0 7 ) S y s t e m R e l i a b i l i t y w i t h L o c a t i o n - S p e c i ¯ c F a i l u r e
P r o b a b i l i t i e s . W o r k i n g p a p e r , U n i v e r s i t y o f C a l i f o r n i a , B e r k e l e y .
A p p e n d i x A : P r o o f o f t h e P r o p o s i t i o n s
A . 1 . P r o o f o f P r o p o s i t i o n 1
L e t ­ = f 0 ; 1 g J b e t h e s e t o f f a i l u r e s c e n a r i o s . F o r e a c h ! 2 ­ , l e t p ! b e t h e p r o b a b i l i t y t h a t s c e n a r i o
! w i l l o c c u r , a l s o l e t ± j ! b e t h e b i n a r y p a r a m e t e r i n d i c a t i n g w h e t h e r o r n o t f a c i l i t y j i s o p e r a t i o n a l
i n s c e n a r i o ! . T h e s c e n a r i o b a s e d s t o c h a s t i c p r o g r a m ( S S P ) i s f o r m u l a t e d a s f o l l o w s
( S S P ) M i n
J ¡ 1 X j = 0
f j X j +
I ¡ 1 X i = 0
J X j = 0 X ! 2 ­
¸ i d i j p ! Y i j ! ( 1 7 a )
s . t .
J X j = 0
Y i j ! = 1 8 0 · i · I ¡ 1 ; ! 2 ­ ( 1 7 b )
I ¡ 1 X i = 0
Y i j ! · ± j ! X j 8 0 · j · J ¡ 1 ; ! 2 ­ ( 1 7 c )
X j ; Y i j ! 2 f 0 ; 1 g 8 0 · i · I ¡ 1 ; 0 · j · J ; ! 2 ­ ; ( 1 7 d )
w h e r e X j i s t h e b i n a r y v a r i a b l e i n d i c a t i n g w h e t h e r o r n o t a f a c i l i t y i s b u i l d a t l o c a t i o n j , a n d Y i j !
i s e q u a l t o o n e i f a n d o n l y i f c u s t o m e r i i s s e r v e d b y f a c i l i t y j i n s c e n a r i o ! ( Y i J ! = 1 i n d i c a t e s t h a t
t h e p e n a l t y c o s t i s i n c u r r e d i n s c e n a r i o ! ) .
T o v e r i f y t h a t t h e s c e n a r i o b a s e d f o r m u l a t i o n ( 1 7 a ) - ( 1 7 d ) i s e q u i v a l e n t t o t h e c o m p a c t ( R U F L )
f o r m u l a t i o n ( 1 a ) - ( 1 g ) , w e ¯ r s t s h o w h o w t o m a p a n o p t i m a l s o l u t i o n o f ( R U F L ) t o a f e a s i b l e s o l u t i o n
o f ( S S P ) . L e t ( X ; Y ; P ) b e a n o p t i m a l s o l u t i o n o f ( R U F L ) , w e c o n s t r u c t a s o l u t i o n ( X 0 ; Y 0 ) f o r
( S S P ) b y l e t t i n g X 0 = X . F o r e a c h 0 · i · I ¡ 1 a n d 0 · r · J , l e t j ( i ; r ) 2 f 0 · j · J : Y i j r = 1 g ,
C u i , O u y a n g , a n d S h e n : R e l i a b l e F a c i l i t y L o c a t i o n D e s i g n
A r t i c l e s u b m i t t e d t o O p e r a t i o n s R e s e a r c h ; m a n u s c r i p t n o . ( P l e a s e , p r o v i d e t h e m a n s u c r i p t n u m b e r ! ) 3 3
i . e . j ( i ; r ) i s t h e u n i q u e f a c i l i t y t h a t s e r v e s c u s t o m e r i a t l e v e l r . T h e c u s t o m e r a s s i g n m e n t i n e a c h
s c e n a r i o i s d e t e r m i n e d a s f o l l o w s ( b y c o n v e n t i o n , w e l e t ± J ! = 1 f o r a l l ! 2 ­ )
Y 0 i j ! = ½ 1 i f j = j ( i ; r ) f o r s o m e 0 · r · J ; ± j ! = 1 ; a n d ± j ( i ; ` ) ! = 0 ; 8 0 · ` · r ¡ 1
0 o t h e r w i s e :
B y c o n s t r u c t i o n , ( X 0 ; Y 0 ) i s f e a s i b l e t o ( S S P ) . N e x t , w e s h o w t h a t ( X 0 ; Y 0 ) a c h i e v e s t h e s a m e
o b j e c t v a l u e a s ( X ; Y ; P ) . L e t © ( X ; Y ; P ) a n d ª ( X 0 ; Y 0 ) b e t h e o b j e c t i v e f u n c t i o n o f ( R U F L ) a n d
( S S P ) r e s p e c t i v e l y . A l s o , d e ¯ n e ­ ( i ; r ) = f ! 2 ­ : Y 0 i j ( i ; r ) ! = 1 g , i . e . ­ ( i ; r ) i s t h e s e t o f s c e n a r i o s i n
w h i c h c u s t o m e r i i s s e r v e d b y f a c i l i t y j ( i ; r ) . I t f o l l o w s t h a t
ª ( X 0 ; Y 0 ) =
J ¡ 1 X j = 0
f j X 0 j
+
I ¡ 1 X i = 0
J X j = 0 X ! 2 ­
¸ i d i j p ! Y 0 i j !
=
J ¡ 1 X j = 0
f j X j +
I ¡ 1 X i = 0
J X r = 0
¸ i d i ; j ( i ; r ) X ! 2 ­ ( i ; r )
p !
=
J ¡ 1 X j = 0
f j X j +
I ¡ 1 X i = 0
J X r = 0
¸ i d i ; j ( i ; r ) ( 1 ¡ q j ( i ; r ) )
r ¡ 1 Y ` = 0
q j ( i ; ` )
=
J ¡ 1 X j = 0
f j X j +
I ¡ 1 X i = 0
J X r = 0
J X j = 0
¸ i d i j P i j r Y i j r
= © ( X ; Y ; P ) ;
w h i c h i m p l i e s t h a t s o l v i n g ( S S P ) y i e l d s a l o w e r b o u n d t o ( R U F L ) .
C o n v e r s e l y , g i v e n a n o p t i m a l s o l u t i o n ( X ; Y ) t o ( S S P ) , w e c o n s t r u c t a f e a s i b l e s o l u t i o n
( X 0 ; Y 0 ; P 0 ) t o ( R U F L ) , a l s o b y l e t t i n g X 0 = X . W i t h o u t l o s s o f g e n e r a l i t y , w e a s s u m e t h a t Y i j ! = 1
i f a n d o n l y i f j = m i n f 0 · k · J : ± k ! X k = 1 ; d i k · d i k 0 8 k 0 6 = k s . t . ± k 0 ! X k 0 = 1 g ( b y c o n v e n t i o n ,
w e a s s u m e X J = 1 ) , i . e . e a c h c u s t o m e r i s a l w a y s s e r v e d b y h e r c l o s e s t o p e n f a c i l i t y , a n d i f t h e r e
a r e m o r e t h a n o n e f a c i l i t i e s t h a t a r e e q u a l l y c l o s e , w e b r e a k t h e t i e b y c h o o s i n g t h e f a c i l i t y w i t h
t h e l o w e s t i n d e x .
L e t N = f 0 · j · J ¡ 1 : X j = 1 g b e t h e s e t o f f a c i l i t i e s t h a t a r e c o n s t r u c t e d i n t h e o p t i m a l
s o l u t i o n t o ( S S P ) . F o r e a c h c u s t o m e r i , l e t j ( i ; 0 ) ; j ( i ; 1 ) ; ¢ ¢ ¢ ; j ( i ; j N j ) b e a n o r d e r i n g o f t h e
f a c i l i t i e s i n N S f J g s u c h t h a t f o r a l l 1 · r · j N j , d i ; j ( i ; r ¡ 1 ) · d i ; j ( i ; r ) , a n d i f d i ; j ( i ; r ¡ 1 ) = d i ; j ( i ; r ) , t h e n
C u i , O u y a n g , a n d S h e n : R e l i a b l e F a c i l i t y L o c a t i o n D e s i g n
3 4 A r t i c l e s u b m i t t e d t o O p e r a t i o n s R e s e a r c h ; m a n u s c r i p t n o . ( P l e a s e , p r o v i d e t h e m a n s u c r i p t n u m b e r ! )
j ( i ; r ¡ 1 ) < j ( i ; r ) . A l s o , d e ¯ n e ­ ( i ; r ) = f ! 2 ­ : ± j ( i ; r ) ! = 1 ; a n d ± j ( i ; ` ) ! = 0 ; 8 0 · ` · r ¡ 1 g . W e
s e t t h e v a l u e s o f Y 0 a n d P 0 a s f o l l o w s
Y 0 i j r = ½ 1 i f j = j ( i ; r ) a n d d i j · d i J
0 o t h e r w i s e
P 0 i j r = ½ ( 1 ¡ q j ( i ; r ) ) Q r ¡ 1
` = 0 q j ( i ; ` ) i f j = j ( i ; r ) a n d d i j · d i J
0 o t h e r w i s e :
I t i s c l e a r t h a t b y c o n s t r u c t i o n ( X 0 ; Y 0 ; P 0 ) i s f e a s i b l e t o ( R U F L ) . T h e o b j e c t i v e v a l u e a s s o c i a t e d
w i t h s o l u t i o n i s
© ( X 0 ; Y 0 ; P 0 ) =
J ¡ 1 X j = 0
f j X 0 j
+
I ¡ 1 X i = 0
J ¡ 1 X r = 0
J ¡ 1 X j = 0
¸ i d i j P 0 i j r Y 0 i j r
=
J ¡ 1 X j = 0
f j X j +
I ¡ 1 X i = 0
j N j X r = 0
¸ i d i ; j ( i ; r ) ( 1 ¡ q j ( i ; r ) )
r ¡ 1 Y ` = 0
q j ( i ; ` )
=
J ¡ 1 X j = 0
f j X j +
I ¡ 1 X i = 0
J X r = 0
¸ i d i ; j ( i ; r ) X ! 2 ­ ( i ; r )
p !
=
J ¡ 1 X j = 0
f j X j +
I ¡ 1 X i = 0
J X j = 0 X ! 2 ­
¸ i d i j p ! Y i j !
= ª ( X ; Y ) :
T h e r e f o r e , t h e o p t i m a l s o l u t i o n t o ( S S P ) i s a l s o a l o w e r b o u n d t o ( R U F L ) . T h i s c o m p l e t e s o u r
p r o o f . Q . E . D .
A . 2 . P r o o f o f P r o p o s i t i o n 2
S u p p o s e , f o r a c o n t r a d i c t i o n , t h a t ( X ; Y ; P ) i s o p t i m a l f o r ( R U F L ) w h e r e Y i j r = Y i k ; r + 1 = 1 a n d
d i j > d i k f o r s o m e 0 · i · I ¡ 1 ; 0 · j · J , a n d 0 · r · R . W e w i l l s h o w t h a t b y \ s w a p p i n g " j
a n d k t h e o b j e c t i v e v a l u e w i l l d e c r e a s e . O b v i o u s l y j · J ¡ 1 , o t h e r w i s e j i s t h e p s e u d o f a c i l i t y a n d
c u s t o m e r i c a n n o t b e a s s i g n e d t o f a c i l i t y k a s a b a c k u p . W e c o n s i d e r t w o c a s e s b a s e d o n w h e t h e r
o r n o t k i s t h e p s e u d o f a c i l i t y .
I f k · J ¡ 1 w e c o n s t r u c t a d i ® e r e n t s o l u t i o n ( X 0 ; Y 0 ; P 0 ) a s f o l l o w s :
X 0 = X ;
Y 0 h ` s = 8 < :
1 i f h = i ; ` = k ; s = r o r h = i ; ` = j ; s = r + 1 ;
0 i f h = i ; ` = j ; s = r o r h = i ; ` = k ; s = r + 1 ;
Y h ` s o t h e r w i s e ;
C u i , O u y a n g , a n d S h e n : R e l i a b l e F a c i l i t y L o c a t i o n D e s i g n
A r t i c l e s u b m i t t e d t o O p e r a t i o n s R e s e a r c h ; m a n u s c r i p t n o . ( P l e a s e , p r o v i d e t h e m a n s u c r i p t n u m b e r ! ) 3 5
P 0 h ` s = 8 >
> < >
> :
1 ¡ q k
1 ¡ q j
P j r i f h = i ; ` = k ; s = r ;
q k ( 1 ¡ q j )
1 ¡ q k
P 0 k
r = q k P j r i f h = i ; ` = j ; s = r + 1 ;
0 i f h = i ; ` = j ; s = r o r h = i ; ` = k ; s = r + 1 ;
P h ` s o t h e r w i s e .
B y c o n s t r u c t i o n , ( X 0 ; Y 0 ; P 0 ) i s a f e a s i b l e s o l u t i o n . L e t © ( X ; Y ; P ) b e t h e o b j e c t i v e v a l u e a s s o -
c i a t e d w i t h ( X ; Y ; P ) , i t f o l l o w s t h a t :
© ( X 0 ; Y 0 ; P 0 ) ¡ © ( X ; Y ; P ) = ¸ i ( P 0 k
r d i k + P 0 j ; r + 1 d i j ¡ P j r d i j ¡ P k ; r + 1 d i k )
= ¸ i [ d i k ( P 0 k
r ¡ P k ; r + 1 ) ¡ d i j ( P j r ¡ P 0 j ; r + 1 ) ]
= ¸ i f d i k [
1 ¡ q k
1 ¡ q j
P j r ¡
q j ( 1 ¡ q k )
1 ¡ q j
P j r ] ¡ d i j ( P j r ¡ q k P j r ) g
= ¸ i ( 1 ¡ q k ) ( d i k ¡ d i j ) P j r < 0 :
T h e c a s e i n w h i c h k = J i s s i m i l a r , e x c e p t t h a t Y 0 i j ; r + 1 = P 0 i j ; r + 1 = 0 , w h i c h r e d u c e s t h e c o s t e v e n
m o r e . T h i s i m p l i e s a c o n t r a d i c t i o n t o t h a t ( X ; Y ; P ) i s o p t i m a l . Q . E . D .
A . 3 . P r o o f o f P r o p o s i t i o n 3
L e t S µ f 0 ; ¢ ¢ ¢ ; J ¡ 1 g b e a s u b s e t o f c a n d i d a t e l o c a t i o n s , a n d u ; v 2 f 0 ; ¢ ¢ ¢ ; J ¡ 1 g n S , w e s h o w
t h a t
© i ( S [ f u ; v g ) ¡ © i ( S [ f u g ) ¸ © i ( S [ f v g ) ¡ © i ( S ) : ( 1 8 )
A s s u m e t h a t S = f j 1 ; j 2 ; ¢ ¢ ¢ ; j n g w h e r e d i j 1 · d i j 2 · ¢ ¢ ¢ · d i j n , i . e . , w e s o r t e l e m e n t s i n S i n
n o n d e c r e a s i n g o r d e r o f t h e i r d i s t a n c e t o c u s t o m e r i . L e t
¹ n = i n f f 1 · k · n : d i j k · Á i g
s = i n f f 1 · k · n : d i j k · d i u g
t = i n f f 1 · k · n : d i j k · d i v g :
I n a d d i t i o n , d e ¯ n e
P k = ½ Q k
` = 1 q j ` 1 · k · ¹ n
1 k = 0 ;
C k = ½ P k ¡ 1 ( 1 ¡ q j k ) d i j k 1 · k · ¹ n
P ¹ n Á i k = ¹ n + 1 :
C u i , O u y a n g , a n d S h e n : R e l i a b l e F a c i l i t y L o c a t i o n D e s i g n
3 6 A r t i c l e s u b m i t t e d t o O p e r a t i o n s R e s e a r c h ; m a n u s c r i p t n o . ( P l e a s e , p r o v i d e t h e m a n s u c r i p t n u m b e r ! )
F o l l o w i n g a s i m i l a r a r g u m e n t a s i n t h e p r o o f o f P r o p o s i t i o n 2 , w e k n o w t h a t i t i s o p t i m a l t o a s s i g n
t h e f a c i l i t i e s l e v e l b y l e v e l i n i n c r e a s i n g o r d e r o f d i s t a n c e , u n t i l t h e t r a n s p o r t a t i o n c o s t e x c e e d s t h e
p e n a l t y c o s t , i . e . ,
© i ( S ) = ¸ i
¹ n X k = 1
P k ¡ 1 ( 1 ¡ q j k ) d i j k + P ¹ n Á i + X j 2 S
¹ i j
= ¸ i
¹ n + 1 X k = 1
C k + X j 2 S
¹ i j :
W i t h o u t l o s s o f g e n e r a l i t y , w e a s s u m e t h a t d i u a n d d i v a r e l e s s t h a n t h e p e n a l t y c o s t Á i , i . e . s · ¹ n
a n d t · ¹ n . I t f o l l o w s t h a t
© i ( S [ f v g ) ¡ © i ( S ) = ¸ i [
t X k = 1
C k + P t ( 1 ¡ q v ) d i v + q v
¹ n + 1 X k = t + 1
C k ] + X j 2 S [ f v g
¹ i j ¡ ¸ i
¹ n + 1 X k = 1
C k ¡ X j 2 S
¹ i j
= ¸ i [ P t ( 1 ¡ q v ) d i v ¡ ( 1 ¡ q v )
¹ n + 1 X k = t + 1
C k ] + ¹ i v
= ¸ i ( 1 ¡ q v ) [ P t d i v ¡
¹ n + 1 X k = t + 1
C k ] + ¹ i v :
N o t e t h a t t h e ¯ r s t i t e m i n t h e l a s t e q u a t i o n i s n e g a t i v e , b e c a u s e
P t d i v ¡
¹ n + 1 X k = t + 1
C k = P t [ d i v ¡
¹ n X k = t + 1
(
k ¡ 1 Y ` = t + 1
q j ` ) ( 1 ¡ q j k ) d i j k ¡ (
¹ n Y ` = t + 1
q j ` ) Á i ]
< P t d i v [ 1 ¡ (
k ¡ 1 Y ` = t + 1
q j ` ) ( 1 ¡ q j k ) ¡
¹ n Y ` = t + 1
q j ` ] = 0 :
T o s h o w t h a t ( 1 8 ) h o l d s , w e c o n s i d e r t h e f o l l o w i n g t w o c a s e s .
C a s e 1 : d i u · d i v . I n t h i s c a s e , i t f o l l o w s t h a t
© i ( S [ f u ; v g ) ¡ © i ( S [ f u g ) = ¸ i [
s X k = 1
C k + P s ( 1 ¡ q u ) d i u + q u
t X k = s + 1
C k + q u P t ( 1 ¡ q t ) d i v + q u q v
¹ n + 1 X k = t + 1
C k
+ X j 2 S [ f u ; v g
¹ i j ¡ ¸ i [
s X k = 1
C k + P s ( 1 ¡ q u ) d i u + q u
¹ n + 1 X k = s + 1
C k ] ¡ X j 2 S [ f u g
¹ i j
= ¸ i [ q u P t ( 1 ¡ q v ) d i v ¡ q u ( 1 ¡ q v )
¹ n + 1 X k = t + 1
C k ] + u i v
= ¸ i q u ( 1 ¡ q v ) ( P t d i v ¡
¹ n + 1 X k = t + 1
C k ) + ¹ i v :
C l e a r l y ( 1 8 ) h o l d s i n t h i s c a s e , s i n c e 0 · q u · 1 a n d P t d i v ¡ P ¹ n + 1
k = t + 1 C k < 0 .
C u i , O u y a n g , a n d S h e n : R e l i a b l e F a c i l i t y L o c a t i o n D e s i g n
A r t i c l e s u b m i t t e d t o O p e r a t i o n s R e s e a r c h ; m a n u s c r i p t n o . ( P l e a s e , p r o v i d e t h e m a n s u c r i p t n u m b e r ! ) 3 7
C a s e 2 : d i u > d i v . I n t h i s c a s e t · s , a n d t h e f o l l o w i n g a s s e r t i o n h o l d s :
© i ( S [ f u ; v g ) ¡ © i ( S [ f u g ) = ¸ i [
t X k = 1
C k + P t ( 1 ¡ q v ) d i v + q v
s X k = t + 1
C k + q v P s ( 1 ¡ q u ) d i u + q v q u
¹ n + 1 X k = s + 1
C k ]
+ X j 2 S [ f u ; v g
¹ i j ¡ ¸ i [
s X k = 1
C k + P s ( 1 ¡ q u ) d i u + q u
¹ n + 1 X k = s + 1
C k ] ¡ X j 2 S [ f u g
¹ i j
= ¸ i f P t ( 1 ¡ q v ) d i v ¡ ( 1 ¡ q v ) [
s X k = t + 1
C k + P s ( 1 ¡ q u ) d i u + q u
¹ n + 1 X k = s + 1
C k ] g + ¹ i v
= ¸ i ( 1 ¡ q v ) f P t d i v ¡ [
s X k = t + 1
C k + P s ( 1 ¡ q u ) d i u + q u
¹ n + 1 X k = s + 1
C k ] g + ¹ i v :
W e c l a i m t h a t ( 1 8 ) h o l d s i n t h i s c a s e , b e c a u s e
[
s X k = t + 1
C k + P s ( 1 ¡ q u ) d i u + q u
¹ n + 1 X k = s + 1
C k ] ¡
¹ n + 1 X k = t + 1
C k
· [
s X k = t + 1
C k + P s ( 1 ¡ q u ) d i u + q u
¹ n + 1 X k = s + 1
C k ] ¡
¹ n + 1 X k = s + 1
C k
= ( 1 ¡ q u ) [ P s d i u ¡
¹ n + 1 X k = s + 1
C k ] < 0 :
Q . E . D .
A . 4 . P r o o f o f P r o p o s i t i o n 4
F i r s t , w e i n t r o d u c e a n e q u i v a l e n t f o r m u l a t i o n o f ( R S P ) b y \ s p l i t i n g " t h e d e c i s i o n v a r i a b l e s :
Y j r = ½ 1 i f t h e l e v e l r f a c i l i t y f o r t h i s c u s t o m e r h a s t h e s a m e t r a n s p o r t a t i o n d i s t a n c e a s f a c i l i t y j
0 o t h e r w i s e .
Z j r = ½ 1 i f t h e l e v e l r f a c i l i t y f o r c u s t o m e r i h a s t h e s a m e f a i l u r e p r o b a b i l i t y a s f a c i l i t y j
0 o t h e r w i s e .
I t i s c l e a r t h a t R S P i s e q u i v a l e n t t o t h e f o l l o w i n g p r o b l e m :
M i n
J X j = 0
R X r = 0
¸ i d i j W j r +
J ¡ 1 X j = 0
R ¡ 1 X r = 0
¹ i j Y j r ( 1 9 a )
s . t . ( 4 b ) ¡ ( 4 d ) ( 1 9 b )
J ¡ 1 X j = 0
Z j r +
r ¡ 1 X s = 0
Z J s = 1 8 0 · r · R ( 1 9 c )
R ¡ 1 X r = 0
Z j r · 1 8 0 · j · J ¡ 1 ( 1 9 d )
C u i , O u y a n g , a n d S h e n : R e l i a b l e F a c i l i t y L o c a t i o n D e s i g n
3 8 A r t i c l e s u b m i t t e d t o O p e r a t i o n s R e s e a r c h ; m a n u s c r i p t n o . ( P l e a s e , p r o v i d e t h e m a n s u c r i p t n u m b e r ! )
R X r = 0
Z J r = 1 ( 1 9 e )
P j 0 = 1 ¡ q j 8 0 · j · J ( 1 9 f )
P j r = ( 1 ¡ q j )
J ¡ 1 X k = 0
q k
1 ¡ q k
W i ; k ; r ¡ 1 8 0 · j · J ; 1 · r · R ( 1 9 g )
W j r · P j r 8 0 · j · J ; 0 · r · R ( 1 9 h )
W j r · Z j r 8 0 · j · J ; 0 · r · R ( 1 9 i )
W j r ¸ 0 8 0 · j · J ; 0 · r · R ( 1 9 j )
W j r ¸ P j r + Z j r ¡ 1 8 0 · j · J ; 0 · r · R ( 1 9 k )
Y j r ; Z j r 2 f 0 ; 1 g 8 0 · j · J ; 0 · r · R ( 1 9 l )
Y j r = Z j r 8 0 · j · J ; 0 · r · R : ( 1 9 m )
I f w e r e m o v e t h e l a s t c o n s t r a i n t ( 1 9 m ) , t h e c u s t o m e r i s a l l o w e d t o c h o o s e a n a r b i t r a r y c o m b i -
n a t i o n o f t r a n s p o r t a t i o n c o s t a n d f a i l u r e p r o b a b i l i t y . N e x t , w e s h o w t h a t t h e ( R R S P ) f o r m u l a t i o n
( 7 a ) - ( 7 e ) i s e q u i v a l e n t t o f o r m u l a t i o n ( 1 9 a ) - ( 1 9 l ) , b a s e d o n t h e f o l l o w i n g l e m m a .
L e m m a 1 . T h e r e e x i s t s a n o p t i m a l s o l u t i o n ( Y ¤ ; Z ¤ ; P ¤ ) t o f o r m u l a t i o n ( 1 9 a ) - ( 1 9 l ) , s u c h t h a t i f
Z ¤ j r = 1 , Z ¤ k ; r + 1 = 1 a n d r + 1 · R ¡ 1 , t h e n q j · q k .
P r o o f o f L e m m a 1 . S u p p o s e t h a t ( Y ; Z ; P ) i s a n o p t i m a l s o l u t i o n t o f o r m u l a t i o n ( 1 9 a ) - ( 1 9 l ) , s u c h
t h a t Z j r = 1 , Z k ; r + 1 = 1 , j ; k · R ¡ 1 a n d q j > q k . L e t u a n d v b e t h e f a c i l i t i e s a s s i g n e d t o t h i s
c u s t o m e r a t l e v e l r a n d r + 1 , i . e . Y u r = 1 a n d Y v ; r + 1 = 1 . W e c o n s t r u c t a n e w s o l u t i o n ( Y 0 ; Z 0 ; P 0 )