On the Formulation and Solution of an
Emergency Routing Problem 
Darin Goldstein† Tariq Shehab‡ Juan Casse §
Hsiu- Chin Lin ¶
October 31, 2007
Abstract
I n t h i s w o r k , w e w i l l i d e n t i f y i m p o r t a n t v a r i a b l e s t h a t c o n t r i b u t e t o
v e h i c u l a r m o v e m e n t i n a n e m e r g e n c y e n v i r o n m e n t . I n p a r t i c u l a r , w e f o r -
m u l a t e a n d p o s e t h e C o n v o y R o u t i n g P r o b l e m ( u s i n g f a r f e w e r v a r i a b l e s
t h a n o t h e r i m p o r t a n t m o d e l s w i t h o u t s a c r i fi c i n g t o o m u c h i n t h e w a y o f
s o l u t i o n a c c u r a c y ) . W e s u g g e s t a m e t h o d f o r m o d e l i n g t h e p r o b l e m a n d
f o r m u l a t e a p r e c i s e p r o b l e m s t a t e m e n t . T h e d i ffi c u l t y o f t h e p r o p o s e d
p r o b l e m i s e x a m i n e d , p r a c t i c a l p a r a m e t e r s a r e g a t h e r e d v i a e x t e n s i v e l i t -
e r a t u r e s e a r c h , a n d a n a l g o r i t h m u s i n g a r t i fi c i a l i n t e l l i g e n c e t e c h n i q u e s f o r
i t s s o l u t i o n i s p r e s e n t e d a n d e m p i r i c a l l y a n a l y z e d v i a s o f t w a r e s i m u l a t i o n .
 T h i s w o r k w a s s u p p o r t e d b y M E T R A N S g r a n t 0 6 - 0 3 .
