저작자표시

저작자표시-비영리-변경금지 2.0 대한민국 이용자는 아래의 조건을 따르는 경우에 한하여 자유롭게

l 이 저작물을 복제, 배포, 전송, 전시, 공연 및 방송할 수 있습니다. 다음과 같은 조건을 따라야 합니다:

l 귀하는, 이 저작물의 재이용이나 배포의 경우, 이 저작물에 적용된 이용허락조건 을 명확하게 나타내어야 합니다.

l 저작권자로부터 별도의 허가를 받으면 이러한 조건들은 적용되지 않습니다.

저작권법에 따른 이용자의 권리는 위의 내용에 의하여 영향을 받지 않습니다. 이것은 이용허락규약(Legal Code)을 이해하기 쉽게 요약한 것입니다.

Disclaimer

저작자표시. 귀하는 원저작자를 표시하여야 합니다.

비영리. 귀하는 이 저작물을 영리 목적으로 이용할 수 없습니다.

변경금지. 귀하는 이 저작물을 개작, 변형 또는 가공할 수 없습니다.

/ B

N † < Æ~ Ã Ì † < Æ 0 A  7 Hë H

þ

j& h o l Z O ` ¦ : Ÿ xô Ç @ /× æ“ §: Ÿ x W 1à Ô0 >ß ¼ ç

H+ þ A „ à ÐÒ  o

Equilibrium of Transit Assignment via Optimization

2016 ¸ 2 Z 4

"

fÖ ¦@ /† < Ɠ § @ /† < Æ" é ¶ í

ß

–\ O · › ¸‚ / B N† < Æ Ò

^

” ⠐

 ï Ÿ ´

"

fÖ¦@/†<Ɠ§ @/†<Æ"é¶ í

ß

–\O·›¸‚/BN†<ÆÂÒ íߖ\O/BN†<Æ „/BN

^

” ⠐

@

/×擧:Ÿx :Ÿx'ŸC&ñ ëH]j(transit assignment problem)¢¸H â–Ђ×þ˜ ëH ]

j(route choice problem)H 5px̐os ئµ1Ït\"f 3lq&htt #Q‹" â–Ð\¦ :Ÿx

#Œ s1lxÙþ¡Ht ÆÒ&ñ,s1lx½+Ét\¦ \V8£¤H כ s.‘:r 7HëH“Ér t

^ o

=?/ :Ÿx'Ÿ`¦ ×æd”ܼ–Ð 5px̐o ‚ ñ_ €ªœ$í(taste variation)`¦ìøÍ%òH :Ÿx'Ÿ C

&ñ—¸+þA >hµ1Ï\ œí&h`¦ ´úÆÒ%3.s\¦ 0AK ‚ ñ_ €ªœ$í`¦ “¦9ôÇ l”>r

ƒ

½¨õ\¦&ño%i.Õªo“¦›'a8£¤÷&H :Ÿx'Ÿ|¾Ó`¦ çH+þA:Ÿx'Ÿ|¾Ós“¦ ˜Ð“¦ :

Ÿ

x'ŸC&ñ õ çH+þA:Ÿx'Ÿ|¾Ós ÷&•¸2Ÿ¤ H ~½ÓZO:r`¦ ]jr%i. 'Í P:

–

Ð “§:Ÿx×¼ X<s'(Smart card Data)–Ð ÂÒ' t^o= ?/ 5px̐os z´]j s6 x ô

Ç â–Ð x9 \P\¦ ÆÒ&hH ·ú˜“¦o1pu`¦ >hµ1Ï%i. "fÖ¦t^o=`¦ @/©œÜ¼

–

Ð {9ÅÒ{9çߖ5px̐o â–Ð\¦ÆÒ&hôÇ õ €• 90%5px̐o\ @/K"fâ–ÐÆÒ&h\$í /

B

N%i.

6£§Ü¼–Ð5px̐o ‚ ñ_€ªœ$í`¦s1lxrçߖ,¨8Š5pxx9™D¥¸úšõ °ú “Érq6 xכ¹™è _

‚ ñ p'\¦ SX‰Ò¦Ãº–Ð “¦9%i`¦ M:, %iþj&ho(inverse optimiza- tion) lZO`¦ 6 x#Œ ‚ ñ p'_ ½+ËSX‰Ò¦x9•¸ †<Êú\¦ ÆÒ&ñH s

>

^¦2Ÿ¤þj&ho(convex quadratic program)—¸+þA`¦ >hµ1Ï%i.

t}Œ•Ü¼–Ð ÆÒ&ñ)a ½+ËSX‰Ò¦x9•¸ †<Êú\¦ 6 x#Œ SX‰Ò¦&h çH+þA`¦ &ñ_

“¦ “¦&ñ&h&ño\¦ 6 x#Œ Õª ”>rF$í`¦ 7£x"î%i.¢¸ôÇ,çH+þA`¦ >íߖ

#

Œ Õª õ\¦ z´]j @/½©—¸ t^o= W1àÔ0>ß¼\"f Ž7£x%i. Ž7£x õ ‘:r

ƒ

½¨_ :Ÿx'ŸC&ñ ~½ÓZOs 5px̐o ‚ ñ_ €ªœ$í`¦ “¦9H @/³ð&h“ —¸+þA“

™ D

¥½+˖Ðf± —¸+þA˜Ð \V8£¤§4`¦€• 10% >h‚ rvHכ `¦ SX‰“%i. Ì

Á³À#a : @/×擧:Ÿx :Ÿx'ŸC&ñ, ‚ ñ€ªœ$í, %iþj&ho, t^o= 5px̐oâ–ÐÆÒ&h,

“

§:Ÿx×¼.

Á þ

š£U> : 2011-31005

  â

´

±

%K ïŸ´ i

1 "Òeµ 1

1.1 ƒ½¨_ Câ x9 3lq&h . . . 1

1.2 ƒ½¨#30A x97HëH ½¨$í . . . 3

2 e×iµ¥o>Ä© 5 2.1 &ñ&h 6 xçH+þA . . . 5

2.1.1 rÛ¼%7›þj&h—¸+þA . . . 5

2.1.2 0>×¼\vçH+þA . . . 6

2.1.3 Beckmann—¸+þA . . . 6

2.1.4 çH+þAõ rÛ¼%7› þj&hK . . . 7

2.1.5 1lxÂÒ1pxd” . . . 10

2.1.6 q‚+þA ©œ˜ÐëH]j . . . 11

2.1.7 “¦&ñ&h &ño . . . 12

2.1.8 Frank-Wolfe·ú˜“¦o1pu . . . 14

2.2 SX‰Ò¦&h 6 xçH+þA . . . 15

2.2.1 SX‰Ò¦&h :Ÿx'ŸC&ñ—¸+þA . . . 15

2.2.2 †½Ó–Ðf± —¸+þA . . . 17

2.2.3 †½ÓáԖÐc± —¸+þA . . . 20

2.2.4 SX‰Ò¦&h 6 x çH+þA . . . 20

2.3 ‚ ñ_ €ªœ$í`¦ ìøÍ%òôÇ —¸+þA . . . 24

2.3.1 &ñ&h—¸+þA . . . 24

2.3.2 SX‰Ò¦&h—¸+þA . . . 25

2.3.3 l”>rƒ½¨_ ôÇ> . . . 26

3 m㍠¢ [Ëc˜+ § šßj&P„7 29

3.1 5px̐o â–Ð ÆÒ&h . . . 29

3.1.1 5px̐o â–Ð ÆÒ&h ~½ÓZO:r . . . 29

3.1.2 5px̐o â–Ð ÆÒ&h \V]j . . . 34

3.1.3 5px̐o â–Ð ÆÒ&h õ . . . 36

3.2 â–Ђ×þ˜_ {9›'a$í . . . 38

3.3 ™D¥¸úšs â–Ђ×þ˜\ puH %ò†¾Ó . . . 39

3.4 5px̐o ‚ ñ_ €ªœ$í ›'a¹1Ï . . . 42

4 P-§ šßj:Ça ˜¿ÌfC 46 4.1 rçߖSX‰©œW1àÔ0>ß¼ x9q6 xכ¹™è . . . 46

4.2 â–Ð|9½+Ë Òqt$í . . . 48

4.3 q6 x†<Êú . . . 49

4.4 P-çH+þA_ ”>rF$í . . . 51

4.5 P-:Ÿx'ŸC&ñ·ú˜“¦o1pu . . . 54

5 ¤n>¡õ i'a˜+ ÚrTÒ¼†„È·™–¿ÁþÊÁ ÍÙÇa 55 5.1 %iþj&ho . . . 55

5.2 %iþj&ho\¦ 6 xôÇ ½+ËSX‰Ò¦x9•¸†<Êú ÆÒ&ñ . . . 56

6 ™‹“@&P„7 61 6.1 z´+«>X<s' x9z´+«>>S\‰ . . . 61

6.2 ™D¥½+˖Ðf± —¸+þA . . . 62

6.3 EM·ú˜“¦o1pu`¦ 6 xôÇ SX‰Ò¦ìrŸíÆÒ&ñ . . . 65

