Ceder, A., Butcher, M. and Wang, L.

Optimization of bus stop placement forroutes on uneven topology
Transportation Research Part B, Vol.74, pp.40-61, 2015.

ཧ࿦ஊ࿩ձ#4 2015/5/15
٢໺ େհ

·ͱΊΔͱ ΞΫηεɾΠάϨεͷࡍͷޯ഑Λߟྀͯ͠όε࿏ઢͷωοτϫʔΫ‫ܭ‬ըͱ഑෼Λೋஈ֊࠷దϞσϧͰղ͍͍ͯΔ఺͕৽͍͠ɽ ఆࣜԽࣗମ͸‫ط‬ԟ‫ʹڀݚ‬฿ͬͨ΋ͷͰ͋Γޯ഑Ҏ֎ͷ෦෼͸ҰൠతɽΞϧΰϦζϜ͸‫ط‬ԟ‫ڀݚ‬ΛࢀߟʹਐԽతΞϧΰϦζϜΛ࢖༻͓ͯ͠Γɼ‫ࢉܭ‬଎౓͸ࠓҰͭɽචऀ΋‫ݟ‬௚͕͠ඞཁͱ‫͍ͯͬݴ‬Δɽ શͯͷ໨తؔ਺ɾ੍໿৚݅ͷࣜͷղઆ͕ஸೡʹࢪ͞Ε͓ͯΓ෼͔Γ΍͍͢ɽ࢖༻ͨ͠ϓϩάϥϜɾύοέʔδɼσʔλͷ࡞੒ํ๏ͳͲ͕۩
ମతʹ঺հ͞Ε͓ͯΓɼ࣮૷ͷࢀߟʹͳΔ఺͕༗༻ɽ

1

Contents
1. Introduction
2. Related literature
3. Bus stop placement design– Impact of slope on design issues

4. Model– Definitions / Bilevel model / Upper level model / Lower level model

5. Solution method
6. Examples– Small example / Large example

7. Case study– Data collection / Access path calculation / Algorithm results / Discussion

8. Conclusions
2

Introduction
˙ఀཹॴ഑ஔʹ͓͚ΔτϨʔυΦϑ– ΞΫηγϏϦςΟͱΦϖϨʔγϣϯ– ͜Ε·Ͱʹଟ͘ͷ਺ཧϞσϧ͕։ൃ͞Ε͖͕ͯͨɺΞΫηγϏϦςΟͱΦϖϨʔγϣϯʹ͔͔Δίετ྆ऀΛ૊ΈࠐΜͩϞσϧ͸গͳ͍˙஍‫ܗ‬ͷෆ‫ۉ‬Ұੑʢޯ഑ͷߟྀʣ– ޯ഑Λߟྀ͢Δ͜ͱͷॏཁੑ• ఀཹॴʹ͓͚ΔՃ‫ݮ‬଎ͷࡍʹେ͖ͳӨ‫ڹ‬• ฏୱͳಓ΍ԼΓࡔͱൺ΂্ͯΓࡔ͸าߦ଎౓͕௿Լ͠ɺఀཹॴͷҐஔ͕ΞΫηγϏϦςΟʹେ͖͘Ө‫ڹ‬• ఀཹॴΞΫηεʹ͕͔͔࣌ؒΔ͜ͱͰาߦऀͷधཁ͕௿Լ
– ॏཁੑ͸ೝࣝ͞Εͭͭ΋ɺ͜Ε·ͰϞσϧͷதͰ໌ࣔతʹऔΓѻΘΕͯ͜ͳ͔ͬͨ

3