† D e p a r t m e n t o f C o m p u t e r E n g i n e e r i n g a n d C o m p u t e r S c i e n c e , C a l i f o r n i a S t a t e U n i v e r s i t y ,
L o n g B e a c h , C A 9 0 8 4 0 ( dgoldste@ csulb. edu ) .
‡ D e p a r t m e n t o f C i v i l E n g i n e e r i n g , C a l i f o r n i a S t a t e U n i v e r s i t y , L o n g B e a c h , C A 9 0 8 4 0
( shehab@ csulb. edu ) .
§ D e p a r t m e n t o f C o m p u t e r E n g i n e e r i n g a n d C o m p u t e r S c i e n c e , C a l i f o r n i a S t a t e U n i v e r s i t y ,
L o n g B e a c h , C A 9 0 8 4 0
¶ D e p a r t m e n t o f C o m p u t e r E n g i n e e r i n g a n d C o m p u t e r S c i e n c e , C a l i f o r n i a S t a t e U n i v e r s i t y ,
L o n g B e a c h , C A 9 0 8 4 0
1
ON THE FORMULATION OF AN EMERGENCY ROUTING PROBLEM 2
1 I n t r o d u c t i o n
T h e a f t e r m a t h o f h u r r i c a n e s K a t r i n a a n d R i t a a n d t h e p o o r r e s p o n s e o f t h e
g o v e r n m e n t a l e m e r g e n c y s e r v i c e s h i g h l i g h t t h e n e e d f o r a m o r e e ffi c i e n t a n d
c a p a b l e p o s t - d i s a s t e r a s s e t - m o v e m e n t s y s t e m . A t i m e l y a n d s e a m l e s s m o v e m e n t
o f g o o d s ( e s p e c i a l l y c o n s u m a b l e a n d p e r i s h a b l e m a t e r i a l ) a n d p e o p l e i s d i ffi c u l t
d u r i n g n o r m a l c i r c u m s t a n c e s i n a n y l a r g e u r b a n a r e a w i t h c o m p l e x g r i d l i n e s a n d
a l a r g e t r a n s p o r t a t i o n n e t w o r k . T h e c o m p l e x i t y i s m a g n i fi e d w h e n a d i s a s t e r
e l i m i n a t e s s o m e o f t h e r o u t e s a n d / o r d e s t r o y s s o m e o f t h e s t o r a g e l o c a t i o n s . I t
i s , h o w e v e r , e x a c t l y i n s u c h c i r c u m s t a n c e s w h e n a r o b u s t a n d a d a p t i v e p l a n o f
t r a n s p o r t a t i o n i s v i t a l i n s u p p o r t o f t h e g e n e r a l p o p u l a t i o n .
A s o l u t i o n f o r t h e m o v e m e n t o f g o o d s t h a t r e l i e s o n a r e l a t i v e l y s t a t i c c o n -
d i t i o n o f r o a d s a n d s e r v i c e s c a n n o t s i m p l y b e a d o p t e d d u r i n g a n d i m m e d i a t e l y
a f t e r a d i s a s t e r ; t h e c h a o t i c m o v e m e n t o f p r e c i o u s c o m m o d i t i e s s u c h a s i c e a f t e r
K a t r i n a , f o r e x a m p l e , w a s c l e a r l y u n a c c e p t a b l e . A n e x c e r p t f r o m a 2 0 0 5 a r t i c l e
b y M a t t R y a n ( R y a n , 2 0 0 5 ) i l l u s t r a t e s t h e b a s i c p o i n t .
“ F e d e r a l l y f u n d e d d i s a s t e r r e l i e f i s n o t u s e d e ffi c i e n t l y b e c a u s e o ffi -
c i a l s d o n ’ t f a c e t h e s a m e d i s c i p l i n e t h a t p e o p l e f a c e i n p r i v a t e m a r -
k e t s . T h e j o u r n e y o f a n i c e t r u c k p r o v i d i n g K a t r i n a r e l i e f i l l u s t r a t e s
F E M A ’ s i n a b i l i t y t o c o o r d i n a t e a n d i t s b l i n d n e s s t o c o s t e ff e c t i v e -
n e s s . A f t e r l e a v i n g W i s c o n s i n a n d a r r i v i n g i n L o u i s i a n a , t h e t r u c k
w a s s e n t t o G e o r g i a b u t t h e n r e - r o u t e d t o S o u t h C a r o l i n a . A f t e r
e n d i n g u p i n M a r y l a n d , t h e t r u c k ’ s i c e s a t s t a t i o n a r y f o r d a y s , w h i l e
c o s t i n g t a x p a y e r s m o n e y a n d l e a v i n g t h o s e i n n e e d o f r e l i e f w i t h
f e w e r s u p p l i e s . ”
C l e a r l y , a n a d a p t i v e / i n t e l l i g e n t a g e n t i s n e c e s s a r y t o m a n a g e a n d d i r e c t t h e
m o v e m e n t o f g o o d s a s t h e o p e r a t i n g e n v i r o n m e n t e v o l v e s . W h e n d e v e l o p i n g
a g o o d s d i s t r i b u t i o n s y s t e m , a s R y a n n o t e s a b o v e , i t i s d e s i r a b l e t o d e s i g n a
s y s t e m t h a t i s n o t o n l y a b l e t o o b t a i n r e a s o n a b l e s o l u t i o n s f o r g i v e n s e t o f
c i r c u m s t a n c e s , b u t i t i s a l s o a b l e t o a d a p t i t s s o l u t i o n s r a p i d l y t o u n f o r e s e e n
ON THE FORMULATION OF AN EMERGENCY ROUTING PROBLEM 3
r o a d b l o c k s ( a n d p o t e n t i a l l y t a k e a d v a n t a g e o f f o r t u i t o u s o c c u r r e n c e s a s t h e y
h a p p e n ) .
C o m m o n l y , s y s t e m s t h a t a d d r e s s t h e g o o d s d i s t r i b u t i o n p r o b l e m c o m e i n
t h e f o r m o f m o d e l s t h a t , g i v e n i n p u t s t h a t m i g h t c o n s i s t o f a g o o d s m a n i f e s t
a n d a d a t a b a s e o f r o a d m a p s , p r o d u c e a s c h e d u l e f o r d i s t r i b u t i o n . S u c h m o d e l s
a r e a l l o w e d t o s e a r c h f o r h o u r s o r e v e n d a y s f o r t h e o p t i m a l s o l u t i o n . O f c o u r s e ,
i n t h e f a c e o f a n i m m e d i a t e a n d c a t a s t r o p h i c e m e r g e n c y , t h e s e a r c h f o r o p t i m a l
s o l u t i o n s t a k e s t o o l o n g t o c o m p u t e a n d i m p l e m e n t ; a p e r f e c t s o l u t i o n , t h o u g h
d e s i r a b l e d u r i n g n o r m a l c i r c u m s t a n c e s , i s n o t p o s s i b l e t o o b t a i n i n r e a l - t i m e
g i v e n t h e fl u i d n a t u r e o f a p o s t - c a t a s t r o p h i c e n v i r o n m e n t .
T h e t e c h n o l o g i e s f o r c o l l e c t i n g d a t a o n r o a d c o n d i t i o n s a n d g o o d s m o v e -
m e n t h a v e i m p r o v e d s i g n i fi c a n t l y o v e r t h e p a s t s e v e r a l y e a r s . I t i s n o w p o s s i b l e
t o a c c e s s t h e v e l o c i t y o f m o s t s e c t i o n s o f t h e m a j o r f r e e w a y s a n d h i g h w a y s i n
s o u t h e r n C a l i f o r n i a v i a t h e I n t e r n e t ( T e c h n o l o g i e s , n . d . ) . M a n y t r u c k i n g c o m p a -
n i e s n o w c a r r y G P S n a v i g a t i o n s y s t e m s a n d / o r e l e c t r o n i c t r a c k i n g d e v i c e s t h a t
a l l o w t h e i r c e n t r a l h a n d l i n g a g e n c i e s t o h a v e a l m o s t i n s t a n t a n e o u s k n o w l e d g e
o f t h e p o s i t i o n s o f t h e e n t i r e fl e e t a t o n c e . P o l i c e h e l i c o p t e r s a r e n o w a v a i l a b l e
i n e v e r y m a j o r p o p u l a t i o n c e n t e r . A s i n g l e h u m a n b e i n g ( o r , s o m e t i m e s , e v e n a
h i g h l y q u a l i fi e d t e a m , a s K a t r i n a s h o w e d ) i s n o l o n g e r a b l e t o p r o c e s s a l l t h a t
i n f o r m a t i o n a t o n c e . T h e d a t a i s a v a i l a b l e ; w h a t i s n o w n e e d e d i s a s y s t e m f o r
c o l l e c t i n g , o r g a n i z i n g , a n d p r o c e s s i n g i t i n a r e a l - t i m e a d a p t i v e w a y .
O u r fi r s t g o a l i n S e c t i o n 1 . 1 w i l l b e t o i d e n t i f y t h e v a r i a b l e s t h a t c o n t r i b u t e t o
a r e a l i s t i c m o d e l o f p o s t - d i s a s t e r t r a ffi c fl o w v i a c o m p a r i s o n w i t h p r e v i o u s w o r k .
I n S e c t i o n 2 , w e w i l l t h e n u s e t h i s i n f o r m a t i o n t o d e r i v e a m a t h e m a t i c a l p r o b l e m
t h a t c a n b e a n a l y z e d u s i n g t h e t o o l s o f t h e o r e t i c a l c o m p u t e r s c i e n c e . W e m a k e
a f e w r e m a r k s a b o u t t h e p r o b l e m f o r m u l a t i o n a n d t h e n d e l v e i n t o a n a l y s i s o f
t h e l i m i t i n g b e h a v i o r o f t h e p r o b l e m i t s e l f i n S e c t i o n 2 . 2 . W e w i l l s h o w t h a t
t h e p r o b l e m i s m o s t l i k e l y i n t r a c t a b l e ( S e c t i o n 2 . 3 ) . I n S e c t i o n 3 , w e d i s c u s s
r e a l i s t i c p a r a m e t e r s f o r t h e p r o b l e m . F i n a l l y , w e s u g g e s t v a r i o u s m e t h o d s f o r
fi n d i n g a p p r o x i m a t e s o l u t i o n s t o t h e p r o b l e m i n s p i t e o f i t s i n t r a c t a b i l i t y u s i n g
c e r t a i n f o r m s o f a r t i fi c i a l i n t e l l i g e n c e i n S e c t i o n 4 .
ON THE FORMULATION OF AN EMERGENCY ROUTING PROBLEM 4
1 . 1 P r e v i o u s W o r k
T h e r e i s a s u b s t a n t i a l b o d y o f w o r k o n t r a ffi c m o d e l s . S e e ( K l a r & W e g e n e r ,
1 9 9 7 a ; K l a r & W e g e n e r , 1 9 9 7 b ; K l a r e t a l . , 1 9 9 6 ; I o a n n o u & C h a s s i a k o s , 2 0 0 1 ;
C h a r d a i r e e t a l . , 2 0 0 5 ) f o r a s m a l l s a m p l i n g . I n I o a n n o u a n d C h a s s i a k o s ( I o a n -
n o u & C h a s s i a k o s , 2 0 0 1 ) , t h e a u t h o r s h a v e e s s e n t i a l l y p e r f o r m e d t h e s a m e t y p e
o f a n a l y s i s t h a t w e i n t e n d t o d o f o r t h e s p e c i fi c c a s e o f t r a ffi c fl o w a s p e r t a i n s
s p e c i fi c a l l y t o t r u c k s a t t h e L o n g B e a c h p o r t s ; i n a r e c e n t p a p e r b y C h a r d a i r e
e t a l . ( C h a r d a i r e e t a l . , 2 0 0 5 ) , t h e a u t h o r s i n t r o d u c e a n d a n a l y z e a p r o b l e m
v e r y s i m i l a r t o o u r s . T h i s s e c t i o n w i l l b e a s h o r t c o m p a r i s o n o f o u r w o r k w i t h
t h e i r s a n d a j u s t i fi c a t i o n o f o u r a s s u m p t i o n s : S e c t i o n 1 . 1 . 1 i l l u s t r a t e s h o w w e
a r e a b l e t o s a c r i fi c e a c e r t a i n a m o u n t o f a c c u r a c y i n t h e m o d e l i n e x c h a n g e f o r
a p o t e n t i a l s p e e d - u p i n d a t a c o l l e c t i o n a n d p r o c e s s i n g , a n d S e c t i o n 1 . 1 . 2 i s a
s h o r t d i s c u s s i o n o f c o m p l e x i t y i s s u e s a n d t h e i n t e r a c t i o n e ff e c t b e t w e e n e n t i t i e s
i n t h e m o d e l .
1 . 1 . 1 M o d e l S i m p l i fi c a t i o n
O n e o f t h e p r i m a r y o b j e c t i v e s o f t h i s w o r k i s t o p u t t o g e t h e r a r e a l i s t i c m a t h e -
m a t i c a l m o d e l o f t r a ffi c fl o w i n s u c h a w a y t h a t t h e p a r a m e t e r s o f t h e p r o b l e m
a r e e a s i l y g l e a n e d f r o m t h e s u r r o u n d i n g e n v i r o n m e n t . I n t h e fi r s t s e c t i o n o f
I o a n n o u a n d C h a s s i a k o s ( I o a n n o u & C h a s s i a k o s , 2 0 0 1 ) , t h e a u t h o r s d e t e r m i n e d
s e v e r a l v a r i a b l e s t h a t s u b s t a n t i a l l y c o n t r i b u t e t o t h e i r m o d e l . T h e i r m o d e l f o r
t h e b e h a v i o r o f t h e t r u c k s c o n s i s t s o f t w o p a r t s , a l o n g i t u d i n a l a n d l a t e r a l t r u c k
m o d e l . T h e l o n g i t u d i n a l m o d e l a l o n e c o n t a i n s s e v e n d i ff e r e n t t y p e s o f f o r c e s ,
a n d d e t e r m i n i n g t h e m o t i o n o f a s i n g l e t r u c k r e q u i r e s s o l v i n g a fi r s t o r d e r l i n e a r
d i ff e r e n t i a l e q u a t i o n ( p r o b a b l y n u m e r i c a l l y ) .
I n a n e m e r g e n c y e n v i r o n m e n t , w h e n i t c o m e s t o m o v e m e n t o f s u p p l i e s a n d
p e o p l e , s o l u t i o n s p e e d i s f a r m o r e c r i t i c a l a p a r a m e t e r t h a n fi n d i n g t h e o p t i m a l
s o l u t i o n . I n m o s t c a s e s , a f a i r a p p r o x i m a t i o n t o t h e o p t i m a l s o l u t i o n ( e v e n t o
w i t h i n r e l a t i v e l y l a r g e c o n s t a n t f a c t o r s ) q u i c k l y i s f a r p r e f e r a b l e t o a p e r f e c t
b u t l a t e s o l u t i o n . A d d i t i o n a l l y , i n a n e v o l v i n g e n v i r o n m e n t , t h e p a r a m e t e r s o f
ON THE FORMULATION OF AN EMERGENCY ROUTING PROBLEM 5
t h e p r o b l e m m a y ( a n d m o s t l i k e l y w i l l ) c h a n g e a t a m o m e n t ’ s n o t i c e . T h u s ,
i n o u r m a t h e m a t i c a l m o d e l , w e s a c r i fi c e s e v e r a l v a r i a b l e s t h a t c o n t r i b u t e t o t h e
a c c u r a c y o f t h e m o d e l s o t h a t w e c a n r e a s o n a b l y g u a r a n t e e t h a t t h e d a t a r e l e v a n t
t o t h e p r o b l e m c a n b e c o l l e c t e d a n d p r o c e s s e d e ffi c i e n t l y . I n p a r t i c u l a r , w e d o
a w a y w i t h t h e s t a n d a r d n o t i o n o f v e h i c l e s ( c a r s , t r u c k s , e t c . ) a n d g r o u p t h e s e
i n t o “ c o n v o y s . ” I n a n e m e r g e n c y s i t u a t i o n , i t i s r e a l i s t i c t o a s s u m e t h a t u n l e s s
l i v e s a r e c l e a r l y a n d i m m e d i a t e l y t h r e a t e n e d , p e o p l e w i l l o r g a n i z e t h e m s e l v e s
i n t o g r o u p s t h a t t h e y t r u s t t o t r a v e l t o g e t h e r , t h e r e b y m a x i m i z i n g e v e r y o n e ’ s
s a f e t y . I n f a c t , t h e m i l i t a r y , a n o u t fi t t h a t f o r t h e m o s t p a r t a l w a y s f u n c t i o n s i n
a n e v o l v i n g e m e r g e n c y e n v i r o n m e n t , r e g u l a r l y u s e s c o n v o y s t o m o v e v i t a l a s s e t s
f r o m p l a c e t o p l a c e . C h a r d a i r e e t a l . ( C h a r d a i r e e t a l . , 2 0 0 5 ) u s e t h i s s a m e
s i m p l i fi c a t i o n i n t h e i r p r o b l e m s t a t e m e n t a s w e l l . T o i l l u s t r a t e t h e i m p o r t a n c e o f
t h e p r o b l e m t o t h e m i l i t a r y , C h a r d a i r e e t a l . ( C h a r d a i r e e t a l . , 2 0 0 5 ) n o t e t h a t
a n e n o r m o u s a m o u n t o f t i m e a n d r e s o u r c e s w a s s p e n t p l a n n i n g t h e m o v e m e n t s
o f c o n v o y s d u r i n g t h e i n t e r v e n t i o n i n K o s o v o i n t h e l a t e 1 9 9 0 ’ s ( C u m m i n g s ,
1 9 9 9 ; C h a r d a i r e e t a l . , 2 0 0 1 ) .
1 . 1 . 2 I n t e r a c t i o n s a n d C o m p l e x i t y
I n t h e s e c o n d s e c t i o n o f I o a n n o u a n d C h a s s i a k o s ( I o a n n o u & C h a s s i a k o s , 2 0 0 1 ) ,
t h e a u t h o r s e s s e n t i a l l y u s e a m o d i fi c a t i o n o f D i j k t r a ’ s s i n g l e - s o u r c e s h o r t e s t p a t h
a l g o r i t h m ( D i j k s t r a , 1 9 5 9 ) t o c o m e u p w i t h a n a d a p t i v e a l g o r i t h m f o r v e h i c u l a r
r e - r o u t i n g . I n t h i s s e c t i o n , t h e c o m p l e x m o d e l t h a t t h e y c o m e u p w i t h i n t h e fi r s t
s e c t i o n o f t h e i r p a p e r i s u s e d t o d e t e r m i n e t h e w e i g h t s o n t h e e d g e s o f a d i g r a p h .
D i j k s t r a ’ s a l g o r i t h m i s t h e n b a s i c a l l y u s e d f o r e a c h v e h i c l e o n t h i s d i g r a p h t o
d e t e r m i n e t h e s h o r t e s t d i s t a n c e t o t h e t e r m i n a l p o i n t . I f t h e i r a l g o r i t h m i s r u n
o n e a c h v e h i c l e i n t h e d i g r a p h , a s s u m i n g t h e r e a r e n t o t a l e d g e s a n d m t o t a l
v e h i c l e s , t h e r u n n i n g t i m e o f t h e i r a l g o r i t h m i s O ( n 3 m ) i n t h e w o r s t c a s e . A
q u i c k o v e r v i e w o f t h e i r a n a l y s i s s h o w s t h a t i f t h e e d g e w e i g h t s c h a n g e f a i r l y
o f t e n , a s t h e y w o u l d i n a n e v o l v i n g e n v i r o n m e n t , t h i s w o r s t c a s e r u n n i n g t i m e
i s t h e m o s t l i k e l y r u n n i n g t i m e . T h e r e a r e t w o p o i n t s t o n o t e .
ON THE FORMULATION OF AN EMERGENCY ROUTING PROBLEM 6
• G e n e r a l l y s p e a k i n g , a c u b i c d e p e n d e n c y o n a r e l a t i v e l y l a r g e p a r a m e t e r i s
n o t s u ffi c i e n t f o r a r e a l - t i m e a n a l y s i s .
• I n t e r e s t i n g l y , t h o u g h t h e a u t h o r s h a v e t h o r o u g h l y s t u d i e d t h e m o v e m e n t
o f a n i n d i v i d u a l t r u c k o n a r o a d w a y , i n t e r a c t i o n s b e t w e e n v e h i c l e s a r e
e n t i r e l y i g n o r e d .
W e d e a l w i t h t h e fi r s t i s s u e b y d r a s t i c a l l y r e d u c i n g 1 t h e s i z e o f t h e p a r a m e t e r
m a n d r e p l a c i n g t h e e d g e w e i g h t s w i t h s t a t i c v a l u e s . T h o u g h t h i s s i m p l i fi c a t i o n
r e d u c e s t h e q u a l i t y o f o u r m o d e l , w e b e l i e v e t h a t t h e p h i l o s o p h y o f r e a s o n a b l y
t r a d i n g a c c u r a c y f o r s w i f t n e s s a p p l i e s i n t h i s c a s e . W e w i l l s e e l a t e r o n , h o w e v e r ,
t h a t t h i s “ s i m p l i fi c a t i o n ” d o e s n o t m a k e t h e p r o b l e m t r i v i a l . O n t h e c o n t r a r y ,
t h e p r o b l e m w e s e t u p w i l l p r o v e t o b e m o s t l i k e l y i n t r a c t a b l e a n d w i l l h a v e t o b e
d e a l t w i t h u s i n g a r t i fi c i a l i n t e l l i g e n c e a p p r o x i m a t i o n t e c h n i q u e s . A s o p p o s e d t o
t h e s o l u t i o n i n ( I o a n n o u & C h a s s i a k o s , 2 0 0 1 ) , t h e s e t e c h n i q u e s h a v e t h e b e n e fi t
t h a t , o n c e a f e a s i b l e s o l u t i o n i s d e c i d e d u p o n , t h e a l g o r i t h m c a n b e t e r m i n a t e d
a s s o o n a s a “ g o o d e n o u g h ” s o l u t i o n h a s b e e n f o u n d ; t h e l o n g e r t h e a l g o r i t h m
i s r u n , t h e b e t t e r t h e s o l u t i o n . A g a i n , C h a r d a i r e e t a l . ( C h a r d a i r e e t a l . , 2 0 0 5 )
m a k e a s s u m p t i o n s s i m i l a r t o o u r s , g r o u p i n g v e h i c l e s i n t o c o n v o y s ; h o w e v e r , t h e i r
m o d e l i s s u b s t a n t i a l l y d i ff e r e n t , a n d w e w a i t u n t i l t h e f o r m a l i n t r o d u c t i o n o f t h e
p r o b l e m t o d i ff e r e n t i a t e .
T h e s e c o n d p o i n t i s m o r e d i s t u r b i n g . A n y o n e w h o h a s d r i v e n a v e h i c l e i n
L o s A n g e l e s k n o w s t h a t t h e p r e s e n c e o f o n e o r m o r e a d d i t i o n a l d r i v e r s o n t h e
r o a d w a y i s a n e x t r e m e l y s i g n i fi c a n t v a r i a b l e . S u c h a n i n t e r a c t i o n i s c e r t a i n l y
m u l t i p l i e d w h e n i t c o m e s t o c o n v o y s o f v e h i c l e s t r a v e l i n g t o g e t h e r . O n e s h o u l d
a s s u m e t h a t t w o c o n v o y s t r a v e l i n g o n t h e s a m e r o a d w a y i n t h e s a m e d i r e c t i o n
w i l l i n t e r f e r e w i t h o n e a n o t h e r a n d s l o w e a c h o t h e r d o w n ; c o n v o y s t h a t h a v e t o
c r o s s e a c h o t h e r a t i n t e r s e c t i o n s w i l l a l s o c a u s e s e r i o u s d i s r u p t i o n s . S e e m i n g l y
s i g n i fi c a n t i n t e r a c t i o n s o f t h i s k i n d a r e i n c l u d e d i n o u r m o d e l .
1 R e c a l l f r o m S e c t i o n 1 . 1 . 1 t h a t w e o r g a n i z e o u r v e h i c l e s i n t o c o n v o y s , e a c h c o n v o y b e i n g a
s i n g l e l a r g e e n t i t y .
ON THE FORMULATION OF AN EMERGENCY ROUTING PROBLEM 7
2 F o r m u l a t i n g t h e P r o b l e m
I n t h i s s e c t i o n , w e w i l l f o r m u l a t e t h e C o n v o y R o u t i n g P r o b l e m ( C R P ) r i g o r -
o u s l y 2 . F i r s t , w e d e fi n e w h a t i t m e a n s t o b e a “ c o n v o y ” m a t h e m a t i c a l l y .
D e fi n i t i o n 1 A s s u m e t h a t a w e i g h t e d d i g r a p h 3 G = ( V , E ) i s g i v e n , a l o n g w i t h
a s t r a i g h t - l i n e e m b e d d i n g i n t o t h e 2 - d i m e n s i o n a l p l a n e R 2 i n s u c h a w a y t h a t
a n y t w o d i s t i n c t d i r e c t e d l i n e s e g m e n t s t h a t a r e n o t o f t h e f o r m { ( a , b ) , ( b , a ) }
e i t h e r i n t e r s e c t i n o n e p o i n t o r n o t a t a l l 4 . ( T h e w e i g h t s o n t h e e d g e s n e e d n o t
n e c e s s a r i l y h a v e a n y t h i n g t o d o w i t h t h e p o s i t i o n o f t h e v e r t i c e s i n t h e p l a n e . )
A c o n v o y a t a n y g i v e n p o i n t i n t i m e i s d e fi n e d t o b e a n o r d e r e d s e q u e n c e o f
p o i n t s w i t h i n t h e d i g r a p h ( a , v 1, v 2, . . . , v c , b ) . ( N o t e t h a t w e a l l o w c = 0 . W e
t h i n k o f a a s t h e r e a r o f t h e c o n v o y a n d b a s t h e f r o n t . ) W e m u s t h a v e t h a t
v i 2 V f o r e v e r y v a l i d i . H o w e v e r , t h e p o i n t s a a n d b a r e n o t r e q u i r e d t o b e
v e r t i c e s o f t h e d i g r a p h ; t h e y a r e r e q u i r e d t o l i e a l o n g d i r e c t e d e d g e s i n E . M o r e
r i g o r o u s l y , 9 ( v i , v j ) 2 E s u c h t h a t a 2 { ( 1 − t ) v i + t v j | t 2 [ 0 , 1 ] } a n d s i m i l a r l y
f o r b , w h e r e t h e l i n e a r c o m b i n a t i o n o f t w o p o i n t s r e f e r s t o t h e l i n e a r c o m b i n a t i o n
o f t h e i r r e s p e c t i v e e m b e d d i n g c o o r d i n a t e s i n R 2 .
W e n o w d e fi n e w h a t i t m e a n s f o r t w o c o n v o y s t o “ o v e r l a p . ” T h e r e a r e
t w o p o s s i b i l i t i e s f o r c o n v o y o v e r l a p . T w o d i s t i n c t c o n v o y s c a n e i t h e r ( a ) b e
s i m u l t a n e o u s l y p r o c e e d i n g a l o n g t h e s a m e d i r e c t e d e d g e i n s u c h a w a y t h a t
t h e d i r e c t e d i n t e r v a l s d e s c r i b e d b y t h e c o n v o y s i n D e fi n i t i o n 1 h a v e n o n e m p t y
i n t e r s e c t i o n o r ( b ) b e c r o s s i n g a t a g i v e n v e r t e x .
2 T h e C o n v o y M o v e m e n t P r o b l e m ( C M P ) w a s i n t r o d u c e d i n ( C h a r d a i r e et al. , 2 0 0 5 ) . T h e s e
t w o p r o b l e m s a r e s i g n i fi c a n t l y d i ff e r e n t a s w e n o t e b e l o w .
3 I n m o s t c a s e s , i t w i l l b e p o s s i b l e t o a s s u m e t h a t t h i s d i g r a p h i s p l a n a r . H o w e v e r , t o k e e p
t h e m o d e l a s g e n e r a l a s p o s s i b l e a n d t o a c c o u n t f o r t h e p o s s i b i l i t y o f b r i d g e s a n d t u n n e l s , w e
a l l o w n o n p l a n a r i t y .
4 T h e r e a r e n u m e r o u s a l g o r i t h m s f o r s t r a i g h t - l i n e e m b e d d i n g s o f p l a n a r g r a p h s . W e c i t e
t w o h e r e f o r r e f e r e n c e p u r p o s e s : ( H a r e l & S a r d a s , 1 9 9 5 ; C h r o b a k & P a y n e , 1 9 9 5 ) . T o e m b e d
a g e n e r a l g r a p h w i t h t h e s e r e s t r i c t i o n s i s t r i v i a l : S i m p l y p l a c e a l l t h e v e r t i c e s o f t h e g r a p h
e q u i d i s t a n t o n t h e d i a m e t e r o f a c i r c l e .
ON THE FORMULATION OF AN EMERGENCY ROUTING PROBLEM 8
D e fi n i t i o n 2 T w o c o n v o y s A = ( a 1, a 2, . . . , a n ) a n d B = ( b 1, b 2, . . . , b m ) c r o s s
a t a v e r t e x v i f a n d o n l y i f t h e f o l l o w i n g h o l d :
1 . 9 i , j s u c h t h a t 1 < i < n , 1 < j < m , a n d a i = b j = v .
2 . T h e p a i r o f e q u a t i o n s a i + 1 t + a i − 1 ( 1 − t ) = b j + 1 s + b j − 1 ( 1 − s ) h a s a
s o l u t i o n s u c h t h a t 0 < s , t < 1 . ( N o t e t h a t t h e a ’ s a n d b ’ s a r e p o i n t s i n t h e
t w o - d i m e n s i o n a l p l a n e ; t h e r e f o r e , t h i s o n e e q u a t i o n i s a c t u a l l y s h o r t h a n d
f o r t w o d i s t i n c t e q u a t i o n s . )
T h e fi r s t p a r t o f t h e d e fi n i t i o n e n s u r e s t h a t a n i n t e r s e c t i o n d o e s i n f a c t t a k e
p l a c e , a n d t h e s e c o n d g u a r a n t e e s t h a t t h e p a t h s d o i n f a c t c r o s s .
D e fi n i t i o n 3 L e t t w o c o n v o y s A a n d B b e g i v e n a s i n D e fi n i t i o n 1 , a n d fi x a
p a r t i c u l a r p o i n t i n t i m e t . W e d e fi n e t h e v e r t e x o v e r l a p ( w h i c h d e p e n d s o n t h e
t i m e t ) t o b e t h e n u m b e r o f t i m e s t h a t A a n d B c r o s s a s i n D e fi n i t i o n 2 .
N o t e t h a t D e fi n i t i o n 3 a l l o w s t w o o r m o r e c o n v o y s t o l e a v e f r o m a s i n g l e
v e r t e x o r a r r i v e a t a s i n g l e v e r t e x w i t h o u t a n y a s s o c i a t e d c o s t . A l s o , a n d m o r e
i m p o r t a n t l y , i f t w o c o n v o y s m e e t a t a n i n t e r s e c t i o n b u t d o n o t a c t u a l l y c r o s s
p a t h s , w e a s s u m e t h a t t h e r e i s n o i n t e r a c t i o n t h a t n e e d o c c u r b e t w e e n t h e t w o .
T h i s i s a s i m p l i f y i n g a s s u m p t i o n t h a t t a k e s a w a y f r o m t h e a c c u r a c y o f t h e m o d e l
b u t n o t c r u c i a l l y .
D e fi n i t i o n 4 L e t t w o c o n v o y s b e g i v e n a s i n D e fi n i t i o n 1 , a n d fi x a p a r t i c u l a r
p o i n t i n t i m e t . W e d e fi n e t h e e d g e o v e r l a p ( w h i c h d e p e n d s o n t h e t i m e t )
b e t w e e n t h e t w o c o n v o y s t o b e t h e s u m o f t h e w e i g h t s o f t h e i n t e r s e c t i n g e d g e s
a n d e d g e p i e c e s o f t h e t w o c o n v o y s .
M o r e s p e c i fi c a l l y , c o n s i d e r t h e i n t e r s e c t i o n o f t w o c o n v o y s w i t h i n t h e w e i g h t e d
p l a n a r d i g r a p h G . N o t e t h a t b y D e fi n i t i o n 1 , w e c a n s e p a r a t e t h e i n t e r s e c t i o n
i n t o d i s j o i n t p i e c e s ( x , y ) s u c h t h a t 9 ( v i , v j ) 2 E s u c h t h a t x = ( 1 − t x ) v i + t x v j
a n d y = ( 1 − t y ) v i + t y v j f o r s o m e t x  t y 2 [ 0 , 1 ] . L e t t h e w e i g h t o f e d g e ( v i , v j )
b e w ( v i , v j ) . T h e n t h e c o n t r i b u t i o n o f ( x , y ) t o t h e s u m i s ( t y − t x ) w ( v i , v j ) .
ON THE FORMULATION OF AN EMERGENCY ROUTING PROBLEM 9
N o t e t h a t D e fi n i t i o n 4 s i m p l y c o d i fi e s t h a t t h e o v e r l a p b e t w e e n t w o c o n v o y s
t r a v e l i n g p a r a l l e l t o e a c h o t h e r i s e q u a l t o t h e s u m o f t h e o v e r l a p d i s t a n c e
w h e r e d i s t a n c e i s d e fi n e d n o t i n t e r m s o f t h e d i s t a n c e b e t w e e n t h e p o i n t s i n t h e
e m b e d d i n g o f t h e d i g r a p h G i n t h e p l a n e b u t r a t h e r i n t e r m s o f t h e w e i g h t s o n
t h e e d g e s . N o t e t h a t t h e t ’ s i n t h e d e fi n i t i o n c o r r e s p o n d t o t h e p e r c e n t a g e o f
t h e e d g e i n q u e s t i o n t h a t t h e c o n v o y s h a v e b o t h t r a v e l e d o v e r . W e t h e n t a k e a
w e i g h t e d s u m o f t h e s e t r a v e r s a l s t o g e t t h e fi n a l r e s u l t .
W e a r e n o w i n a p o s i t i o n t o d e fi n e t h e m a i n p r o b l e m o f t h e p a p e r .
D e fi n i t i o n 5 T h e C o n v o y R o u t i n g P r o b l e m ( C R P ) . A p r o b l e m i n s t a n c e i s g i v e n
a s f o l l o w s :
1 . L e t C 1, C 2  0 b e k n o w n c o n s t a n t s .
2 . L e t n  1 b e t h e n u m b e r o f c o n v o y s t o b e r o u t e d .
3 . L e t G = ( V , E ) b e a w e i g h t e d p l a n a r d i g r a p h , a n d l e t ( v s
1, v s
2, . . . , v s n
)
( t h e “ s t a r t ” v e r t i c e s ) a n d ( v f
1 , v f
2 , . . . , v f n
) ( t h e “ fi n i s h ” v e r t i c e s ) b e t w o
s e q u e n c e s o f d i s t i n g u i s h e d v e r t i c e s s u c h t h a t f o r a l l v a l i d i , d ( v s
i , v f
i ) < 1 .
4 . L e t ( x 1, x 2, x 3, . . . , x n ) b e a s e q u e n c e o f p o s i t i v e r a t i o n a l n u m b e r s , r e p r e -
s e n t i n g c o n v o y l e n g t h s t r a v e l i n g a t s p e e d 1 .
A s o l u t i o n t o t h i s p r o b l e m c o m e s a s a s e q u e n c e o f “ r o u t i n g i n s t r u c t i o n s ” f o r
e a c h 1  i  n . A “ c o n v o y ” i s r e p r e s e n t e d b y a d i r e c t e d i n t e r v a l w i t h i n t h e
d i g r a p h a s d e s c r i b e d i n D e fi n i t i o n 1 . M o r e s p e c i fi c a l l y , a s o l u t i o n t o t h e p r o b l e m
c o n s i s t s o f , f o r e a c h v a l i d i ,
1 . A s e q u e n c e o f n n o n n e g a t i v e r a t i o n a l n u m b e r s ( t 1, t 2, t 2, . . . , t n ) , “ s t a r t
t i m e s , ” s u c h t h a t m i n 1  i  n t i = 0 .
2 . F o r e a c h 1  i  n , a d i r e c t e d p a t h w i t h i n G r e p r e s e n t e d a s a s e q u e n c e o f
v e r t i c e s
( v i ,1, v i ,2, v i ,3, . . . , v i , m i )
s u c h t h a t 8 1  i  n , v i ,1 = v s
i a n d v i , m i = v f
i .
ON THE FORMULATION OF AN EMERGENCY ROUTING PROBLEM 1 0
3 . F o r e a c h 1  i  n , a s e q u e n c e o f p o s i t i v e r a t i o n a l n u m b e r s
( s i ,1, s i ,2, s i ,3, . . . , s i , m i − 1 )
t h a t r e p r e s e n t c o n v o y s p e e d s . W e m u s t h a v e , f o r e v e r y v a l i d i a n d j ,
s i , j  1 . ( I n o t h e r w o r d s , 1 i s t h e u n i v e r s a l s p e e d l i m i t t h a t w e a l l o w i n
o u r d i g r a p h . )
F o r e a c h 1  i  n , a t t i m e t i , c o n v o y i i s r e l e a s e d f r o m v s
i = v i ,1 . W h e n
t h e f r o n t o r r e a r o f c o n v o y i r e a c h e s v i , j , i t c h a n g e s i t s s p e e d t o s i , j . T h e s p e e d
o f t h e e n d p o i n t s ( f r o n t o r r e a r ) o f t h e c o n v o y i s u s e d a s f o l l o w s : A s s u m e t h a t
a n e n d p o i n t o f c o n v o y i i s a t ( 1 − T ) v i + T v j f o r s o m e ( v i , v j ) 2 E a n d s o m e
T 2 [ 0 , 1 ] w i t h s p e e d s , a n d l e t t h e w e i g h t o f e d g e ( v i , v j ) b e w ( v i , v j ) . A t t i m e
T  > T , t h e r e a r e t w o c a s e s t o c o n s i d e r :
1 . I f ( T + s
w ( v i , v j )
( T  − T ) )  1 , t h e n t h e e n d p o i n t o f t h e c o n v o y w i l l h a v e
m o v e d s ( T  − T ) u n i t s t o w a r d s v j . T h e n e w p o s i t i o n o f t h e e n d p o i n t i s
( 1 − T +
s
w ( v i , v j )
( T − T  ) ) v i + ( T +
s
w ( v i , v j )
( T  − T ) ) v j
2 . O t h e r w i s e , t h e e n d p o i n t h a s r e a c h e d v e r t e x v j w i t h i n t h e t i m e i n t e r v a l
[ T , T  ] a n d c h a n g e s s p e e d s a c c o r d i n g l y .
N o t e t h a t t h e n u m b e r o f e d g e s t h a t t h e c o n v o y o c c u p i e s m a y i n c r e a s e o r d e c r e a s e
a s t i m e p r o g r e s s e s .
C o n s i d e r t w o d i s t i n c t c o n v o y s A a n d B . L e t f A , B ( t ) b e t h e a m o u n t o f e d g e
o v e r l a p i n t h e c o n v o y s A a n d B w i t h i n t h e d i g r a p h a t t i m e t a s d e fi n e d i n
D e fi n i t i o n 4 . A t t i m e t , l e t g A , B ( t ) e q u a l t h e v e r t e x o v e r l a p b e t w e e n A a n d B a s
d e fi n e d i n D e fi n i t i o n 3 . L e t T b e t h e t i m e a t w h i c h t h e g r a p h G i s fi r s t e m p t y
o f c o n v o y s . T h e g o a l i s m i n i m i z e t h e c o s t q u a n t i t y
T + X a l l c o n v o y p a i r s A 6 = B
Z T
0
[ C 1 f A , B ( t ) + C 2 g A , B ( t ) ] d t
N o t e t h a t w e h a v e d e fi n e d t h e p r o b l e m a s a n o p t i m i z a t i o n p r o b l e m . W e c a n
e a s i l y r e f o r m u l a t e t h e p r o b l e m i n t o n u m e r o u s o t h e r d o m a i n s . F o r t h e e q u i v a l e n t
ON THE FORMULATION OF AN EMERGENCY ROUTING PROBLEM 1 1
d e c i s i o n p r o b l e m , w e c a n s i m p l y i n t r o d u c e a p a r a m e t e r k a n d a s k w h e t h e r t h e
fi n a l c o s t q u a n t i t y c a n b e m a d e l e s s t h a n o r e q u a l t o k . I f w e w i s h t o m a k e
t h e p r o b l e m o n l i n e , w e c a n s p e c i f y t h a t c e r t a i n p a r a m e t e r s a r e m a d e k n o w n t o
t h e u s e r a t p a r t i c u l a r t i m e s d u r i n g t h e e x e c u t i o n . F o r e x a m p l e , t h e n u m b e r n
m i g h t i n c r e a s e a s t i m e g o e s o n , i . e . c o n v o y s m a y w i s h t o f o r m a n d l e a v e w i t h
n o p r i o r w a r n i n g . T h e e d g e w e i g h t s o f t h e d i g r a p h G m a y c h a n g e d u r i n g t h e
e x e c u t i o n o f t h e a l g o r i t h m , a n d s o o n .
E a c h f o r m u l a t i o n w i l l s e r v e i t s o w n f u n c t i o n . T h e o p t i m i z a t i o n p r o b l e m i s
t h e s t a n d a r d p r e s e n t a t i o n t h a t m o s t p e o p l e a r e f a m i l i a r w i t h . T h e d e c i s i o n
p r o b l e m w i l l s e r v e t o p r o v e r i g o r o u s l y i n S e c t i o n 2 . 3 t h a t t h e p r o b l e m p r e s e n t e d
i s n o t o n l y c h a l l e n g i n g , b u t m o s t l i k e l y i n t r a c t a b l e . T h e o n l i n e v a r i a t i o n o f t h e
p r o b l e m i s t h e m o s t r e a l i s t i c f o r m u l a t i o n , w h e r e t h e u s e r i s i n f o r m e d o f t h e
c h a n g i n g p a r a m e t e r s o f t h e p r o b l e m a s t i m e p r o g r e s s e s .
2 . 1 M o d e l C o m p a r i s o n w i t h C h a r d a i r e , M c K e o w n , V e r i t y -
H a r r i s o n , a n d R i c h a r d s o n
I n t h i s s e c t i o n , w e w i l l c o m p a r e o u r f o r m u l a t i o n o f t h e C R P w i t h t h e o t h e r m a i n
c o n v o y m o d e l , t h e C M P f o r m u l a t e d r i g o r o u s l y i n C h a r d a i r e e t a l . ( C h a r d a i r e
e t a l . , 2 0 0 5 ) . ( I n t h i s p a p e r , C h a r d a i r e e t a l . d e s c r i b e t h e i r m o d e l a s a “ s l i g h t l y
m o d i fi e d v e r s i o n o f t h e s p e c i fi c a t i o n s g i v e n i n L e e e t a l . ( L e e e t a l . , 1 9 9 6 ) . ” ) I n
( C h a r d a i r e e t a l . , 2 0 0 5 ) , t h e p r o b l e m i s p h r a s e d a s a c o n s t r a i n e d o p t i m i z a t i o n
p r o b l e m . W e f o u n d s e v e r a l e s s e n t i a l d i ff e r e n c e s b e t w e e n o u r m o d e l a n d t h e i r s ;
w e l i s t m o s t o f t h e s e d i ff e r e n c e s b e l o w . W h i c h m o d e l b e s t e n c a p s u l a t e s t h e
s i t u a t i o n s e n c o u n t e r e d i n p r a c t i c e / o n t h e b a t t l e fi e l d i s a q u e s t i o n t h a t i s b e s t
a n s w e r e d b y t h o s e w i t h p r a c t i c a l / b a t t l e fi e l d e x p e r i e n c e . ( C h a r d a i r e e t a l . u s e
t h e n o t a t i o n u t o r e p r e s e n t a c o n v o y i t e r a t o r ; w h e r e p o s s i b l e , w e t r y t o m i m i c
t h e i r n o t a t i o n a s l o n g a s i t d o e s n o t c o n fl i c t w i t h o u r o w n n o t a t i o n i n t r o d u c e d
a b o v e . )
• C h a r d a i r e e t a l . i n t r o d u c e t h e p a r a m e t e r s b u w h i c h a r e m e a n t t o r e p r e s e n t
t h e e a r l i e s t t i m e a t w h i c h c o n v o y u c a n b e g i n i t s m o v e m e n t . I n o u r m o d e l ,
ON THE FORMULATION OF AN EMERGENCY ROUTING PROBLEM 1 2
b u = 0 f o r e v e r y u .
• C h a r d a i r e e t a l . i n t r o d u c e t h e p a r a m e t e r s f u w h i c h a r e m e a n t t o r e p r e s e n t
t h e l a t e s t t i m e a t w h i c h c o n v o y u i s a l l o w e d t o m o v e i n G . I n o u r m o d e l ,
f u = 1 f o r e v e r y u .
• C h a r d a i r e e t a l . i n t r o d u c e t h e p a r a m e t e r s g u w h i c h a r e m e a n t t o r e p r e s e n t
t h e “ w a i t i n g i n t e r v a l ” o f c o n v o y u . I n o t h e r w o r d s , i f c o n v o y u d o e s n o t
b e g i n t r a v e l i n g a t t i m e e x a c t l y b u , t h e n i t m u s t w a i t f o r a c o n s t a n t m u l t i p l e
o f g u t i m e u n i t s b e f o r e i t i s a l l o w e d t o b e g i n m o v i n g . I n o u r m o d e l , g u = 0
f o r e v e r y u .
• C h a r d a i r e e t a l . u s e i n t e g e r u n i t s f o r t i m e s , t i m e i n t e r v a l s , a n d c o s t m e a -
s u r e m e n t s . T h i s m a k e s f o r a fi n a l m o d e l i n w h i c h t h e m e t h o d s o f i n t e g e r
p r o g r a m m i n g m i g h t b e a p p l i e d . O u r m o d e l i s a l l o w e d t o u s e w e i g h t s w i t h
v a l u e s i n Q + .
• T h o u g h C h a r d a i r e e t a l . a s s u m e t h a t t h e t i m e i t t a k e s f o r t h e h e a d o f
c o n v o y u t o p a s s t h r o u g h a n e d g e o f G m a y v a r y d e p e n d i n g o n t h e c o s t
o f t h e e d g e , t h e t a i l o f e a c h c o n v o y w i l l a l w a y s t a k e c o n s t a n t t i m e w u
( i n d e p e n d e n t o f t h e e d g e c o s t ) i n o r d e r t o r e a c h a v e r t e x a f t e r t h e h e a d
d o e s . O u r m o d e l m a k e s t h e a s s u m p t i o n t h a t t h e h e a d s a n d t a i l s o f c o n v o y s
t r a v e l a t t h e s a m e r a t e : b o t h h e a d a n d t a i l o f t h e c o n v o y h a v e t r a v e l t i m e
b e t w e e n v e r t i c e s d e p e n d e n t o n b o t h t h e s p e e d o f t r a v e l a n d e d g e w e i g h t s .
H o w e v e r , c o n v o y s m a y h a v e d i ff e r e n t l e n g t h s x i .
• C h a r d a i r e e t a l . a s s u m e t h a t t h e w e i g h t s o f t h e e d g e s m i g h t b e d i ff e r e n t
f o r e a c h c o n v o y . E a c h c o n v o y u h a s i t s o w n s e p a r a t e c o s t f u n c t i o n f o r
t h e w e i g h t s , n a m e l y C u : E ! Z + . O u r e d g e w e i g h t s a r e a s s u m e d t o b e
c o n s t a n t f o r e v e r y c o n v o y .
• C h a r d a i r e e t a l . a s s u m e t h a t c o n v o y s a r e a b l e t o “ b l o c k ” o t h e r c o n v o y s
f r o m e n t e r i n g a v e r t e x . I n f a c t , o n c e t h e h e a d o f c o n v o y u e n t e r s a v e r t e x
i n t h e g r a p h G , n o o t h e r c o n v o y m a y t o u c h t h e v e r t e x f o r a n o t h e r w u
ON THE FORMULATION OF AN EMERGENCY ROUTING PROBLEM 1 3
t i m e u n i t s . ( R e c a l l t h a t w u i s t h e t i m e t h a t i t t a k e s f o r t h e r e a r o f t h e
c o n v o y t o r e a c h t h e v e r t e x . ) O u r m o d e l a s s u m e s t h a t t w o c o n v o y s m a y
u t i l i z e t h e s a m e v e r t e x , b u t t h a t t w o c o n v o y s m a y c r o s s p a t h s o n l y a t
s o m e p r e d e t e r m i n e d c o s t .
• C h a r d a i r e e t a l . a s s u m e t h a t c o n v o y s m a y n o t p a s s e a c h o t h e r m o v i n g i n
o p p o s i t e d i r e c t i o n s a l o n g e d g e s . W e a s s u m e t h a t a l l e d g e s a r e d i r e c t e d ;
t h e r e f o r e c o n v o y s d o n o t i n t e r a c t w i t h e a c h o t h e r i f t h e y m o v e i n o p p o s i t e
d i r e c t i o n s b e t w e e n t w o v e r t i c e s b e c a u s e t h e y w i l l n o t b e t r a v e l i n g a l o n g
t h e s a m e e d g e .
T h e r e a r e o t h e r d i ff e r e n c e s b e t w e e n t h e t w o m o d e l s , a n d t h i s i s b y n o m e a n s a n
e x h a u s t i v e l i s t . T h o u g h o u r m o d e l r e q u i r e s f a r f e w e r s p e c i fi c a t i o n s , i t w i l l t u r n
o u t t h a t 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 t h e d e c i s i o n p r o b l e m d e r i v e d f r o m
t w o m o d e l s a r e , p e r h a p s s u r p r i s i n g l y , t h e s a m e .
N o t e t h a t i t i s e a s i l y p o s s i b l e t o m a k e o u r p r o b l e m m o r e c o m p l e x o r s i m p l e b y
a d j u s t i n g t h e p r o b l e m s t a t e m e n t . W e h a v e c h o s e n a f o r m u l a t i o n t h a t a t t e m p t s
t o b a l a n c e r e a l i s m w i t h s i m p l i c i t y . O u r m o d e l h a s f a r f e w e r p a r a m e t e r s t h a n
d o e s C h a r d a i r e e t a l . , o u r c o s t f u n c t i o n i s m u c h s i m p l e r t o s t a t e a n d e v a l u a t e ,
a n d w e d o n o t r e q u i r e a c o n s t r a i n e d o p t i m i z a t i o n ; h o w e v e r , i t i s p o s s i b l e t o
m a k e t h e a r g u m e n t t h a t C h a r d a i r e e t a l . ’ s m o d e l i s m o r e g e n e r a l t h a n o u r s i n
c e r t a i n w a y s .
O n e fi n a l n o t e a b o u t t h e p r o b l e m s t a t e m e n t : W e h a v e c h o s e n t o u s e a u n i -
f o r m m a x i m u m s p e e d l i m i t o n t h e r o a d w a y s , n a m e l y 1 . A s e v e r y o n e k n o w s , t h i s
i s n o t a r e a l i s t i c a s s u m p t i o n , a n d , i n a d d i t i o n , t h e m a x i m u m s p e e d o n t h e v a r i -
o u s r o a d w a y s m a y c h a n g e d u e t o c h a n g i n g w e a t h e r c o n d i t i o n s o r o t h e r p r o b l e m s
t h a t a r i s e . W e c l a i m t h a t t h i s u n i f o r m c h o i c e c a n b e m a d e w i t h o u t a n y l o s s o f
g e n e r a l i t y i n t h e m o d e l b y a l l o w i n g v a r i a t i o n s i n t h e r o a d w a y w e i g h t s . A s s u m e
t h a t t h e m a x i m u m s p e e d l i m i t o n a g i v e n s t r e t c h o f r o a d w a y w i t h e d g e w e i g h t
w i s M 6 = 1 . ( O b v i o u s l y , i t i s a l s o t r u e t h a t M 6 = 0 o r t h e e d g e c o u l d n o t e x i s t a t
a l l . ) W e c a n s i m p l y a d j u s t t h e w e i g h t o n t h e e d g e o f t h a t r o a d w a y b y a f a c t o r
o f 1
M t o 1
M w . N o t e t h a t t h e t i m e n e c e s s a r y t o t r a v e r s e t h e r o a d w a y o f l e n g t h
ON THE FORMULATION OF AN EMERGENCY ROUTING PROBLEM 1 4
w a t s p e e d M i s w
M , a n d t h e t i m e n e c e s s a r y t o t r a v e r s e t h e r o a d w a y o f l e n g t h
1
M w a t s p e e d 1 i s
1
M w
1 = w
M .
2 . 2 L i m i t i n g B e h a v i o r
I n t h i s s e c t i o n , w e w i l l e x a m i n e t h e b e h a v i o r o f t h e o p t i m i z a t i o n p r o b l e m g i v e n
i n D e fi n i t i o n 5 a s t h e p a r a m e t e r s C 1 a n d C 2 a p p r o a c h t h e i r l i m i t s .
F i r s t , n o t e t h e l i m i t i n g b e h a v i o r o f t h e p r o b l e m a s C 1, C 2 ! 0 a n d a s
C 1, C 2 ! 1 .
• A s C 1, C 2 ! 0 , t h e e m p h a s i s o n t h e “ o v e r l a p ” a p p r o a c h e s 0 . T h u s , w e
c a r e l e s s a n d l e s s a b o u t c o n v o y o v e r l a p a n d m o r e o n t h e q u i c k e s t r o u t e
f r o m s t a r t t o fi n i s h . I n t h e c a s e w h e r e C 1 = C 2 = 0 , t h e o p t i m a l s o l u t i o n i s
t r i v i a l : U s i n g a s h o r t e s t p a t h a l g o r i t h m ( D i j k s t r a ’ s s i n g l e - s o u r c e s h o r t e s t
p a t h a l g o r i t h m ( D i j k s t r a , 1 9 5 9 ) , f o r e x a m p l e ) , fi n d t h e s h o r t e s t p a t h f r o m
v s
i t o v f
i f o r e a c h v a l i d i . L e t e v e r y c o n v o y m o v e a l o n g t h i s p a t h a t t h e
m a x i m u m s p e e d a n d t h i s o p t i m a l l y s o l v e s t h e p r o b l e m . T h i s s e e m s t o b e
t h e c a s e o f “ m a x i m u m e m e r g e n c y ” : i f p e o p l e d o n o t l e a v e t h e s c e n e o f t h e
e m e r g e n c y a s q u i c k l y a s p o s s i b l e , l i v e s w i l l b e l o s t s i m p l y v i a t h e d e l a y
( e . g . t h e C h e r n o b y l d i s a s t e r , T h r e e M i l e I s l a n d , e t c . )
• A s C 1, C 2 ! 1 , w e c a r e l e s s a n d l e s s a b o u t t h e t i m e n e e d e d t o g e t t o t h e
d e s t i n a t i o n a n d m o r e a b o u t p o t e n t i a l i n t e r - c o n v o y a c c i d e n t s . I n t h i s c a s e ,
t h e r e i s n o r e a l e m e r g e n c y t o l e a v e , b u t i t i s s t i l l t h e g o a l t o g e t e v e r y o n e
a w a y f r o m t h e a r e a e v e n t u a l l y ( e . g . v o l u n t a r y e v a c u a t i o n s f r o m h e a v y
s t o r m a r e a s , e t c . ) . I n t h e l i m i t , t h i s r e d u c e s t o t h e p r o b l e m o f fi n d i n g
d i s j o i n t p a t h s i n t h e d i r e c t e d g r a p h G ( a n d t h i s w i l l fi g u r e h e a v i l y i n t o
o u r p r o o f i n S e c t i o n 2 . 3 ) .
• I f C 1 ! 1 a n d C 2 r e m a i n s fi n i t e , t h e n t h e p r o b l e m r e d u c e s t o w h e t h e r
t h e r e e x i s t s a n o p t i m a l s c h e d u l e i n w h i c h n o c o n v o y e v e r s h a r e s r o a d w a y
w i t h a n y o t h e r c o n v o y . I f C 2 ! 1 w h i l e C 1 r e m a i n s fi n i t e , t h e n t h e
p r o b l e m s r e d u c e s t o w h e t h e r t h e r e e x i s t s a n o p t i m a l s c h e d u l e i n w h i c h n o
ON THE FORMULATION OF AN EMERGENCY ROUTING PROBLEM 1 5
c o n v o y n e e d e v e r c r o s s p a t h s w i t h a n y o t h e r . C l e a r l y , i n b o t h o f t h e s e
c a s e s , t h e r e e x i s t s a s c h e d u l e i n w h i c h n o c o n v o y e v e r n e e d i n t e r a c t w i t h
a n y o t h e r c o n v o y : S i m p l y r o u t e o n e c o n v o y a f t e r a n o t h e r t o i t s d e s t i n a t i o n
a n d o n l y s t a r t t h e n e x t c o n v o y o n c e t h e fi r s t c o n v o y h a s c o m p l e t e l y r e a c h e d
i t s d e s t i n a t i o n . ( B e l o w , i n S e c t i o n 4 . 3 , w e w i l l r e f e r t o t h i s a s A l g o r i t h m
O b v i o u s . ) H o w e v e r , d e t e r m i n i n g a n o p t i m a l s o l u t i o n t h a t m i n i m i z e s t h e
t i m e n e c e s s a r y i s a h i g h l y n o n t r i v i a l p r o b l e m . O b v i o u s l y , i t m a y n o t b e
n e c e s s a r y t o w a i t u n t i l t h e fi r s t c o n v o y h a s r e a c h e d i t s d e s t i n a t i o n b e f o r e
s t a r t i n g t h e s e c o n d ; t h e r e m a y b e w a y s o f r o u t i n g c o n v o y s s o t h a t n o
i n t e r a c t i o n i s n e c e s s a r y . T h i s h o w e v e r i s a n e x t r e m e l y d i ffi c u l t p r o b l e m ,
a n d b e c a u s e t h e o n l y m e t h o d s k n o w n f o r s o l v i n g i t a s o f t h i s w r i t i n g a r e
t h e s a m e a s t h o s e f o r t h e m o r e g e n e r a l p r o b l e m , w e o n l y f o c u s o n t h e m o r e
g e n e r a l p r o b l e m .
O r d i n a r i l y , C 1 a n d C 2 w i l l b e r e a s o n a b l y l a r g e p o s i t i v e v a l u e s , r e fl e c t i n g b o t h
t h e u r g e n c y o f t h e e v a c u a t i o n a n d t h e n e c e s s i t y o f s e p a r a t i n g t h e c o n v o y s s o
a s t o a v o i d c o l l i s i o n s a n d a c c i d e n t s . F o r e x a m p l e , d u r i n g t h e K a t r i n a d i s a s t e r ,
w h e r e C 1 a n d C 2 w o u l d s e e m t o t a k e s u c h a r e a s o n a b l e “ m i d d l e ” v a l u e , i f t h e
g o v e r n m e n t h a d s e t u p o r g a n i z e d c o n v o y r e s c u e t e a m s t o g e t t h e p e o p l e o u t a n d
a w a y f r o m t h e a ff e c t e d a r e a , i t i s p o s s i b l e t h a t t h e u n f o r t u n a t e i n c i d e n t s t h a t
o c c u r r e d m i g h t h a v e b e e n a v o i d e d .
2 . 3 T h e C o m p l e x i t y o f C R P
I n t h i s s e c t i o n , w e w i l l e x h i b i t s t r o n g e v i d e n c e t h a t t h e r e d o e s n o t e x i s t a n e f -
fi c i e n t s o l u t i o n t o t h e d e c i s i o n p r o b l e m v e r s i o n o f o p t i m i z a t i o n p r o b l e m C R P
p r e s e n t e d i n D e fi n i t i o n 5 . T h i s w i l l b e e q u a l l y s t r o n g e v i d e n c e t h a t a l l o t h e r
v e r s i o n s o f t h e p r o b l e m w e m e n t i o n e d a r e i n t r a c t a b l e a s w e l l . R e c a l l t h a t t h e
a s s o c i a t e d d e c i s i o n p r o b l e m i s t h e s i m p l e m o d i fi c a t i o n o f t h e o p t i m i z a t i o n v e r -
s i o n t h a t c h o o s e s i n a d v a n c e a p a r a m e t e r k i n a d d i t i o n t o t h e o t h e r p a r a m e t e r s
s p e c i fi e d i n D e fi n i t i o n 5 a n d a s k s t h e q u e s t i o n : “ D o e s t h e r e e x i s t a s c h e d u l e
w i t h c o s t l e s s t h a n o r e q u a l t o k ? ”
ON THE FORMULATION OF AN EMERGENCY ROUTING PROBLEM 1 6
T h e o r e m 1 T h e d e c i s i o n v e r s i o n o f C R P ( h e n c e f o r w a r d , D C R P ) i s N P - c o m p l e t e .
T h i s s e t o f N P - c o m p l e t e p r o b l e m s i s i n t e r e s t i n g b e c a u s e i t h a s b e e n s h o w n
t h a t i f a s i n g l e o n e o f t h e s e p r o b l e m s i s s o l v a b l e i n p o l y n o m i a l t i m e , t h e n a l l a r e ;
h o w e v e r , i f i t c a n b e s h o w n t h a t a s i n g l e o n e o f t h e s e p r o b l e m s i s i n t r a c t a b l e ,
t h e n a l l o t h e r s m u s t b e i n t r a c t a b l e a s w e l l ( C o r m e n e t a l . , 1 9 9 0 ) . I t i s c u r r e n t l y
t h o u g h t b y m o s t t h e o r e t i c a l c o m p u t e r s c i e n c e r e s e a r c h e r s t h a t N P - c o m p l e t e
p r o b l e m s a r e i n t r a c t a b l e t h o u g h , t o d a t e , t h e r e h a s b e e n n o p r o o f o f t h i s f a c t . I n
t h e o v e r f o r t y y e a r s t h a t r e s e a r c h e r s h a v e b e e n s e a r c h i n g , n o t a s i n g l e p o l y n o m i a l
t i m e s o l u t i o n h a s b e e n f o u n d f o r a s i n g l e o n e o f t h e s e p r o b l e m s n o r h a s a s i n g l e
i n t r a c t a b i l i t y p r o o f b e e n p r e s e n t e d .
I n o r d e r t o p r o v e T h e o r e m 1 , w e w i l l r e q u i r e t w o s e p a r a t e l e m m a s , L e m m a
1 a n d L e m m a 2 . T h e r e s u l t w i l l b e i m m e d i a t e f r o m t h e s e t w o v i a t h e p r i n c i p l e
o f l a n g u a g e r e d u c t i o n ( G a r e y & J o h n s o n , 1 9 7 9 ) .
L e m m a 1 D C R P 2 N P
P r o o f : A s s u m e t h a t a v a l u e o f k , a v a l i d D C R P p r o b l e m i n s t a n c e , a n d a
s c h e d u l e a r e g i v e n . T h e g o a l i s t o v e r i f y t h a t t h e g i v e n s c h e d u l e d o e s i n f a c t
e v a l u a t e t o a c o s t l e s s t h a n o r e q u a l t o t h e g i v e n v a l u e k i n t i m e p o l y n o m i a l i n
t h e p r o b l e m s i z e . T h e n o n t r i v i a l p a r t o f t h i s p r o o f a r i s e s w h e n w e c o n s i d e r t h a t
t h e c o s t f u n c t i o n i n v o l v e s a n i n t e g r a l . R e c a l l t h a t t h e c o s t o f a s c h e d u l e i s
T + X a l l c o n v o y s A 6 = B
Z T
0
[ C 1 f A , B ( t ) + C 2 g A , B ( t ) ] d t
f r o m D e fi n i t i o n 5 .
T h e v a l u e T c a n c l e a r l y b e d e t e r m i n e d f r o m t h e s c h e d u l e i n p o l y n o m i a l t i m e .
I f w e c a n s h o w t h a t f o r a s i n g l e p a i r o f d i s t i n c t c o n v o y s A a n d B , t h e v a l u e o f
R T
0 [ C 1 f A , B ( t ) + C 2 g A , B ( t ) ] d t c a n b e c o m p u t e d i n p o l y n o m i a l t i m e f r o m t h e g i v e n
s c h e d u l e , t h e n t h e r e s u l t w i l l f o l l o w .
C o n s i d e r a n y t w o d i s t i n c t c o n v o y s A a n d B . N o t e t h a t t h e f u n c t i o n s f A , B ( t )
a n d g A , B ( t ) a r e p i e c e w i s e l i n e a r , a n d o n c e a n i n t e r s e c t i o n i s d e t e c t e d , d e t e r -
m i n i n g t h e s l o p e o f t h e l i n e a r c u r v e i s e a s y . W e t h e r e f o r e o n l y r e a l l y n e e d t o
ON THE FORMULATION OF AN EMERGENCY ROUTING PROBLEM 1 7
d e t e r m i n e , f o r t h e s e t w o c o n v o y s , a t w h a t t i m e s t h e y i n t e r s e c t a n d i n w h a t
w a y ( i . e . v e r t e x o r e d g e i n t e r s e c t i o n ) . I t m a y n o t b e i m m e d i a t e l y o b v i o u s t h a t
t h i s i s a p o l y n o m i a l t i m e p r o c e s s b e c a u s e t i m e p r o c e e d s i n a c o n t i n u o u s w a y .
T h e p r o b l e m t h e r e f o r e r e d u c e s t o t h e p r o b l e m o f d e t e r m i n i n g a l l i n t e r s e c t i o n s
b e t w e e n c o n v o y s d u r i n g a l l t i m e u p u n t i l T .
B e c a u s e t h e g r a p h i s p l a n a r a n d t h e r e a r e n u m e r o u s l i n e s e g m e n t i n t e r s e c -
t i o n a l g o r i t h m s f r o m c o m p u t a t i o n a l g e o m e t r y t h a t f u n c t i o n i n p o l y n o m i a l t i m e
( e . g . C h a z e l l e a n d E d e l s b r u n n e r ’ s o p t i m a l a l g o r i t h m ( C h a z e l l e & E d e l s b r u n n e r ,
1 9 9 2 ) ) , w e c a n d e t e r m i n e e x a c t l y w h e r e a n d h o w t h e c o n v o y s i n t e r s e c t a t a n y
s p e c i fi c p o i n t i n t i m e . T h e q u e s t i o n i s t o d e t e r m i n e w h i c h p o i n t s i n t i m e s h o u l d
t h e s e i n t e r s e c t i o n a l g o r i t h m s b e r u n .
H a p p i l y , w e c a n r e s t r i c t o u r s e l v e s t o t h e f o l l o w i n g e v e n t s : E i t h e r t h e f r o n t
o f o n e o f t h e c o n v o y s r e a c h e s a n e w v e r t e x o r t h e r e a r o f o n e o f t h e c o n v o y s
r e a c h e s a n e w v e r t e x . B e t w e e n a n y o n e o f t h e s e e v e n t s , i n t e r s e c t i o n s m a y o c c u r .
I t i s v e r y e a s y t o d e t e r m i n e w h e t h e r t h e t r a j e c t o r i e s o f t w o p o i n t s t r a v e l i n g
a t c o n s t a n t s p e e d i n t e r s e c t ; n o t e t h a t b e t w e e n t h e s e e v e n t s a l l r e l e v a n t p o i n t s ,
n a m e l y t h e f r o n t a n d r e a r o f b o t h c o n v o y s , a r e t r a v e l i n g a t c o n s t a n t s p e e d s .
T h u s , t h e t i m e s o f e a c h i n t e r s e c t i o n c a n b e d e t e c t e d i n p o l y n o m i a l t i m e , a n d
w e a d d e a c h o f t h e s e i n t e r s e c t i o n s t o t h e e v e n t l i s t .
O n c e w e d e t e r m i n e t h e t i m e s o f e a c h r e l e v a n t e v e n t , w e o r d e r t h e e v e n t s i n
o r d e r o f i n c r e a s i n g t i m e . W e c a n t h e n c r e a t e t h e f u n c t i o n s f A , B ( t ) a n d g A , B ( t )
i n p o l y n o m i a l t i m e e a s i l y b y n o t i n g t h a t e a c h i s p i e c e w i s e l i n e a r b e t w e e n t h e
g i v e n o r d e r e d e v e n t s . 2
D e fi n i t i o n 6 T h e D i r e c t e d D i s j o i n t P a t h s ( D D P ) p r o b l e m i s d e fi n e d a s f o l l o w s .
W e a r e g i v e n a d i r e c t e d g r a p h G a n d k p a i r s o f n o d e s ( s 1, t 1 ) , ( s 2, t 2 ) , . . . , ( s k , t k ) .
T h e p r o b l e m i s t o d e c i d e w h e t h e r t h e r e e x i s t v e r t e x d i s j o i n t p a t h s  1,  2, . . . ,  k
s o t h a t  i g o e s f r o m s i t o t i .
T h e D D P w a s s h o w n t o b e N P - c o m p l e t e i n K a r p ’ s s e m i n a l p a p e r ( K a r p ,
1 9 7 5 ) . S c h r i j v e r n o t e s i n ( S c h r i j v e r , 1 9 9 8 ) t h a t t h e p l a n a r v e r s i o n o f t h i s p r o b l e m
w a s a l s o s h o w n t o b e N P - c o m p l e t e i n t h e 1 9 7 5 p a p e r b y L y n c h ( L y n c h , 1 9 7 5 ) .
ON THE FORMULATION OF AN EMERGENCY ROUTING PROBLEM 1 8
F i g u r e 1 : T h e t r a n s f o r m a t i o n t h a t o c c u r s f o r e a c h v e r t e x v 2 V t o f o r m t h e
n e w g r a p h G 0 f r o m G .
W e w i l l r e f e r t o t h e p l a n a r v e r s i o n o f t h e D D P a s P D D P . I t m a y b e i n t e r e s t i n g
f o r t h e r e a d e r t o n o t e t h a t i f t h e v a l u e o f k i n t h e P D D P i s c o n s i d e r e d fi x e d
( i . e . i s n o t a p a r a m e t e r o f t h e p r o b l e m i t s e l f ) , t h e n t h e p r o b l e m i s t h e o r e t i c a l l y
s o l v a b l e i n p o l y n o m i a l t i m e ( R o b e r t s o n & S e y m o u r , 1 9 9 5 ) . T h i s i m p l i e s t h a t
t h e r e i s h o p e f o r t h e D C R P i f w e a s s u m e t h a t t h e n u m b e r n i s n o t a p a r a m e t e r
o f t h e a l g o r i t h m b u t i s r a t h e r s p e c i fi e d i n a d v a n c e . F o r e x a m p l e , i f w e l i m i t t h e
n u m b e r o f c o n v o y s t h a t o u r a l g o r i t h m w i l l e v e r b e r e q u i r e d t o r o u t e t o 2 0 , t h e n
t h e r e i s h o p e t h a t a p o l y n o m i a l - t i m e a l g o r i t h m m a y e x i s t .
T h o u g h C h a r d a i r e e t a l . i n ( C h a r d a i r e e t a l . , 2 0 0 5 ) a l s o u s e d t h e D D P i n
t h e i r p a p e r t o p r o v e t h e N P - c o m p l e t e n e s s o f t h e i r d e c i s i o n p r o b l e m , t h e i r p r o o f
w a s s o m e w h a t s i m p l e r d u e t o t h e r e s t r i c t i o n s t h a t t h e i r v a l u e s w e r e o n l y a l l o w e d
t o b e i n t e g r a l a n d t h e y w e r e a l l o w e d t o s p e c i f y fi n i t e v a l u e s f o r f u , t h e t i m e b y
w h i c h c o n v o y u w a s r e q u i r e d t o h a v e r e a c h e d i t s t e r m i n a t i o n p o i n t .
L e m m a 2 P D D P  D C R P
P r o o f : A s s u m e t h a t o n e i s g i v e n a n i n s t a n c e o f P D D P , a d i r e c t e d p l a n a r
g r a p h G = ( V , E ) a n d k p a i r s o f n o d e s ( s 1, t 1 ) , ( s 2, t 2 ) , . . . , ( s k , t k ) . W e t r a n s -
f o r m t h i s i n t o a D C R P p r o b l e m v i a t h e f o l l o w i n g . N o t e t h a t b e c a u s e a l l p a t h s
a r e v e r t e x d i s j o i n t , w e k n o w t h a t t h e r e c a n n o t e x i s t i 6 = j s u c h t h a t t i = t j . I n
o t h e r w o r d s , a l l p a t h m u s t h a v e d i s t i n c t d e s t i n a t i o n s . O t h e r w i s e , w e c a n e a s i l y
e l i m i n a t e t h i s t r i v i a l c a s e i n p o l y n o m i a l t i m e .
F o r e a c h v e r t e x v 2 V , w e t r a n s f o r m v i n t o v 1 ! v 2 s u c h t h a t a l l i n p u t s t o
v h e a d i n t o v 1 a n d a l l o u t p u t s f r o m v h e a d o u t w a r d s f r o m v 2 . T h i s w i l l f o r m a
ON THE FORMULATION OF AN EMERGENCY ROUTING PROBLEM 1 9
n e w g r a p h G 0 = ( V 0 , E 0 ) f r o m G . S e e F i g u r e 2 . 3 .
W e c a n c r e a t e t h e f o l l o w i n g i n s t a n c e o f t h e D C R P . L e t G 0 a s c r e a t e d a b o v e
b e t h e d i g r a p h u n d e r c o n s i d e r a t i o n . L e t C 1 = 3 | V 0 | + 1 , C 2 = 0 , a n d n = k
( w h e r e k r e p r e s e n t s t h e p a r a m e t e r i n t h e P D D P ) . L e t t h e w e i g h t o f e a c h e d g e o f
G 0 b e 1 . F o r e a c h 1  i  n , w e l e t v s
i b e t h e t e r m i n a l v e r t e x ( i . e . v 2 i n F i g u r e
2 . 3 ) o f t h e t r a n s f o r m e d v e r t e x f o r s i a n d w e l e t v f
i b e t h e i n i t i a l v e r t e x ( i . e . v 1
i n F i g u r e 2 . 3 ) o f t h e t r a n s f o r m e d v e r t e x f o r t i . F i n a l l y , f o r e a c h 1  i  n , l e t
x i = 2 | V 0 | a n d l e t t h e d e c i s i o n p r o b l e m a s k : “ D o e s t h e r e e x i s t a s c h e d u l e w i t h
c o s t l e s s t h a n o r e q u a l t o 3 | V 0 | ? ” W e c l a i m t h a t t h e a n s w e r t o t h i s q u e s t i o n i s
Y E S i f a n d o n l y i f t h e c o r r e s p o n d i n g P D D P q u e s t i o n i s Y E S a s w e l l . N o t e t h a t
t h e c o n s t r u c t i o n i s c l e a r l y p o l y n o m i a l - t i m e .
F i r s t , a s s u m e t h a t t h e a n s w e r t o t h e P D D P q u e s t i o n i s Y E S . T h e n w e c a n
r o u t e e v e r y c o n v o y a l o n g i t s o w n d i s j o i n t p a t h a t m a x i m u m s p e e d 1 . T h e
a r r i v a l t i m e o f t h e r e a r o f c o n v o y i i s e q u a l t o t h e p a t h l e n g t h f r o m v s
i t o v f
i
p l u s t h e l e n g t h o f c o n v o y i . T h i s e x p r e s s i o n i s u n i f o r m l y u p p e r b o u n d e d b y
| V 0 | + 2 | V 0 | = 3 | V 0 | . T h u s , t h e s c h e d u l e p e r f o r m s w i t h c o s t l e s s t h a n o r e q u a l
t o 3 | V 0 | a n d t h e a n s w e r t o t h e D C R P i s Y E S a s w e l l .
N o w , a s s u m e t h a t t h e a n s w e r t o t h e P D D P q u e s t i o n i s N O . L e t a n y s c h e d u l e
f o r t h e c o r r e s p o n d i n g D C R P p r o b l e m b e g i v e n . L e t t h e p a t h t a k e n b y t h e h e a d
o f c o n v o y i f r o m v s
i t o v f
i b e c a l l e d  i . N o t e t h a t b e c a u s e t h e a n s w e r t o t h e
P D D P q u e s t i o n i s N O , w e m u s t h a v e t w o c o n v o y s , s a y i a n d j , s u c h t h a t  i a n d
 j s h a r e a t l e a s t o n e v e r t e x v 0 2 V 0 i n c o m m o n . N o t e a l s o t h a t v 0 w i l l n o t b e