6.4 %iþj&ho\¦ 6 xôÇ SX‰Ò¦ìrŸíÆÒ&ñ . . . 68

6.5 z´+«>õ . . . 70

6.5.1 ”¸2£§\ Ér ìr$3 . . . 72

6.5.2 EM·ú˜“¦o1puõ_ q“§ìr$3 . . . 73

6.5.3 ™D¥½+˖Ðf± —¸+þAõ_ q“§ìr$3 . . . 74

7 ³À»ÈÐ ™ ÍÙÑñ ¥o>Ä© 78 7.1 כ¹€• . . . 78 7.2 ÆÒÊꃽ¨ ~½Ó†¾Ó . . . 80

½ Ç

Ô ”§ %K «¹› 82

Æ Z

%K ïŸ´ 88

¸

Ø   â ´

2.1 ‚ ñ €ªœ$í`¦“¦9ôÇ l”>rƒ½¨ . . . 28

3.1 2011¸ 11Z4 21{9 X<s' כ¹€• . . . 36

3.2 ¨8Š5px›¸½+Ë\ Ér â–ÐÆÒ&h $í/BNÖ¦ . . . 37

3.3 o\ Ér â–ÐÆÒ&h $í/BNÖ¦ . . . 38

3.4 ÅÒ×攸‚â–Ђ×þ˜ qÖ¦ . . . 41

3.5 rçߖ@/\ Ér”¸‚â–Ð ‚×þ˜qÖ¦ o . . . 41

3.6 Fg"î%i-Œ™z´%içߖ ¿º 5px̐o_ ‚×þ˜â–Ðü<@/îߖâ–Ð 5Åq$í . . . . 43

5.1 %iþj&ho\¦ :ŸxôÇ ìrŸíÆÒ&ñ \V]j . . . 59

6.1 SX‰Ò¦ìrŸí ÆÒ&ñõ —¸4Sq Ž7£x\ 6 x)a X<s' . . . 61

6.2 –Ðf± —¸+þAõ ™D¥½+˖Ðf± —¸+þA_ p' ÆÒ&ñõ. . . 64

6.3 EM·ú˜“¦o1puܼ–Ð ÆÒ&ñ)a ½+ËSX‰Ò¦ìrŸí . . . 66

6.4 EM·ú˜“¦o1puܼ–Ð ÆÒ&ñ)a :Ÿx>°úכ . . . 67

6.5 L2-”¸2£§Ü¼–Ð ÆÒ&ñ)a½+ËSX‰Ò¦ìrŸí . . . 71

6.6 %iþj&ho–Ð ÆÒ&ñ)a SX‰Ò¦ìrŸí_:Ÿx>°úכ . . . 71

6.7 ”¸2£§\ Ér $í0pxìr$3 . . . 73

6.8 EM·ú˜“¦o1puõ_$í0pxìr$3 . . . 75

6.9 ™D¥½+˖Ðf± —¸+þA\ Érq“§ìr$3 . . . 76

6.10 P-:Ÿx'ŸC&ñõ_ q“§ìr$3 . . . 76

6.11 P-:Ÿx'ŸC&ñõ –Ðf± lìøÍ 6 xçH+þA_ >íߖrçߖ ìr$3 . . . 77

7.1 ‘:r ƒ½¨ õ_ Z>$íx9 __ . . . 80

Ü

«Í Ï   â ´

1.1 7HëH½¨$í âì2£§•¸ . . . 4

2.1 Pigou_ \V . . . 7

2.2 Braess Paradox_ \V . . . 8

2.3 Boston Big Dig . . . 9

2.4 New Braess Paradox . . . 10

2.5 SX‰Ò¦&h 6 xçH+þA :¿º >h_ â–Ð . . . 20

3.1 4Ÿx…;%i-sú%i¨8Š5px‚ÃЛ¸5px̐o . . . 31

3.2 ’aË>%i-"fÖ¦%i0px â–Ð . . . 31

3.3 ’aË>%i-y©œzŒ™%i5px̐o[þt_ {9©œryŒ•õ @©œryŒ•1 "é¶ ÕªAáÔ. 32 3.4 ’aË>%i-y©œzŒ™%i5px̐o[þt_ {9©œryŒ•õ @©œryŒ•2 "é¶ ÕªAáÔ. 33 3.5 ’aË>%i-|ÃÌr©œ ”¸‚â–Ð . . . 34

3.6 ’aË>-|ÃÌr©œ5px̐o â–ÐÆÒ&h\V]j . . . 35

3.7 ئµ1Ï-•¸‚ÃÌ%iŠ©œZ> ”¸‚â–Ð[þt_¨8Š5px›¸½+Ë qÖ¦ . . . 37

3.8 2011.11.20∼26 â–ÐÆÒ&h $í/BNÖ¦ . . . 39

3.9 â–Ђ×þ˜_ {9›'a$í . . . 40

3.10 Fg"îo-Œ™z´ ”¸‚â–Ð . . . 43

3.11 5px̐oaü< b_ Áº Z>/BG‚ s. . . 44

3.12 ¨îçH»1Ñ5px|¾Ó- ?/s1lxrçߖ\ Ér â–Ђ×þ˜ qÖ¦ . . . 45

3.13 ¨8Š5pxrú- ?/s1lxrçߖ\ Érâ–Ђ×þ˜ qÖ¦ . . . 45

4.1 rçߖSX‰©œW1àÔ0>ß¼ . . . 47

4.2 Fg"îo-Œ™z´çߖ 4>h_â–Ð . . . 48

4.3 [j t ”¸‚â–Ð\ @/ôÇ 5px̐o ‚×þ˜ . . . 50

4.4 yŒ• â–Ð(P ¢¸H Q) þj‚_ ‚×þ˜“ Γ_ %ò%i . . . 52

5.1 Fg"î%i-Œ™z´%iŠ©œ\"f â–Ð Iõ â–Ð II þj‚_ ‚×þ˜“ Γ_ % ò %i . . . 57

5.2 yŒ• â–Ð þj‚_ ‚×þ˜“ Γ_ %ò%iõ ›'a¹1ϝ)a 5px̐o ‚×þ˜ qÖ¦ 59 6.1 z´+«>>S\‰•¸ . . . 62

6.2 EM·ú˜“¦o1pu ½+ËSX‰Ò¦x9•¸†<Êú . . . 67

6.3 EM·ú˜“¦o1pu Åҁ SX‰Ò¦x9•¸†<Êú :α . . . 68

6.4 EM·ú˜“¦o1pu Åҁ SX‰Ò¦x9•¸†<Êú :β . . . 69

6.5 EM·ú˜“¦o1pu Åҁ SX‰Ò¦x9•¸†<Êú : 1-α-β . . . 70

6.6 L₂-”¸2£§ ½+ËSX‰Ò¦x9•¸†<Êú . . . 72

6.7 L₂-”¸2£§ Åҁ SX‰Ò¦x9•¸†<Êú :α . . . 73

6.8 L₂-”¸2£§ Åҁ SX‰Ò¦x9•¸†<Êú :β . . . 74

6.9 L₂-”¸2£§ Åҁ SX‰Ò¦x9•¸†<Êú : 1-α-β . . . 75

6.10 X<s' 1_ ·ú˜“¦o1pu ú§4 õ . . . 77

1. " Ò e µ

1.1 ¥o>Ä©˜+ :¿R ™  â´†\

@

/×擧:Ÿx\"f ×æכ¹ôÇ ëH]j ×æ H, 5px̐os ئµ1Ït\"f 3lq&htt #Q‹"

â

–Ð\¦ :Ÿx#Œ s1lxÙþ¡Ht ÆÒ&ñ, s1lx½+Ét\¦ \V8£¤H כ s. s\¦

“

§:Ÿx/BN†<Æ\"fH @/×擧:Ÿx :Ÿx'ŸC&ñ ëH]j(transit assignment problem) ¢¸H

â

–Ђ×þ˜ ëH]j(route choice problem)s“¦ôÇ [5].

:

Ÿ

x'ŸC&ñëH]jH 5px̐o yŒ•’_q6 x`¦þj™èo9H 5px̐o[þt_'ŸI, 7

£

¤,>hZ>&hĺhA(selfish routing)ܼ–Г#Œ ĺhA>e”ܼ–Ð^¦Ãºe”.Õª o

“¦ ĺhA >e”_ çH+þA“Ér “§:Ÿx/BN†<Æ\"f #Q‹" 5px̐o•¸ 1lq&hܼ–Ð ‰&³F ‚

× þ

˜(â–Ð)\¦ ÜãJ 1lxl \OH âì2£§“ 0>×¼\v çH+þAõ {9uôÇ. :Ÿx'ŸC&ñ ëH ]

j þj&ho_›'a&h\"f<ɪp–ÐîrsÄ»HþjH>e”s:r\"fH çH+þA_”>rF

$ í

÷rëߖ mz´]jçH+þAK\¦ ½¨H כ s &h ×æכ¹KtH ©œS!“X< ĺ h

A >e”_çH+þA`¦ þj&ho —¸+þA`¦ :ŸxK"f ½¨½+É Ãº e”H &hs. :

Ÿ

x'ŸC&ñ ëH]j\¦ Û¦l 0A#Œ tèߖ 30#Œ¸çߖ #ŒQ —¸+þAs >hµ1Ï÷&“¦ µ1Ï

„

÷&#QM®o. sQôÇ —¸+þA`¦ ß¼> ¿º t–Ð ¾º€ —¸ŽH 5px̐os â–Ð_ q 6

x`¦ &ñSX‰y “tH &ñ\"f_ &ñ&h :Ÿx'ŸC&ñ —¸+þAõ ´ò6 xþj@/

o(utility maximization)s:r_síߖ‚×þ˜—¸+þA`¦ lìøÍܼ–Ð HSX‰Ò¦&h :Ÿx'Ÿ C

&ñ —¸+þAs. Õªo“¦ ¿º t :Ÿx'ŸC&ñ —¸+þA —¸¿º 5px̐os Ö¼zH â–Ð_

q

6 x <ʓÉr´ò6 x`¦ :Ÿx'Ÿrçߖõ °ú “Ér›'a8£¤0pxôÇq6 xכ¹™è\¦6 xôÇq6 x†<Êú

–

Ð ³ð‰&³ôÇ."f,‰&³z´&h“—¸+þA½¨»¡¤`¦0AK"fH 5px̐o[þts Ö¼zH q6 x

†

<

Êú ‰&³z´&hܼ–Ð —¸+þAo÷&#Q ôÇ. q

6 x†<Êú\¦ ‰&³z´&hܼ–Ð —¸+þAoH ~½ÓZO ×æ H :Ÿx'Ÿ[þt_ ‚ ñ

€ ª

œ$í(taste variations)`¦ ìøÍ%òHכ s.7£¤,1lx{9ôÇ ›¸|\"f•¸ Ér â–Ð

\

¦‚×þ˜H 5px̐o[þts”>rFHX< q6 x†<Êú_q6 xכ¹™è p'\¦„^‰5px Ì



o\ @/K_ °úכܼ–Ð 6 xH âĺ\HsQôÇ ‰&³z´`¦[O"î½+Éú\O.

Õ

ªo“¦ [O"î ÷rm \V8£¤s ×æכ¹ôÇ 6£x6 x\"fH \V8£¤§4 †¾Ó©œ`¦ 0A#Œ ‚  

ñ €ªœ$íìøÍ%ò`¦ ìøÍ%òH âĺ´ú§. {

9

ìøÍ&hܼ–Ð ‚ ñ €ªœ$í`¦ ìøÍ%òH ~½ÓZO“Ér ™D¥½+˖Ðf± —¸+þA(mixed logit model)õ °ú s q6 xכ¹™è_p'\¦SX‰Ò¦Ãº–Ð ˜ÐHכ s.Õªo“¦SX‰Ò¦



ú ØԍH SX‰Ò¦ìrŸí\¦ ‚+«>&hܼ–Ð &ñ“¦ SX‰Ò¦ìrŸí_ p'\¦ ÆÒ

&

ñ

#ŒM®o.tëߖ,þjH‚+«>&hܼ–Ð ìrŸí\¦ &ñH —¸Ãº&h ~½ÓZO“Ér &ñ ô

Ç SX‰Ò¦ìrŸí\ _ôÇ ¼#†¾Ó(bias)\¦ 4R`¦Ãº e”H ƒ½¨õ µ1ϳð÷&%3 [31]. "f, ‚+«>&hܼ–Ð ìrŸí\¦ &ñt ·ú§“¦ Êê&hܼ–Ð ìrŸí\¦ &ñ



H q—¸Ãº&h ìrŸí ÆÒ&ñ ~½ÓZO\ @/ôÇ ƒ½¨”'Ÿ÷&“¦e”.

‘ :

r ƒ½¨\"fH %iþj&ho lZO`¦ 6 x#Œ q—¸Ãº&hܼ–Ð 5px̐o ‚ ñ p

'_ ìrŸí\¦ ÆÒ&ñ“¦ ôÇ. %iþj&hoêøÍ {9ìøÍ&h“ þj&ho ëH]j —¸+þA _

p' ÅÒ#Q” ©œS!\"f þj&hK\¦½¨H ìø̀,%iþj&hoëH]jH ›'a 8

£

¤)a þj&hK\¦ :ŸxK —¸+þA_ p'\¦ ÆÒ&ñH כ `¦ 3lq&hܼ–Ð 9 &ñSX‰ ô

Ǘ¸+þA_p'\¦ 8£¤&ñt3lw½+ÉM: 6 xôÇ.#ŒQ t כ¹“sâ–Ђ

× þ

˜\ %ò†¾Ó`¦ ÅҍH âĺ &ñSX‰>5px̐o_ ‚ ñ €ªœ$í`¦ 8£¤&ñH כ “Ér ‰&³z´

&

h

ܼ–Ð Ô¦0px. tëߖ, “§:Ÿx W1àÔ0>ß¼\"fH ·ú¡"f [O"îôÇ@/–Ð 5px̐os

’s Ö¼zH þj™èq6 xܼ–Ð s1lxôǍH&ñ`¦ 6 x#Œ ›'a8£¤÷&H :Ÿx'Ÿ|¾Ó

`

¦ çH+þA:Ÿx'Ÿ|¾Ós“¦ ˜Ð“¦:Ÿx'ŸC&ñõçH+þA:Ÿx'Ÿ|¾Ós ÷&•¸2Ÿ¤H%iþj

&

h

o ëH]j\¦ &ñ_½+Éú e”. þ

jH GPS x9 “§:Ÿx×¼ X<s'ü< °ú s ›'a8£¤÷&H :Ÿx'Ÿ|¾Ó\ @/ôÇ &ñ˜Ð

´ ú

§t“¦ &ñSX‰K f”\ “§:Ÿx W1àÔ0>ß¼\"f %iþj&ho lZO`¦ 6 x½+É Ãº e

”

H 0px$ís7£x“¦e”.tëߖ,@/×擧:Ÿx :£¤y t^o=\ @/K"fHþj

Ht ‰&³F 5px̐o[þt_ s6 x“¦ e”H z´I\¦ &ñSX‰y ·ú˜ ú \O%3.7£¤,#QÖ¼

\

P\¦ “¦ ?/§4ܼ 9 ¨8Š5px%is #QŽt ·ú˜ ú \O. [16, 34]. "f, ‘:r ƒ

½

¨_ 'Í P: 3lq&h“Ér“§:Ÿx×¼ X<s'–Ð ÂÒ' z´]j t^o= â–Ђ×þ˜X<s'

\

¦ SX‰˜ÐH ~½ÓZO:r`¦ >hµ1ύH כ s.

¿

º P: 3lq&h“Ér z´]j t^o= â–Ђ×þ˜ X<s'–ÐÂÒ' 5px̐o_ s1lx'ŸI\¦ ì

r$3#Œ â–Ђ×þ˜\ %ò†¾Ó`¦ÅҍHq6 xכ¹™è\¦›'a¹1ϓ¦&h]XôÇ q6 x†<Êú_

+ þ

AI\¦ &ñH כ s. [

j P:3lq&h“Ér%iþj&holZO`¦lìøÍܼ–Ð H‚ ñ p'_½+ËSX‰ Ò

¦x9•¸†<Êú\¦q—¸Ãº&hܼ–Ð ÆÒ&ñH~½ÓZO:r`¦>hµ1ύHכ s.tFKt

% i

þj&ho–Ð >hZ>p'_ °úכ`¦ÆÒ&ñHƒ½¨He”%3tëߖp'_ìr

Ÿ

í\¦ ÆÒ&ñH ƒ½¨H \O%3.

t}Œ•Ü¼–Ð ÆÒ&ñ)a ½+ËSX‰Ò¦x9•¸ †<Êú\¦ 6 x#Œ SX‰Ò¦&h çH+þA`¦ &ñ_

“¦ Õª ”>rF$í`¦ 7£x"îôÇ. ¢¸ôÇ,çH+þA`¦ >íߖ#Œ Õª õ\¦ z´]j @/½©—¸ t

^o=W1àÔ0>ß¼\"fŽ7£xôÇ.@/ÂÒìr_ƒ½¨\"f5px̐o_€ªœ$í`¦ìøÍ%òôÇ

—

¸+þA_Ž7£x“Ér :Ÿx>&hŽ7£x\²DGôÇ÷&#QM®oܼ 9 —¸+þA_Ž7£x`¦"fÖ¦t^o=õ

° ú

 s /BNçߖ&h,rçߖ&h #30AHâĺ\H &h6 x)a YV\¦ ¹1ԘÐl #Q9îrz´

&

ñ s.

‘ :

r 7HëH_ 3lq&h`¦&ño€ 6£§õ °ú .

• Û¼àÔ ×¼ X<s'–Ð ÂÒ' z´]j t^o= â–Ђ×þ˜X<s' SX‰˜Ð

• z´]j t^o= â–Ђ×þ˜ X<s'–Ð ÂÒ' t^o= 5px̐os1lx 'ŸIìr$3

• %iþj&ho–Ð ‚ ñ p'_ ìrŸí ÆÒ&ñ

• çH+þA`¦ >íߖ“¦z´]j @/½©—¸ W1àÔ0>ß¼\"f Ž7£x

1.2 ¥o>Ä© ƒ7€D ™ Ðaµ%K Ä©Å]

 7