Related literature˙όεఀཹॴ഑ஔσβΠϯʹ܎Δٕज़••••୯Ұ࿏ઢΛऔΓѻͬͯఀཹॴ഑ஔΛܾఆ͠ɺ࿏ઢؒͷ૬‫༻࡞ޓ‬͸ߟྀͤͣωοτϫʔΫશମʹ֦େ͢Δํ๏࠷దͳఀཹॴִؒ΋͘͠͸ີ౓Λબఆ͠ɺΤϦΞશମʹ͓͚Δఀཹॴީิ஍ͷ཭ࢄू߹ͷத͔Β࠷దͳఀཹॴͷ૊Έ߹ΘͤΛ‫͚ͭݟ‬Δํ๏ԊઢधཁΛ࿈ଓؔ਺Ͱߟྀ͠ɺधཁΛϙΠϯτ΋͘͠͸ΤϦΞͷ཭ࢄू߹ͷத͔Βൃੜͤ͞Δํ๏ಓ࿏ωοτϫʔΫΛ୯७Խɺ΋͘͠͸GISσʔλΛ༻͍ͯෳࡶͳωοτϫʔΫΛऔΓѻ͏˙ఀཹॴσβΠϯʹ͓͚Δޯ഑ͷߟྀ•

Rodriguez and Joo (2004)ࡔɺԊಓ‫ڥ؀‬ɺาಓ΍ࣗసंಓͷ੔උ͕ϞʔυνϣΠεʹ༩͑ΔӨ‫ڹ‬Λଟ߲બ୒ϞσϧʹΑΓ‫ه‬ड़ɻ͜ΕΒͷӨ‫ڹ‬ͷมԽʹ൐͏Ϟʔυબ୒ͷ஄ྗ஋Λࢉग़͠ɺޯ഑ʹΑΔ஗Ԇʹͱ͓ͳ͏าߦબ୒ͷ஄ྗ஋Λࢉग़ɻ

•

Fruth and SanClemente (2006)ࡔ෇ۙͷఀཹॴ͸஗ԆΛੜͤ͡͞Δ͜ͱΛҟͳΔޯ഑ͷόε࿏ઢؒͷൺֱ෼ੳʹΑΓ੔ཧɻ•

Terrier et al. (2010)ޯ഑ͷมԽʹΑΓาߦऀͷՃ଎౓ͱࢎૉফඅྔͷؔ܎ੑʹ͍ͭͯ੔ཧɻ

4

Model˙ωοτϫʔΫ৚݅ͷఆٛ৐ंఀཹॴm߱ंఀཹॴnधཁϙΠϯτʢ‫఺ى‬ʣiधཁϙΠϯτʢऴ఺ʣjΞΫηείετ

ޯ഑ύϥϝʔλॴཁ࣌ؒ‫཭ڑ‬ඪߴ/‫ޯʹ཭ڑ‬഑5Model˙ޯ഑ͱาߦ଎౓ͷؔ܎

6

Model˙ޯ഑σʔλͷิ‫׬‬7

Model˙ޯ഑ύϥϝʔλ࣮ࡍͷҠಈ࣌ؒͱ‫ܦ‬࿏͕ϑϥοτͳ৔߹ͷҠಈ࣌ؒͷࠩ‫ܦ‬࿏͕ϑϥοτͳ৔߹ͷҠಈ࣌ؒޯ഑ͱาߦऀधཁͷ஄ྗ஋าߦऀϞʔυγΣΞͷมԽྔޯ഑ʹΑΔ஗Ε࣌ؒͷมԽྔʻ‫ྫࢉܭ‬ʼ•‫׬‬શʹϑϥοτͳಓͰ͋Ε͹1.7kmͷ‫཭ڑ‬͸໿20෼ͰҠಈͰ͖Δʢาߦ଎౓ʹ1.4m/sʣ•্Γޯ഑ʹΑΓҠಈ͕࣌ؒ25෼ʹͳͬͨ৔߹
1

•

0.162

1.04

ԼΓޯ഑ʹΑΓҠಈ͕࣌ؒ5෼୹ॖͨ͠৔߹
10.1620.96

8Model˙ޯ഑ʹΑΔ஗Εͱޯ഑ύϥϝʔλɼΞΫηείετͷؔ܎ʢBD  NJOͷ৔߹ʣ

9Model˙౸ୡՄೳੑͷߟྀ•‫఺ى‬धཁϙΠϯτi͔Β৐ंఀཹॴmʹ౸ୡͰ͖Δ͔൱͔

•߱ंఀཹॴn͔Βऴ఺धཁϙΠϯτjʹ౸ୡͰ͖Δ͔൱͔•

