2 ( ) ( 657-850 -) 2 ( 980-8579 06) ( ) maximin logit Key Words :. () ( ) ( ) ),2) (e.g. ) ( ) 3) 4) HazTrans 4) PC*HazRoute 5) ( (2) ) LPHC (Low Probability with High Conseuence: ) ( ) ),6) Bell 6) LPHC ( ) maximin Bell 6) 2 i) ii) heuristic LPHC Bell 6) logit
(2) 2. Bell 6) 3. 2 4. 5. 6. 7. (2) N {,, N} L {,, L} (o, d) o d K k K C k ( ) min. k K C k 3) 5) C k C k δ,k c. () L δ,k k, 0 Kronecker () c c (e.g. ) (potential exposure) 3),5) ),6) Abkowitz 4) ( Erkut and Ingolfsson ) ) 3) Asakura 4) (incident probability) { } ( Erkut and Verter 0) 0 6 0. 0.8) 2 { } ( ) 2 C k LPHC (low-probability with high-conseuence: ) Bell 6) LPHC Bell 6) LPHC 2 ( ) 2
2 2 ( ) LPHC (catastrophe averse) ) 0 3 0 0 7 0, 000 ambiguity ( Knight 7) ) 8),9),20),2) 22) Bell 6) k K h k ( ) C k k K h k C k ( ) 2 {h k } { } ( ) maximin (MM) Bell 6) maximin (MSA: Method of Successive Averages) MM 3 MM (i.e. ) 2 Bell heuristics 2 Bell 6) 3 Bell MM 2 (o, d ) (o, d 2 ) (o, d ) (o, d 2 ) Bell 6) Bell 6) MM ( ) 2 MM 2 2. maximin (MM) () (2) Bell 6) MM (3) 2 () ( ) G N {,, N} L {,, L} o D D (o, d) K d, d D L 3
( ) c G ( ) { L} =. (2) L 0, L (3) (o, d) k K d k ( ) C d k () c δ d,k, k Kd, d D. (4) L δ d,k Kronecker (o, d) k n n k 0 d D f d (o, d) d k K d h d k h {h d k k Kd, d D} h k K d h d k = f d, d D. (5) h d k 0, k Kd, d D. (6) h π (h) c, L. (7) h d k δd,k k K d (exposure) δ d,k (4) Kronecker h ( ) Z 0 (h, ) h d k c δ d,k k K d L = h d k Cd k () k K d = π (h) L Z 0 (h, ) (h ) (2) LPHC (LPHC: Low Probability with High Conseuence) (i.e. ) h maximin [P0] max. min. Z 0 (h, ), h s.t. (h, ) Ω h Ω. Ω h h (5) (6) Ω (2) (3) [P0] ( ) maximin (MM) MM 2 6) 2 (i.e. ) (i.e. ) MM [P0] Nash ( ) (3) Bell 6) MM 2 (LP: Linear Programming) MM [P0] 4
[P0] [P0 -Dual] max. Z 0 (), s.t. Ω. Z 0 () h [LP0 ()] Z 0 () min. Z 0 (h, ), s.t. h Ω h. h [LP0 ()] [LP0 -()-Dual] Z 0 () = max. f d S d 0, S 0 s.t. S d 0 Cd k (), k Kd, d D. (8) S 0 {S d 0 d D} (5) Lagrange (8) S d 0 (o, d) ( ) [LP0 ()-Dual] Z 0 () [P0 -Dual] maximin [P0] S 0 [LP0-Dual] max. f d S d 0,,S 0 s.t. S d 0 Cd k (), k Kd, d D, Ω. (o, d) S d 0 S d 0 () min. C d k K d k (), d D. (9) [LP0-Dual] [CP0-Dual] max. f d S d 0 (), s.t. Ω. [LP0-Dual] h (2) Lagrange Q 0 [LP0-Primal] min. h,q 0 Q 0, s.t. Q 0 π (h), L, (0) h Ω h. π (h) (7) [LP0-Primal] Q 0 (0) h h Q 0 (h) max. L π (h)c () [LP0-Primal] h [CP0-Primal] (4) min. Q 0 (h), s.t. h Ω h. h MM [P0] 2 [LP0-Dual] [LP0-Primal] LP 2 [LP0-Dual] [LP0-Primal] h 2 [LP0-Dual] [LP0-Primal] {h d k } {Cd k ()} (o, d) K d Bell 6) MM [P0] (MSA: Method of Successive Averages) Bell heuristic 6) 3. MM [P0] [P0] ( ) (variation) 2 5
4. () [P0] [P] max. min. Z (h, ) h s.t. (h, ) Ω h Ω. Z 0 (h, ) f d HK d θ (h), Ω h Ω h (5) (6) (2) (3) [P] (RM) RM [P0] 2 H d K (h) (o, d) d D H d K (h) k K d h d k f d ln hd k f d. (2) HK d (h) H K d (h) (o, d) (i.e. h d = hd 2 = ) ln K d (i.e. k K d h d k = f d, h d k = 0, k k) 0 HK d (h) (o, d) HK d (h) HK d (h) RM [P] h θ (i.e. ) θ 0 Z 0 (h, ) θ RM [P] MM [P0] (2) RM [P] 2 h RM [P] [P -Dual] max. Z (), s.t. Ω. Z () h [CP ()] Z () min. Z 0 (h, ) f d HK d h θ (h), s.t. h Ω h. [CP ()] {C k ()} logit 23) d D h d k () f exp [ θc d d k [ ()] exp k θc d Kd. (3) k ()], k K d Z () Z () f d S d (). (4) S d () (o, d) d D S d () θ ln [ θc d k ()]. (5) k K d exp (4) (5) RM [P] [CP-Dual] Z () max. f d S d (), s.t. Ω. Ω (2) (3) h 6
[CP-Primal] min. Q (h) h θ s.t. h Ω h f d HK d (h), [CP-Primal-Link] min. Q (x) x θ s.t. x Ω x f { d HL d (x) Hd N (x)}, Ω h h (5) (6) Q (h) Q (h) max. L π (h) (6) [CP-Primal] RM [P] (3) [CP-Primal] logit (4) (3) logit Markov HK d (h) 24) HK d (h) = Hd L [x(h)] Hd N [x(h)], d D. (7) x(h) xi d j (h), L, d D. (8) k K d h d k δd,k HL d(x) Hd N (x) d D HL d (x) xi d j f ln xd d f, d L HN d (x) x d i N f d ln j O(i) x d = f d ln j N i I( j) xi d j f d j O(i) xi d j f d i I( j),. O(i) { j L} I( j) {i L} i j [P-Primal] x {xi d j L, d D} Q (x) (6) x Ω x x p d ni xim d + bd i = 0, i N, d D. (9) n I(i) m O(i) x d 0, L, d D. (20) b d i i f d i f d 0 (4) [CP-Dual] [CP-Primal] [CP-Primal-Link] [CP-Primal] h 2 HK d (h) h h h [CP-Primal-Link] x 2 3 HL d(x) Hd N (x) x 24) x x [CP-Dual] (o, d) S d () ( C d {C d k k Kd } ) {C d } S [P] 7
7. 4. RM [P] [CP-Dual] logit (Bell 6) all-or-nothing heuristic ) 3 a) Z b) d c) α () logit (2) (SUE: Stochastic User Euilibrium) Maher 25) () Z () Z () logit d Z () [ Z () ] f d S d () = π (), L. (2) π () L π () c xi d j (), (22) xi d j () L d D x d () k K d h d k ()δd,k, (23) h d k () (3) (2) (23) Z () d D k K d ( ) C k () logit x() {xi d j () L, d D} (23) logit ( ) Dial 26) Bell 27) Akamatsu 28) Bell-Akamatsu 27),28) x() S () {S d () d D} 2 i, j N exp [ ] θc if L, W () (24) 0 otherwise. d D S d () S d () = θ ln V od(). (25) xi d j () d D L xi d j () = f d V oi()w ()V jd (). (26) V od () V () i j V() [ I W() ] I. (27) W() N N i j (24) I N N V() (27) II 8
Z () [CP-Dual] Z () 0 α + α Z () (2) (3) Ω n Z ( (n) ) α (n) max d (n) (n) z (n) Z ( (n) ) r(n) arg. max. L z (n) n ˆL(n) L\r(n) ˆL(n) [d (n) z (n) z (n) r(n) if (n) > 0, ] 0 if (n) = 0. (28) [d (n) ] r(n) d (n). (29) ˆL(n) L d (n) = 0 α (n) + αd (n) (2) r(n) d (n) 0 d (n) < 0 n α (n) α (n) max min. ˆL max { } (n) /d(n). (30) α [0, α (n) max] (n) + αd (n) (3) (2) n α (n) [0, α (n) max] Z () logit (i.e. (27) V() ) Z ( (n) + αd (n) ) α (n) ( ) 2 SUE Maher 25) (uadratic interpolation) n (n) d (n) α Ẑ (n) (α) Z ( (n) + αd (n) ) Maher 25) α [0, α (n) max] Ẑ (n) ( ) α = 0, α (n) max Ẑ (n) (α) dẑ (0) dα dẑ (α (n) max) dα Z ( (n) ) d (n) g (n) 0, (3) Z ( (n) + α (n) maxd (n) ) d (n) g (n) max. (32) α (n) α (n) := g (n) 0 α (n) max. (33) g (n) max g (n) 0 (3) (33) I [Algorithm ] Step 0 ( ) () Ω n := Step ( ) (n) (n) [CP-Dual] Step 2 () (2) (30) d (n) α (n) max Step 3 ( ) (2) (27) Z ( (n) + α (n) maxd (n) ) (3) (33) α (n) Step 4 ( ) (n+) := (n) + α (n) d (n) n := n + Step 5. 9 2 (e.g. ) 9 9
6 2 5 3 32 7 28 7 22 4 K 2 6 f 9 = θ = 0.00, 0.0, 0.,, 0 RM [P] {h k } {C k C k( )} (i.e. ) Z S θ ln k e θc k () = /2 θ h S 2 2 θ MM [P0] {C k } S 0 k C k h k θ {h k } 2 θ {C k } θ (i.e. ) θ θ S (RM [P] ) 2 θ = n (n) [CP-Dual] Z (n) S ( (n) ) [ [ 6,9, 8,9 ] = c 6,9 c 6,9 +c 8,9, c 8,9 c 6,9 +c 8,9 ] [0.452, 0.548] S 0 = c 6,9 6,9 = c 8,9 8,9 = 7.677 (h k ) ID θ =.0 θ =.05 θ =. θ = θ = 0 2 3 6 9 0.84 0.26 0.22 0.22 0.22 2 2 5 6 9 0.48 0.23 0.20 0.20 0.20 3 2 5 8 9 0.69 0.40 0.37 0.37 0.37 4 4 5 6 9 0.48 0.23 0.20 0.20 0.20 5 4 5 8 9 0.69 0.40 0.37 0.37 0.37 6 4 7 8 9 0.84 0.259 0.274 0.274 0.274 0.000 0.003 0.004 0.004 0.004 2 (Ck ) ID θ =.0 θ =.05 θ =. θ = θ = 0 θ 0 3.540 5.833 7.493 7.659 7.677 2 22.055 4.900.53 8.06 7.76 7.677 3 8.702 2.229 0.77 7.928 7.702 7.677 4 22.055 4.900.53 8.06 7.76 7.677 5 8.702 2.229 0.77 7.928 7.702 7.677 6 0 0 3.246 7.234 7.633 7.677 98.727 39.776.629 0.6 0.00 0 Z (n) (S ) -69.33-27.077-9.693 5.940 7.504 7.677 6 Z ( ) 5 4 3 2 20 40 60 80 # of iterations 2 Z = 5.940 60 ( 2 ) Bell 6) heuristics 00 ( ) 6. 0
() (i.e. ) (i.e. ) d D (i.e. ) f { f d d D} f (strategic level) h (operational level) f h d D (e.g. ) Ψ d f Z D ( f) f d Ψ d. (34) f d = E. (35) f d 0, d D. (36) E E = [P2] max. min. Z 2 (h,, f) h, f Z 0 (h, ) + Z D () f d HK d θ (h) ξ H D( f), s.t. (, h, f) Ω Ω h Ω f. H D H D ( f) f d ln f d. (37) ξ ( ) f Ω f (35) (36) [P2] - 29) [P2] RM [P] [P2] h f d D nested-logit f d () exp [ ξ { S d () + Ψd}] exp [ ξ { (38) S od () + Ψd}], d D h d k () f exp [ θc d d k () [ ()] exp k θc d Kd. (39) k ()], k K d S d () (o, d) (5) [P2] [CP2-Dual] min. Z 2 () ξ ln exp [ ξ { S d () + Ψd}], s.t. Ω. [P2] [CP2-Dual] Z 2 () [ Z 2 ()] = Z 2() Z 2 S d = () S d = c xi d j (), (40) xi d j () L d D x () h d k ()δd,k. (4) k K d h d k () (39) [CP2-Dual] [Algorithm-] Step 2 z() Z 2 () Z 2 () (25) (27) S () V() 2 S () (38)
f() 3 f() V() xi d j () = f d () V oi()w ()V jd (). V od () (2) LPHC (catastrophic averse) (i.e. ) (e.g. ) (i.e. ) (RM [P] ) [P] (i.e. ) p {p } p =, and p > 0, L. (42) L p ( ) ( ) p R(; p) ln (43) p L R(; p) > 0 R(; p) 0 p = p R(; p) = 0 RM [P] [P3] min. h max. Z 3 (h, ) Z (h, ) R(; p), η s.t. (h, ) Ω h Ω. /η(> 0) p (i.e. p ) [P3] [P3] RM [P] /η 0 [P3] [CP3-Dual] max. Z 3 () f d S d () R(; p), η s.t. Ω. 2 [P3] RM [P] ( h [P] ) [CP3-Dual] RM [CP2-Dual] [Algorithm-] Step 2 [CP3-Dual] [ Z3 () ] = Z 3 = = π () η f d S d () { ln p + R(; p), η }, (44) π () (22) [CP3-Dual] [Algorithm-] Step 2 z() Z 3 () 7. Bell 6) maximin 2 2
I 25) n (n) d (n) α [0, α (n) max] Ẑ (n) (α) Z ( (n) + αd (n) ) Maher 25) α [0, α (n) max] Ẑ (n) (α) Q (n) (α) β(n) 2 ( ) α β (n) 2 2 + β (n) 3. (I.) α n β (n), β(n) 2 β (n) 3 (i.e. α = 0, α (n) max) Ẑ (n) (α) = Q(α), dẑ (α) = dq(α) dα dα. (I.2) α = 0, α (n) max Ẑ (n) (α) Ẑ (n) (0) Z ( (n) ) d (n) g (n) α 0, Ẑ (n) (α(n) max) Z ( (n) + αd (n) ) d (n) g (n) α max. Q (n) (α) II α (n) = β (n) 2 = g (n) 0 g (n) max g (n) 0 α (n) max. (I.3) Logit x i N (i.e. 2 ) O {,, β} T {β +,, γ} D {γ +,, N} O O = β, T T = γ β D D = N γ β 2 G(N, L) 0 oo W ot 0 od W 0 to W tt W td, 0 do 0 dt 0 dd W ot {W oi i = β +,, γ, o =,, β}, W tt {W i = β +,, γ, j = β +,, γ}, W td {W id i = β +,, γ, d = γ +,, N}. (II.) O T T T T D 0 oo, 0 od, 0 to, 0 do, 0 dt 0 dd 0 O O, O D, T O, D O, D T D D (27) N N V 0 oo V ot V od V [I W] I = 0 to V tt V td, 0 do 0 dt 0 dd (II.2) V ot W ot [I W tt ], V od W ot [I W tt ] W td, V tt [I W tt ] I, V td [I W tt ] W td. (II.3) O T, O D, T T, T D V W (o, d) x d {xi d j L} i j x d f d V owv d V od, (o, d) OD. (II.4) V o V d N N i V o,i V i,d (II.4) x d (II.3) V V ot, V td V od (II.4) [I W] [I W tt ] V ot = W ot, o O, (II.5) [I W tt ]V td = W td, d D. (II.6) V ot V td V ot W td V od = V ot W td. (II.7) ( V od = W ot V td ) (II.5) (II.6) 3
W tt L SOR (Successive Over relaxation) JOR (Jacobi Over Relaxation) ) U.S. Department of Commerce, Bureau of the Census, Washington, DC.: Truck Inventory and User Survey, 994. 2) Itoh, T., Hayano, M., Naito, T., Asakura, Y., Hato, E. and Wada, T.: Empirical analysis on hazardous material transportation using road traffic census and accident data, in E., T. and G., T. R. eds., City Logistics III, pp. 245 258, Institute for City Logistics, 2003. 3) List, G., Mirchandi, P., Turnuist, M. and Zofrafos, K.: A modelling and analysis for hazardous materials transportation: Risk analysis, routing-scheduling and facility location, Transportation Science, Vol. 25, No. 2, pp. 00 4, 99. 4) Abkowitz, M., Lepofsky, M. and Cheng, P.: Selecting criteria for designating hazardous materials highway routes, Transportation Research Record, Vol. 333, pp. 30 35, 992. 5) Sivakumar, R. and Batta, M., R. Karwan: A network based model for transporting extremely hazardous materials, Operations Research Letters, Vol. 3, No. 2, pp. 85 93, 993. 6) Sivakumar, R. and Batta, M., R. Karwan: A multiple route conditional risk model for transporting hazardous materials, INFOR, Vol. 33, pp. 20 33, 995. 7) Erkut, E.: On the credibility of the conditional risk model for routing hazardous materials, Operations Research Letters, Vol. 8, pp. 49 52, 995. 8) Jin, H., Batta, R. and Karwan, M. H.: On the analysis of two new models for transporting hazardous materials, Operations Research, Vol. 44, No. 5, pp. 70 723, 996. 9) Sherali, H. D., Brizendine, L. D., Glickman, T. S. and Subramanian, S.: Low probability-high conseuence considerations in routing hazardous material shipments, Transportation Science, Vol. 3, No. 3, pp. 237 25, 997. 0) Erkut, E. and Verter, V.: Modeling of transport risk for hazardous materials, Operations Research, Vol. 46, No. 5, pp. 625 642, 998. ) Erkut, E. and Ingolfsson, A.: Catastrophe avoidance models for hazardous materials route planning, Transportation Science, Vol. 34, No. 2, pp. 65 79, 2000. 2) Kara, B., Erkut, E. and Verter, V.: Accurate calculation of hazardous materials transport risks, Operations Research Letters, Vol. 3, pp. 285 292, 2003. 3),,,, Vol. 30, pp. CD ROM, 2004. 4) Asakura, Y.: Risk assessment for hazardous materials transportation in a road network, in Proceedings of 2nd International Symposium on Transport Network Reliability, pp. 5 9, 2004. 5) ALK Associates, Princeton, New Jersey: ALK s PC*HazRoute (Version 2.0), 994. 6) Bell, M. G. H.: Mixed route strategies for the risk-averse shipment of hazardous materials, Networks and Spatial Economics, Vol. 6, pp. 253 265, 2006. 7) Knight, F. H.: Risk, Uncertainty and Profit, Houghton, Mifflin, Boston, 92. 8) Ellsberg, D.: Risk, ambiguity, and the Savage axioms, Quarterly Journal of Economics, Vol. 75, pp. 643 669, 96. 9) Gilboa, I.: Expected utility with purely subjective nonadditive probabilities, Journal of Mathematical Economics, Vol. 6, pp. 65 88, 987. 20) Schmeidler, D.: Subjective probability and expected utility without additivity, Econometrica, Vol. 57, pp. 57 587, 989. 2) Gilboa, I. and Schmeidler, D.: Maxmin expected utility with non-uniue prior, Journal of Mathematical Economics, Vol. 8, pp. 4 53, 989. 22),,, 2006. 23) Fisk, C. S.: Some developments in euilibrium traffic assignment, Transportation Research B, Vol. 4, pp. 243 255, 980. 24) Akamatsu, T.: Decomposition of path choice entropy in general transport networks, Transportation Science, Vol. 3, No. 4, pp. 349 362, 997. 25) Maher, M.: Algorithms for logit-based stochastic user euilibrium assignment, Transportation Research B, Vol. 32, No. 8, pp. 539 549, 998. 26) Dial, R. B.: A probabilistic multipath traffic assignment algorithm which obviates path enumeration, Transportation Research, Vol. 5, pp. 83, 97. 27) Bell, M. G. H.: Alternative to Dial s logit assignment algorithm, Transportation Research B, Vol. 29B, No. 4, pp. 287 295, 995. 28) Akamatsu, T.: Cyclic flows, Markov process and stochastic traffic assignment, Transportation Research B, Vol. 30, No. 5, pp. 369 386, 996. 29),, Vol. 40/IV, pp. 09 8, 989. ( 9 2 4 ) Catastrophe Averse Strategies for Routing and Siting in the Disposal of Hazardous Materials Takeshi NAGAE and Takashi AKAMATSU This study provides a method for uantitative analysis of a shipment planning of hazardous materials (hazmats). We first formulate a hazmat routing problem as a maximin problem: the assignment of hazmat vehicles is determined so as to minimize the expected conseuence; the incident probabilities on each link are chosen so as to maximize the expected conseuence, reflecting catastrophe avoidance of the dispatcher. Our analysis then reveals that the maximin problem reduces to a single-level convex programming problem, which shares a common mathematical structure with a logit-type stochastic user euilibrium problem that is well known in the field of transportation science. This enables us to develop a globally convergent algorithm for obtaining the optimal mixed route strategy, which can be effectively applied to real world large-scale networks. 4