HëH“Ér 8úx7>h_ ©œÜ¼–Ð ½¨$í)a. 2©œ\"fH þj&ho —¸+þA`¦ 6 xôÇ &ñ&h

6 xçH+þAõq6 x†<Êú\SX‰Ò¦&h“tš¸ \¦ìøÍ%òôÇSX‰Ò¦&h6 xçH+þA`¦

¶ ú

˜(R‘:r.Õªo“¦ 5px̐o ‚ ñ_ €ªœ$í`¦ “¦9ôÇ l”>rƒ½¨[þt`¦ ™è>h“¦ Õª ô

Ç>\¦ lÕütôÇ.

3©œ\"fH “§:Ÿx ×¼ X<s'\¦ s6 x#Œ t^o= ?/ 5px̐os z´]j s6 xôÇ

â

–Ðx9 \P\¦ÆÒ&hH~½ÓZO:r`¦[O"îôÇ.›'a¹1ϝ)a5px̐o_‰&³r«Ñ(revealed preference)\"f â–Ђ×þ˜\ %ò†¾Ó`¦ ÅҍH q6 xכ¹™è\¦ ›'a¹1ϓ¦ &h]XôÇ q6 x

†

<

Êú_ +þAI\¦ ]jrôÇ.

4©œ\"fH 5px̐o_ €ªœôÇ ‚ ñ\¦ìøÍ%òl 0A#Œ q6 xכ¹™è[þt_p '

\¦ SX‰Ò¦Ãº–Б:r.Õªo“¦ s\ @/ôÇ ½+ËSX‰Ò¦x9•¸†<Êú ÅÒ#Q&’`¦M:, D

h–Ðîr P-:Ÿx'ŸC&ñ ~½ÓZO:r`¦ ]jrôÇ.¢¸ôÇ, P-:Ÿx'ŸC&ñ\"f_ SX‰Ò¦&h çH +

þ

A`¦ &ñ_“¦ Õª ”>rF$í`¦ 7£x"îôÇ.

5©œ\"fH %iþj&ho\ @/ôÇ [O"îõ †<Êa 4©œ\"f ]jrôÇ P-:Ÿx'ŸC&ñ`¦

l0AôÇ ½+ËSX‰Ò¦x9•¸†<Êú\¦ %iþj&ho lZO`¦ 6 x#Œ ÆÒ&ñH ~½ÓZO:r

`

¦ [O"îôÇ.

6©œ\"fH 4©œ x9 5©œ\"f ]jrôÇ ~½ÓZO:r`¦ z´]j "fÖ¦ t^o= W1àÔ0>ß¼

\

 z´+«>ìr$3ôÇ.—¸+þA_ [O"î§4`¦ z´]j â–Ђ×þ˜ õü< Ž7£x9 ™D¥½+˖Рf

±—¸+þAõ °ú s5px̐o ‚ ñ\¦ìøÍ%òHl”>r—¸+þAõ_$í0px`¦ q“§ôÇ.t }

Œ

•Ü¼–Ð 7©œ\"fH ƒ½¨õ\¦ כ¹€•“¦ ÆÒÊꃽ¨\¦ ™è>hôÇ.

› '

aº l”>rƒ½¨_ “¦¹1Ï(2©œ)

z

´]j t^o= â–Ђ×þ˜ „ÃÐҐo x9 :Ÿx'Ÿìr$3 (3©œ)

P-:Ÿx'ŸC&ñ —¸+þA >hµ1Ï(4©œ)

% i

þj&ho\¦ :ŸxôÇ 5px̐o‚ ñ p' ìrŸíÆÒ&ñ (5©œ)

t

^o= W1àÔ0>ß¼\"f Ž7£xz´+«> (6©œ)

כ

¹€• x9 ÆÒÊꃽ¨ (7©œ)

?

?

?

?

?

Õ

ªaË> 1.1: 7HëH ½¨$í âì2£§•¸

2. e × i µ¥ o >Ä ©

2.1 ÚrÇa†\ £ !CÌfC

2.1©œ\"fH —¸ŽH 5px̐os â–Ð_ q6 x`¦ &ñSX‰y “tH &ñ\"f þj

&

h

o —¸+þA`¦ 6 xôÇ &ñ&h 6 xçH+þA\ @/K"f ™è>hôÇ. 2.1.1 kâ«`gi¦†\˜¿ÌfC

c^∗_e\¦ ‰&³FaAß¼e_ ôÇ>q6 x,7£¤c^∗_e(f_e)≡(f_e·c_e(f_e))⁰ܼ–Ð ³ðl.Õªo“¦ c^∗_P(f) :=P

e∈Pc^∗_e(f_e).

Å ]

™ 2.1.1 ƒ5Åq ĺhA>e”(G, r, c)\"f, —¸ŽH  ñe\"f x·c_e(x)^¦2Ÿ¤†<Ê Ã

º“¦ . ÕªQ€, f^∗ (G, r, c)_ rÛ¼%7› þj&hK |¨c €9כ¹Øæìr›¸|“Ér

—

¸ŽH i= 1, . . ., k\ @/K,

∀P, Q∈ P_i :f_P >0⇒c^∗_P(f^∗)6c^∗_Q(f^∗). (2.1)

¤

ÃZ 6£§_ þj&hoëH]j\¦ÒqtyŒ•: min{X

P

c_P(f)f_P : X

P∈Pi

f_P =d_i, f_P >0} (2.2)

Õª|½Ótîߖ“Ér 6£§õ °ú . L(f, λ, ρ, µ) = P

P∈Pc_P(f)f_P +P

iλ_i¡P

P∈Pif_P −d_i¢

−P

P∈Pµ_Pf_P

(2.3)

^

¦2Ÿ¤$í\_Kf þj™èq6 xâì2£§{9€9כ¹Øæìr›¸|“Ér6£§`¦ëߖ7ᤍHλ,µ>

0 ”>rFH כ s.

c^∗_P(f) =λ_i+µ_P, P ∈ P_i, i= 1, . . . , k,

µ_P ·f_P = 0, P ∈ P_i. (2.4)

"f f^∗ rÛ¼%7› þj&hK{9 M:, f_P^∗ >0s€ µ_P = 0sÙ¼–Ð,—¸ŽH i\ @/K

›

¸| (2.1)s $íwnôÇ.

% i

ܼ–Ð(2.1)s$íwnHâĺ,λ_i←min_P∈Pic^∗_P(f^∗),µ_P ←c^∗_P(f^∗)−λ_i–Ð Z

~ܼ€ (2.39) $íwnôÇ.7£¤,f^∗ rÛ¼%7› þj&hK)a.

Ÿ¸Çah 2.1.2 f^∗(G, d, c)_þj™èq6 xâì2£§{9€9כ¹Øæìr›¸|“Ér(G, d, c^∗)_

ç

H+þAâì2£§s ÷&H כ s. 2.1.2 3AÞ«Ÿ¹!CÌfC Ç

a

˜+ 2.1.3 (3AÞ«Ÿ¹ !CÌfC[56],Wardrop equilibrium) f\¦ ƒ5Åq ĺhA>

e

”

(G, d, c)_0pxK“¦ .ëߖ{9f 6£§õ °ú “Ér›¸|`¦ëߖ7ᤀ 0>×¼

\

v çH+þAs“¦ôÇ:—¸ŽH i= 1,. . .,k\ @/K,e”__P,Q∈ P_i\ @/K,ëߖ

€



• f_P >0s€6£§ ›'a>$íwnôÇ.

c_P(f)6c_Q(f). (2.5)

0

>×¼\vçH+þA“Ér?//'çH+þA_H&h ƒ5Åq—¸+þAsHכ `¦˜Ð{9úe”:éߖ 0

Aâì2£§`¦ °úH >hZ>5px̐o[þts (G, d, c)–Ð {9§4s ÅÒ#QtH W1àÔ0>ß¼\"f Ä

ºhA>e”`¦ ½+É M: µ1ÏÒqtH ?//'çH+þA“Ér 5px̐o_ ú´ú§t€ 0>×¼\v çH+þA s

)a.

2.1.3 Beckmann˜¿ÌfC

2£§&ño 2.1.2\ _#Œ  ñq6 xs h(x) =xc_e(x)ܼ–Ð ÅÒ#QtHƒ5ÅqĺhA

>

e” (G, d, c)_ þj™èq6 xâì2£§õ éߖ0Aq6 xs h⁰(x)–Ð ÅÒ#QtH ƒ5Åq ĺhA

>

e”_ çH+þAâì2£§s 1lx{9†<Ê`¦ _pôÇ.Õªo“¦ s 7£x"î“Ér  ñq6 x h(x) ^¦ 2

Ÿ

¤†<Êú“ âĺ,+þAIü< Áº›'a.

"f, (G, d, c)_ çH+þAâì2£§“Ér h(f_e) = R_fe

0 c_e(x)dx\¦  ñq6 xܼ–Ð °úH (Õªo“¦ Qt {9§4“Ér °ú “Ér) ƒ5ÅqĺhA —¸+þA_ rÛ¼%7› þj&hKe”`¦ ·ú˜ ú e

” .

Ÿ¸Çah 2.1.4 f^∗(G, r, c)_ çH+þAâì2£§{9€9כ¹Øæìr›¸|“Érf^∗  ñq6 xs

6£§õ °ú “Ér ƒ5Åq ĺhA >e”_ þj™èq6 xâì2£§s ÷&H כ s. h_e(f_e) =

Z _fe

0

c_e(x)dx. (2.6)

Beckmann et al. [10]

min{Φ(f) =X

e∈E

Z _fe

0

c_e(x)dx: X

P∈Pi

f_P =d_i, f_P >0}, (2.7)

#

Œl"f,

Φ(f) :=X

e∈E

Z _fe

0

c_e(x)dx. (2.8)

2.1.4 !CÌfCø kâ«`g i¦†\B U

d 2.1.5 Pigou [48]˜+ Ud s-t :Ÿx'ŸÃºכ¹1“ Aü< °ú “Ér ĺhA>e”`¦ Ò

q

tyŒ•K˜Ð.âì2£§€ªœs x{9 M:, yŒ•  ñ_ éߖ0Aq6 x“Ér c₁(x) = 1õ c₂(x) = x–Ð Å

Ò#Q”.

Õ

ªaË> 2.1: Pigou_ \V

—

¸ŽHâì2£§\ @/#Œ,c₂(x)6c₁(x)sÙ¼–Ð,—¸ŽH 5px̐o“Ére₂\¦ :ŸxK >hZ>&h

ĺhA`¦ z´‰&³ôÇ.7£¤,çH+þAâì2£§“Ér f^∗= (0,1)s )a.

ô

Ǽ#, ñe₁_âì2£§`¦f₁s“¦ €,q6 x_ ½+˓Érf₁·1+(1−f₁)·(1−f₁) = f₁²−f₁+ 1, "f rÛ¼%7› þj&hKH f_{OP T} = (1/2,1/2) )a.sM:, q6 x

“ É

r 3/4s )a. Ç

a

˜+ 2.1.6 Price of anarchy= çH+þAâì2£§ ×æ\"f þj@/q6 x r

Û¼%7› þj&hâì2£§_ q6 x = (x½¨_\V, 4/3).

Price of anarchyH q6 x†<Êú_ :£¤$í\ _”>rôÇ. \V\¦ [þt#Q, q6 x†<Êú c_e q6£§>ú\¦ ” ú p s“ †½Ód”“ âĺ, Price of anarchyH p+ 1ss[18].

U

d 2.1.7 Braess Paradox [15]˜+ Ud

Õ

ªaË>2.2: Braess Paradox_ \V

œ

íl W1àÔ0>ß¼_ 0>×¼\v çH+þA“Érâ–ÐP,Q\ yŒ•yŒ•1/2`¦˜Ð?/ 98úx µ1ÏÒqt q

6 x“Ér3/2 )a.#Œl\v→w\ éߖ0Aq6 xs0“aAß¼\¦ÆÒK ˜Ð.Dh

–

Ðîr â–Ð R“Ér†½Ó©œP,Q˜Ðéߖ0Aq6 xs°ú Œ•l M:ëH\,çH+þA\"f —¸

Ž

H âì2£§`¦ °úH.ÕªQ éߖ0A q6 x“Ér 2 ÷&#Q, 8úx µ1ÏÒqt q6 xs œíl W1àÔ 0

>ß¼ ˜Ð8 &”. U

d 2.1.8 Braess Paradox˜+ ™V Ud- Boston’s Big Dig

• http://blogs.cornell.edu/info2040/2011/09/25/real-life-example-of-braesss- paradox-bostons-big-dig/

Õ

ªaË> 2.3: Boston Big Dig

- A : South Boston→ Broadway subway(c_a=x) - B : Broadway subway → Government center(c_b = 1) - C : South Boston → Enter CBD(c_c= 1)

- D : Enter CBD →Government center(c_d=x) - E : Express highway ”Big Dig”(c_e= 0)

U

d 2.1.9 Braess Paradox˜+ ™V Ud [58]

U

d 2.1.10 Braess Paradox˜+ ÒR Ud- ÍÙ ÿbæ« kâ«`g i¦†\BÐM 5

¤ n

>komï5Ñ !CÌfC j£ ÖR ¤ koÐM UdV.

œ

íl W1àÔ0>ß¼_ çH+þAâì2£§“Érf_P = 0.5,f_Q= 0.5→c_P(f) = 1.5,c_Q(f) = 1.5, C(f) = 1.5. þj™èq6 xâì2£§“Ér f_P = 3/8, f_Q = 5/8 → c_P(f) = 9/8, c_Q(f) = 13/8,C(f) = 1.4375ú&ñ)a W1àÔ0>ß¼\"f_ çH+þAâì2£§“Ér f_P = 1/3, f_Q = 0, f_R= 2/3 → c_P(f) = 5/3,c_Q(f) = 5/3, c_R(f) = 5/3, C(f) = 1.666.

Õ

ªaË> 2.4: New Braess Paradox þ

j™èq6 xâì2£§“Ér f_P = 4/14, f_Q = 5/14, f_R = 5/14 → c_P(f) = 17/14, c_Q(f) = 24/14,c_R(f) = 19/14, C(f) = 1.393

2.1.5 £o>žâ Éٞ ÐÏ



1lxÂÒ1pxd”(variational inequality; VI) ëH]jH —¸ŽH 0pxâì2£§ x\ @/#Œ (2.9)`¦ëߖ7ᤍHf<sup>∗</sup>\¦¹1ԍH ëH]js.1lxÂÒ1pxd”“Ér€ªœôÇìr\"fçH+þA`¦

½

¨H ëH]jü<x9]XôǛ'a>\¦t“¦e”."f,1lxÂÒ1pxd”õ“§:Ÿx W1àÔ 0

>ß¼\"fçH+þAs_›'a>ü<s\¦½¨l0AôÇ´ú§“Érƒ½¨[þt[53, 20, 21, 42]s

”

'Ÿ÷&%3.

c(f^∗)^T(f^∗−x)60 (2.9)

Å ]