ᮢ஋g͸ΞΫηε‫ڐ‬༰࣌ؒͷ্‫ݶ‬஋ʢॴ༩ʣͰઃఆ•ߦ͖ͱ‫ؼ‬ΓͰޯ഑͕ҟͳΔͨΊɼ10Model˙ೋஈ֊࠷దԽ໰୊ͱͯ͠ఆࣜԽ

˙*CFBT FUBM  ΛࢀߟʹఆࣜԽ্Ґ໰୊ԼҐ໰୊্Ґ໰୊ɿఀཹॴ഑ஔͷ࠷దԽObj: ΦϖϨʔγϣϯίετͱར༻ऀίετͷ࠷খԽԼҐ໰୊ɿ৐٬Λ֤࿏ઢʹ഑෼
Obj: ΞΫηε࣌ؒͱ৐ं࣌ؒͷ࠷খԽ

11Model˙্Ґ໰୊ɿόεఀཹॴ഑ஔͷ࠷దԽ໨తؔ਺ɿΦϖϨʔγϣϯίετͱར༻ऀίετͷ࠷খԽΦϖϨʔγϣϯίετʢӡߦ‫ܦ‬අɾΞΠυϦϯάίετɾਓ݅අɾ‫ݻ‬ఆඅʣར༻ऀίετʢఀཹॴΞΫηε࣌ؒʹ܎Δίετɾ৐ं࣌ؒʹ܎Δίετʣ੍໿৚݅ɿ‫͔఺ى‬Β౸ୡͰ͖Δఀཹॴ͕1ͭҎ্ɼ͔ͭऴ఺ʹ౸ୡͰ͖Δఀཹॴ͕1ͭҎ্: ॱํ޲(OÞD)ͷఀཹॴηοτ: ‫(޲ํٯ‬DÞO)ͷఀཹॴηοτ※ఀཹॴ͕࠾༻͞ΕΔ৔߹1ɼͦ͏Ͱͳ͚Ε͹0ΛͱΔόΠφϦม਺

12

Model˙ΦϖϨʔγϣϯίετͷఆٛ෼ੳର৅࣌ؒ(h)ӡߦ‫ܦ‬අ
୯Ձ($/km)ӡసִؒ(min)ϧʔτԆ௕(km)1ਓ౰ͨΓฏ‫ۉ‬৐߱࣌ؒ(sec)ΞΠυϦϯάίετ
୯Ձ($/h)෼ੳର৅࣌ؒ(h) ijؒͷधཁྔ(veh/h)ϧʔτ1αΠΫϧ͋ͨΓͷ૯ॴཁ࣌ؒ(h)෼ੳର৅࣌ؒ(h)ਓ݅අ୯Ձ($/h) ӡసִؒ(min)ϧʔτ1αΠΫϧ͋ͨΓͷ૯ॴཁ࣌ؒ(h)ं྆ʹ܎Δ‫ݻ‬ఆඅ୯Ձ($/veh)ӡసִؒ(min)13

Model˙ΦϖϨʔγϣϯίετͷఆٛ૯ॴཁ࣌ؒҠಈʴ଴ͪʴՃ‫ݮ‬଎ʴ৐‫ܧ‬଴߹Θͤʢ‫ݻ‬ఆʣҠಈ࣌ؒ

Furth and SanClemente (2006)ΑΓฏ‫ۉ‬ӡߦ଎౓(km/h)

଴ͪ࣌ؒՃ଎ʹ‫ى‬Ҽ ޯ഑ʹ‫ى‬Ҽ ‫ݮ‬଎ʹ‫ى‬Ҽ͢Δ஗Ε ͢Δ஗Ε ͢Δ஗ΕՃ‫ݮ‬଎஗Εॱํ޲ͷ஗Ε‫޲ํٯ‬ͷ஗Ε

14

Model˙ར༻ऀίετͷఆٛधཁྔόΠφϦม਺ʢ‫఺ى‬i͔Βఀཹॴm, nΛ‫ܦ‬༝ͯ͠ऴ఺jʹ౸ୡͰ͖Ε͹1ɼͦ͏Ͱͳ͚Ε͹0ʣΞΫηε࣌ؒΞΫηε ΠάϨείετ ίετ৐ं࣌ؒҠಈ࣌ؒఀཹॴmnؒͷॴཁ࣌ؒ(h)15Model˙ར༻ऀίετͷఆٛ஗Ε࣌ؒ‫఺ى‬ఀཹॴmʹ͓͚ΔՃ଎஗Ε

