(2) 2. Bell 6) (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.

Size: px

Start display at page:

Download "(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."

さみうえや
7 years ago
Views:

1 2 ( ) ( ) 2 ( ) ( ) 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) 2. Bell 6) (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) ) 2 { } ( ) 2 C k LPHC (low-probability with high-conseuence: ) Bell 6) LPHC Bell 6) LPHC 2 ( ) 2

3 2 2 ( ) LPHC (catastrophe averse) ) , 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

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

4 ( ) 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

(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

5 [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

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.

6 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

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.

7 [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

(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),.

8 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

(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)

9 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 (e.g. ) 9 9

(30) α [0, α (n) max] (n) + αd (n) (3) (2) n α (n) [0, α (n) max] Z () logit (i.e.

10 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 = (h k ) ID θ =.0 θ =.05 θ =. θ = θ = (Ck ) ID θ =.0 θ =.05 θ =. θ = θ = 0 θ Z (n) (S ) Z ( ) # of iterations 2 Z = ( 2 ) Bell 6) heuristics 00 ( ) 6. 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.

11 () (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)

(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.

12 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

/η(> 0) p (i.e. p ) [P3] [P3] RM [P] /η 0 [P3] [CP3-Dual] max. Z 3 () f d S d () R(; p), η s.t. Ω.

13 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) β (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

14 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, ) 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 , Institute for City Logistics, ) 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 , ) Sivakumar, R. and Batta, M., R. Karwan: A network based model for transporting extremely hazardous materials, Operations Research Letters, Vol. 3, No. 2, pp , ) Sivakumar, R. and Batta, M., R. Karwan: A multiple route conditional risk model for transporting hazardous materials, INFOR, Vol. 33, pp , ) Erkut, E.: On the credibility of the conditional risk model for routing hazardous materials, Operations Research Letters, Vol. 8, pp , ) 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 , ) 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 , ) Erkut, E. and Verter, V.: Modeling of transport risk for hazardous materials, Operations Research, Vol. 46, No. 5, pp , 998. ) Erkut, E. and Ingolfsson, A.: Catastrophe avoidance models for hazardous materials route planning, Transportation Science, Vol. 34, No. 2, pp , ) Kara, B., Erkut, E. and Verter, V.: Accurate calculation of hazardous materials transport risks, Operations Research Letters, Vol. 3, pp , ),,,, Vol. 30, pp. CD ROM, ) 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, ) ALK Associates, Princeton, New Jersey: ALK s PC*HazRoute (Version 2.0), ) Bell, M. G. H.: Mixed route strategies for the risk-averse shipment of hazardous materials, Networks and Spatial Economics, Vol. 6, pp , ) 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 , 96. 9) Gilboa, I.: Expected utility with purely subjective nonadditive probabilities, Journal of Mathematical Economics, Vol. 6, pp , ) Schmeidler, D.: Subjective probability and expected utility without additivity, Econometrica, Vol. 57, pp , ) Gilboa, I. and Schmeidler, D.: Maxmin expected utility with non-uniue prior, Journal of Mathematical Economics, Vol. 8, pp. 4 53, ),,, ) Fisk, C. S.: Some developments in euilibrium traffic assignment, Transportation Research B, Vol. 4, pp , ) Akamatsu, T.: Decomposition of path choice entropy in general transport networks, Transportation Science, Vol. 3, No. 4, pp , ) Maher, M.: Algorithms for logit-based stochastic user euilibrium assignment, Transportation Research B, Vol. 32, No. 8, pp , ) Dial, R. B.: A probabilistic multipath traffic assignment algorithm which obviates path enumeration, Transportation Research, Vol. 5, pp. 83, ) Bell, M. G. H.: Alternative to Dial s logit assignment algorithm, Transportation Research B, Vol. 29B, No. 4, pp , ) Akamatsu, T.: Cyclic flows, Markov process and stochastic traffic assignment, Transportation Research B, Vol. 30, No. 5, pp , ),, Vol. 40/IV, pp. 09 8, 989. ( ) 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

, City Logistics III, pp. 245 258, Institute for City Logistics, 2003. 3) List, G., Mirchandi, P., Turnuist, M. and Zofrafos, K.

04-04 第 57 回土木計画学研究発表会講演集 vs

04-04 第 57 回土木計画学研究発表会講演集 vs 04-04 vs. 1 2 1 980-8579 6-6-06 E-mail: shuhei.yamaguchi.p7@dc.tohoku.ac.jp 2 980-8579 6-6-06 E-mail: akamatsu@plan.civil.tohoku.ac.jp Fujita and Ogawa(1982) Fujita and Ogawa Key Words: agglomeration economy,