™ 2.1.11 1lxÂÒ1pxd”`¦ ëߖ7ᤍH f^∗H 0>×¼\v çH+þAõ 1lxus.[53]

¤

ÃZ €$,0>×¼\v çH+þA`¦ ëߖ7ᤍH fH O-D s_ þj™èq6 xâ–Ð\ëߖ âì 2

£

§s µ1ÏÒqtÙ¼–Ð Ér0pxâì2£§x–Ð_âì2£§â“Ér 8úxq6 x`¦yŒ™™èr~´ ú\O

."f,c(f)^Tf 6c(f)^Tx›'a>$íwn÷&“¦ sH 1lxÂÒ1pxd”ëH]j_f^∗ ë

ß

–7á¤K½+É ›¸|õ {9uôÇ. ìøÍ@/–Ð, 0>×¼\v çH+þA`¦ ëߖ7á¤t ·ú§H âì2£§

f_P > 0, c_P(f) > c_Q(f), P, Q ∈ P_i f_P\"f f_Q–Ð âì2£§`¦ ›¸7áxôÇ 0pxâì2£§ xH 8úxq6 xs yŒ™™è)a. "f, c(f)<sup>T</sup>f −c(f)<sup>T</sup>x > 0s÷&#Q 1lxÂÒ1pxd”`¦ ë