ऴ఺ఀ
ཹॴnʹ
͓͚Δ
‫ݮ‬଎஗
Ε

தؒఀཹॴoʹ͓͚ΔՃ଎ɾ‫ݮ‬଎஗Ε

dir=1ͳΒ͹nͷલʹm͕഑ஔ
dir=-1ͳΒ͹mͷલʹn͕഑ஔ

16Model˙ར༻ऀίετͷఆٛ଴ͪ࣌ؒதؒఀཹॴͰऴྃ͢ΔτϦοϓ தؒఀཹॴ͔Βൃੜ͢ΔτϦοϓ

17

Model˙ԼҐ໰୊ɿར༻ऀͷ഑෼໨తؔ਺ɿΞΫηε࣌ؒͱ৐ं࣌ؒͷ࠷খԽʢ΋͘͠͸ΞΫηε࣌ؒͷΈͷ࠷খԽʣ੍໿৚݅ɿશͯͷधཁ͕ϧʔτ্ʹ഑෼͞ΕΔμϛʔม਺೚ҙͷODϖΞijʹ͍ͭͯ౸ୡఀཹॴϖΞΛநग़ʢΞΫηεɾΠάϨε྆ํͱ΋࣮‫͖Ͱݱ‬Δ৔ʣ

18

Solution method˙ղ๏ʹ͍ͭͯ•্Ґ໰୊͸NPࠔ೉Ͱ͋Γۙࣅղ๏Λ༻͍Δඞཁ͕͋Δɽ•ԼҐ໰୊͸্Ґ໰୊ͷղΛΠϯϓοτͯ͠ղΛฦ͢൓Ԡؔ਺ʹΑͬͯఆࣜԽ͞Ε͓ͯΓɼ্Ґ໰୊ͷղΛ‫ݻ‬ఆͯ͠ղ͘͜ͱʹͳΔͨΊ୯७ɽCPLEX౳ͷιϧόʔͰղ͚Δɽ˙ೋஈ֊࠷దԽ໰୊ͷ্Ґ໰୊ΛҰൠࣜΛ੔਺‫ܭ‬ը໰୊ͱͯ͠ఆࣜԽ˙ద߹౓ؔ਺•্Ґ໰୊ͷ੍໿৚݅ΛϖφϧςΟ߲ͱͯ͠༩͑Δͱͱ΋ʹɼԼҐ໰୊ͷ࣮‫ݱ‬ෆՄೳղʹ͍ͭͯ͸બఆ͠ͳ͍Α͏ʹఆࣜԽɽ

19

Solution method˙ΞϧΰϦζϜʢਐԽతΞϧΰϦζϜʣॳ‫ஂूظ‬ͷੜ੒ɼධՁ

＝਌ूஂม਺ॳ‫ظ‬਌ूஂ ‫ݸ‬Λੜ੒ద߹౓ࢠੈ୅ͷੜ੒ɼධՁʢੜ੒‫ ਺ݸ‬ʣ
֬཰CXPBͰަࠥͤ͞ΔʢҰ఺ަࠥʣ
֬཰1-CXPBͰಥવมҟͤ͞ΔʢFLIP_BITʣࢠͷద߹౓Λࢉग़gੈ୅ͷࢠूஂ͕ੜ੒͞ΕΔo࣍ͷੈ୅΁

g+1ੈ୅ͷ਌ूஂ͸gੈ୅ͷ਌ɾࢠͷ͏ͪΤϦʔτ͔Βநग़ऩଋ৚݅·Ͱ‫܁‬Γฦ͠
20

Example˙Small example

21

Example
˙Large example

22

Example˙্Ґ໰୊໨తؔ਺ͷऩଋঢ়‫گ‬•

൓෮ճ਺40•ղͷੜ੒‫਺ݸ‬40ʢ =30ɼl=10ʣ•ಥવมҟ֬཰0.4ʢFLIP_BIT֬཰0.1ʣɼަࠥ֬཰0.6

23