t h e t e r m i n a l v e r t e x o f a n y p a t h b e c a u s e a l l c o n v o y s h a v e d i s t i n c t d e s t i n a t i o n s .
L e t t h i s s c h e d u l e r u n f o r | V 0 | t i m e u n i t s , a n d c o n s i d e r t h e s t a t e o f t h e c o n v o y s
i n t h e n e t w o r k . T h e r e a r e t w o c a s e s t o c o n s i d e r .
1 . T h e v e r t e x v 0 i s n o t o c c u p i e d b y a n y c o n v o y a t t i m e t = | V 0 | . N o t e
t h a t b e c a u s e e a c h c o n v o y i s o f l e n g t h 2 | V 0 | , e a c h e d g e i s o f l e n g t h 1 , a n d
t h e m a x i m u m s p e e d l i m i t i s 1 , n e i t h e r c o n v o y i n o r j c a n h a v e a l r e a d y
c o m p l e t e l y p a s s e d b y t h e v e r t e x v 0 . C o n s i d e r o n l y c o n v o y i : a l o w e r b o u n d
f o r t h e t i m e t h a t i t w o u l d t a k e f o r t h e r e a r o f c o n v o y i t o m a k e i t t o v f
i i s
ON THE FORMULATION OF AN EMERGENCY ROUTING PROBLEM 2 0
g i v e n b y t h e d i s t a n c e f r o m v 0 t o v f
i i n G 0 ( w h i c h i s g r e a t e r t h a n o r e q u a l
t o 1 b e c a u s e v 0 6 = v f
i ) p l u s t h e | V 0 | t i m e u n i t s t h a t h a v e a l r e a d y p a s s e d
b y p l u s a n a d d i t i o n a l 2 | V 0 | u n i t s t o a c c o m m o d a t e t h e e n t i r e l e n g t h o f t h e
c o n v o y . T h i s q u a n t i t y i s  3 | V 0 | + 1 ; t h u s , i n t h i s c a s e , t h e a n s w e r t o t h e
D C R P m u s t b e N O .
2 . T h e v e r t e x v 0 i s o c c u p i e d b y a t l e a s t o n e c o n v o y a t t i m e t = | V 0 | . A s s u m e
t h a t v e r t e x v 0 i s o c c u p i e d b y e x a c t l y o n e c o n v o y a t t h i s t i m e . T h e n b y
t h e s a m e r e a s o n i n g a s a b o v e , w e k n o w t h a t a t l e a s t o n e o f c o n v o y i o r j
m u s t n o t h a v e r e a c h e d v 0 ; v i a t h e s a m e c a l c u l a t i o n s a s a b o v e , w e k n o w
t h a t t h e r e e x i s t s a c o n v o y t h a t h a s a l o w e r b o u n d o f 3 | V 0 | + 1 u n i t s o f t i m e
b e f o r e i t s r e a r c a n r e a c h t h e t e r m i n a l v e r t e x o f i t s p a t h . T h u s , i f o n l y o n e
c o n v o y i s o c c u p y i n g v 0 , t h e a n s w e r t o t h e D C R P i s N O a s w e l l .
F i n a l l y , c o n s i d e r t h e p o s s i b i l i t y t h a t v 0 i s o c c u p i e d b y a t l e a s t t w o c o n v o y s
a t t i m e t = | V 0 | . C h o o s e a n y t w o o f t h e i n t e r s e c t i n g c o n v o y s , s a y i a n d j .
A t t h i s p o i n t , w e c a n n o t e t h a t v 0 i s e i t h e r t h e i n i t i a l o r t e r m i n a l v e r t e x
o f a t r a n s f o r m e d v e r t e x f r o m t h e o r i g i n a l g r a p h G .
N o t e t h a t a t l e a s t | V 0 |  2 u n i t s o f c o n v o y l e n g t h m u s t r e m a i n “ b e h i n d ”
e a c h o f t h e i n t e r s e c t i n g c o n v o y s .
• I f v 0 i s t h e t e r m i n a l v e r t e x v 2 , t h e n w e k n o w t h a t a t l e a s t o n e u n i t
l e n g t h o f t h e t r a i l i n g c o n v o y s m u s t b e i n t e r s e c t i n g o n t h e e d g e v 1 !
v 2 a n d w i l l c o n t i n u e t o i n t e r s e c t c o m p l e t e l y a l o n g t h i s e d g e f o r a t
l e a s t o n e m o r e u n i t o f t i m e a f t e r t i m e t . B e c a u s e C 2 = 3 | V 0 | + 1 , t h i s
w i l l p u t t h e c o s t o f t h e s o l u t i o n o v e r 3 | V 0 | + 1 .
• I f v 0 i s t h e i n i t i a l v e r t e x v 1 , t h e n w e k n o w t h a t a f t e r o n e m o r e t i m e
u n i t , t h e e d g e v 1 ! v 2 m u s t c o n t a i n b o t h c o n v o y s a n d w i l l c o n t i n u e
t o d o s o f o r a t l e a s t o n e m o r e t i m e u n i t a f t e r w a r d s b e c a u s e | V 0 |  2 .
O n c e a g a i n , b e c a u s e C 2 = 3 | V 0 | + 1 , t h e c o s t o f t h e s o l u t i o n m u s t b e
o v e r 3 | V 0 | + 1 .
I n b o t h c a s e s , t h e a n s w e r t o t h e D C R P i s N O .
ON THE FORMULATION OF AN EMERGENCY ROUTING PROBLEM 2 1
2
3 R e a l i s t i c P a r a m e t e r s f o r t h e P r o b l e m
I n t h i s s e c t i o n , w e p e r f o r m a l i t e r a t u r e r e v i e w o n t h e i m p a c t o f v e h i c u l a r s p e e d s
g i v e n v a r i o u s t y p e s o f d i s a s t e r s . T h e s e v a l u e s a r e n e c e s s a r y t o d e t e r m i n e w h a t
t h e e d g e w e i g h t s o f t h e n e t w o r k s h o u l d b e .
3 . 1 W e a t h e r I m p a c t o n S p e e d o f V e h i c l e s
A d v e r s e w e a t h e r c o n d i t i o n s h a v e a m a j o r i m p a c t o n t h e o p e r a t i o n o f o u r n a t i o n ’ s
r o a d s . T h e i m p a c t o f w e a t h e r c o n d i t i o n s o n h i g h w a y t r a ffi c h a s b e e n c o n s i d e r e d
a n a c t i v e a r e a o f r e s e a r c h f o r m a n y y e a r s ( A g a r w a l e t a l . , 2 0 0 5 ; I b r a h i m &
H a l l , 1 9 9 4 ; P a y e r & K u c h e n h o ff , 2 0 0 4 ; P i n e l l i e t a l . , 2 0 0 4 ) . A d v e r s e w e a t h e r
c o n d i t i o n s s u c h a s s n o w , r a i n , a n d w i n d h a v e b e e n d o c u m e n t e d t o n e g a t i v e l y
i m p a c t t r a ffi c c h a r a c t e r i s t i c s i n a n u m b e r o f w a y s , i n c l u d i n g v e h i c u l a r s p e e d .
M a n y r e s e a r c h e r s h a v e e v a l u a t e d a n d q u a n t i fi e d t h i s i m p a c t a n d t h e i r r e s e a r c h
fi n d i n g s a r e p r e s e n t e d i n t h e f o l l o w i n g p a r a g r a p h s ( C h i n e t a l . , 2 0 0 4 ; F H W A ,
2 0 0 4 ; G o o d w i n , 2 0 0 4 ; K y t e e t a l . , 2 0 0 1 ) .
G o o d w i n ( G o o d w i n , 2 0 0 4 ) p e r f o r m e d a s t u d y t o e v a l u a t e t h e i m p a c t o f
w e a t h e r o n a r t e r i a l t r a ffi c fl o w . I n t h i s s t u d y , a n u m b e r o f w e a t h e r e v e n t s a r e
d e s c r i b e d a l o n g w i t h t h e i r a s s o c i a t e d i m p a c t o n t r a ffi c o p e r a t i o n s . T h e s e e v e n t s
a r e r a i n , s n o w , s l e e t , h a i l , fl o o d i n g , h i g h w i n d , f o g , s m o g , s m o k e , l i g h t i n g , a n d
e x t r e m e t e m p e r a t u r e . T h e s e e v e n t s h a v e b e e n d o c u m e n t e d t o i n fl u e n c e t r a ffi c
fl o w b y r e d u c i n g r o a d w a y c a p a c i t y a n d s p e e d o f v e h i c l e s . S p e e d v a r i a b i l i t y h a s
a l s o b e e n s h o w n t o i n c r e a s e a s a r e s u l t o f t h e s e w e a t h e r e v e n t s . F u r t h e r m o r e , t h e
r e s e a r c h e r c o n d u c t e d a n e x t e n s i v e l i t e r a t u r e r e v i e w o n t h e i m p a c t o f t h e s e e v e n t s
o n t h e s p e e d o f v e h i c l e s . T h i s l i t e r a t u r e r e v i e w r e v e a l e d a s p e e d r e d u c t i o n r a n g e
o f 1 0 % t o 3 6 % f o r v a r i o u s c a t e g o r i e s o f w e a t h e r e v e n t s . A d e t a i l e d d e s c r i p t i o n
o f t h e s e w e a t h e r e v e n t s a n d t h e i r a s s o c i a t e d s p e e d r e d u c t i o n v a l u e s i s l i s t e d i n
T a b l e 2 .
ON THE FORMULATION OF AN EMERGENCY ROUTING PROBLEM 2 2
W e a t h e r c o n d i t i o n S p e e d r e d u c t i o n ( % )
D r y 0
R a i n 1 0
W e t a n d s n o w i n g 1 3
W e t a n d s l u s h y 2 5
W h e e l p a t h s l u s h 3 0
S n o w y a n d s t i c k i n g 3 6
F i g u r e 2 : W e a t h e r i m p a c t ( G o o d w i n ( 2 0 0 2 ) )
W e a t h e r c o n d i t i o n S p e e d r e d u c t i o n ( % )
L i g h t r a i n 8
H e a v y r a i n 1 7
S n o w 1 3 – 4 0
H i g h w i n d 1 4
L o w v i s i b i l i t y 1 5
C o m b i n a t i o n o f s n o w , l o w v i s i b i l i t y a n d h i g h w i n d 3 0 - 3 8
W e t a n d s l u s h p a v e m e n t 2 5
S l u s h y w h e e l p a t h s 3 0
F i g u r e 3 : W e a t h e r i m p a c t ( F H W A 2 0 0 4 ) )
I n a r e p o r t p u b l i s h e d b y t h e F e d e r a l H i g h w a y A d m i n i s t r a t i o n ( F H W A , 2 0 0 4 ) ,
a n u m b e r o f f a c t o r s w e r e a l s o m e n t i o n e d t o h a v e h i g h i m p a c t o n t h e s p e e d o f
v e h i c l e s . T h e s e f a c t o r s a r e r a i n , s n o w , w i n d , a n d l o w v i s i b i l i t y . T h e i r i m p a c t
w a s f o u n d t o r e d u c e s p e e d b y u p t o 3 8 % . A d e t a i l e d d e s c r i p t i o n o f t h e s e i m p a c t s
a n d t h e i r a s s o c i a t e d r e d u c t i o n r a n g e i s g i v e n i n T a b l e 3 .
C h i n e t . a l . ( C h i n e t a l . , 2 0 0 4 ) p e r f o r m e d a s t u d y t o e v a l u a t e t h e t e m p o r a r y
l o s s e s o f h i g h w a y c a p a c i t y a n d q u a n t i f y t h e i r i m p a c t o n p e r f o r m a n c e . I n t h e i r
s t u d y , t h e y c a t e g o r i z e d h i g h w a y s i n t o f o u r c a t e g o r i e s : 1 ) u r b a n f r e e w a y s ; 2 )
r u r a l f r e e w a y s ; 3 ) u r b a n a r t e r i a l s a n d 4 ) r u r a l a r t e r i a l s . T h e y a l s o i d e n t i fi e d s i x
ON THE FORMULATION OF AN EMERGENCY ROUTING PROBLEM 2 3
W e a t h e r c o n d i t i o n H i g h w a y T y p e
U r b a n f r e e w a y R u r a l f r e e w a y U r b a n a r t e r i a l R u r a l a r t e r i a l
L i g h t r a i n 1 0 % 1 0 % 1 0 % 1 0 %
H e a v y r a i n 1 6 % 2 5 % 1 0 % 1 0 %
L i g h t s n o w 1 5 % 1 5 % 1 3 % 1 3 %
H e a v y s n o w 3 8 % 3 8 % 2 5 % 2 5 %
F o g 1 3 % 1 3 % 1 3 % 1 3 %
I c e 3 8 % 3 8 % 2 5 % 2 5 %
F i g u r e 4 : W e a t h e r i m p a c t ( C h i n e t . a l . ( 2 0 0 4 ) )
W e a t h e r c o n d i t i o n S p e e d r e d u c t i o n ( % )
W e t p a v e m e n t s u r f a c e 9 . 5
S n o w 1 6 . 4
W i n d > 1 5 m i / h ( 2 4 k m / h ) 1 1 . 7
V i s i b i l i t y < . 1 7 m i ( 0 . 2 8 k m ) 0 . 4 8 m i p e r . 0 0 6 m i b e l o w 0 . 1 7 m i
F i g u r e 5 : W e a t h e r i m p a c t ( K y t e e t . a l . 2 0 0 1 ) )
w e a t h e r e v e n t s o f g r e a t i m p a c t o n v e h i c u l a r s p e e d . T h e s e e v e n t s a r e l i g h t r a i n ,
h e a v y r a i n , l i g h t s n o w , h e a v y s n o w , f o g , a n d i c e . T h e r e s u l t s o f t h i s s t u d y a r e
s h o w n i n T a b l e 4 .
A s c a n b e n o t i c e d f r o m T a b l e 4 , t h e i m p a c t o f v a r i o u s w e a t h e r e v e n t s o n
u r b a n a n d r u r a l a r t e r i a l s i s e x a c t l y t h e s a m e ( i . e . s a m e % o f s p e e d r e d u c t i o n ) .
T h e s a m e o b s e r v a t i o n i s a l s o t r u e f o r u r b a n a n d r u r a l f r e e w a y s , e x c e p t f o r h e a v y
r a i n . H e a v y r a i n w a s f o u n d t o r e d u c e t h e s p e e d o f v e h i c l e s b y 1 6 % a n d 2 5 % o n
u r b a n a n d r u r a l h i g h w a y s , r e s p e c t i v e l y .
K y t e e t . a l . ( K y t e e t a l . , 2 0 0 1 ) p e r f o r m e d a s t u d y t o e v a l u a t e t h e e ff e c t o f
w e a t h e r o n f r e e - fl o w s p e e d o f v e h i c l e s . I n t h i s s t u d y a n u m b e r o f w e a t h e r e v e n t s
w e r e c o n s i d e r e d : w e t p a v e m e n t s u r f a c e , s n o w , w i n d , a n d v i s i b i l i t y . T h e i m p a c t
o f t h e s e w e a t h e r e v e n t s i s s h o w n i n T a b l e 5 .
ON THE FORMULATION OF AN EMERGENCY ROUTING PROBLEM 2 4
W e a t h e r c o n d i t i o n S p e e d r e d u c t i o n ( % )
L i g h t r a i n 8 – 1 0
H e a v y r a i n 1 0 – 2 5
L i g h t s n o w 1 3 – 1 6 . 4
H e a v y s n o w 2 5 – 4 0
I c e 2 5 – 3 8
H i g h w i n d 1 1 . 7 – 1 4
L o w v i s i b i l i t y / f o g 5 1 3 – 1 5
W e t a n d s n o w i n g 1 5
W e t a n d s l u s h y 2 5
W h e e l p a t h s l u s h 3 0
S n o w y a n d s t i c k i n g 3 6
S n o w , l o w v i s i b i l i t y a n d h i g h w i n d 3 0 – 3 8
S n o w , w e t s u r f a c e , l o w v i s i b i l i t y a n d w i n d 6 S p e e d = 1 0 0 . 2 - 1 6 . 4 s n o w - 9 . 5 w e t + 7 7 . 3 v i s - 1 1 . 7 w i n d
F i g u r e 6 : W e a t h e r i m p a c t ( s u m m a r y )
3 . 2 S u m m a r y o f L i t e r a t u r e R e v i e w
T h e l i t e r a t u r e r e v i e w r e v e a l s t h a t t h e r e a r e a n u m b e r o f w e a t h e r e v e n t s t h a t
n e g a t i v e l y i m p a c t t h e s p e e d o f v e h i c l e s o n h i g h w a y s . T h e s e e v e n t s w e r e c l a s s i fi e d
i n t o e l e v e n c a t e g o r i e s b y d i ff e r e n t r e s e a r c h e r s . T h e s e c a t e g o r i e s a r e l i g h t r a i n ,
h e a v y r a i n , l i g h t s n o w , h e a v y s n o w , w i n d , l o w v i s i b i l i t y , w e t a n d s n o w i n g , w e t
a n d s l u s h y , w h e e l p a t h s l u s h , s n o w y a n d s t i c k i n g a n d c o m b i n a t i o n o f s n o w , l o w
v i s i b i l i t y a n d h i g h w i n d . T a b l e 6 l i s t s t h e s e e v e n t s a n d t h e i r a s s o c i a t e d a v e r a g e
i m p a c t .
3 . 3 R o a d W e a t h e r I n f o r m a t i o n S y s t e m s
M a n y s t a t e s h a v e i n v e s t e d i n a d v a n c e d t e c h n o l o g i e s d e s i g n e d t o m o n i t o r , r e p o r t ,
a n d f o r e c a s t r o a d r e l a t e d w e a t h e r c o n d i t i o n s ( B o o n & C l u e t t , 2 0 0 2 ; F H W A ,
2 0 0 3 ; D e c i s i o n , n . d . ) . C o l l e c t i v e l y , t h e s e t e c h n o l o g i e s a r e r e f e r r e d t o a s R o a d
ON THE FORMULATION OF AN EMERGENCY ROUTING PROBLEM 2 5
W e a t h e r I n f o r m a t i o n S y s t e m s ( R W I S ) ( B o o n & C l u e t t , 2 0 0 2 ) . U s u a l l y , d e p l o y e d
R W I S c o m p o n e n t s i n c l u d e r o a d s i d e s e n s o r s t a t i o n s , c o m m u n i c a t i o n n e t w o r k s ,
t a i l o r e d w e a t h e r f o r e c a s t i n g s e r v i c e s , a d v a n c e d w e a t h e r m o d e l i n g , p a v e m e n t
t e m p e r a t u r e m o d e l i n g a n d p r e d i c t i o n , a n d a n I n t e r n e t w e b s i t e f o r d e c i s i o n m a k -
i n g a n d t r a v e l e r i n f o r m a t i o n ( B o o n & C l u e t t , 2 0 0 2 ) . I m p l e m e n t a t i o n o f t h e s e
R W I S c o m p o n e n t s s e r v e s p r i m a r i l y t o e n a b l e t h e u s e o f c o s t - e ff e c t i v e c o n t r o l
p r a c t i c e s t h a t i m p r o v e s a f e t y a n d t h e l e v e l o f s e r v i c e p r o v i d e d t o u s e r s . I t
s h o u l d b e n o t e d t h a t t h e r o a d c o n d i t i o n a n d w e a t h e r i n f o r m a t i o n i s u s u a l l y d i s -
s e m i n a t e d t o t h e p u b l i c a s a w a y o f h e l p i n g t r a v e l e r s m a k e i n f o r m e d d e c i s i o n s
f o r s a f e a n d e ffi c i e n t t r a v e l .
T h e R W I S u s u a l l y c o l l e c t a l l r e l e v a n t i n f o r m a t i o n u s i n g t h r e e t y p e s o f s e n -
s o r s . T h e s e a r e : 1 ) s n o w a n d i c e s e n s o r s ; 2 ) f o g s e n s o r s a n d 3 ) s t o r m s e n s o r s .
T h e s e d i ff e r e n t t y p e s o f s e n s o r s p r o v i d e i n f o r m a t i o n o n w a t e r c o n t e n t , d e n s i t y o f
f o g , w i n d s p e e d a n d d i r e c t i o n , p r e c i p i t a t i o n a m o u n t a n d r a t e , a i r t e m p e r a t u r e ,
r e l a t i v e h u m i d i t y a n d r o a d w a y s u r f a c e c o n d i t i o n s ( D e c i s i o n , n . d . ) . I t s h o u l d
b e n o t e d t h a t t h e s e s e n s o r s c o l l e c t a n d t r a n s m i t d a t a t o a c e n t r a l p r o c e s s i n g
u n i t t h a t i s u s u a l l y l o c a t e d i n a h i g h w a y m a i n t e n a n c e f a c i l i t y . T h e s e c e n t r a l
p r o c e s s i n g u n i t s t h e n c o m m u n i c a t e , c o l l e c t , a r c h i v e , a n d d i s t r i b u t e t h e d a t a .
4 A l g o r i t h m i c S o l u t i o n s t o t h e O n l i n e P r o b l e m
B y T h e o r e m 1 i n S e c t i o n 2 . 3 , w e k n o w t h a t t h e C R P p r o b l e m s t a t e d i n D e fi n i t i o n
5 i s t h o u g h t t o b e c o m p u t a t i o n a l l y i n t r a c t a b l e b y t h e m a j o r i t y o f c o m p u t e r
s c i e n c e r e s e a r c h e r s . I n t h i s s e c t i o n , w e o u t l i n e a f e w a l t e r n a t i v e p o s s i b l e m e t h o d s
f o r a t t a c k i n g t h i s p r o b l e m d e s p i t e i t s p r o b a b l e i n t r a c t a b i l i t y .
N o t e t h a t t h e r e i s o n e r e l a x a t i o n t h a t i s i m m e d i a t e l y o b v i o u s . F o r e x a m p l e ,
r a t h e r t h a n d e m a n d i n g a n o p t i m a l s o l u t i o n t o t h e p r o b l e m , o n e m i g h t a s k o n l y
f o r a s o l u t i o n t h a t i s a p p r o x i m a t e l y c o r r e c t , s a y t o w i t h i n a c e r t a i n p r e d e t e r -
m i n e d f a c t o r o f o p t i m a l . I n p r a c t i c a l s i t u a t i o n s , a s l o n g a s t h e c o s t i s r e a s o n a b l y
b o u n d e d , t h e p e r f e c t s o l u t i o n i s o f s e c o n d a r y i m p o r t a n c e t o i t s i m m e d i a t e i m -
p l e m e n t a t i o n . O n t h i s t o p i c , t h e r e a r e s e v e r a l m e t h o d s u t i l i z e d i n t h e fi e l d o f
ON THE FORMULATION OF AN EMERGENCY ROUTING PROBLEM 2 6
p r a c t i c a l a r t i fi c i a l i n t e l l i g e n c e t h a t c a n m o s t l i k e l y b e a p p l i e d . T h e s e t e c h n i q u e s
h a v e i m p l i c i t b o n u s e s a s s o c i a t e d w i t h t h e m : A s t h e y a r e r u n , b e t t e r a n d b e t t e r
s o l u t i o n s a r e l o c a t e d i n p a r a m e t e r s p a c e ; w e c a n s t o p t h e c a l c u l a t i o n s a t a n y
t i m e w i t h f u l l k n o w l e d g e o f t h e b e s t s o l u t i o n f o u n d t h u s f a r . I n a d d i t i o n , t h e y
a r e i d e a l l y s u i t e d f o r t h i s r e a s o n f o r t h e o n l i n e v e r s i o n o f t h e p r o b l e m . I f t h e
p a r a m e t e r s a r e a l t e r e d i n m i d - c a l c u l a t i o n b y a n a d v e r s a r y ( u s u a l l y , n a t u r e ) , t h e
e n t i r e a l g o r i t h m d o e s n o t n e e d t o b e r e s t a r t e d f r o m t h e b e g i n n i n g .
4 . 1 I m p l e m e n t a t i o n
I n o r d e r t o t e s t w h e t h e r s u c h a n i m p l e m e n t a t i o n i s p o s s i b l e i n p r a c t i c e , u s i n g t h e
v a l u e s t a b u l a t e d i n S e c t i o n 3 , w e i m i t a t e d t h r e e c o n v o y - r o u t i n g s c e n a r i o s w i t h
v a r i o u s d e g r e e s o f d i s a s t e r i n t e n s i t i e s o n r a n d o m l y g e n e r a t e d m a p s d e s i g n e d
t o s i m u l a t e l a r g e s e c t i o n s o f a m e t r o p o l i t a n a r e a . T h e r e a r e t h i r t y c o n v o y s
t h a t n e e d t o b e r o u t e d w i t h i n a r e g i o n o f n i n e h u n d r e d c i t y b l o c k s w i t h t h i r t y
r a n d o m l y g e n e r a t e d b r i d g e s / t u n n e l s . T h e e p i c e n t e r f o r t h e d i s a s t e r i s i n t h e
c e n t e r o f t h e c i t y , a n d t h e c o n v o y s n e e d t o b e r o u t e d a r o u n d t h i s r e g i o n . E a c h
s e c t i o n o f e v e r y s t r e e t h a s s o m e p r o b a b i l i t y o f b e i n g d a m a g e d b y t h e d i s a s t e r .
M o r e s p e c i fi c a l l y , w e c r e a t e d 3 0 c o n v o y s ; e a c h h a s a r a n d o m l y s e l e c t e d l e n g t h
b e t w e e n 2 a n d 1 7 . M a n y l a r g e c i t i e s a r e d e s i g n e d , f o r t h e m o s t p a r t , a s g r i d s
( e . g . N e w Y o r k C i t y ) w i t h v a r i o u s t u n n e l s a n d b r i d g e s . W e s t a r t o u r g r a p h
w i t h a t h i r t y - b y - t h i r t y g r i d ; a n e x a m p l e g r a p h i s i l l u s t r a t e d i n F i g u r e 7 . T h e
i n t e r s e c t i o n s o f t h e g r i d a r e v e r t i c e s i n t h e g r a p h , a n d e a c h i n t e r s e c t i o n h a s a n
e d g e c o n n e c t e d t o i t s n e i g h b o r i n g v e r t i c e s . W e a d d t w o e x t r a v e r t i c e s b e t w e e n
e a c h a d j a c e n t i n t e r s e c t i o n ( s e e F i g u r e 8 ) , t h u s t h e r e a r e 4 3 8 0 v e r t i c e s a n d 1 0 4 4 0
e d g e s ( o r 5 2 2 0 t w o - w a y s t r e e t s ) i n t h e g r i d . E v e r y e d g e i s a s s o c i a t e d w i t h a
r a n d o m w e i g h t b e t w e e n 0 . 7 a n d 1 . 3 . R e c a l l t h a t t h e t h e o r e t i c a l m a x i m u m s p e e d
f o r a n y c o n v o y i s 1 u n i t . T h u s , i t t a k e s b e t w e e n 0 . 7 a n d 1 . 3 u n i t s o f t i m e f o r t h e
h e a d o f a c o n v o y t o t r a v e r s e a n y g i v e n u n d a m a g e d e d g e i f i t t r a v e l s a t m a x i m u m
s p e e d . T h e b r i d g e s / t u n n e l s a r e b u i l t b y r a n d o m l y a d d i n g a n e d g e b e t w e e n t w o
v e r t i c e s , a n d t h e w e i g h t o f t h e b r i d g e s / t u n n e l s i s a p p r o x i m a t e l y t h e E u c l i d e a n
ON THE FORMULATION OF AN EMERGENCY ROUTING PROBLEM 2 7
F i g u r e 7 : T h i s i s a v i s u a l i z a t i o n o f t h e i m a g i n a r y c i t y u s e d a s a t e s t c a s e . T h e
b r i d g e s / t u n n e l s a r e r a n d o m l y g e n e r a t e d f o r e a c h n e w p r o b l e m i n s t a n c e . T h e
w e i g h t o f e a c h e d g e i n t h e g r a p h i s c h o s e n t o b e 1 p l u s o r m i n u s 3 0 % , a n d t h e
w e i g h t o f e a c h t u n n e l i s c h o s e n t o b e a p p r o x i m a t e l y i t s E u c l i d e a n d i s t a n c e . N o t e
t h e s i z e a n d l o c a t i o n o f t h e c o n v o y o r i g i n a r e a , t h e c o n v o y d e s t i n a t i o n a r e a , a n d
t h e d i s a s t e r e p i c e n t e r .
ON THE FORMULATION OF AN EMERGENCY ROUTING PROBLEM 2 8
F i g u r e 8 : T h i s p i c t u r e i l l u s t r a t e s t h e a d d i t i o n a l v e r t i c e s t h a t w e f o r m w i t h i n
e a c h “ c i t y b l o c k . ” T h i s i s e m p h a s i z e d i n t h e u p p e r - l e f t c o r n e r o f F i g u r e 7 a s
w e l l . U s u a l l y a c i t y b l o c k w i l l h a v e m a n y m o r e t h a n o n e “ a d d r e s s ” p e r b l o c k .
I n a d d i t i o n t o t h e b l o c k i n t e r s e c t i o n s , w e c h o s e t o u s e t h e a p p r o x i m a t i o n t h a t
t h e r e a r e t w o a d d r e s s e s p e r c i t y b l o c k i n o r d e r t o b a l a n c e t h i s r e a l i s t i c f a c t w i t h
c o m p u t a t i o n a l f e a s i b i l i t y . ( N o t e t h a t t h e n u m b e r o f a d d r e s s e s p e r c i t y b l o c k i s
a m u l t i p l i c a t i v e f a c t o r i n t h e n u m b e r o f e d g e s i n t h e n e t w o r k . ) I n a p r a c t i c a l
s i t u a t i o n , w e m u s t a s s u m e t h a t i t w i l l m a k e n o d i ff e r e n c e i f a c o n v o y t h a t i s t e n
b l o c k s l o n g a r r i v e s a t a n a d d r e s s t h a t i s o n l y t w o d o o r s a w a y f r o m i t s “ r e a l ”
d e s t i n a t i o n .
ON THE FORMULATION OF AN EMERGENCY ROUTING PROBLEM 2 9
d i s t a n c e b e t w e e n t h e s e t w o v e r t i c e s . T h e s t a r t i n g v e r t e x o f e a c h c o n v o y i s
r a n d o m l y s e l e c t e d f r o m t h e l o w e r - l e f t n i n e - b y - n i n e c o r n e r , w h i c h a c c o u n t s f o r
1 0 p e r c e n t o f t h e g r i d , a n d t h e d e s t i n a t i o n v e r t e x i s r a n d o m l y s e l e c t e d f r o m t h e
u p p e r - r i g h t n i n e - b y - n i n e c o r n e r ( 1 0 p e r c e n t ) o f t h e g r i d . T h e e p i c e n t e r o f t h e
d i s a s t e r o c c u r s a t t h e c e n t e r o f t h e g r i d a n d c o v e r s a n a r e a o f t w e l v e - b y - t w e l v e
c i t y b l o c k s . A p e r c e n t a g e o f t h e s t r e e t s w i t h i n t h e e p i c e n t e r a r e d a m a g e d ,
a n d t h e r e s t o f t h e g r i d s e e s a d a m a g e o f o n e t h i r d o f t h a t o f t h e e p i c e n t e r .
T h i s p e r c e n t a g e i s v a r i e d b e t w e e n t h e d i ff e r e n t s c e n a r i o s . I n t h i s e x p e r i m e n t ,
3 p r o b l e m i n s t a n c e s a r e g e n e r a t e d , a n d e a c h h a s 2 5 % , 5 0 % , a n d 7 5 % o f s t r e e t
d a m a g e r e s p e c t i v e l y . T o a d d d a m a g e t o a g i v e n s t r e t c h o f r o a d , w e r a n d o m l y
s e l e c t a n e d g e a n d a d d a r a n d o m n u m b e r b e t w e e n 0 a n d 1 3 t o i t s w e i g h t .
4 . 2 T h e “ O r i g i n a l ” G e n e t i c A l g o r i t h m
O u r g o a l i s t o fi n d a n a p p r o x i m a t e l y o p t i m a l s o l u t i o n t o t h i s p r o b l e m i n s t a n c e
w i t h i n a t i m e f r a m e t h a t c a n r e a l i s t i c a l l y b e c a l l e d r e a l - t i m e i n t h e c o n t e x t
o f t h i s p r o b l e m . T h e c o s t o f a g i v e n s o l u t i o n i s c o m p u t e d v i a d i s c r e t e - e v e n t
s i m u l a t i o n .
W e u s e a f o r m o f g e n e t i c a l g o r i t h m t o a p p r o x i m a t e t h e o p t i m a l s o l u t i o n .
T o g e n e r a t e a n i n i t i a l s o l u t i o n , w e u s e d D i j k s t r a ’ s s i n g l e - s o u r c e s h o r t e s t p a t h
a l g o r i t h m t o fi n d t h e s h o r t e s t p a t h f o r e v e r y c o n v o y f r o m t h e i r o r i g i n t o t h e i r
d e s t i n a t i o n , a n d e a c h h a s a n i n i t i a l c o n s t a n t s p e e d o f 1 ( t h e t h e o r e t i c a l m a x i -
m u m ) . T h e i n i t i a l p o p u l a t i o n c o n s i s t s o f 1 0 c o p i e s o f t h e i n i t i a l s o l u t i o n . F o r
e a c h s o l u t i o n i n t h e p o p u l a t i o n , w e r a n d o m l y s e l e c t 8 i n t e r s e c t i o n e v e n t s a n d
a v o i d t h e m ; t h i s c r e a t e s 8 n e w s o l u t i o n s .
T h e a l g o r i t h m “ a v o i d s ” i n t e r s e c t i o n e v e n t s i n t w o d i ff e r e n t w a y s : ( 1 ) s l o w i n g
d o w n a c o n v o y s o a s t o r e a c h t h e p o i n t w h e r e t h e t w o c o n v o y s i n t e r s e c t j u s t a s
t h e o t h e r c o n v o y h a s c l e a r e d i t a n d ( 2 ) r e - r o u t i n g a c o n v o y . W h e n a n i n t e r s e c t i o n
o c c u r s , t h e a l g o r i t h m c h o o s e s o n e o f t h e s e m e t h o d s w i t h p r o b a b i l i t y 5 0 % e a c h .
1 . I f t h e a l g o r i t h m c h o o s e s t o s l o w d o w n a c o n v o y , t h e a l g o r i t h m w i l l s l o w
d o w n t h e s e l e c t e d c o n v o y f r o m t h e v e r t e x p r i o r t o t h e “ c o l l i s i o n ” s o t h a t
ON THE FORMULATION OF AN EMERGENCY ROUTING PROBLEM 3 0
t h e h e a d o f t h e s e l e c t e d c o n v o y r e a c h e s t h e e v e n t v e r t e x j u s t a f t e r t h e t a i l
o f t h e o t h e r c o n v o y l e a v e s t h e c o l l i s i o n p o i n t .
2 . I f t h e a l g o r i t h m c h o o s e s t o r e - r o u t e a c o n v o y , t h e v e r t e x i n t h e p a t h o f t h e
c o n v o y p r i o r t o c o l l i s i o n i s c h o s e n , a n d t h e s e l e c t e d c o n v o y i s r e - r o u t e d
b y fi n d i n g t h e s h o r t e s t p a t h ( u s i n g D i j k s t r a ’ s a l g o r i t h m ) f r o m a v e r t e x
a d j a c e n t t o t h i s p o i n t t o t h e d e s t i n a t i o n . N o t e t h a t i n t h e c a s e w h e r e t h e
c h o s e n v e r t e x h a s o u t - d e g r e e t w o ( i . e . t h e v e r t e x i s n o t a t t h e i n t e r s e c t i o n
o f t h e g r i d ) , t h e r e c a n n o t e x i s t a v a l i d r e - r o u t i n g : a n y r e - r o u t e f r o m t h a t
v e r t e x m u s t s e n d t h e b a c k i n t o i t s e l f b e c a u s e t h e o n l y v e r t e x a d j a c e n t t o
t h e c o l l i s i o n i s b a c k t o w a r d s t h e c o n v o y . I n t h i s c a s e , t h e e v e n t i s a v o i d e d
b y s l o w i n g d o w n t h e c o n v o y ; s l o w i n g d o w n a c o n v o y i s a l w a y s p o s s i b l e .
I f a d e r i v e d s o l u t i o n i s b e t t e r t h a n a n y s o l u t i o n i n t h e c u r r e n t p o p u l a t i o n ,
t h e w o r s t s o l u t i o n i n t h e p o p u l a t i o n i s r e p l a c e d b y t h e n e w s o l u t i o n . T h u s ,
t h e p o p u l a t i o n a l w a y s c o n t a i n s t h e t o p 1 0 s o l u t i o n s . T h e a l g o r i t h m c o n t i n -
u e s t o d i s c o v e r b e t t e r s o l u t i o n s a n d e l i m i n a t e w o r s e s o l u t i o n s u n t i l n o o b v i o u s
i m p r o v e m e n t c a n b e m a d e .
4 . 3 E v o l u t i o n o f t h e G e n e t i c A l g o r i t h m
D i ff e r e n t s t r a t e g i e s f o r d e a l i n g w i t h e v e n t a v o i d a n c e w e r e a t t e m p t e d . T h e r e
e x i s t s a n o b v i o u s s o l u t i o n f o r s c h e d u l i n g t h e c o n v o y s w h i c h w e r e f e r t o a s A l -
g o r i t h m O b v i o u s : l e t t h e c o n v o y s m o v e o n e a t a t i m e ; a c o n v o y c a n n o t d e p a r t
u n l e s s t h e p r e v i o u s c o n v o y a r r i v e s a t i t s d e s t i n a t i o n . ( C l e a r l y , t h i s i s n o t t h e
o p t i m a l s i t u a t i o n . ) O r i g i n a l l y , t h e g e n e t i c a l g o r i t h m h a d a n e q u a l c h a n c e t o
s l o w d o w n o r r e - r o u t e a c o n v o y a s d e s c r i b e d a b o v e . O u r fi r s t a t t e m p t h a d fi n a l
s o l u t i o n c o s t j u s t s l i g h t l y l e s s t h a n i f w e h a d r u n A l g o r i t h m O b v i o u s . U p o n
t e r m i n a t i o n , t h e r e w e r e s t i l l o v e r l a p p i n g e v e n t s , b u t t h e a l g o r i t h m c o u l d n o t
d e r i v e a b e t t e r s o l u t i o n b y r e - r o u t i n g o r s l o w i n g d o w n . O u r o r i g i n a l a l g o r i t h m
p e r f o r m e d w e l l o n s m a l l p r o b l e m s b u t n o t o n t h e p r o b l e m a s d e s c r i b e d i n S e c t i o n
4 . 1 .
ON THE FORMULATION OF AN EMERGENCY ROUTING PROBLEM 3 1
G i v e n t h a t t h e o r i g i n a l s t r a t e g y f a i l e d t o fi n d a s a t i s f a c t o r y s o l u t i o n t o o u r
p r o b l e m , w e a d j u s t e d t h e a l g o r i t h m i n t h e f o l l o w i n g w a y s b a s e d o n o u r r e a s o n i n g
f o r w h y i t d i d n o t p e r f o r m w e l l .
1 . I n s t e a d o f r e - r o u t i n g a c o n v o y f r o m t h e p o i n t o f c o l l i s i o n , w e a t t e m p t e d
t o fi n d a r e - r o u t e p a t h f r o m t h e l a s t g r i d i n t e r s e c t i o n t h e c o n v o y p a s s e d ;
t h u s , t h e a l g o r i t h m a v o i d s r e - r o u t i n g f r o m a n o u t - d e g r e e 2 v e r t e x . B e f o r e
m a k i n g t h i s a d j u s t m e n t , i t w a s o b s e r v e d t h a t a n u n u s u a l l y l a r g e n u m b e r
o f c o n v o y s w e r e b e i n g s l o w e d d o w n r a t h e r t h a n r e r o u t e d . T h e r e a s o n f o r
t h i s i s t h a t a l a r g e p r o p o r t i o n o f t h e v e r t i c e s i n t h e g r a p h h a v e o u t - d e g r e e
2 . I m m e d i a t e l y s w i t c h i n g t o t h e s l o w - d o w n o p t i o n w a s n o t a l l o w i n g t h e
a l g o r i t h m t o a d e q u a t e l y s e a r c h f o r p o t e n t i a l r e - r o u t e s . N o t e t h a t a r e -
r o u t e i s n o w a l w a y s p o s s i b l e , s i n c e a c o n v o y c a n a l w a y s b e r e - r o u t e d f r o m
i t s s t a r t i n g p o i n t .
2 . I n t h e c a s e o f a n e d g e i n t e r s e c t i o n , i n s t e a d o f s l o w i n g d o w n a c o n v o y o n t h e
e d g e w h e r e t w o c o n v o y s s t a r t t o i n t e r s e c t , w e h a d t h e a l g o r i t h m r a n d o m l y
c h o s e a p o i n t t o s l o w d o w n f r o m t h e c o n v o y ’ s p a t h p r i o r t o r e a c h i n g t h e
o ff e n d i n g e d g e . T h i s w a y t h e c o n v o y r e m a i n s c l o s e t o i t s s t a r t i n g p o i n t
w i t h h i g h e r p r o b a b i l i t y k e e p i n g c l e a r o f o t h e r c o n v o y s t h a t m a y b e t r a v -
e l i n g a l o n g t h e s a m e e d g e s , a n d t h u s a v o i d i n g p o s s i b l e i n t e r a c t i o n s w i t h
o t h e r c o n v o y s .
3 . W e a l l o w e d t h e a l g o r i t h m t o f a v o r s l o w i n g d o w n o v e r r e - r o u t i n g . T h e o r i g -
i n a l a l g o r i t h m h a d e q u a l c h a n c e t o d e l a y o r d e t o u r t h e o v e r l a p p i n g c o n v o y ,
b u t n o w , 2 / 3 o f t h e s e c o n v o y s a r e s l o w e d , a n d o n l y 1 / 3 w i l l b e r e - r o u t e d .
B e c a u s e o f t h e l a c k o f s h o r t p a t h s f r o m t h e o r i g i n t o t h e d e s t i n a t i o n i n
o u r p r o b l e m , s e a r c h i n g f o r a q u i c k e r r e - r o u t e t h a t a v o i d s a d d i t i o n a l i n -
t e r s e c t i o n s w i l l n o t s u c c e e d m u c h o f t h e t i m e . O u r a l g o r i t h m s h o u l d n o t
h a v e t h e “ p a t i e n c e ” t o s i f t t h r o u g h t o o m a n y f a i l u r e s , b u t i t w o u l d b e
i m p r u d e n t t o i g n o r e t h e p o s s i b i l i t y o f a s u c c e s s f u l r e - r o u t e c o m p l e t e l y .
A f t e r t h i s m o d i fi c a t i o n , t h e s e c o n d a t t e m p t y i e l d e d b e t t e r r e s u l t s . T h e fi n a l
ON THE FORMULATION OF AN EMERGENCY ROUTING PROBLEM 3 2
c o s t o f t h e s o l u t i o n d r o p p e d o r d e r s o f m a g n i t u d e . H o w e v e r , w e f o u n d t h a t i t
w a s p o s s i b l e t o i n c r e a s e t h e p e r f o r m a n c e o n e m o r e t i m e b a s e d o n t h e f o l l o w i n g
o b s e r v a t i o n : I f w e s l o w d o w n a c o n v o y i n t h e m i d d l e o f t h e g r i d , t h a t c o n v o y
w i l l o c c u p y a c e r t a i n n u m b e r o f e d g e s w h i l e i t i s “ w a i t i n g ” f o r t h e o t h e r c o n v o y
t o p a s s b y t h e c o l l i s i o n p o i n t . O n t h e o t h e r h a n d , i f t h e s t a r t i n g t i m e f o r t h a t
s a m e c o n v o y i s d e l a y e d , a s o p p o s e d t o d e l a y i n g t h e c o n v o y w h i l e i t i s b l o c k i n g u p
r o a d w a y s i n t h e n e t w o r k , t h o s e o t h e r w i s e o c c u p i e d e d g e s w o u l d t h e n b e a v a i l a b l e
f o r o t h e r c o n v o y s t o t r a v e l o r d e t o u r . T h e r e f o r e , d e l a y i n g t h e d e p a r t u r e t i m e f o r
s o m e c o n v o y s i s a p r o m i s i n g s t r a t e g y w h e n o n l y a f e w “ s h o r t ” p a t h s f r o m o r i g i n
t o d e s t i n a t i o n a r e a v a i l a b l e a s i n o u r c a s e . F o r t h e t h i r d a t t e m p t , t h e a l g o r i t h m
d e l a y s t h e s t a r t t i m e o f a c o n v o y d u r i n g a s l o w - d o w n i f t h e v e r t e x s e l e c t e d f o r
s l o w - d o w n h a p p e n s t o b e t h e s t a r t i n g p o i n t o f t h a t c o n v o y ; t h e s t a r t t i m e i s
c h a n g e d t o a r a n d o m v a l u e n o t e x c e e d i n g t h e m a x i m u m a m o u n t o f t i m e i t t a k e s
a c o n v o y t o r e a c h i t s d e s t i n a t i o n . ( I n o t h e r w o r d s , w e a t m o s t d o u b l e t h e t i m e
i t t a k e s t o r e a c h i t s d e s t i n a t i o n i f i t t r a v e l e d a t m a x i m u m s p e e d . ) I t i s t h i s fi n a l
s o l u t i o n f o r w h i c h w e p r e s e n t o u r r e s u l t s b e l o w .
T h e fi n a l a l g o r i t h m t h e n i s a s f o l l o w s .
1 . I n i t i a l i z a t i o n
( a ) U s e D i j k s t r a ’ s a l g o r i t h m t o g e n e r a t e a n i n i t i a l s o l u t i o n
( b ) B u i l d t h e i n i t i a l p o p u l a t i o n b y m a k i n g 1 0 c o p i e s o f t h e i n i t i a l s o l u t i o n
2 . I t e r a t i o n
( a ) F o r e a c h s o l u t i o n i n t h e p o p u l a t i o n , g e n e r a t e 8 n e w s o l u t i o n s b y
s e l e c t i n g 8 r a n d o m e v e n t s t o a v o i d . T h e e v e n t a v o i d a n c e c a n b e
p e r f o r m e d v i a t w o m e t h o d s :
i . W i t h p r o b a b i l i t y 1 / 3 , t h e e v e n t a v o i d a n c e i s a c c o m p l i s h e d v i a
r e - r o u t i n g a c o n v o y , a s d e s c r i b e d a b o v e .
i i . W i t h p r o b a b i l i t y 2 / 3 , t h e e v e n t a v o i d a n c e i s a c c o m p l i s h e d v i a
s l o w i n g d o w n a c o n v o y .
ON THE FORMULATION OF AN EMERGENCY ROUTING PROBLEM 3 3
5 10 15 20 25 30
Iterations
100
200
300
400
500
Cost Ratio
30 Iterations of the Genetic
Algorithm: 25% Damage
5 10 15 20 25 30
Iterations
100
200
300
400
500
Cost Ratio
30 Iterations of the Genetic
Algorithm: 50% Damage
5 10 15 20 25 30
Iterations
100
200
300
400
500
600
Cost Ratio
30 Iterations of the Genetic
Algorithm: 75% Damage
F i g u r e 9 : T h e s e fi g u r e s i l l u s t r a t e t h e r e s u l t s o f t h e g e n e t i c a l g o r i t h m c o m p u t a -
t i o n . N o t e t h a t a f t e r r o u g h l y 3 0 i t e r a t i o n s , i n e a c h c a s e t h e c o s t r a t i o i s r o u g h l y
2 , a n e x t r e m e l y g o o d r e s u l t .
ON THE FORMULATION OF AN EMERGENCY ROUTING PROBLEM 3 4
A . R a n d o m l y s e l e c t a v e r t e x f r o m t h e p a t h o f o n e o f t h e c o n v o y s
p r i o r t o t h e i n t e r s e c t i o n p o i n t .
B . I f t h e s e l e c t e d v e r t e x i s t h e o r i g i n o f t h e c o n v o y , d e l a y t h e
d e p a r t u r e t i m e o f t h e c o n v o y b y a d d i n g a r a n d o m n u m b e r a s
d e s c r i b e d a b o v e .
C . I f t h e s e l e c t e d v e r t e x i s n o t t h e s t a r t i n g p o i n t , a d j u s t t h e
s p e e d o f t h e c o n v o y o n t h e p a t h , s o t h a t t h e h e a d o f t h e
c o n v o y r e a c h e s t h e i n t e r s e c t i o n i m m e d i a t e l y a f t e r t h e t a i l o f
t h e o t h e r c o n v o y .
i i i . F r o m t h e 1 0 + 8 * 1 0 = 9 0 s o l u t i o n s i n t h e p o p u l a t i o n , k e e p t h e t o p
1 0 s o l u t i o n s f o r t h e n e x t i t e r a t i o n
D e fi n i t i o n 7 O n e w a y t o c a l c u l a t e a t h e o r e t i c a l l o w e r b o u n d f o r t h e c o s t o f a n y
s o l u t i o n i s t o c a l c u l a t e t h e l o n g e s t t r a v e l t i m e i f a l l c o n v o y s t a k e t h e s h o r t e s t
r o u t e a t m a x i m u m s p e e d f r o m e a c h i n d i v i d u a l o r i g i n t o d e s t i n a t i o n a s s u m i n g
t h a t C 1 = C 2 = 0 . W e d e fi n e t h e c o s t r a t i o o f a g i v e n s o l u t i o n S t o b e t h e r a t i o
o f t h e c o s t o f s o l u t i o n S t o t h e c o s t o f t h e l o w e r b o u n d .
T h e c o s t r a t i o f o r t h i s e x p e r i m e n t u p t o 3 0 i t e r a t i o n s i s s h o w n i n F i g u r e
9 . F o r e a c h p r o b l e m i n s t a n c e w e g e n e r a t e d , o u r e x p e r i m e n t s h o w e d t h a t o u r
fi n a l a l g o r i t h m f o u n d t h e b e s t s o l u t i o n i t c o u l d fi n d i n u n d e r 6 0 i t e r a t i o n s ,
a n d t h e fi n a l c o s t i s l e s s t h a n t w i c e t h e t h e o r e t i c a l l o w e r b o u n d o n a v e r a g e .
M o r e o v e r , i n s o m e c a s e s , w e a r e a b l e t o s c h e d u l e e v e r y c o n v o y f r o m i t s o r i g i n
t o i t s d e s t i n a t i o n w i t h o u t a n y i n t e r s e c t i o n e v e n t s a t a l l . E a c h s i m u l a t i o n l a s t e d
b e t w e e n 5 - 1 5 m i n u t e s , w h i c h , i n t e r m s o f d i s a s t e r r o u t i n g , i s c l o s e e n o u g h t o
r e a l - t i m e t o b e a c c e p t a b l e f o r o u r p u r p o s e s .
5 F u t u r e W o r k
F u t u r e w o r k i n c l u d e s e x t e n d i n g t h e a l g o r i t h m t o fi n d b e t t e r s o l u t i o n s m o r e
e ffi c i e n t l y . C u r r e n t l y , t h e a l g o r i t h m t e r m i n a t e s w h e n n o s i g n i fi c a n t i m p r o v e m e n t
i s m a d e a f t e r 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 o r t h e r e a r e n o m o r e i n t e r a c t i o n s t o
ON THE FORMULATION OF AN EMERGENCY ROUTING PROBLEM 3 5
a v o i d . A d v a n c i n g t h e c o n v o y s ’ s t a r t i n g t i m e o r s p e e d i n g u p c o n v o y s m a y y i e l d
b e t t e r r e s u l t s . A l s o , i n s t e a d o f r a n d o m l y p i c k i n g u p a n e v e n t t o a v o i d , s e l e c t i n g
a n e v e n t t h a t h a s r e l a t i v e l y h i g h e r c o s t m i g h t l e a d t o f a s t e r c o n v e r g e n c e .
O t h e r r e l a x a t i o n s t o t h e C R P a r e a l s o p o s s i b l e , p e r h a p s b y c o n s t r a i n i n g t h e
C 1, C 2, o r M p a r a m e t e r s t o l i e w i t h i n a c e r t a i n r a n g e d e p e n d i n g o n t h e v a l u e s
i n G . H o w e v e r , w e b e l i e v e t h a t s t u d y i n g t h e m o r e g e n e r a l p r o b l e m i s m o r e c o s t -
e ffi c i e n t t h a n p o u r i n g r e s o u r c e s i n t o r e s e a r c h i n g p o t e n t i a l l y m i n o r s u b p r o b l e m s .
R e f e r e n c e s
A g a r w a l , M . , M a z e , T . , & S o u l e y r e t t e , R . 2 0 0 5 . I m p a c t s o f w e a t h e r o n u r b a n
f r e e w a y t r a ffi c fl o w c h a r a c t e r i s t i c s a n d f a c i l i t y c a p a c i t y . P r o c e e d i n g s o f t h e
2 0 0 5 M i d - C o n t i n e n t T r a n s p o r t a t i o n R e s e a r c h S y m p o s i u m , A m e s , I o w a .
B o o n , C . , & C l u e t t , C . 2 0 0 2 . R o a d w e a t h e r i n f o r m a t i o n s y s t e m s : e n a b l i n g
p r o a c t i v e m a i n t e n a n c e p r a c t i c e s i n W a s h i n g t o n s t a t e . W a s h i n g t o n R e s e a r c h
T r a n s p o r t a t i o n C e n t e r ( T R A C ) , R e s e a r c h P r o j e c t T 1 8 0 3 , T a s k 3 9 .
C h a r d a i r e , P . , M c K e o w n , G . P . , H a r r i s o n , S . A . , & R i c h a r d s o n , S . B . 2 0 0 1 . C o n v o y
p l a n n i n g i n a d i g i t i z e d b a t t l e s p a c e . J o u r n a l o f D e f e n c e S c i e n c e , 6 ( 2 ) , 1 6 8 –
1 7 5 .
C h a r d a i r e , P . , M c K e o w n , G . P . , V e r i t y - H a r r i s o n , S . A . , & R i c h a r d s o n , S . B .
2 0 0 5 . S o l v i n g a T i m e - S p a c e N e t w o r k F o r m u l a t i o n f o r t h e C o n v o y M o v e m e n t
P r o b l e m . O p e r . R e s . , 5 3 ( 2 ) , 2 1 9 – 2 3 0 .
C h a z e l l e , B e r n a r d , & E d e l s b r u n n e r , H e r b e r t . 1 9 9 2 . A n o p t i m a l a l g o r i t h m f o r
i n t e r s e c t i n g l i n e s e g m e n t s i n t h e p l a n e . J . A C M , 3 9 ( 1 ) , 1 – 5 4 .
C h i n , S . , F r a n z e s e , O . , G r e e n e , D . , & H w a n g , H . 2 0 0 4 . T e m p o r a r y L o s s e s
o f H i g h w a y C a p a c i t y a n d I m p a c t s o n P e r f o r m a n c e : P h a s e 2 . O a k R i d g e
N a t i o n a l L a b o r a t o r y , R e p o r t # O R N L / T M - 2 0 0 4 / 2 0 9 .
C h r o b a k , M a r e k , & P a y n e , T . H . 1 9 9 5 . A L i n e a r - T i m e A l g o r i t h m f o r D r a w i n g
a P l a n a r G r a p h o n a G r i d . I n f o r m a t i o n P r o c e s s i n g L e t t e r s , 5 4 ( 4 ) , 2 4 1 – 2 4 6 .
ON THE FORMULATION OF AN EMERGENCY ROUTING PROBLEM 3 6
C o r m e n , T h o m a s T . , L e i s e r s o n , C h a r l e s E . , & R i v e s t , R o n a l d L . 1 9 9 0 . I n t r o -
d u c t i o n t o a l g o r i t h m s . C a m b r i d g e , M A , U S A : M I T P r e s s .
C u m m i n g s , N . 1 9 9 9 . H o w O R h e l p e d p a c i f y B o s n i a . O R N e w s l e t t e r ( O p e r . R e s .
S o c . ) , 3 4 2 , 1 5 – 1 7 .
D e c i s i o n , I T S . W e a t h e r d e t e c t i o n S y s t e m s . A c c e s s i b l e v i a
h t t p : / / w w w . c a l c c i t . o r g / i t s d e c i s i o n / s e r v a n d t e c h / W e a t h e r a p p l i c a t i o n s / d e t e c t i o n . h t m .
D i j k s t r a , E . W . 1 9 5 9 . A N o t e o n T w o P r o b l e m s i n C o n n e x i o n w i t h G r a p h s .
N u m e r i s c h e M a t h e m a t i k , 1 , 2 6 9 – 2 7 1 .
F H W A . 2 0 0 3 . B e s t P r a c t i c e f o r R o a d w e a t h e r M a n a g e m e n t , fi n a l r e p o r t . F e d e r a l
H i g h w a y A d m i n i s t r a t i o n , R e p o r t # F H W A - O P - 0 3 - 0 8 1 , W a s h i n g t o n D C .
F H W A . 2 0 0 4 . I d e n t i f y i n g a n d a s s e s s i n g k e y w e a t h e r - r e l a t e d p a r a m e t e r s a n d
t h e i r i m p a c t s o n t r a ffi c o p e r a t i o n s u s i n g s i m u l a t i o n , fi n a l r e p o r t . F e d e r a l
H i g h w a y A d m i n i s t r a t i o n , R e p o r t # F H W A - H R T - 0 4 - 1 3 1 , W a s h i n g t o n D C .
G a r e y , M i c h a e l R . , & J o h n s o n , D a v i d S . 1 9 7 9 . C o m p u t e r s a n d I n t r a c t a b i l i t y :
A G u i d e t o t h e T h e o r y o f N P - C o m p l e t e n e s s . N e w Y o r k , N Y , U S A : W . H .
F r e e m a n & C o .
G o o d w i n , L . 2 0 0 4 . W e a t h e r i m p a c t s o n a r t e r i a l t r a ffi c fl o w . M i t r e t e k S y s t e m s ,
I n c . , F a l l s C h u r c h .
H a r e l , D a v i d , & S a r d a s , M e i r . 1 9 9 5 . A n A l g o r i t h m f o r S t r a i g h t - L i n e D r a w i n g
o f P l a n a r G r a p h s . T e c h . r e p t . M C S 9 5 - 2 4 . R e h o v o t , I s r a e l .
I b r a h i m , & H a l l , F . 1 9 9 4 . E ff e c t o f a d v e r s e w e a t h e r c o n d i t i o n s o n s p e e d - fl o w -
o c c u p a n c y r e l a t i o n s h i p s . T r a n s p o r t a t i o n R e s e a r c h R e c o r d s , 1 4 5 7 , 1 8 4 – 1 9 1 .
I o a n n o u , P . , & C h a s s i a k o s , A . 2 0 0 1 . M o d e l i n g a n d R o u t e G u i d a n c e o f T r u c k s
i n M e t r o p o l i t a n A r e a s .
K a r p , R . M . 1 9 7 5 . O n 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 c o m b i n a t o r i a l p r o b l e m s .
N e t w o r k s , 5 , 4 5 – 6 8 .
ON THE FORMULATION OF AN EMERGENCY ROUTING PROBLEM 3 7
K l a r , A . , & W e g e n e r , R . 1 9 9 7 a . A h i e r a c h y o f m o d e l s f o r m u l t i l a n e v e h i c u l a r
t r a ffi c I : M o d e l i n g .
K l a r , A . , & W e g e n e r , R . 1 9 9 7 b . A h i e r a c h y o f m o d e l s f o r m u l t i l a n e v e h i c u l a r
t r a ffi c I I : N u m e r i c a l a n d s t o c h a s t i c i n v e s t i g a t i o n s .
K l a r , A . , K u e h n e , R . , & W e g e n e r , R . 1 9 9 6 . M a t h e m a t i c a l m o d e l s f o r v e h i c u l a r
t r a ffi c .
K y t e , M . , K h a t i b , Z . , S h a n n o n , P . , & K i t c h e n e r , F . 2 0 0 1 . E ff e c t o f w e a t h e r o n
f r e e - fl o w s p e e d . T r a n s p o r t a t i o n R e s e a r c h R e c o r d s , 1 7 7 6 , 6 0 – 6 8 .
L e e , Y . N . , M c K e o w n , G . P . , & R a y w a r d - S m i t h , V . J . 1 9 9 6 . T h e C o n v o y M o v e -
m e n t P r o b l e m w i t h I n i t i a l D e l a y s . P a g e s 2 1 3 – 2 3 4 o f : R a y w a r d - S m i t h , V . J . ,
O m a n , I . , R e e v e s , C . R . , & S m i t h , G . D . ( e d s ) , M o d e r n H e u r i s i t c S e a r c h
M e t h o d s . W i l e y .
L y n c h , J a m e s F . 1 9 7 5 . T h e e q u i v a l e n c e o f t h e o r e m p r o v i n g a n d t h e i n t e r c o n -
n e c t i o n p r o b l e m . S I G D A N e w s l . , 5 ( 3 ) , 3 1 – 3 6 .
P a y e r , T . , & K u c h e n h o ff , H . 2 0 0 4 . M o d e l l i n g e x t r e m e w i n d s p e e d s a t a G e r m a n
w e a t h e r s t a t i o n a s b a s i c i n p u t f o r a s u b s e q u e n t r i s k a n a l y s i s f o r h i g h - s p e e d
t r a i n s . J o u r n a l o f w i n d e n g i n e e r i n g a n d i n d u s t r i a l a e r o d y n a m i c s , 9 2 ( 3 ) ,
2 4 1 – 2 6 1 .
P i n e l l i , J . , S u b r a m a n i a n , C . , & P l a m o n d o n , M . 2 0 0 4 . W i n d e ff e c t o n e m e r g e n c y
v e h i c l e s . J o u r n a l o f w i n d e n g i n e e r i n g a n d i n d u s t r i a l a e r o d y n a m i c s , 9 2 ( 7 ) ,
6 6 3 – 6 8 5 .
R o b e r t s o n , N . , & S e y m o u r , P . D . 1 9 9 5 . G r a p h M i n o r s X I I I : T h e D i s j o i n t P a t h s
P r o b l e m . J o u r n a l o f C o m b i n a t o r i a l T h e o r y B , 6 3 , 6 5 – 1 1 0 .
R y a n , M a t t . 2 0 0 5 . T a k e t h e P o l i t i c s O u t o f D i s a s t e r R e l i e f . T h e I n d e p e n d e n t
I n s t i t u t e ( C o m m e n t a r y A r t i c l e s ) .
S c h r i j v e r . 1 9 9 8 . R o u t i n g a n d T i m e t a b l i n g b y T o p o l o g i c a l S e a r c h . I n : I C M :
P r o c e e d i n g s o f t h e I n t e r n a t i o n a l C o n g r e s s o f M a t h e m a t i c i a n s .
ON THE FORMULATION OF AN EMERGENCY ROUTING PROBLEM 3 8
T e c h n o l o g i e s , J a y t u . h t t p : / / w w w . s i g a l e r t . c o m .