ß

–7á¤t 3lwôÇ.

¢

¸ôÇ, 1lxÂÒ1pxd” ëH]jH c(f)_ Jacobian matrix symmetric“¦ pos- itive semidefinite(definite) matrixs€ R

c(f)\¦ 3lq&h†<Êú–ЍH Beckmann

—

¸+þA(2.7)õ 1lx1pxK”. Å

]

™ 2.1.12 R

c(f) ƒ5Åqs“¦ pìr0px½+É M:, Beckmann —¸+þA (2.7)_ þj

&

h

K f^∗H 1lxÂÒ1pxd” (2.9)_ K)a.

¤

ÃZ t\ @/ôÇ 6£§õ °ú “Ér †<Êú\¦ &ñ_.φ(t) =R

c(f^∗+t(f−f^∗)), t∈ [0,1]Hφ(0)\"f þj™è°úכ`¦ tÙ¼–Ð φ<sup>0</sup>(0) =c(f<sup>∗</sup>)<sup>T</sup>(f−f<sup>∗</sup>)>0`¦ ëߖ7á¤Ù¼

–

Ð f^∗H 1lxÂÒ1pxd”_ K)a. Å

]

™ 2.1.13 R

c(f)^¦2Ÿ¤†<Êús“¦f^∗1lxÂÒ1pxd”(2.9)`¦ëߖ7ᤀf^∗H Beckmann —¸+þA (2.7)_ þj&hK )a.

¤ ÃZ R

c(f)^¦2Ÿ¤†<ÊúsÙ¼–Ð —¸ŽH0pxâì2£§f\ @/K"fR

c(f)>R

c(f^∗) + c(f)^T(f −f^∗) )a. c(f)^T(f −f^∗) >0sÙ¼–Ð —¸ŽH 0pxâì2£§ f\ @/K"f R c(f)>R

c(f^∗) ÷&Ù¼–Ð f^∗H(2.7) þj&ho ëH]j_ þj&hKs.

t}Œ•Ü¼–Ё1lxÂÒ1pxd”ëH]jH ^¦2Ÿ¤þj&hoëH]j\"f‰&³FKx\¯"f− 5 f(¯x)^Ty > 0\¦ ëߖ7ᤍH >h‚~½Ó†¾Ó y ”>rF€ 3lq&h†<Êú f`¦ yŒ™™è r~´Ãº e