Example˙্Ґ໰୊‫݁ࢉܭ‬Ռʢճ൓෮ऴྃ‫ޙ‬ʗ྘৭͕ར༻͞ΕͨఀཹॴʣͨͿΜ৭͕‫ٯ‬24

Example˙ԼҐ໰୊ͷղϕΫτϧʢधཁϙΠϯτɾఀཹॴͷ૊Έ߹Θͤʣ

25

Case study
˙֓ཁ•

Auck and CBDʹ͓͚ΔேϐʔΫ࣌ؒଳʢ7:00-9:00ʣΛର৅ʹέʔεελσΟΛ࣮ࢪɽ•σʔλͷιʔτ͸PostgreSQLɼPythonͱPortgreSQLσʔλϕʔεΛ઀ଓ͢Δࡍʹ͸
GeoDjangoΛ࢖༻ɽ࠷୹‫ܦ‬࿏୳ࡧ͸PythonͷNetworkXΛ࢖༻ɽ•‫ࢉܭ‬ΞϧΰϦζϜʹ͍ͭͯ͸PythonͷDistributed Evo utionary A goritums in Pythonͱ
PuLP(CPLEXιϧόʔ૊ΈࠐΈ)Λ࢖༻ɽ•ՄࢹԽʹ͍ͭͯ͸QGISΛ࢖༻ɽ˙ωοτϫʔΫσʔλ•ωοτϫʔΫɿOpen Data Commons Open Databese LicenseͷOSMϓϩδΣΫτΑΓೖखɼ
PortGISͰ੔ཧʢ※าߦෆՄೳͳωοτϫʔΫ͸আ֎ʣ•ඪߴσʔλɿAuck and Counci GIS Viewer website͔Β1mִؒͷ΋ͷΛೖख•‫ط‬ଘόε࿏ઢɾఀཹॴɿOSMϓϩδΣΫτʢThe Goog e Transit Feed Specification DataExchangeͳͲͰ୅ସՄೳʣ•ఀཹॴީิ஍ɿ‫ط‬ଘ࿏ઢʹԊͬͯ50mϐονͰઃஔ•धཁͷϙϦΰϯσʔλɿOSMϓϩδΣΫτʢεϙʔπࢪઃɼ঎‫ۀ‬ɼҩྍɼϗςϧɼॅ୐ɼֶߍ౳ʣ•धཁൃੜՕॴɿϙϦΰϯσʔλͷॏ৺ʹ࠷΋͍ۙಓ࿏ωοτϫʔΫ্ͷϊʔυ
26

Case study
˙0%σʔλ•New Zea and trips database bureauͷτϦοϓ਺σʔλΛ࢖༻ʢ1985͔Β2012೥·Ͱͷࢪઃ‫ػ‬ೳผচ໘ੵ౰ͨΓͷτϦοϓ਺σʔλ͕੔උʣ•ίʔυϯϥΠϯʢCBDΤϦΞʣ্ʹΤϯτϦʔϙΠϯτͱ‫ݺ‬͹ΕΔμϛʔͷधཁϙΠϯτΛઃஔ͠ɼCBD֎ͷधཁΛશͯू໿ʢAM͸‫఺ى‬ɼPM͸ऴ఺ͱͳΔʣ˙࠷୹‫ܦ‬࿏୳ࡧ•౸ୡՄೳఀཹॴϚτϦΫεɼ౸ୡՄೳधཁϙΠϯτϚτϦΫεɼΞΫηείετϚτϦΫεͷ࡞੒ɽ•PythonͷύοέʔδͷNetworkXΛ࢖༻ɽ·ͣOSMͷωοτϫʔΫσʔλΛNetworkXͷάϥϑΦϒδΣΫτʹม‫͠׵‬ɼఀཹॴީิ஍΍धཁϙΠϯτͷϊʔυʢϢχʔΫID෇͖ʣΛ࡞੒ɽ•ϦϯΫίετ͸ޯ഑ʹԠͯ͡෇༩ɽ

•NetworkXύοέʔδͷμΠΫετϥ๏Ͱ࠷୹‫ܦ‬࿏୳ࡧΛ࣮ࢪɽΧοτΦϑ஋ ͸ΞΫηε࣌ؒͷ‫ڐ‬༰্‫ݶ‬ʢ͜͜Ͱ͸ =5minʣΛ࢖༻ɽ˙ΞϧΰϦζϜ•‫܁‬Γฦ͠ճ਺300
27