”

H >h‚~½Ó†¾Ó&ñoü<•¸ {9uôÇ. 7£¤, çH+þA\"fH K\¦ 8s©œ >h‚r~´ Ã

º \O.

c(f)(f −x)60,∀x∈F ⇔ − µZ _f

0

c(f)df

¶_T

(x−f)60 2.1.6 j¤n>ÌfC (‘×™×%KV

q

‚+þA©œ˜ÐëH]j(nonlinear complementarity problem; NCP)ëH]jH(2.10)`¦ ë

ß

–7ᤍH f^∗\¦ ¹1ԍH ëH]js [30]. 1lxÂÒ1pxd”õ ðøÍt–Ð q‚+þA ©œ˜Ð ë

H]j•¸ “§:Ÿx W1àÔ0>ß¼\"fçH+þA`¦ ½¨½+ÉM: 6 x)a.











c(f^∗)^Tf^∗ = 0 c(f^∗) >0 f^∗ >0

(2.10)

Å ]

™ 2.1.14 q‚+þA ©œ˜ÐëH]j_ f^∗H 1lxÂÒ1pxd”`¦ ëߖ7ᤍH f^∗ü< 1lxus

.

€

$ f^∗ (2.10)`¦ ëߖ7á¤ôǓ¦ € e”__ âì2£§ x > 0H c(f^∗)^Tx > 0

 )

a. "f, c(f^∗)^Tx−c(f^∗)^Tf^∗ > 0sÙ¼–Ð c(f^∗)^T(f^∗ −x) 60 $íwnôÇ

. ìøÍ@/–Ð 1lxÂÒ1pxd” c(f^∗)^T(f^∗−x) 6 0`¦ ëߖ7ᤍH f^∗H 0pxâì2£§sÙ¼

–

Ð f^∗ > 0, c(f^∗) >0\¦ ëߖ7á¤ôÇ. 0 > c(f^∗)^Tf^∗ > c(f^∗)^Txs“¦ x = 0s€ c(f^∗)^Tf^∗ = 0s)a.

Ÿ¸Çah 2.1.15 (2.11)þj&hoëH]j_þj&h3lq&h†<Êú°úכs 0“ f^∗H1lxÂÒ 1

p

xd”`¦ ëߖ7á¤ôÇ.

minc(f)^Tf c(f)>0,

f >0

(2.11)

2.1.7 ”§Ça†\ Çah

“

¦&ñ&h &ño(fixed-point theorem)“Ér “§:ŸxW1àÔ0>ß¼\"f çH+þAK_ ”>rF$í`¦

˜

ÐsHX< 6 x÷&H&ños.“¦&ñ&h &ñoHBrouwer“¦&ñ&h&ño, Kakutani

“

¦&ñ&h&ño, Lefschetz“¦&ñ&h&ño1px €ªœôÇ +þAIe”. e

ÔeµÇah 2.1.16 Brouwer˜+ ”§Ça†\Çah T Ä»9þtonîߖ /BNçߖ(Euclidean space)_ F\"f F–Ð_ ƒ5Åq†<Êús€ &h#Q•¸ _ “¦&ñ&h 7£¤ T(f) =f\¦ ë

ß

–7ᤍH âì2£§ f ∈F ”>rFôÇ.

“

¦&ñ&h &ñoH ÈÒ%ò¨8Š(projection operator)`¦ :ŸxK1lxÂÒ1pxd”õ ›'a>

\

¦ ”.

e

ÔeµÇah 2.1.17 F Rⁿ\"f {Œ—˜2³ ^¦2Ÿ¤|9½+Ë(closed convex set){9 M:, x ∈ Rⁿ\ @/K"f (2.12)\¦ ëߖ7ᤍH Ä»{9ôÇ y∈F ”>rFôÇ.

kx−yk6kx−zk,∀z∈F (2.12)

yHx\¦F–Ðf”“§ÈÒ%ò(orthogonal projection)ôÇ כsÙ¼–Ð (2.13)ܼ–Ð ³ð

‰

&

³)a.

y=P_Fx= arg min

z∈Fkx−zk (2.13)

Å ]

™ 2.1.18 FRⁿ\"f{Œ—˜2³^¦2Ÿ¤|9½+Ë(closed convex set){9M:,y=P_FfH y^T ·(z−y)>x^T ·(z−y),∀z∈Fü< 1lxus.

Å ]

™ 2.1.19 F Rⁿ\"f {Œ—˜2³ ^¦2Ÿ¤|9½+Ë(closed convex set){9 M:, f^∗∈F



1lxÂÒ1pxd”(2.9)\¦ ëߖ7ᤍHכ “Ér γ >0“ f^∗ =T(f^∗) =P_F(f^∗−γc(f^∗))\¦ ë

ß

–7ᤍH “¦&ñ&hs ÷&H כ õ 1lxus.

¤

ÃZ f^∗∈F 1lxÂÒ1pxd” c(f^∗)^T(x−f^∗)>0`¦ ëߖ7᤽+É M:,−γ\¦ YL“¦€ªœ A

á

¤\f^∗T·(x−f^∗)\¦8€f^∗T·(x−f^∗)>(f^∗−γc(f^∗))^T·(x−f^∗)s ÷&“¦$í|9 2.1.18\ @/K"fy =f^∗,x=f^∗−γc(f^∗)–Ð €y^T·(x−f^∗)>x^T·(x−f^∗)\¦ ë

ß

–7á¤Ù¼–Ð f^∗ = P_F(f^∗ −γc(f^∗))s. ìøÍ@/–Ð f^∗ = P_F(f^∗ −γc(f^∗))s€ f^∗T ·(x−f^∗)>(f^∗−γc(f^∗))^T ·(x−f^∗)sÙ¼–Ðc(f^∗)^T(x−f^∗)>0s. Å

]

™ 2.1.20 T(f^∗) = P_F(f^∗−γc(f^∗))\¦ ëߖ7ᤍH T†<Êú F\"f F–Ð_

ƒ

5Åq†<ÊúsÙ¼–Ð Brouwer_ “¦&ñ&h&ño\ _K &h#Q•¸ _ “¦&ñ&h 7£¤ T(f^∗) =f^∗\¦ ëߖ7ᤍH çH+þAâì2£§ f^∗∈F ”>rFôÇ.

¤

ÃZ f”“§ÈÒ%ò P_Fü< f − γc(f)s yŒ•yŒ• ƒ5Åq†<ÊúsÙ¼–Ð T(f) = P_F(f − γc(f))•¸ ƒ5Åq†<Êús. T(f) ƒ5Åq†<ÊúsÙ¼–Ð Brouwer_ “¦&ñ&h&ño\ _

K &h#Q•¸ _“¦&ñ&hs ”>rFôÇ.

2.1.8 Frank-Wolfe N±Ó”§hžæ¸

(2.7) þj&ho ëH]j\¦ ÉҍH @/³ð&h“ ·ú˜“¦o1puܼ–ЍH Frank-Wolfe ·ú˜“¦o1pu [28]s e”. Frank-Wolfe ·ú˜“¦o1pu“Ér ‘:rA 2 >S\‰ZO(quadratic program- ming)`¦ ÉҍH ·ú˜“¦o1puܼ–Ð ]jr÷&%3. Frank-Wolfe·ú˜“¦o1pu“Ér 3lq&h†<Êú f(x){9M:, ìøÍ4Ÿ¤éߖ> k 3lq&h†<Êú\¦ f(x^k) +5f(x^k)^T(x−x^k)–Ð ‚+þA

H(linear approximation)#Œ (2.14)_ ‚+þA>S\‰ëH]j_ þj&hK y^k+1\¦ ½¨

“¦ x^kü< y^k+1_ ^¦2Ÿ¤›¸½+Ë ×æ 3lq&h†<Êúf(x) þj™è÷&H x^k+1`¦ ¹1Ô ìøÍ4Ÿ¤

&

h

ܼ–Ð K\¦ ¹1ԍH ~½ÓZOs.

minx∈Kf(x^k) +5f(x^k)^T(x−x^k) (2.14) N

±

Ӕ§hžæ¸ 2.1.21 Frank-Wolfe ·ú˜“¦o1pu`¦ (2.7)\ &h6 x€ 6£§õ °ú . Step 0. œílo : n= 0, f_eⁿ=f_e⁰= 0, e∈E, ² >0.

Step 1. aAß¼_ q6 x °úכ >íߖ :cⁿ_e =c_e(f_eⁿ), e∈E.

Step 2. 3lq&h†<Êú\¦ ‚+þAH#Œ ‰&³F âì2£§ fⁿ\"f_ ‚+þA>S\‰ëH]j (2.15)\¦ Û¦#Q þj&h 0pxâì2£§ yⁿ\¦ ½¨ôÇ.

s

M:, þj&h 0pxâì2£§ yⁿH (2.15)  ñ_ q6 xs âì2£§ fⁿ\"f “¦&ñ÷&%3 6

£

§Ü¼–Ð yŒ• O-DŠ©œ_ þjéߖâ–ЖРC&ñH כ õ °ú .

min P

ec_e(f_eⁿ)y_eⁿ

s.t P

P∈Piy_P =d_i, ∀i∈I y_P >0, P ∈ P

(2.15)

Step 3. (2.16)_þj&hs1lxß¼lλⁿ\¦&ñôÇ.{9ìøÍ&hܼ–Ђ„ÃÐҐo(line search)`¦ 6 xôÇ.

λⁿmin∈[0,1]

X

e

Z _fn

e+λⁿ(yeⁿ−feⁿ) 0

c_e(w)dw (2.16)

Step 4 : :Ÿx'|Ÿ¾Ó`¦ Ìqt’ôÇ.

f_eⁿ⁺¹=f_eⁿ+λⁿ(y_eⁿ−f_eⁿ), e∈E.

Step 5. 7áx«Ñ›¸| : - ëߖ€•,

P

e∈EP|feⁿ⁺¹−f_eⁿ|

e∈Efeⁿ 6² s€,·ú˜“¦o1pu 7áx«Ñ,‰&³F K\¦ ئ§4; - u´ âĺ, n←n+ 1, Step 1 ܼ–Ð s1lx;

2.2 †„È·†\ £ !CÌfC 2.2.1 †„È·†\ § šßj:Ça˜¿ÌfC

2.1©œ\"f êr :Ÿx'ŸC&ñ —¸+þA“Ér q6 x†<Êú &ñ&h“ —¸+þAs. tëߖ,

‰

&

³z´\"fH þjéߖâ–Ð  â–Ð\¦ s6 xH 5px̐o[þts ›'a¹1Ï÷&HX< sH (2.5)_ 0>×¼\v çH+þA\ 0AC)a.s\¦ [O"îl 0A#Œ “§:Ÿx/BN†<Æ\"fH z´ ]

j :Ÿx'Ÿq6 xõ :Ÿx'Ÿ “tH :Ÿx'Ÿq6 x çߖ_ š¸ µ1ÏÒqt½+É Ãº e”“¦

&ñH SX‰Ò¦&h:Ÿx'ŸC&ñ—¸+þA`¦]jr%i.l‘:r&hܼ–ÐSX‰Ò¦&h :Ÿx'ŸC&ñ

“ É

r 5px̐o[þt_ â–Ђ×þ˜`¦ ‚×þ˜ 0pxôÇ â–Ð ×æ \¦ ‚×þ˜H síߖ‚×þ˜—¸ +

þ

A(discrete choice)ܼ–Ð ÒqtyŒ•ôÇ. S

X

‰Ò¦&h :Ÿx'ŸC&ñ\"f 6 xH â–Ђ×þ˜ q6 x†<ÊúH SX‰&ñ&h q6 xõ SX‰ Ò

¦&h q6 x`¦ ½+Ë#Œâ–Ð_q6 x`¦&ñHX<,Õª l‘:r+þAIH6£§õ °ú 

.

C_P =c_P +²_P, ∀P ∈ P. (2.17)

c_P“Ér â–Ð P_ &ñ&hq6 x`¦,²<sub>P</sub>“Ér “tš¸ q6 x`¦ _pôÇ.C_P\¦ â

–

Ð P_ “tq6 x(perceived cost)s ôÇ. (2.17)\"f “tš¸ †½Ó_ l@/

° ú

כ, E[²_P]`¦ 0s &ñ€,â–Ðq6 x_ l@/°úכ“Ér E[C_P] =c_P, ∀P ∈ Pܼ

–

Ð jþt ú e”.

â

–Ðq6 x_ SX‰Ò¦ìrŸí ÅÒ#Qt€, —¸|9éߖ\"f ½™ ü> ‚&ñôÇ 5px̐os

‚

×þ˜ôÇ â–Ð\ @/ôÇSX‰Ò¦°úכ`¦>íߖ½+Éúe”.â–ÐP\¦‚×þ˜½+ÉSX‰Ò¦`¦P_P

€,Õª °úכ“Ér â–Ðq6 x C_P_ °úכs Ér @/îߖ â–Ð_ â–Ðq6 x˜Ð °ú 



Œ

•`¦ SX‰Ò¦s.

P_P =P[C_P 6C_Q, Q∈ P, Q6=P], ∀P ∈ P.

Å ]

™ 2.2.1 0pxâì2£§ f\"f â–Ð P_ ‚×þ˜SX‰Ò¦ P_P(f)H 6£§`¦ ëߖ7á¤ôÇ [51].

P_P(f) = ∂E(C(f))

∂c_P(f) (2.18)

¤

ÃZ ²[þt_|9½+Ë A_P\¦ 6£§õ °ú s&ñ_“¦ c_P(f) +²_P < c_Q(f) +²_Q;∀Q6=

P;A_P_ the indicator functionI_P(²₁, . . . ²_N)\¦ 6£§õ °ú s &ñ_

I_P(²₁, . . . ²_N) =





1 (²₁, . . . ²_N)∈A_P 0 (²₁, . . . ²_N)∈/ A_P e

”

__ ئµ1Ï-•¸‚ÃÌ n Š©œ i_â–Ðj = 1, . . . , Nt e”€,C_j(f) = c_j(f) + ²_js“¦ (²₁, . . . ²_N)“Ér SX‰Ò¦Ãº 7˜' )a. sM:, ½+ËSX‰Ò¦x9•¸†<Ê Ã

º(joint density function)\¦ g(²₁, . . . ²_N)“¦ € ‚×þ˜ â–Ð_ “tq6 x C(f) = min

j C_j(f)_ l@/“tq6 x“Ér (2.19)s)a. E(C(f)) =

Z

· · · Z

minj (c_j(f) +²_j)g(²₁, . . . ²_N)d²₁. . . d²_N (2.19) c_P\ @/ôÇ l@/ôÇ>“tq6 x(marginal expected perceived cost)

∂min

j (c_j(f) +²_j)

∂c_P(f) =I_P(²₁, . . . ²_N) (2.20)

∂E(C(f))

∂cP(f) =R

· · ·R ^∂min_j ^(cj(f)+²j)

∂cP(f) g(²₁, . . . ²_N)d²₁. . . d²_N

=R

· · ·R

I_p(²₁, . . . ²_N)g(²₁, . . . ²_N)d²₁. . . d²_N