Case study
˙Auckland CBD data28

Case study˙ϧʔτேϐʔΫधཁԼͰͷఀཹॴ഑ஔ

Zmin=53,456.47

29

Case study˙ϧʔτேϐʔΫधཁԼͰͷఀཹॴ഑ஔʢϑϥοτωοτϫʔΫͷ৔߹ʣ

Zmin=53,377.7($78.77 (0.2%)վળ)※άϥϑؒҧ͍ʁ30

Case study˙ϧʔτேϐʔΫधཁԼͰͷఀཹॴ഑ஔʢϑϥοτωοτϫʔΫͷ৔߹ʣ31

Case study˙ϧʔτேϐʔΫधཁԼͰͷఀཹॴ഑ஔʢޯ഑Λߟྀͨ͠ωοτϫʔΫͷ৔߹ʣ32

Case study˙ޯ഑ͷߟྀ• ޯ഑Λߟ͑Δ͜ͱͰ্Γࡔͷ‫ܦ‬࿏ͷར༻͕‫ݮ‬ΓɼԼΓࡔɾฏୱͳ‫ܦ‬࿏ͷར༻͕૿• ໨తؔ਺஋0.2%ͷࠩ͸Πϯϓοτσʔλͷ‫ࠩޡ‬Λ౿·͑Δͱ༗ҙͳࠩͱ͸‫͍ͳ͑ݴ‬• ͕ɼSan FranciscoͷΑ͏ͳࡔ͕ଟ͍஍ҬͰ͸ॏཁͳཁૉʹͳΔͷͰ͸ɾɾ˙ேϐʔΫͱ༦ϐʔΫͷҧ͍• Aucklandͷ৔߹ɼே͸΄ͱΜͲͷτϦοϓ͕ϋʔόʔϑϩϯτํ໘ʢԼΓํ໘ʣɼ༦ํ͸্Γࡔ• ༦ํͷ෼ੳ݁Ռͷํ͕ఀཹॴ෼෍͕ີʹͳΔ33

Conclusions˙੒Ռ•ωοτϫʔΫσβΠϯͷ‫ݕ‬౼ʹ͋ͨͬͯޯ഑Λߟྀ͢Δͱͱ΋ʹɼΞΫηε‫ܦ‬࿏ʹ͓͚ΔΞΫηγϏϦςΟΛϧʔτ‫ݕ‬౼ͷࡍʹ໌ࣔతʹऔΓѻͬͨ•

GISΛ‫͢༻׆‬Δ͜ͱͰඪߴ΍ಓ࿏ಛੑͷৄࡉͳσʔλΛऔѻ͍ɼେ‫ن‬໛ωοτϫʔΫͷ‫ʹࢉܭ‬΋ରԠͨ͠˙ఆࣜԽʹ͓͚Δ՝୊•ෳ਺ϧʔτͷ૊Έ߹Θͤʢϧʔτؒͷ૬‫༻࡞ޓ‬ʣ΁ͷରԠ•ԼҐ໰୊Λ‫ߧۉ‬഑෼ʹ֦ு•‫ܦ‬࿏બ୒ʹ͓͚Δ֬཰Ϟσϧͷಋೖ•ӡߦִؒͷܾఆ໰୊΋ಉ࣌ʹղ͘΂͖•धཁൃੜϙΠϯτͷ༩͑ํ˙ΞϧΰϦζϜʹ͓͚Δ՝୊•ߴ଎Խ•ΞϧΰϦζϜࣗମ‫ݟ‬௚ͨ͠ํ͕͍͍34ຊࢿྉ࡞੒ʹ܎Δͦͷଞࢀߟจ‫ݙ‬•

Ibeas, A., dell’Olio, L., Alonso B., Sainz, O.: Optimizing bus stop spacing in urban
areas, Transportation Research Part E, Vol.46, pp.446-458, 2010.

•Beyer, H.-G., Schwefel, H.-P.: Evolution strategies: a comprehensive introduction,
Natural Computing, Vol.1, pp.3-52, 2002.

35