=P((²₁, . . . ²_N)∈A_P)

=P_P(f)

“

tš¸ †½Ó ²_P_ SX‰Ò¦ìrŸí ÅÒ#Qt€ â–Ðq6 x_ SX‰Ò¦ìrŸí\¦ &ñ½+É Ã

º e”.@/³ð&h“ \V–Ð †½Ó–Ðf± —¸+þA(multimonial logit model)õ †½ÓáԖРc

±

—¸+þA(multinomial probit model)se”HX<,€$ †½Ó–Ðf± —¸+þA“Ér“tš¸

†

½

Ó_SX‰Ò¦ìrŸí1lqwn&hs9(independently and identically distributed;IID), 1

l

x{9> Ž^¦(gumbel)ìrŸí\¦ sÀғ¦ e”“¦ &ñôÇ. †½ÓáԖÐc± —¸+þA“Ér

“

tš¸ †½Ó_ ½+ËSX‰Ò¦ìrŸí |¾Ó &ñ½©ìrŸí\¦sÀғ¦ e”“¦ &ñôÇ. 2.2.2 /‘×—×=˜¿ÌfC

†½Ó–Ðf± —¸+þA“Ér “tš¸ †½Ó_ SX‰Ò¦ìrŸí1lqwn&hs9,1lx{9>Ž^¦ ìrŸí

\

¦ sÀғ¦ e”“¦ &ñôÇ. †½Ó–Ðf± —¸+þA“Ér â–Ð_ ‚×þ˜ SX‰Ò¦s `‚+þAd”ܼ

–

Ð q“§&hçߖéߖ> >íߖ÷&#Q V,o&h6 x÷&HSX‰Ò¦&h :Ÿx'ŸC&ñ—¸+þAs. Å

]

™ 2.2.2 †½Ó–Ðf± —¸+þA\"f 5px̐os â–Ð P\¦ ‚×þ˜½+ÉSX‰Ò¦“Ér (2.21)°ú . P_P = e^−θcP

P|P|

i=1

e^−θci

, ∀P ∈ P. (2.21)

¤

ÃZ â–Ð_ q6 xs &t€ ´ò6 x(utility)H Œ•tÙ¼–Ð â–Ð_ q6 x\ 6£§Ãº

−θ\¦ YL#Œ â–ÐP_ SX‰Ò¦&h´ò6 x U_P =−θc_P +²_P\¦&ñ_.çߖéߖ>

θ= 1–Ð &ñ.€$,5px̐os ´ò6 xs Ér â–ИРZ}“Ér â–Ð P\¦ ‚×þ˜

½ +

É SX‰Ò¦“Ér(2.22)õ °ú .

P_P =P rob(U_P > U_Q,∀Q6=P)

=P rob(−c_P +²_P >−c_Q+²_Q,∀Q6=P)

=P rob(²_P −²_Q> c_P −c_Q,∀Q6=P)

=P rob(²_Q< c_Q−c_P +²_P,∀Q6=P)

(2.22)

ë ß

–€• ²_P ÅÒ#Q&’“¦ ²_Q Ž^¦ìrŸí\¦ Øԓ¦ 1lqwn&hs“¦ &ñ€ (2.23)`¦ ëߖ7á¤> )a.

P_P|²_P = Q

∀Q6=P

R_cQ−cP+²P

−∞ (e^−²Qe^−e−²Q)d²_Q,

= Q

∀Q6=P

e^{−e−(cQ−cP+²P)} (2.23)

²_P\ @/ôÇ ›¸|ÂÒ SX‰Ò¦`¦ s6 x€ (2.22)H(2.24)–Ð „>h)a.

P_P = Z 

 Y

∀Q6=P

e^{−e−(cQ−cP+²P)}



e^−²Pe^−e−²Pd²_P (2.24)

c_P−c_P = 0sÙ¼–Ðe^{−e−(cP−cP+²P)} =e^−e−²P\¦s6 x€(2.24)H(2.25)–Ð

„

>h)a.

P_P = Z 

Y

∀Q

e^{−e−(cQ−cP+²P)}



e^−²Pd²_P

= Z

exp(−e^−²P X

Q

e^−(cQ−cP))e^−²Pd²_P

(2.25)

e^−²P\¦t–Ð u¨8Š€ dt=−e^−²Pd²_P ÷&“¦ s\¦ &h6 x€(2.26)s )a.

P_P = Z ₀

∞

exp(−tX

Q

e^−(cQ−cP))(−dt)

= Z _∞

0

exp(−tX

Q

e^−(cQ−cP))dt

=

·exp(−tP

Qe^−(cQ−cP))

−P

Qe^−(cQ−cP)

¸

(2.26)

t}Œ•Ü¼–Ð P_P(∞) ' −exp(−∞) = 0s“¦ P_P(0) = ^exp(0)

−P

Qe^−(cQ−cP) =

−P ¹

Qe^−(cQ−cP)sÙ¼–Ð þj7áx&hܼ–Ð(2.27)s )a. P_P = P ¹

Qe^−(cQ−cP) = ¹

e^−cPP

Qe^−cQ = P^e−cP

Qe^−cQ (2.27)

Ÿ¸Çah 2.2.3 ²_P\¦Ž^¦ìrŸí–Ð &ñ½+ÉM:,P_P(f) = exp(−θc_P(f))/P

j

exp(−θc_j(f))s Ù

¼–Ð $í|9 2.2.1õ (2.21)\ _K"f l@/“tq6 x“Ér (2.29)s. exp(−θc_P(f))

P

j

exp(−θc_j(f)) = ∂E(C(f))

∂c_P(f) (2.28)

E(C(f)) =−1 θlnX

j

exp(−θc_j(f)) (2.29)

l

@/“tq6 x`¦ e”__ â–Ð P\ @/K &ño€ f_P = ^{Pexp(−θcP)(f)}

j

exp(−θcj)(f) × d_isÙ¼–Ð P

jexp(−θc_j(f)) = exp(−θc_P(f))_f^di

P \¦ ëߖ7á¤Ù¼–Ð (2.30)s. E(C(f)) =−¹_θlnP

jexp(−θc_j(f)) =−¹_θln

³

exp(−θc_P(f))^d_fpⁱ

´

=c_P(f) +¹_θlnf_P −¹_θlnd_i

(2.30)

Ÿ¸Çah 2.2.4 l@/›'a8£¤q6 x E(c(f))H (2.31)ü< °ú . E(c(f)) =

P

jc_j(f)exp(−θc_j(f)) P

jexp(−θc_j(f)) (2.31)

Ÿ¸Çah 2.2.5 E(C(f))6min{c₁, c₂,· · ·, c_N}6E(c(f))\¦ ëߖ7á¤ôÇ.

€

$, min{c₁, c₂,· · ·, c_N}6E(c(f))\¦˜Ðs€min{c₁, c₂,· · ·, c_N}\¦ e”_ _

c_k“¦ € (2.32)\¦ ëߖ7á¤ôÇ. min{c₁, c₂,· · ·, c_N}=c_k(f) =

P

jc_k(f)exp(−θc_j(f)) P

jexp(−θc_j(f)) 6E(c(f)) (2.32)

6£§Ü¼–Ð E(C(f))6min{c₁, c₂,· · ·, c_N}\¦ ˜Ðs€ (2.33)õ °ú . P

jexp(−θc_j) >min{exp(−θc₁),· · ·,exp(−θc_N)}

lnP

jexp(−θc_j) >min{−θc₁,· · ·,−θc_N}

−¹_θlnP

jexp(−θc_j) 6−¹_θmin{−θc₁,· · ·,−θc_N} E(C(f)) 6min{c₁,· · ·, c_N}

(2.33)

“

tš¸ µ1ÏÒqtt ·ú§H“¦ &ñ€ 5px̐o“Ér þj™èq6 x â–Ð\¦ s6 x

½ +

É כ sÙ¼–Ð 2£§&ño 2.2.5–Ð SX‰Ò¦&h :Ÿx'ŸC&ñ\"f 5px̐os Ö¼zH l@/“

t

q6 x“Ér &ñ&h:Ÿx'ŸC&ñ_q6 x˜ÐHŒ•tëߖ l@/›'a8£¤q6 x“Ér &ñ&h :Ÿx '

Ÿ

C&ñ_ q6 x˜ÐH &tH &h`¦ ·ú˜Ãºe”.

/‘×—×=˜¿ÌfC˜+ ø5N

· ú

¡\"f [O"îôÇכ õ °ú s †½Ó–Ðf± —¸+þA“Ér ìr"îôÇ ©œ&h`¦ t“¦ e”H —¸+þA s

tëߖSheffi [50]ƒ/åLôÇ%ƒ!3¿º tH‘:r&h“ ôÇ>\¦ t“¦ e”.'Í