JAIST Repository: 遺伝的アルゴリズムに基づく電子商取引における問題解決システムの構築
55
0
0
全文
(2) ୃ ჻ ⺰ ᢥ. ㆮવ⊛ࠕ࡞ࠧ࠭ࡓߦၮߠߊ㔚ሶขᒁߦ߅ߌࠆ 㗴⸃ࠪࠬ࠹ࡓߩ᭴▽. ᜰዉᢎቭ ⮮ ㅴ ᢎ. ർ㒽వ┵⑼ቇᛛⴚᄢቇ㒮ᄢቇ ⍮⼂⑼ቇ⎇ⓥ⑼⍮⼂␠ળࠪࠬ࠹ࡓቇኾ. 250051. ⮮ ᱜ᮸. ክᩏᆔຬ㧦 ⮮ ㅴ ᢎ㧔ਥᩏ㧕 ⮮ᵄ ദ ഥᢎ ศ↰ ᱞ⒤ ᢎ ᧄ ৻ᔒ ഥᢎ 2004 ᐕ㧞. Copyright հ 2004 by Masaki Hyodo.
(3) ⋡ ᰴ. 1 ᐨ⺰ . 㧝. 1.1 ᧄ⎇ⓥߩ⢛᥊ 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚. 㧝. 1.2 ᧄ⎇ⓥߩ⋡⊛ 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚. 㧟. 1.3 ᧄ⺰ᢥߩ᭴ᚑ 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚. 㧠. 2 㑐ㅪ⎇ⓥ . 㧡. 2.1 㑐ㅪ⎇ⓥ 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚. 㧡. 2.1.1 㔚ሶขᒁ 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧡 2.1.2 ឭ៤ᒻᚑᚻᴺ 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧢 2.1.3 ㆮવ⊛ࠕ࡞ࠧ࠭ࡓ 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧣 2.2 ᧄ⎇ⓥߩ․⦡ 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚. 㧣. 3 㔚ሶห⾼ࡑࠤ࠶࠻ߦ߅ߌࠆታᤨ㑆ឭ៤ᒻᚑ 㧤 3.1 ઍᦧ⽷ࠍ↪ߚ㔚ሶห⾼ 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧤 3.2 ታᤨ㑆ឭ៤ᒻᚑ 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧝㧠 4 ㆮવ⊛ࠕ࡞ࠧ࠭ࡓࠍ↪ߚታᤨ㑆ឭ៤ᒻᚑࠕ࡞ࠧ࠭ࡓ 㧞㧝 4.1 ㆮવ⊛ࠕ࡞ࠧ࠭ࡓ 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧞㧝 4.2 ㆮવሶ 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧞㧝 4.3 ߦࠃࠆ⥌ᱫㆮવሶߩᛥ 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧞㧟 4.4 ㆮવሶ㓸࿅ߩಽᢔ 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧞㧡. i.
(4) 5 ታ㛎 㧞㧢 5.1 ห⾼ߦ߅ߌࠆᦨㆡឭ៤ᒻᚑ 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧞㧢 5.1.1 ห⾼ߦ߅ߌࠆᦨㆡឭ៤ᒻᚑ㗴 㧚 㧚 㧚 㧚 㧚 㧚. 㧞㧢. 5.1.2 ᦨㆡឭ៤ᒻᚑ㗴ߩ․ᕈ߅ࠃ߮⸃ࠕ࡞ࠧ࠭ࡓߩ․ᕈ 㧚 㧚 㧞㧣 5.1.3 ࠕ࡞ࠧ࠭ࡓߩ⹏ଔ 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚. 㧞㧥. 5.2 ห⾼ߦ߅ߌࠆታᤨ㑆ឭ៤ᒻᚑ 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧟㧞 5.2.1 ห⾼ߦ߅ߌࠆታᤨ㑆ឭ៤ᒻᚑ㗴 㧚 㧚 㧚 㧚 㧚 㧚. 㧟㧞. 5.2.2 ታᤨ㑆ឭ៤ᒻᚑ㗴ߩ․ᕈ߅ࠃ߮⸃ࠕ࡞ࠧ࠭ࡓߩ․ᕈ 㧚 㧚 㧟㧞 5.2.3 ࠕ࡞ࠧ࠭ࡓߩ⹏ଔ 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚. 㧟㧡. 5.3 ⇐ଔᩰߦၮߠߊห⾼ߦ߅ߌࠆታᤨ㑆ឭ៤ᒻᚑ 㧚 㧚 㧚 㧟㧣 5.3.1 ⇐ଔᩰߦၮߠߊห⾼ߦ߅ߌࠆታᤨ㑆ឭ៤ᒻᚑ㗴 㧚 㧚 㧟㧤 5.3.2 ⇐ଔᩰߦၮߠߊห⾼ߦ߅ߌࠆታᤨ㑆ឭ៤ᒻᚑ㗴ߩ․ᕈ߅ࠃ߮ ⸃ࠕ࡞ࠧ࠭ࡓߩ․ᕈ 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚㧟㧥 6 ⚿⺰ 㧠㧟 6.1 ᚑᨐ 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧠㧟 6.2 ᓟߩ⺖㗴 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧠㧠. ⻢ㄉ . 㧠㧡. ෳ⠨ᢥ₂ . 㧠㧢. ⊒⺰ᢥ . ii. 㧠㧥.
(5) ࿑ ⋡ ᰴ 1.1 ᣢሽߩห⾼ 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚㧡 3.1 ઍᦧ⽷ࠍ↪ߚห⾼ 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧝㧝 3.2 ឭ៤ᒻᚑ᩺ A 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧝㧟 3.3 ឭ៤ᒻᚑ᩺ B 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧝㧟 3.4 㔚ሶห⾼ࡑࠤ࠶࠻ߩᤨ㑆⚻ㆊ 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧝㧡 3.5 ታᤨ㑆ឭ៤ᒻᚑ㧝 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧝㧢 3.6 ታᤨ㑆ឭ៤ᒻᚑ㧞 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧝㧢 3.7 ታᤨ㑆ឭ៤ᒻᚑ㧟 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧝㧣 3.8 ታᤨ㑆ឭ៤ᒻᚑ㧠 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧝㧣 3.9 ታᤨ㑆ឭ៤ᒻᚑ㧡 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧝㧤 3.10 ታᤨ㑆ឭ៤ᒻᚑ㧢 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧝㧤 3.11 ታᤨ㑆ឭ៤ᒻᚑ㧣 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧝㧥 4.1 ㆮવሶ 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧞㧞 4.2 ߦࠃࠆ⥌ᱫㆮવሶߩᛥ 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧞㧠 4.3 ㆮવሶ㓸࿅ߩಽᢔߩᔨ࿑ 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧞㧡 5.1 ฦࠕ࡞ࠧ࠭ࡓߩᤨ㑆ㆫ⒖ 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧟㧠 5.2 ⇐ଔᩰߦၮߠߊห⾼ߦ߅ߌࠆታᤨ㑆ឭ៤ᒻᚑߩᤨ㑆ㆫ⒖ 㧚㧠㧝. iii.
(6) ⋡ ᰴ 3.1 ଔᩰ࠹ࡉ࡞ 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚㧝㧜 5.1 ᄁࠅᚻߩଔᩰ࠹ࡉ࡞㧔㗴 a㧕 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚㧞㧣 5.2 ᄁࠅᚻߩଔᩰ࠹ࡉ࡞㧔㗴 b㧕 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚㧞㧤 5.3 ⾈ᚻߩ⇐ଔᩰ 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧞㧤 5.4 ⾈ᚻߩല↪ߩว⸘୯ 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧞㧥 5.5 Ṷ▚ᤨ㑆 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧞㧥 5.6 ᐔဋṶ▚ᤨ㑆㧦⾈ᚻ 10ޔᄁࠅᚻ 5 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚㧟㧜 5.7 ឭ᩺ᚻᴺߣ᰼ᒛࠅᴺߩᱜ╵ᐲᲧセ㧦⾈ᚻ 10ޔᄁࠅᚻ 5 㧚 㧚 㧚 㧚㧟㧜 5.8 ᐔဋṶ▚ᤨ㑆㧦⾈ᚻ 11ޔᄁࠅᚻ 6 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚㧟㧜 5.9 ឭ᩺ᚻᴺߣ᰼ᒛࠅᴺߩᱜ╵ᐲᲧセ㧦⾈ᚻ 11ޔᄁࠅᚻ 6 㧚 㧚 㧚 㧚㧟㧝 5.10 ᄁࠅᚻߩଔᩰ࠹ࡉ࡞㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚㧟㧟 5.11 ⾈ᚻߩ⇐ଔᩰ㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚㧟㧟 5.12 ห⾼ࡑࠤ࠶࠻ߩ࠲ࠗࡓ࠹ࡉ࡞ 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚㧟㧟 5.13 ࡑࠤ࠶࠻⚳ੌᤨߩല↪ߩว⸘㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚㧟㧡 5.14 ࠗࡌࡦ࠻⏕₸㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚㧟㧢 5.15 ࡑࠤ࠶࠻⚳ੌᤨߦ߅ߌࠆല↪ߩว⸘ߩᐔဋ 㧚 㧚 㧚 㧚 㧚 㧚㧟㧣 5.16 ࡑࠤ࠶࠻⚳ੌᤨߦ߅ߌࠆㆡว⸃ዉ࿁ᢙ 㧚 㧚 㧚 㧚 㧚 㧚 㧚㧟㧣 5.17 ᄁࠅᚻߩଔᩰ࠹ࡉ࡞㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚㧟㧥 5.18 ⇐ଔᩰ࠹ࡉ࡞ 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧠㧜 5.19 ห⾼ࡑࠤ࠶࠻ߩ࠲ࠗࡓ࠹ࡉ࡞ 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚㧠㧜 5.20 ࡑࠤ࠶࠻⚳ੌᓟߩല↪ߩว⸘୯ 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚 㧚㧠㧞. iv.
(7) ╙㧝┨ ᐨ⺰ 1.1 ᧄ⎇ⓥߩ⢛᥊ ㄭᐕ㧘⸘▚ᯏᛛⴚߩᕆㅦߥ⊒ዷߦࠃࠅ㧘ડᬺߛߌߢߥߊੱߢ߽◲නߦ⸘▚ᯏ߇ ↪ߐࠇࠆࠃ߁ߦߥߞߚ㧚ߘࠇߦ㧘ࠦࡦࡇࡘ࠲ߪኾ㐷⊛ߥṶ▚ߛߌߢߥߊ㧘ੱ ⊛ߥᵴേߦ߹ߢᐢߊ↪ߐࠇࠆࠃ߁ߦߥߞߚ㧚߹ߚ㧘ࠗࡦ࠲ࡀ࠶࠻ߩᢛ᳢↪ ൻߦࠃࠅ㧘ࠗࡦ࠲ࡀ࠶࠻ⅣႺߪቇᩞ߿ડᬺߛߌߢߥߊ㧘ኅᐸ߹ߢᐢ߇ߞߡ߅ࠅ㧘ࠗ ࡦ࠲ࡀ࠶࠻ࠍၮ␆ߣߒߚᣂߚߥ␠ળ߇ᒻᚑߐࠇߡ߈ߚ㧚ࠗࡦ࠲ࡀ࠶࠻␠ળߦ߅ߌ ࠆᦨ߽㗼⪺ߥᄌൻߣߒߡࠗࡦ࠲ࡀ࠶࠻ࠍ↪ߚࡆࠫࡀࠬ㧘㔚ሶขᒁ㧔Electronic Commerce㧕߇ߍࠄࠇࠆ[1][2]㧚㔚ሶขᒁߣߪ㧘ขᒁࠍࡀ࠶࠻ࡢࠢߢㆀⴕߔ ࠆߢࠅ㧘㔚ሶ⊛ߦ⽷⽻߿ࠨࡆࠬ߿ᖱႎࠍ⾼⾈ߒ㧘⽼ᄁߔࠆㆊ⒟ߢࠆ㧚 㔚ሶขᒁߪขࠅᛒ߁ຠ߿ࠨࡆࠬߦࠃߞߡ᭽ߥޘᒻᘒ߇ࠆ[11][12]㧚ߥ߆ߢ ߽ห⾼ߪᵈ⋡ࠍ㓸ߡࠆ㔚ሶขᒁߩ৻ᒻᘒߢࠆ[10]㧚ห⾼ߣߪ㧘⾈ ᚻߩੱᢙߦࠃߞߡຠଔᩰ߇ቯߐࠇ㧘ࠃࠅᄙߊߩ⾈ᚻ߇ෳടߔࠇ߫⾈ᚻߪࠃࠅ ߊຠࠍ⾼ߢ߈ࠆขᒁߢࠆ㧚⾈ᚻߪᄙੱᢙߢឭ៤ߒߡ߹ߣ߹ߞߚᢙߩຠ ࠍ৻ᐲߦ⾼ߔࠆߢ⾈ᚻߪࠃࠅ߿ߔߊ⾼ߢ߈㧘ᄁࠅᚻߪ߹ߣ߹ߞߚᐶࠍ৻ᐲ ߦಣಽߔࠆ߇᧪ࠆ㧚ࠗࡦ࠲ࡀ࠶࠻ߢߩห⾼ߪࡑࠤ࠶࠻ߩෳട⠪߇ᤨ㑆߿ ႐ᚲߦ❈ࠄࠇࠆߥߊห⾼ߦෳടߢ߈ࠆߚ㧘ߕ⍮ࠄߕߩੱ㑆ห჻߇ឭ៤ߔࠆ ߎߣߢ㕖Ᏹߦଔߦຠ߇⾼ߢ߈ࠆߣ߁ᄢ߈ߥὐ߇ࠆ㧚ߒ߆ߒߥ߇ࠄ㔚ሶ ห⾼ߦߪࠗࡦ࠲ࡀ࠶࠻ߩขᒁߢࠆ࠺ࡔ࠶࠻߽หᤨߦሽߔࠆ㧚ᣢሽߩห ⾼ࠨࠗ࠻ߦߪ㧘ᄙߊߩห৻߅ࠃ߮㘃ૃߒߚຠ߇ሽߔࠆ㧚ห⾼ߪࠃࠅᄙߊߩ ⾈ᚻ߇ෳടߔࠆߢࠃࠅଔߦຠࠍ⾼ߢ߈ࠆߚ㧘ᐢࠗࡦ࠲ࡀ࠶࠻ߩ⇇. 1.
(8) ߦ߅ߡ⾈ᚻ߇ಽᢔߒߡߒ߹߁ߎߣ߇ࠆ㧚ߘߩߚ㧘⾈ᚻห჻ߩឭ៤ᒻᚑ߇ච ಽߢߥ߹߹ขᒁ߇ᚑ┙ߒߚࠅ㧘⾈ᚻ߇චಽߥଔᩰ߹ߢᒁ߈ਅߍࠄࠇߥຠߦኻ ߒߡขᒁߦෳടߖߕ㧘ขᒁ߇ਇᵴᕈൻߐࠇߚࠅߒߡߒ߹߁ߣ߁㗴ࠍߔࠆ㧚. ࿑ 1.1 ᣢሽߩห⾼. 2.
(9) 1.2 ᧄ⎇ⓥߩ⋡⊛ ᧄ⎇ⓥߢߪઍᦧ⽷ࠍ↪ߚห⾼ࡑࠤ࠶࠻ࠍឭ᩺ߒ㧘⾈ᚻ߇ᦨᄢ㒢ߩല↪ࠍ ᓧࠄࠇࠆឭ៤ᒻᚑࠍᡰេߔࠆࠪࠬ࠹ࡓࠍ᭴▽ߔࠆ㧚. ઍᦧ⽷ࠍ↪ߚห⾼ࡑࠤ࠶࠻ߩ᭴▽. ઍᦧ⽷ߣߪ㧘ࠆ⾈ᚻߦߣߞߡㆬᛯ⢇ߩ߁ߜߩߤߩຠࠍ⾼ߒߡ߽ࠃ႐ว㧘 ߘࠇࠄోߡߩຠࠍઍᦧ⽷ߣ߱㧚1.1 ߢㅀߴߚࠃ߁ߦ㧘ᣢሽߩห⾼ߪห৻㘃 ૃߒߚຠ߇ὐߔࠆߦࠃࠆ⾈ᚻߩಽᢔ߇㗴ߣߥߞߡࠆ㧚ᧄ⺰ಽߢឭ᩺ߔࠆ ઍᦧ⽷ࠍ↪ߚห⾼ࡑࠤ࠶࠻ߪ㧘⾈ᚻߦห৻ߩࠞ࠹ࠧߩຠࠍឭ␜ߔࠆߎ ߣߢ⾈ᚻ߇Ꮧᦸߔࠆຠ⟲߆ࠄน⢻ߥ㒢ࠅଔߦຠߩ⾼߇᧪ࠆขᒁࠍน⢻ ߣߔࠆ[5][6]㧚. ⾈ᚻห჻ߩᦨㆡߥឭ៤ᒻᚑߩᡰេ. ߒ߆ߒߥ߇ࠄ㧘ห⾼ߪขᒁߐࠇࠆຠᢙߢߘߩනଔ߇േ⊛ߦᄌൻߔࠆ㧚ߒߚ߇ߞ ߡෳട⠪ోຬ߇⾼ߔࠆຠ‛ࠍቯߔࠆ߹ߢฦ⾈ߩޘᚻߩ⾼නଔ߇ቯߢ߈ߥ 㧚ోߡߩ⾈ᚻߪᏗᦸଔᩰౝ߆ߟน⢻ߥ㒢ࠅଔߦຠࠍ⾼ߔࠆࠍᦸࠎߢࠆ㧚 ߘߎߢ㧘ోߡߩ⾈ᚻߩᏗᦸଔᩰౝ߆ߟ⾼㊄㗵ߩว⸘୯߇ᦨ߽ዊߐߊߥࠆࠃ߁ߥᦨ ㆡߥឭ៤⚵ߺวࠊߖࠍዉߔࠆᔅⷐ߇ࠆ㧚 ห⾼ߦ߅ߌࠆ⾈ᚻߩᦨㆡᝄࠅಽߌ㗴ߪ NP ࿎㔍ߥ㗴ߢࠆ㧚ోߡߩ⾈ ᚻ߇Ꮧᦸଔᩰౝ߆ߟోߡߩ⾈ᚻߩ⾼㊄㗵ߩว⸘୯߇ᦨ߽ዊߐߊߥࠆឭ៤⚵ߺว ࠊߖࠍዉߔࠆߚߦߪోߡߩ⚵ߺวࠊߖࠍ⸘▚ߔࠆᔅⷐ߇ࠆ㧚ߒ߆ߒ㧘ࠗࡦ࠲ ࡀ࠶࠻ߦࠃࠆห⾼ߪਇ․ቯᄙᢙߩ⾈ᚻ߇ෳടߔࠆߚᜰᢙ⊒߇ߎࠅ㧘ోᬌ ⚝ߦࠃࠆᦨㆡ⚵ߺวࠊߖߩត⚝ߪ⸘▚ᤨ㑆߇ᄢ߈ߊ㧘ታ↪⊛ߢߪߥ㧚ߘߎߢ㧘ല₸ ߩࠃ⸃ត⚝ᴺߦࠃࠆឭ៤ᒻᚑࠕ࡞ࠧ࠭ࡓࠍឭ᩺ߔࠆ㧚. േ⊛ߥ㔚ሶห⾼ࡑࠤ࠶࠻ߦ߅ߌࠆឭ៤ᒻᚑᡰេ. 3.
(10) ߹ߚ㧘ࠗࡦ࠲ࡀ࠶࠻ߢⴕࠊࠇࠆ㔚ሶขᒁߪෳട⠪߇ᤨ㑆ߦ᧤❈ߐࠇࠆߥߊ ฦߦ࠻࠶ࠤࡑߢࠣࡦࡒࠗ࠲ߥ↱⥄߇ޘෳട㧛ㅌߔࠆ߇ߢ߈ࠆ㧚ᓥߞߡ㧘ෳട⠪ ੱᢙ߇േ⊛ߦᄌൻߔࠆ㧚ห⾼ߪ⾈ᚻੱᢙߦࠃߞߡ⾼ଔᩰ߇ቯߐࠇࠆߚ㧘 ᦨㆡߥឭ៤ᒻᚑࠍߔࠆߢേ⊛ߥෳടੱᢙߩᄌൻߪ㗴⸃ࠍ㕖Ᏹߦ࿎㔍ߦߔࠆⷐ ࿃ߢࠆߣ߃ࠆ㧚ߘߩߚ㧘ⅣႺߩᄌൻߦኻᔕߒߚឭ៤ᒻᚑᡰេ߇ᔅⷐߢࠆ㧚. ߩ⇐ଔᩰ⸳ቯߦኻᔕߒߚឭ៤ᒻᚑᡰេ. ᧄ⺰ᢥߢᛒ߁ห⾼ࡑࠤ࠶࠻ߪઍᦧ⽷ࠍ↪ߚห⾼ࡑࠤ࠶࠻ߢ㧘⾈ᚻ ߪⶄᢙߩᄁࠅᚻ߇ຠߔࠆห৻ߩ⒳㘃ߩຠߩਛ߆ࠄߥࠆߴߊല↪߇ᄢ߈ߊߥࠆ ຠࠍㆬᛯߒߡ⾼ߒߚ㧚ߒ߆ߒ㧘⾈ᚻߪ༵ߩޘᅢࠍᜬߞߡ߅ࠅ㧘ోߡߩຠߦ ኻߒߡห৻ߩଔ୯ⷰࠍᜬߚߥ߽ߩߢࠆ㧚ߘߎߢ㧘⾈ᚻߪోߡߩຠߦኻߒߡ ⇐ߩޘଔᩰࠍ⸳ቯߔࠆ㧚⇐ߩޘଔᩰ⸳ቯࠍߔࠆߎߣߢ⾈ᚻߪࠃࠅᏗᦸㅢࠅ ߩຠࠍ⾼ߒ߿ߔߊߥࠆ㧚߹ߚ㧘Ꮧᦸߩຠࠍଔߦ⾼ߒߚ႐วߪല↪ߩ୯߇ᄢ ߈ߊߥࠅ㧘⾈ᚻߩ༵ᅢ߇ല↪ߦᤋߐࠇࠆߎߣߦߥࠆ㧚⾈ߩޘᚻ߇ߘࠇߙࠇߩ ⽷ߦኻߒߡ⇐ߩޘଔᩰࠍ⸳ቯߔࠆߚ㧘ᦨㆡߥឭ៤ᒻᚑߪ㕖Ᏹߦ࿎㔍ߦߥࠆ㧚ߘ ߎߢ㧘⇐ଔᩰ⸳ቯߦኻᔕߒߚឭ៤ᒻᚑᡰេ߇ᔅⷐߢࠆ㧚. 1.3 ᧄ⺰ᢥߩ᭴ᚑ ᧄ⺰ᢥߢߪ㧘߹ߕ╙㧞┨ߢ㑐ㅪ⎇ⓥߦߟߡ⺑ߔࠆ㧚╙㧟┨ߢߪ㔚ሶห⾼ࡑ ࠤ࠶࠻ߦߟߡㅀߴࠆ㧚ઍᦧ⽷ࠍ↪ߚ㔚ሶห⾼ߦߟߡ␜ߒ㧘ታᤨ㑆ឭ៤ᒻ ᚑߦߟߡ⺑ߔࠆ㧚ߘߒߡ㧘ឭ᩺ߔࠆ㔚ሶห⾼ࡑࠤ࠶࠻ߦߟߡㅀߴࠆ㧚╙ 㧠┨ߢߪ㔚ሶห⾼ߦ߅ߌࠆឭ៤ᒻᚑࠕ࡞ࠧ࠭ࡓߦߟߡ⺑ߔࠆ㧚߹ߕឭ᩺ࠕ ࡞ࠧ࠭ࡓߩၮ␆ߢࠆㆮવ⊛ࠕ࡞ࠧ࠭ࡓߦߟߡ⺑ߒ㧘ᧄ㗴⸃ߩߚߦ․ ൻߒߚᯏ᭴ߦߟߡ⺑ߔࠆ㧚╙㧡┨ߢߪࠪࡒࡘ࡚ࠪࡦߦࠃࠆᧄࠕ࡞ࠧ࠭ࡓߩ ലᕈࠍ␜ߔ㧚╙㧢┨ߢᧄ⺰ᢥߩ߹ߣ㧘ᓟߩ⺖㗴ࠍㅀߴࠆ㧚. 4.
(11) ╙㧞┨ 㑐ㅪ⎇ⓥ 2.1 㑐ㅪ⎇ⓥ ᧄ┨ߢߪ㔚ሶขᒁߣឭ៤ᒻᚑᚻᴺߦ㑐ߔࠆ㑐ㅪ⎇ⓥࠍ␜ߒ㧘ᧄ⎇ⓥߣߩᏅ⇣ࠍ ࠄ߆ߦߔࠆ㧚ᧄ⎇ⓥߩ㑐ㅪ⎇ⓥߪએਅߩ▵ߦಽߌߡ␜ߔ㧚. 㔚ሶขᒁ. ឭ៤ᒻᚑᚻᴺ. ㆮવ⊛ࠕ࡞ࠧ࠭ࡓ. 㔚ሶขᒁߩ▵ߢߪㄭᐕߩࠗࡦ࠲ࡀ࠶࠻࡚ࠝࠢࠪࡦߦ߅ߌࠆ⸳⸘ߦ㑐ߔࠆ⎇ⓥ ࠍ␜ߒ㧘ᧄ⺰ᢥߢឭ᩺ߔࠆ㔚ሶห⾼ࡑࠤ࠶࠻ߣߩ㆑ࠍࠄ߆ߦߔࠆ㧚ឭ៤ᒻ ᚑᚻᴺߩ▵ߢߪ㧘ឭ៤ᒻᚑ㗴ࠍᛒ߁ઁᚻᴺߩ⎇ⓥࠍ⺑ߒ㧘ᧄᚻᴺߣߩᏅ⇣ࠍ⏕ ߦ␜ߔ㧚ㆮવ⊛ࠕ࡞ࠧ࠭ࡓߩ▵ߢߪㆮવ⊛ࠕ࡞ࠧ࠭ࡓߦ߅ߌࠆᒛ⊛ߥㆮવሶᠲ ᚻᴺࠍ⺑ߒ㧘ᧄࠕ࡞ࠧ࠭ࡓߦ߅ߌࠆᠲߣߩ㆑ࠍ␜ߔ㧚. 2.1.1 㔚ሶขᒁ ᧄ▵ߢߪ㔚ሶࡑࠤ࠶࠻ߩ⎇ⓥߦߟߡ⺑ߔࠆ㧚 ࡚ࠝࠢࠪࡦࠨࡃߦ AuctionBot ߇ࠆ㧚࡙ࠩߪ㧘ຠࠍᄁࠆߚߦࠝ㧙ࠢ. 5.
(12) ࡚ࠪࡦࠍ㐿ߊ㧚ᧄ࡚ࠝࠢࠪࡦߢߪ㧘ࠛࠫࠚࡦ࠻ߪ೨ߦቯߐࠇߚࡊࡠ࠻ࠦ࡞ߦ ၮߠ߈ᧅࠍⴕ߁㧚AuctionBot ߪ࡙ࠩ߇ࡑࠤ࠶࠻ߦࠛࠫࠚࡦ࠻↢ᚑߔࠆߚ ߩ API ࠍឭଏߒߡࠆ㧚 Kasbah ߪ㧘Web ߦࡑࠤ࠶࠻ࡊࠬࠍឭଏߒߡࠆ㧚࡙ࠩߪ㧘ࡑࠤ࠶࠻ ࡊࠬߢขᒁߔࠆߚߩ⥄ᓞ⊛ߥ⾈ᚻࠛࠫࠚࡦ࠻߿ᄁࠅᚻࠛࠫࠚࡦ࠻ࠍ ↢ᚑߢ߈ࠆ㧚Kasbah ߢߩขࠅᒁ߈ߪ㧘න⚐ߥࡊࡠ࠻ࠦ࡞ߦၮߠߡࠆ㧚 Yamamoto ࠄߪ GroupBuyAuction ࠍឭ᩺ߒߚ[17]㧚GroupBuyAuction ߪࠛࠫࠚ ࡦ࠻ࡌࠬߩ㔚ሶࡑࠤ࠶࠻ߢࠛࠫࠚࡦ࠻߇⥄േ⊛ߦฦ࡙ࠩߩޘ⋉ߩߚߦ ᷤࠍߔࠆ߽ߩߢࠆ㧚⾈ᚻࠛࠫࠚࡦ࠻ߪ⋉ߩᄢ߈ଔߥଔᩰߢ⾼ߢ߈ࠆ ឭ៤ࠍ᭴ᚑߢ߈ࠆ㧚ᧄ⎇ⓥߣߩ㆑ߪ GroupBuyAuction ߪࠛࠫࠚࡦ࠻ࠍ↪ߚ⾈ ᚻⷞߩޘὐ߆ࠄߚឭ៤ᒻᚑࠪࠬ࠹ࡓߢࠆߩߦኻߒ㧘ᧄࠕ࡞ࠧ࠭ࡓߪࡑࠤ ࠶࠻߆ࠄߚ㧘⾈ᚻోࠍᷰߒߡోߩ⋉߇ᦨᄢߦߥࠆឭ៤ᒻᚑࠍ⋡⊛ߣߒ ߡࠆ㧚 Layton-Brown ࠄߪ BiddingClub ࠍឭ᩺ߒߚ[8]㧚BiddingClub ߪࡊ࡚ࠝࠢࠪࡦ ߢ㧘ࠛࠫࠚࡦ࠻߇ࠄ߆ߓᧅࠍߔࠆߎߣߢᧄᧅᤨߦ⋉ࠍ⏕ߔࠆ߽ߩߢ ࠆ㧚ⶄᢙ⽷ߩ࡚ࠝࠢࠪࡦࠍቢ⽷߅ࠃ߮ઍᦧ⽷ߦ߅ߡⴕ߁႐วߩലᕈ߇␜ߐࠇ ߡࠆ㧚ᧄ⎇ⓥߣߩ㆑ߪ㧘BiddingClub ߇ࡊ࡚ࠝࠢࠪࡦࠍⴕߞߡ⋉ࠍ⏕ߒ ߡࠆߩߦኻߒ㧘ᧄࠕ࡞ࠧ࠭ࡓߪห⾼ࠨࠗ࠻ߦኻߒߡታᤨ㑆ߢߩ㗴⸃ࠍน ⢻ߣߒߡࠆ㧚. 2.1.2 ឭ៤ᒻᚑᚻᴺ ᧄ▵ߢߪ᭽ߥޘឭ៤ᒻᚑᚻᴺߦߟߡߩ⎇ⓥࠍ⺑ߔࠆ㧚 Sen ࠄߪ Order Based Genetic Algorithm (OBGA)ࠍឭ᩺ߒߚ[14]㧚OBGA ߪㆮવ ⊛ࠕ࡞ࠧ࠭ࡓࡌࠬߩត⚝ࠕ࡞ࠧ࠭ࡓߢ㧘ߎߎߢㆮવ⊛ࠕ࡞ࠧ࠭ࡓߦࠃࠆᦨㆡ ឭ៤ᒻᚑߩലᕈ߇␜ߐࠇߡࠆ㧚ߒ߆ߒᧄ⎇ⓥߣㆡ↪ߔࠆ㗴ߩᕈ⾰߇ᄢ߈ߊ⇣ߥ ࠆ㧚Sen ࠄߩឭ៤ᒻᚑ[15]ߪ࿕ቯ⊛ߥࡔࡦࡃߦࠃࠆᦨㆡឭ៤ᒻᚑࠍ⋡⊛ߣߒߡࠆ߇ 㔚ሶห⾼ߪࡔࡦࡃߩᢙߪേ⊛ߦᄌൻߔࠆ㧚߹ߚ㧘⾈ᚻߩ⇐ଔᩰ⸳ቯߦੱᏅ ߇ࠆߣ߁․ᓽࠍᜬߞߡࠆ㧚㔚ሶห⾼ߦ߅ߌࠆ⾈ᚻห჻ߩᦨㆡឭ៤ᒻᚑߪ ࠃࠅⶄ㔀ߥ㗴ߢࠆߣ߃ࠆ㧚ᓥߞߡ Sen ࠄߩឭ᩺ߔࠆᚻᴺߢߪᧄ㗴ࠍ⸃ߔࠆ. 6.
(13) ߪ᧪ߥ㧚. 2.1.3 ㆮવ⊛ࠕ࡞ࠧ࠭ࡓ ᧄ▵ߢߪㆮવ⊛ࠕ࡞ࠧ࠭ࡓߦ߅ߌࠆᒛ⊛ᚻᴺߩ⎇ⓥߦߟߡ⺑ߔࠆ㧚ㆮવ⊛ ࠕ࡞ࠧ࠭ࡓߪ↢‛ㅴൻࠍᮨߒߚត⚝ࠕ࡞ࠧ࠭ࡓߢࠆ㧚ㆮવ⊛ࠕ࡞ࠧ࠭ࡓߪၮ ᧄ⊛ߦౣ↢⓭ὼᄌ⇣ߩਃߟߩㆮવ⊛ࠝࡍ࠹ࠖࡦࠣߢ᭴ᚑߐࠇߡࠆ㧚ㆮ વ⊛ࠝࡍ࠹ࠖࡦࠣߪߎࠇ߹ߢߦ᭽ߥޘᡷ⦟߇ߥߐࠇ㧘⸃ߔࠆ㗴ߦࠊߖߡല ₸ߩࠃᣇᴺ߇⎇ⓥߐࠇߡ߈ߚ㧚 Tanese ࠄߪ Distributed Genetic Algorithm ࠍឭ᩺ߒߚ[13]㧚Distributed Genetic Algorithm ߪㆮવሶ㓸࿅ࠍಽᢔߒߡṶ▚ࠍⴕ߁ߢ㛐ߒߩᄙ㗴ߦ߅ߡ߽ዪᚲ ⸃ߦ㒱ࠆߎߣߥߊ⸃ࠍត⚝ߔࠆ߇᧪ࠆࠍ␜ߒߚ㧚ᧄ⎇ⓥߣߩ㆑ߪㆮવߒࠀ㓸 ࿅ࠍಽᢔߐߖࠆ⌕⋡ὐߩ㆑ߢࠆ㧚Tanese ࠄߪㆮવሶ㓸࿅ࠍዊߐߥࠣ࡞ࡊߦಽ ߌߡṶ▚ߔࠆߢ㛐ߒߩᄙ㗴ߢ߽ㆮવሶోߡ߇ዪᚲ⸃ߦ᧤ߔࠆࠍ㒐ߛ㧚ᧄ ⎇ⓥߢߪಽᢔߒߚㆮવሶߦߘࠇߙࠇᓎഀࠍਈ߃㧘㗴ᄌൻᤨߦ߽ㅪ⛯⊛ߥ⸃ត⚝ࠍน ⢻ߣߒߚ㧚 Syswerda ࠄߪ Uniform Crossover in Genetic Algorithm ࠍឭ᩺ߒߚ[16]㧚Uniform Crossover in Genetic Algorithm ߪ 0-1 ߢߐࠇㆮવ⊛ࠕ࡞ࠧ࠭ࡓߦ߅ߡല₸ ࠃᴺߢࠆ㧚ᧄ⎇ⓥߣߩ㆑ߪ⸃ߔࠆ㗴ߣߘࠇߦ߁ㆮવሶߩ㆑߆ ࠄല₸ߩࠃᴺߩ㆑ߢࠆ㧚ᧄ⎇ⓥߦ߅ߌࠆ⥌ᱫㆮવሶᛥߪᧄ㗴․ ߩ⥌ᱫㆮવሶ⊒↢ࠍᅹߍࠆ㧚. 2.2 ᧄ⎇ⓥߩ․⦡ ᧄ⎇ⓥߪઍᦧ⽷ࠍ↪ߚ㔚ሶห⾼ࡑࠤ࠶࠻ߦ߅ߌࠆ⾈ᚻห჻ߩᦨㆡឭ៤ᒻ ᚑࠍᡰេߔࠆᯏ᭴ࠍ᭴▽ߔࠆ㧚ઍᦧ⽷ࠍ↪ߚห⾼ߪ߹ߢߦߥࡑࠤ࠶࠻ߢ ࠅ㧘ᧄࡑࠤ࠶࠻ߦ߅ߌࠆ⾈ᚻห჻ߩឭ៤ᒻᚑߪࡑࠤ࠶࠻᭴▽ߩߢㆱߌࠄࠇ ߥ㗴ߢࠆ㧚 ߹ߚ㧘ᧄ⎇ⓥߩឭ៤ᒻᚑߪࡑࠤ࠶࠻߆ࠄߚᦨㆡߥឭ៤ᒻᚑߢࠅ㧘⾈ߩޘ ᚻ߇⋉ߩߚߦឭ៤ᒻᚑߔࠆߩߢߪߥ㧚. 7.
(14) ᧄឭ᩺ࠕ࡞ࠧ࠭ࡓߪᧄឭ៤ᒻᚑ㗴ࠍ⸃ߔࠆߚߦ⸳⸘ߐࠇߡࠆ㧚․ߦታᤨ 㑆ߢߩឭ៤ᒻᚑߪ㕖Ᏹߦ࿎㔍ߥ㗴ߢࠅ㧘ᧄࠕ࡞ࠧ࠭ࡓߪઁߩࠕ࡞ࠧ࠭ࡓߢߪ ࿎㔍ߥታᤨ㑆ឭ៤ᒻᚑࠍน⢻ߣߒߡࠆ㧚. 8.
(15) ╙㧟┨ 㔚ሶห⾼ࡑࠤ࠶࠻ߦ߅ߌࠆ ታᤨ㑆ឭ៤ᒻᚑ 3.1 ઍᦧ⽷ࠍ↪ߚ㔚ሶห⾼ ห⾼ߣߪ㧘ᄁࠅᚻ߇ຠߒߚන৻ߩຠࠍ৻ᐲߦⶄᢙߩ⾈ᚻ߇⾼ߔࠆข ᒁߢࠆ㧚⾈ᚻߪ߹ߣ߹ߞߚᢙߩຠࠍ⾼ߔࠆߢ㧘ࠃࠅනଔߢຠࠍ⾼ ߔࠆ߇᧪ࠆ㧚ᄁࠅᚻߪ߹ߣ߹ߞߚᐶࠍಣಽߔࠆ߇᧪ࠆߣ߁ࡔ࠶࠻߇ ࠆ㧚 ࠗࡦ࠲ࡀ࠶࠻ࠍ↪ߚห⾼ߪ㧘ᕆㅦߦᚑ㐳ߒߡࠆ㔚ሶขᒁߦ߅ߌࠆࡑ ࠤ࠶࠻ࡊࠬߩ৻ᒻᘒߢ㧘ᵈ⋡ࠍ㓸ߡࠆ㧚ࠗࡦ࠲ࡀ࠶࠻ߦ߅ߌࠆห⾼ߩ ὐߪ㧘߅㕙⼂ߩߥਇ․ቯᄙᢙߩ⾈ᚻ߇ࠣ࡞ࡊᒻᚑߔࠆߢߦ⾼ߔ ࠆࠃࠅଔᩰߢຠࠍ⾼ߔࠆߎߣ߇᧪ࠆὐߢࠆ㧚⾈ᚻߪࠆᤨὐߢߘࠇߙ ࠇߩຠߦኻߒ⾈ᚻ߇ੱෳടߒߡࠆ߆ࠍᏱߦ㑛ⷩߔࠆ߇᧪ࠆ㧚ᄁࠅᚻߪ߹ ߣ߹ߞߚᢙߩຠࠍḰߒ㧘ຠࠍḰߒ㧘৻ᐲߩขᒁߢ⾈ᚻߦࠃࠅ⾼ߐࠇࠆᢙ ߦᔕߓߚຠߩනଔࠍឭ␜ߔࠆ㧚৻⥸ߦ㧝ߩࠃ߁ߥ࠹ࡉ࡞ߦࠃࠅຠߩ⽼ᄁᢙߦ ᔕߓߚනଔ߇ឭ␜ߐࠇࠆ㧚߃߫ߦ⾼ߔࠆߣଔᩰ߇㧡㧜㧜㧜ߩຠ‛߽⾈ᚻ ߇㧟ੱ㓸߹ࠅ⾼ߔࠇ߫⾼㊄㗵ߪ㧠㧤㧜㧜ߣߥࠅ㧘㧡㧜㧜㧜㧙㧠㧤㧜㧜㧩㧞㧜㧜 ߆ࠄ㧘ߦ⾼ߔࠆࠃࠅ㧞㧜㧜ଔᩰߢ⾼ߢ߈ࠆ㧚⾈ᚻ߇㧣ੱ㓸߹ࠅข ᒁߒߚ႐วଔᩰߪ㧟㧤㧜㧜ߢ㧡㧜㧜㧜㧙㧟㧤㧜㧜㧩㧝㧞㧜㧜ߣߥࠅߦ⾼ ߔࠆࠃࠅ㧝㧞㧜㧜߽ߊ⾼ߢ߈ࠆ㧚⾈ᚻߪ㧘ឭ␜ߐࠇߚ࠹ࡉ࡞ߣห⾼ࠍ Ꮧᦸߔࠆ⾈ᚻੱᢙߩੑߟߩᖱႎ߆ࠄ⾼ߔࠆ߆ุ߆ࠍ್ᢿߔࠆ㧚 㧘ᄙߊߩห⾼ࠨࠗ࠻ߦ߅ߡⶄᢙߩᄁࠅᚻ߇ห৻߽ߒߊߪ㘃ૃߒߚຠࠍ. 9.
(16) ᛒߞߡࠆ㧚ห৻ߩຠߢߞߡ߽ᄁࠅᚻߦࠃߞߡଔᩰ߇ᄢ߈ߊ⇣ߥࠆ႐ว߽ࠆ㧚 ⾈ᚻߩෳടੱᢙ㒢߿ෳടੱᢙߦࠃࠆ⽼ᄁଔᩰߩᄌൻࠍ⠨ᘦߦࠇࠇ߫㧘⾈ᚻߦ ߣߞߡෳടߔࠆ࠲ࠗࡒࡦࠣ߿ෳടߔࠆࠣ࡞ࡊࠍቯߔࠆߥߤߩᗧᕁቯߪ㊀ⷐߥ 㗴ߛߣ߃ࠆ㧚߹ߚ㧘ⶄᢙߩᄁࠅᚻ߇㘃ૃߒߚຠࠍห⾼ߢᛒ߁႐ว㧘⾈ᚻ ߇ಽᢔߒߡߒ߹ᄢ߈ߥࠣ࡞ࡊߩᒻᚑ߇ߢ߈ߡߥ⁁ᴫ߇ߺࠄࠇࠆ㧚․ߦ㧘ࠗࡦ ࠲ࡀ࠶࠻ߢߪᄁࠅᚻ߇ᢔߒߡࠆߚ⾈ᚻ߇ಽᢔߒ߿ߔߊ㧘ࠗࡦ࠲ࡀ࠶࠻ ߦ߅ߌࠆห⾼ߩὐߢࠆ㧘㕙⼂ߩߥ⾈ᚻ߇ࠣ࡞ࡊࠍᒻᚑߢ߈ࠆߣ߁ ὐ߇↢߆ߐࠇߡߥ㧚ߎߩߚࠆ⾈ᚻࠣ࡞ࡊߦߣߞߡߪචಽߥෳട⠪ߦߥࠄ ߕ㧘ຠࠍߊ⾼ߢ߈ߥߎߣ߇ࠆ㧚. 3.1 ଔᩰ࠹ࡉ࡞. 販売個数 1-2 3-4 5-6 7-8. 単価 5,000 4,800 4,500 3,800. ઍᦧ⽷ࠍ↪ߚห⾼ߣߪ㧘⸥ߩᗧᕁቯ߿⾈ᚻߩಽᢔߥߤߩ㗴ࠍ⸃ߔ ࠆขᒁᒻᘒߢࠆ㧚ਥ⠪ߪຠߐࠇߚຠࠍࠞ࠹ࠧߏߣߦಽ㘃ߒ㧘⾈ᚻߦ ␜ߔࠆ㧚߽ߒ㧘⾈ᚻߦߣߞߡⶄᢙߩຠߩ߁ߜߤࠇࠍ⾼ߒߡ߽߆߹ࠊߥߥࠄ߫㧘 ࠆ⾈ᚻ߇ઁߩ⾈ᚻࠣ࡞ࡊߦ⛔วߐࠇࠆߎߣߢࠃࠅଔߦ⾼ߢ߈ࠆ㧚࿑ 1 ߦ ␜ߐࠇߚઍᦧ⽷ࠍ↪ߚห⾼ߢߪ㧘ຠ A㧘ຠ B㧘ຠ C ߇หߓࠞ࠹ࠧߩ ⽷ߢࠅ㧘ෳടߔࠆ⾈ᚻߪߤࠇࠍ⾼ߒߡ߽ࠃ߽ߩߣߔࠆ㧚. 10.
(17) ࿑ 3.1 ઍᦧ⽷ࠍ↪ߚห⾼. 11.
(18) ᄁࠅᚻߪߘࠇߙࠇຠߒߚຠߦ㧘ຠᢙߣߘߩߣ߈ߩනଔߩ㑐ଥࠍ␜ߒߚ࠹ࡉ ࡞ࠍਥ⠪ߦឭߔࠆ㧚⾈ᚻߪ⇐ଔᩰ㧔reservation price㧕ࠍਥ⠪ߦឭ ߔࠆ㧚⇐ଔᩰߣߪ⾈ᚻ߇ࠆຠߦᡰᛄߞߡ߽ࠃߣ⠨߃ࠆᦨ㜞ଔᩰߢࠆ㧚એ ߩ᧦ઙ߆ࠄ⾈ᚻోຬߩല↪ߩว⸘୯߇ᦨᄢߦߥࠆࠃ߁ߦຠߦ⾈ᚻࠍᝄࠅಽ ߌࠆᦨㆡߥ⚵ߺวࠊߖࠍត⚝ߔࠆ߽ߩߢࠆ㧚ߎࠇࠍᦨㆡᝄࠅಽߌ㗴ߣ߱㧚ࠆ ຠߪනଔ߇㧡㧜㧜㧜ߢࠆ㧚⾈ᚻ߇㧞㨪㧡ੱߢࠆ႐ว㧘ຠߩනଔߪ㧠㧜㧜 㧜ߣߥࠅ㧘ߦ⾼ߔࠆࠃࠅ㧝㧜㧜㧜ߊ⾼ߔࠆߎߣ߇ߢ߈ࠆ㧚⾈ᚻ߇㧢 ੱߩ႐วߥࠄනଔߪ㧟㧜㧜㧜ߣߥࠅ㧘ߦ⾼ߔࠆࠃࠅ㧞㧜㧜㧜ߊ⾼ߢ߈ ࠆ㧚ߎߩຠߩ⾼ࠍᏗᦸߔࠆ⾈ᚻ㧭߇ሽߔࠆ㧚⾈ᚻ㧭ߩ⇐ଔᩰࠍ㧟㧡㧜㧜 ߣߔࠆ㧚ຠߩଔᩰ߇⇐ଔᩰࠃࠅ㜞႐ว㧘⾈ᚻߪ⾼ߒߥ㧚ߎߎߢߎߩ ຠߦߔߢߦ㧡ੱߩ⾈ᚻ߇ෳടߒߡࠇ߫㧘⾈ᚻ㧭߇ෳടߔࠆߎߣߦࠃߞߡߎߩ ຠߩනଔߪ㧟㧜㧜㧜ߦߥࠅ⾼ߔࠆߎߣ߇ߢ߈ࠆ㧚ᧄ⺰ಽߢߪ✢ᒻല↪ࠍቯߔࠆ㧚 ⾈ᚻ㧭ߩ⇐ଔᩰߪ㧟㧡㧜㧜ߥߩߢ⾈ᚻ㧭ߩല↪ߪ㧡㧜㧜ߣߥࠆ㧚৻ᣇ㧘߽ ߒߎߩຠߦ㧠ੱߒ߆⾈ᚻ߇ߟߡߥ߆ߞߚ႐ว㧘⾈ᚻ㧭߇ෳടߒߡ߽නଔߪ 㧠㧜㧜㧜ߩ߹߹ߢࠆ㧚⾈ᚻ㧭ߦߣߞߡ⇐ଔᩰࠃࠅຠߩଔᩰ߇㜞ߩߢߎߩ ᤨὐߢߪෳടߒߥ㧚. 12.
(19) ࿑ 3.2 ឭ៤ᒻᚑ A. ࿑ 3.3 ឭ៤ᒻᚑ B. 13.
(20) 3.2 ታᤨ㑆ឭ៤ᒻᚑ ࠗࡦ࠲ࡀ࠶࠻ߩขᒁߪᤨ㑆߿႐ᚲߦ㒢ߐࠇࠆߎߣߥߊਇ․ቯᄙᢙߩੱ㑆߇ ෳടߢ߈ࠆߣ߁ὐ߇ࠆ㧚ห⾼ߪᄙᢙߩ⾈ᚻ߇ߟߊ߶ߤଔߦ⾼ߢ߈ࠆ ߚ㧘ਇ․ቯᄙᢙߩੱ㑆߇ෳടߢ߈ࠆߣ߁ὐߪ⾈ᚻߦߣߞߡᄢ߈ὐߢࠆ ߣ߃ࠆ㧚ߒ߆ߒਇ․ቯᄙᢙߩᄁࠅᚻ߿⾈ᚻ߇⥄↱ߦෳടߢ߈ࠆߣ߁ߎߣߪਇⷙ ೣߥⅣႺߩᄌൻࠍ↢㧚ห⾼ߪ⾈ᚻੱᢙߦࠃߞߡຠߩනଔ߇ᄌൻߔࠆߚ㧘 ⾈ᚻੱᢙߩჇᷫߪోߡߩ⾈ᚻߩ⾼ຠଔᩰ߇ᄌേߔࠆᄾᯏߣߥࠆ㧚 ߹ߚ㧘ᣂߒᄁࠅᚻ߇ෳടߒߚ႐ว㧘ోߡߩ⾈ᚻߪㆬᛯ⢇߇Ⴧ߃ࠆߎߣߦߥࠆ㧚 ߎߩ႐วࠃࠅ᧦ઙߩࠃᄁࠅᚻߦߟߊ߶߁߇ല↪ߩว⸘߇ᄢ߈ߊߥࠆ㧚ߘߒߡ㧘⾈ ᚻੱᢙ߇ᄁࠅᚻߩᐶᢙߦ㆐ߒߚߣ߈㧘߹ߚߪᄁࠅᚻ߇⸳ቯߒߚ✦ಾᤨ㑆߇᧪ߚߣ߈ ߦߘߩᄁࠅᚻߣ⾼ߔࠆ⾈ᚻߪߎߩห⾼ขᒁࠍᚑ┙ߐߖߡ⚳߃ࠆߎߣߦߥࠆ㧚 ࿑ 3.4 ߦ㔚ሶห⾼ࡑࠤ࠶࠻ߩᤨ㑆⚻ㆊࠍ␜ߔ㧚࿑ 3.4 ߩࠃ߁ߦᤨ㑆ߩᵹࠇ ߦኻߒߡቯ߹ߞߡߥ࠲ࠗࡒࡦࠣߢ⾈ᚻߪෳട㧛ㅌߔࠆ㧚߹ߚ㧘ᄁࠅᚻߪਇⷙ ೣߥ࠲ࠗࡒࡦࠣߢࡑࠤ࠶࠻ߦෳടߒ㧘⸳߇ޘቯߒߚ⥄↱ߥ࠲ࠗࡒࡦࠣߢຠߩ✦ ಾᤨ㑆ࠍㄫ߃ࠆ㧚ᄁࠅᚻ߇✦ಾᤨ㑆ࠍㄫ߃ࠆߣ߈㧘✦ಾᤨ㑆ࠍㄫ߃ࠆᄁࠅᚻߩຠ⾼ ࠍ੍ቯߒߡߚ⾈ᚻࠣ࡞ࡊߪᄁࠅᚻߣขࠅᒁ߈߇ᚑ┙ߔࠆߦߥࠆ㧚ߎߩࠃ߁ ߦ㧘ታᤨ㑆ߢߩ㔚ሶห⾼ߪേ⊛ߦෳടੱᢙ߇ᄌൻߔࠆ߇੍ᗐߐࠇࠆ㧚 ࿑ 3.5 ߆ࠄ࿑ 3.11 ߦౕ⊛ߥታᤨ㑆ឭ៤ᒻᚑࠍ␜ߔ㧚. 14.
(21) ࿑ 3.4 㔚ሶห⾼ࡑࠤ࠶࠻ߩᤨ㑆⚻ㆊ. 15.
(22) ࿑ 3.5 ታᤨ㑆ឭ៤ᒻᚑ 1. ࿑ 3.6 ታᤨ㑆ឭ៤ᒻᚑ 2. 16.
(23) ࿑ 3.7 ታᤨ㑆ឭ៤ᒻᚑ 3. ࿑ 3.9 ታᤨ㑆ឭ៤ᒻᚑ 4. 17.
(24) ࿑ 3.10 ታᤨ㑆ឭ៤ᒻᚑ 5. ࿑ 3.11 ታᤨ㑆ឭ៤ᒻᚑ 6. 18.
(25) ࿑ 3.12 ታᤨ㑆ឭ៤ᒻᚑ 7. 19.
(26) ⾈ᚻߪⅣႺ߇ᄌൻߔࠆߏߣߦᣂߒ᧦ઙ߆ࠄല↪߇ᄢ߈ߊߥࠆࠃ߁ߦຠߩㆬ ᛯࠍᒝࠄࠇࠆ㧚ਇ․ቯᄙᢙߩੱ㑆߇ෳടߔࠆ㔚ሶขᒁߪᄁࠅᚻ㧘⾈ᚻੱᢙߣ߽ ߦᄢⷙᮨߣߥࠅ㧘ߘߩ⚵ߺวࠊߖߩᢙߪ㕖Ᏹߦᄢ߈ߊߥࠆ㧚ߘߩ⚿ᨐචಽߥࠣ࡞ࡊ ᒻᚑߪ࿎㔍ߢࠆߣ߃ࠆ㧚ߘߎߢⅣႺߩᄌൻߦኻᔕߢ߈ࠆታᤨ㑆ࠣ࡞ࡊឭ៤ᒻᚑ ࠍᡰេߔࠆᯏ᭴߇ᔅⷐߢࠆ㧚. 20.
(27) ╙㧠┨ ㆮવ⊛ࠕ࡞ࠧ࠭ࡓࠍ↪ߚ ታᤨ㑆ឭ៤ᒻᚑࠕ࡞ࠧ࠭ࡓ 4.1 ㆮવ⊛ࠕ࡞ࠧ࠭ࡓ ㆮવ⊛ࠕ࡞ࠧ࠭ࡓߪ㧘↢‛ㅴൻߩේℂߦ⌕ᗐࠍᓧߚࠕ࡞ࠧ࠭ࡓߢࠅ㧘⏕₸⊛ ត⚝ቇ⠌ᦨㆡൻߩ৻ᚻᴺߣߒߡ⍮ࠄࠇߡࠆ[7]㧚ㆮવ⊛ࠕ࡞ࠧ࠭ࡓߪᢙሼߩ㈩ ߢ⸃ࠍߒ㧘ᄢ㊂ߦ↪ᗧߐࠇߚㆮવሶ㓸࿅ࠍᠲߔࠆߢఝ⑲ߥ⸃ࠍ↢ߺߒ㧘 ㆮવሶ㓸࿅ࠍ⸃ߦ᧤ߐߖࠆ㧚 ㆮવ⊛ࠕ࡞ࠧ࠭ࡓߪ⍴ᤨ㑆ߢ NP 㗴ࠍ⸃ߔࠆ߇ߢ߈㧘ೋᦼ⁁ᘒߦଐሽߔ ࠆߎߣߥߊ⸃ត⚝ࠍߔࠆߎߣ߇᧪ࠆ㧚߹ߚ㧘ㆮવሶ㓸࿅ߩᠲ㧔ㆮવ⊛ࠝࡍ࠹ ࠖࡦࠣ㧕ߦ߅ߡዪᚲ⸃ߦ᧤ߔࠆࠍ㒐ߋ߇น⢻ߥߚ㧘ㆮવ⊛ࠕ࡞ࠧ࠭ࡓߪ 㛐ߒߩᄙ㗴ߦ߅ߡ߽ዪᚲ⸃ߦ㒱ࠆߎߣߥߊᦨㆡ⸃ࠍዉߔࠆࠍน⢻ߣߒߡ ࠆ[3][4][9]㧚. 4.2 ㆮવሶ ࠦ࠺ࠖࡦࠣߦߟߡ⺑ߔࠆ㧚GA ߢߩᦨㆡൻߦࠃߞߡὐߪㆮવሶߦࠃߞ ߡ⾈ᚻߦᝄࠅಽߌࠄࠇࠆຠߣຠߏߣߩනଔ㧘⾈ᚻߩല↪߇৻ᐲߦߢ߈ࠆ ߣ߁ὐ߇ࠆ㧚ⶄᢙߩዻᕈࠍ⹏ଔߒߥߌࠇ߫ߥࠄߥ႐ว߿㧘㒢᧦ઙ߇ⶄᢙߩዻ ᕈߦ߆ߌࠄࠇߡߚ႐วߢ߽ߔߴߡࠍ৻ᐲߦ⹏ଔߢ߈ࠆߣ߁ὐ߇ࠆ㧚ຠߩන ଔߪ⾈ᚻߩੱᢙߦࠃߞߡᄌൻߔࠆߚ㧘⾈ᚻోຬߦຠࠍᝄࠅಽߌࠆ߹ߢ⚵ߺว. 21.
(28) ࠊߖߦኻߔࠆ⹏ଔ߇ߢ߈ߥ㧚ߘߎߢ㧘⾈ᚻੱᢙߣหߓᄢ߈ߐߩ㈩ࠍ↪ᗧߒ㧘ฦ ⾈ᚻ߇ߤߩຠࠍᝄࠅಽߌࠄࠇࠆ߆ࠍߔࠆߎߣߢ㧘⸃㓸࿅ߩㆮવሶߣߔࠆ㧚. ࿑ 4.1 ㆮવሶ. ᧄ㗴ߦ߅ߌࠆ㧘⥌ᱫㆮવሶߦߟߡㅀߴࠆ㧚ᦨㆡᝄࠅಽߌ㗴ߦ߅ߡ㒢ߪ 㧝㧕ຠߪᔅߕ㒢ߒ߆ߥߚ㧘ߘࠇࠍ߃ࠆੱᢙߩ⾈ᚻ߇ߘߩຠࠍㆬ߱ߎ ߣߪߢ߈ߥ 㧞㧕⾈ᚻ߇⸳ቯߒߚ㒢ᐲ㗵ࠍ߃ࠆනଔߩຠࠍᝄࠅಽߌߡߪߌߥ ߩੑߟ߇ࠆ㧚 㧞㧕ߩ㒢ߦ㑐ߒߡߪ⾈ᚻ߇ᭂ┵ߦૐ㊄㗵ࠍ⸳ቯߒߚ႐ว⸃ߥߒߣߥࠅ㧘ขᒁ ߢ߈ߥ㧚GA ߦ߅ߡ⥌ᱫㆮવሶߪߘߩߩଔ୯ࠍ㧜ߦߔࠆߚ㧘⥌ᱫㆮવሶ߇ 㓸࿅ߩਛߢᄙᢙሽߔࠆߣ㧘චಽߥ⚿ᨐ߇ᓧࠄࠇߦߊ㧚ㆡ↪ߔࠆ㗴ߦࠃߞߡߪ㧝㧕 ߅ࠃ߮㧞㧕ߦ߅ߌࠆ㒢߆ࠄ㧘㗴ߩ⸃ⓨ㑆ߩᄢㇱಽࠍ⥌ᱫㆮવሶ߇භߡߒ߹߁႐ ว߽ࠆ㧚 ೋᦼㆬᛯ㓸࿅ߦ⥌ᱫㆮવሶ߇ᄙᢙ߹ࠇߚ႐ว㧘GA ߦࠃࠆត⚝ߪ߈ࠊߡዪᚲ⊛ ߣߥࠅ㧘චಽߥ⸃߇ᓧࠄࠇߥ㧚น⢻ߥ㒢ࠅೋᦼㆬᛯߢ㒢▸࿐ౝߩࠍㆬᛯߔࠆ㧚 ೋᦼㆬᛯߪࡦ࠳ࡓߦㆮવሶᐳߩ୯ࠍቯߒ㧘⾈ᚻోຬߦຠࠍᝄࠅಽߌߚㆮવሶ ࠍ߹ߞߚᢙߛߌᚑߔࠆ㧚GA ߦ߅ߡᦨೋߩᠲߢࠅ㧘ㆬᛯߐࠇߚ㓸࿅ߦኻߒ ฦ⒳ߩㆮવ⊛ࠝࡍ࠹ࠖࡦࠣࠍ↪ߡ⸃ࠍត⚝ߔࠆ㧚ೋᦼㆬᛯߢ⥌ᱫㆮવሶࠍᷫࠄ ߔߚ㧘㒢㧝㧕ߩ▸࿐ౝߢࠍㆬᛯߔࠆ㧚ࡦ࠳ࡓߦ㒢ࠍ߆ߌ㧘ࠬ࠻࠶ࠢ㒢 ࠍ߃ࠆຠࠍ⾈ᚻߦᝄࠅಽߌߥࠃ߁ߦߔࠆ㧚㒢㧞㧕ߦኻߒߡ⠨ᘦߔࠆߎߣߪ ߢ߈ߥ߇㧘ೋᦼㆬᛯߦ߅ߌࠆ⥌ᱫㆮવሶ⊒↢₸ࠍዊߐߊߔࠆߎߣ߇ߢ߈ࠆ㧚. 22.
(29) ߎߩ㗴ߦ߅ߌࠆ⹏ଔᣇᴺߦߟߡ⺑ߔࠆ㧚ߔߴߡߩ⾈ᚻߪ⇐ଔᩰࠍᜬߜ㧘 ຠߩଔᩰ߇⇐ଔᩰࠃࠅ㜞႐วขᒁߪᚑ┙ߒߥ㧚ขᒁ߇ᚑ┙ߔࠆߦߪຠଔᩰ ߇⇐ଔᩰએਅߢࠆᔅⷐ߇ࠆ㧚⾼ଔᩰߩว⸘ߩὐߢఝ⑲ߥㆮવሶ߇㧘ࠆ⾈ ᚻߩ෩ߒ㒢᧦ઙߢ⥌ᱫㆮવሶߦߥߞߡߒ߹߁ߩߪ⸃ត⚝ߩߢᄢ߈ߥ៊ᄬߢ ࠆ㧚ߘߎߢ㧘ㆮવ⊛ࠝࡍ࠹ࠖࡦࠣߣ߫ࠇࠆౣ↢㧘㧘⓭ὼᄌ⇣ߩ GA ߦ߅ߌ ࠆߩᠲᤨߩߩ⹏ଔᣇᴺߪ⾈ᚻߩනଔߩว⸘ߦߔࠆ㧚୯߇ዊߐㆮવሶ߶ ߤఝ⑲ߣ߁ߎߣߦߥࠆ㧚ߎߩ⹏ଔᴺߦ߅ߡ㧘㒢㧞㧕ߦᒁߞ߆߆ࠆㆮવሶ߽ଔ୯ ήߒߦߥࠆߎߣߥߊᰴઍߦ↢߈ᱷࠆน⢻ᕈࠍᜬߟߚ㧘ఝ⑲ߥㆮવሶࠍᶖߒࠆߎ ߣߥߊ㧘㓸࿅ߩᄙ᭽ᕈ⛽ᜬߩᓎഀ߽ᨐߚߔ㧚. 4.3 ߦࠃࠆ⥌ᱫㆮવሶߩᛥ ㆮવ⊛ࠝࡍ࠹ࠖࡦࠣߩਛߢ㧘ߪ GA ߦ߅ߡᦨ߽․ᓽ⊛ߥᠲߢࠆ㧚ߒ ߆ߒ㧘᥉ㅢߩ৻ὐࠍⴕߞߚ႐ว㧘㗴ߩᕈᩰ⥌ᱫㆮવሶࠍ↢ߺߒ㧘⸃ត⚝ߩ ല₸ࠍਅߍߡߒ߹߁ߎߣ߇ࠆ㧚⸘▚㊂ߪჇ߃ࠆ߇㧘ߦ߅ߡ⥌ᱫㆮવሶ߇↢߹ ࠇߥࠃ߁ߦ㧘એਅߩࠃ߁ߥᚻ㗅ߢࠍⴕ߁㧚₸ߦࠃߞߡࠍታⴕߔࠆ߆ุ߆ ࠍቯߔࠆ㧚ߩታⴕ߇ቯߐࠇߚੑߟߩߪߔߴߡߩὐߢߐࠇ㧘ⷫ ߣߣ߽ߦ৻ᐲࡊ࡞ߐࠇࠆ㧚ߘߩਛ߆ࠄ⹏ଔߩ㜞ࠍੑߟขࠅߒᰴߩઍߦ ↢߈ᱷࠄߖࠆߩߢࠆ㧚ߎࠇߦࠃࠅ㧘ᦨᖡߩ႐วߒߚ߇ߔߴߡ⥌ᱫㆮવሶߦ ߥߞߚߣߒߡ߽㧘ⷫ߇ᰴߩઍߦᒁ߈⛮߇ࠇࠆ㧚೨ઍߩ߇⥌ᱫㆮવሶߢߥ 㒢ࠅ㧘ߎߩࠝࡍ࠹ࠖࡦࠣߦࠃߞߡ⥌ᱫㆮવሶ߇ᰴઍߦฃߌ⛮߇ࠇࠆߎߣ߇ߥ ߣ߁ὐߢࠆ㧚ߒ߆ߒ㧘߇ቯߐࠇߚ႐ว㧘ᦨ߽⹏ଔߩ㜞߇ᰴઍߦ ฃߌ⛮߇ࠇࠆߚ㧘᧤ࠍᣧ㧘ዪᚲ⸃ߦ᧤ߔࠆⷐ࿃ߦߥࠆ႐ว߽ࠆ㧚₸߿㧘 ⓭ὼᄌ⇣₸ߩ⺞ᢛ߇ᔅⷐߦߥࠆ㧚. 23.
(30) ࿑ 4.2 ߦࠃࠆ⥌ᱫㆮવሶߩᛥ. 24.
(31) 4.4 ㆮવሶ㓸࿅ߩಽᢔ 㗴⸃ߦ GA ࠍ↪ࠆߩߪṶ▚ߩㆊ⒟ߢ↢߹ࠇࠆ⸃ࠍⅣႺᄌൻᓟߦ↪ߒ㧘 Ṷ▚㊂ࠍᷫߔࠆߚߢࠆ㧚ߒ߆ߒ㧘㗴ߩᕈ⾰ⅣႺᄌൻᓟߦోߡߩ⸃߇ᦨ ㆡ⸃ዉߦ↪ߢࠆߣߪ㒢ࠄߥ㧚ⅣႺ߇ᄌൻߒߚ႐วߦోߡࠍೋᦼൻߒߚ㓸࿅߆ ࠄᄢၞ⊛ߦᬌ⚝ߒߥ߅ߔ߶߁߇↪ߥ႐ว߽⠨߃ࠄࠇࠆ㧚ߘߎߢ㧘GA ߩೋᦼ㓸࿅ࠍ ੑߟߦಽߌ㧘ⅣႺᄌൻᤨߦೋᦼൻߔࠆ㓸࿅ߣṶ▚ㅜਛߦዉߐࠇߚ⸃ߩ㓸࿅ߣߔ ࠆ㧚ᄢၞ⊛ត⚝ߣዪᚲ⊛ត⚝ࠍหᤨߦⴕ߁ߎߣߢ㧘ዪᚲ⸃ߦ㒱ࠆߎߣࠍ㒐߉㧘Ṷ▚㊂ ߩᷫࠍⷞ㊁ߦࠇߡ⸃ߩត⚝ࠍⴕ߁ߎߣ߇ߢ߈ࠆ㧚. ࿑ 4.3 ㆮવሶ㓸࿅ߩಽᢔߩᔨ࿑. 25.
(32) ╙㧡┨ ታ㛎 5.1 ห⾼ߦ߅ߌࠆᦨㆡឭ៤ᒻᚑ ᧄ▵ߢߪઍᦧ⽷ࠍ↪ߚห⾼ࡑࠤ࠶࠻ߦ߅ߌࠆ⾈ᚻห჻ߩᦨㆡឭ៤ᒻᚑ 㗴ࠍឭ᩺ߔࠆࠕ࡞ࠧ࠭ࡓߢ⸃ߒ㧘ઁߩࠕ࡞ࠧ࠭ࡓߣᲧセߔࠆߢᧄࠕ࡞ࠧ࠭ ࡓߩ․㐳ࠍㅀߴࠆ㧚. 5.1.1 ห⾼ߦ߅ߌࠆᦨㆡឭ៤ᒻᚑ㗴 ᧄ▵ߢߪઍᦧ⽷ࠍ↪ߚห⾼ࡑࠤ࠶࠻ߦ߅ߌࠆ⾈ᚻห჻ߩᦨㆡឭ៤ᒻᚑ 㗴ߦߟߡ⺑ߒ㧘5.1 ▵ߩታ㛎ߦ↪ࠆ㗴ࠍ⺑ߔࠆ㧚 ᧄ㗴ߪᄁࠅᚻߩଔᩰ࠹ࡉ࡞ߣ⾈ᚻߩ⇐ଔᩰߦࠃߞߡቯߐࠇࠆ㧚৻ቯᢙߩ ᄁࠅᚻߪߘࠇߙࠇߩຠߦኻߒߡ⽼ᄁᢙߣනଔߩ㑐ଥࠍ␜ߒߚࠍឭ␜ߔࠆ㧚ߎࠇ ࠍଔᩰ࠹ࡉ࡞ߣ߁㧚߹ߚ㧘ᄁࠅᚻߪߘࠇߙࠇ߇ຠߦኻߒߡᡰᛄ߁ߩ᧪ࠆ㒢 ᐲ㗵ࠍឭ␜ߔࠆ㧚ߎࠇࠍ⇐ଔᩰߣ߁㧚ోߡߩ⾈ᚻߪ⇐ଔᩰએਅߩ㊄㗵ߢขᒁ ࠍᚑ┙ߐߖࠆᔅⷐ߇ࠆ㧚߹ߚ㧘⾈ᚻߪ⇐ଔᩰ߆ࠄታ㓙ߩ⾼ଔᩰࠍᒁߚ୯ࠍ ല↪ߣߒߡᓧࠆ㧚ขᒁଔᩰ߇⇐ଔᩰࠃࠅ߽ዊߐ߶ߤᓧࠄࠇࠆല↪ߪᄢ߈㧚 ᧄ㗴ߢߪోߡߩ⾈ᚻ߇⇐ଔᩰౝߢขࠅᒁ߈ࠍᚑ┙ߐߖ㧘ోߡߩ⾈ᚻߩല↪ ߩ୯߇ᦨᄢߦߥࠆ⾈ᚻห჻ߩឭ៤⚵ߺวࠊߖࠍዉߔࠆ㧚ᧄ⚵ߺวࠊߖ㗴ߪ NP 㗴ߢࠅ㧘ᦨㆡ⸃ߩዉߪ⸃ⓨ㑆ߩోត⚝એᄖߦᣇᴺ߇ሽߒߥ㧚⾈ᚻੱᢙࠍ m㧘ᄁࠅᚻੱᢙࠍ㨚ߣߔࠆߣ⸃ⓨ㑆 S ߩᄢ߈ߐߪએਅߩᑼߢቯ⟵ߐࠇࠆ㧚. 26.
(33) nm. S. 5.1.2 ᦨㆡឭ៤ᒻᚑ㗴ߩ․ᕈ߅ࠃ߮⸃ࠕ࡞ࠧ࠭ ࡓߩ․ᕈ ᧄ▵ߢߪᦨㆡឭ៤ᒻᚑ㗴ࠍ␜ߒ㧘ᧄ㗴ߩ․ᕈߣ⸃ࠕ࡞ࠧ࠭ࡓߩ㆑ࠍ␜ ߔ㧚 ᧄ▵ߢᛒ߁㗴ߪ⾈ᚻ 10㧘ᄁࠅᚻ 5 ߣߔࠆ㧚ੑߟߩ㗴ࠍ 5.1㧘 5.2 ߅ࠃ ߮ 5.3 ߦ␜ߔ㧚 5.1 ߅ࠃ߮ 5.2 ߪߘࠇߙࠇߩ㗴ߩᄁࠅᚻߩଔᩰ࠹ࡉ࡞ࠍ㧘 5.3 ߪߘࠇߙࠇߩ㗴ㅢߩ⾈ᚻߩ⇐ଔᩰࠍ␜ߒߡࠆ㧚. 5.1 ᄁࠅᚻߩଔᩰ࠹ࡉ࡞㧔㗴 a㧕 商品A 商品B 商品C 商品D 商品E 品数 単価 品数 単価 品数 単価 品数 単価 品数 単価 1 2,000 1-2 1,800 1 2,000 1-3 1,520 1 2,000 2 1,900 3 1,310 2 1,320 4-5 1,440 2-3 1,600 3 1,450 6 1,330 4-5 1,500. 27.
(34) 5.2 ᄁࠅᚻߩଔᩰ࠹ࡉ࡞㧔㗴 b㧕 商品A 商品B 商品C 商品D 商品E 品数 単価 品数 単価 品数 単価 品数 単価 品数 単価 1-4 1,700 1 2,000 1-4 2,000 1-3 1,520 1 2,000 5 1,310 2 1,900 5 1,350 4-5 1,400 2-3 1,600 3 1,450 6 1,300 4-5 1,500. 5.3 ⾈ᚻߩ⇐ଔᩰ 買い手 留保価格 買い手 留保価格 買い手A 1,700 買い手F 1,800 買い手Ｂ 1,650 買い手G 1,680 買い手Ｃ 1,310 買い手H 1,900 買い手D 1,550 買い手I 1,780 買い手E 1,720 買い手J 1,380. એߦ␜ߐࠇࠆੑߟߩᦨㆡឭ៤ᒻᚑ㗴ࠍឭ᩺ᚻᴺ㧘ోᬌ⚝㧘᰼ᒛࠅᴺߢṶ▚ߒ㧘 ߘߩ⚿ᨐࠍᲧセߔࠆ㧚 ឭ᩺ᚻᴺߦ↪ߡࠆㆮવ⊛ࠕ࡞ࠧ࠭ࡓߪ 200 200 ઍߢⴕ㧘₸ߪ 0.5㧘⓭ὼᄌ⇣₸ߪ 0.01 ߦ⸳ቯߒߚ㧚ోߡߩࡊࡠࠣࡓߪ JAVA ߢ㐿⊒ߒ㧘ࠪࡒࡘ ࡚ࠪࡦⅣႺߪ OS㧦WindowsXP㧘CPU㧦Celelon 1GHz㧘ࡔࡕ㧦256MB ߢⴕߞ ߚ㧚 ⾈ᚻߩല↪ߩว⸘୯ࠍ 5.4㧘Ṷ▚ᤨ㑆ࠍ 5.5 ߦ␜ߔ㧚. 28.
(35) 5.4 ⾈ᚻߩല↪ߩว⸘୯. 問題a 問題b. 提案手法 全検索 欲張り法 2,900 2,900 2,900 3,170 3,170 解なし. 5.5 Ṷ▚ᤨ㑆. 提案手法 2352ms. 全検索 14039ms. 欲張り法 18ms. 5.4 ࠃࠅ㧘᰼ᒛࠅᴺߪ㗴ߦࠃߞߡᦨㆡ⸃ࠍዉߔࠆߎߣ߽᧪ࠆ߇㧘㒢᧦ઙ ࠍḩߚߒߚ⸃߇⊒ߢ߈ߥ႐ว߽ሽߔࠆߎߣ߇ࠊ߆ࠆ㧚 5.5 ߢߪోᬌ⚝ߪઁߩត⚝ᴺߦᲧߴ㕖Ᏹߦᤨ㑆߇߆߆ࠆ߇ࠊ߆ࠆ㧚ࠗࡦ࠲ࡀ ࠶࠻ߩขࠅᒁ߈ߢߪࠃࠅᄙߊߩੱ㑆߇ࡑࠤ࠶࠻ߦෳടߔࠆ߇੍ᗐߢ߈ࠆ㧚ోᬌ ⚝ߪታ↪⊛ߥ⸃ᚻᲑߢߪߥߣ߃ࠆ㧚. 5.1.3 ࠕ࡞ࠧ࠭ࡓߩ⹏ଔ ᧄ▵ߢߪ 5.1.2 ▵ࠍ〯߹߃ߡ⸃ⓨ㑆ߩᄢ߈ߐ߇㆑߁㗴ߢឭ᩺ᚻᴺߣ᰼ᒛࠅᴺߩ⸃ ត⚝ᕈ⢻ࠍᲧセߒ㧘ឭ᩺ᚻᴺߩ↪ᕈࠍ␜ߔ㧚 ᧄ▵ߩታ㛎ߢᛒ߁㗴ߪ⾈ᚻ 10㧘ᄁࠅᚻ 5 ߩ㗴ߣ⾈ᚻ 11㧘ᄁࠅᚻ 6 ߩ㗴 ߢࠆ㧚ߘࠇߙࠇߩෳടੱᢙߩᦨㆡឭ៤ᒻᚑ㗴ࠍੂᢙߦࠃߞߡ 100 ᚑߒ㧘ឭ᩺ ᚻᴺ㧘ోᬌ⚝㧘᰼ᒛࠅᴺߦࠃߞߡ⸃ߒߚ㧚ోߡߩ㗴ߪ⾈ᚻోຬ߇⇐ଔᩰౝߢ ขࠅᒁ߈߇ᚑ┙ߔࠆ㧚 ឭ᩺ᚻᴺߦ↪ߡࠆㆮવ⊛ࠕ࡞ࠧ࠭ࡓߪ 200 200 ઍߢⴕ㧘₸ߪ. 29.
(36) 0.5㧘⓭ὼᄌ⇣₸ߪ 0.01 ߦ⸳ቯߒߚ㧚ోߡߩࡊࡠࠣࡓߪ JAVA ߢ㐿⊒ߒ㧘ࠪࡒࡘ ࡚ࠪࡦⅣႺߪ OS㧦WindowsXP㧘CPU㧦Celelon 1GHz㧘ࡔࡕ㧦256MB ߢⴕߞ ߚ㧚 ฦᚻᴺߩṶ▚ᤨ㑆ߩᐔဋࠍ 5.6 ߅ࠃ߮ 5.7 ߦ㧘ឭ᩺ᚻᴺߣ᰼ᒛࠅᴺߩṶ▚⚿ᨐ ߩᱜ╵₸ߩᲧセࠍ 5.8 ߅ࠃ߮ 5.9 ߦ␜ߔ㧚. 5.6 ᐔဋṶ▚ᤨ㑆㧦⾈ᚻ 10㧘ᄁࠅᚻ 5. 提案手法 2352ms. 全検索 14039ms. 欲張り法 18ms. 5.7 ឭ᩺ᚻᴺߣ᰼ᒛࠅᴺߩᱜ╵ᐲᲧセ㧦⾈ᚻ 10㧘ᄁࠅᚻ 5. 提案手法 欲張り法 最適解導出回数 22 9 適合解導出回数 51 14 解なし回数 27 77. 5.8 ᐔဋṶ▚ᤨ㑆㧦⾈ᚻ 11㧘ᄁࠅᚻ 6. 提案手法 2352ms. 全検索 585500ms. 30. 欲張り法 18ms.
(37) 5.9 ឭ᩺ᚻᴺߣ᰼ᒛࠅᴺߩᱜ╵ᐲᲧセ㧦⾈ᚻ 11㧘ᄁࠅᚻ 6. 提案手法 欲張り法 最適解導出回数 9 6 適合解導出回数 51 18 解なし回数 40 76. 5.6 ߅ࠃ߮ 5.8 ߆ࠄ߶ࠎߩዋߒߩෳടੱᢙߩჇടߢ߽ోᬌ⚝ߦ߆߆ࠆᤨ㑆߇ᩰ Ბߦᄢ߈ߊߥߞߡࠆߎߣ߇ࠊ߆ࠆ㧚ߘࠇߦᲧߴឭ᩺ᚻᴺ߿᰼ᒛࠅᴺߪṶ▚ᤨ㑆߇ᄌ ൻߒߥ㧚᰼ᒛࠅᴺߪ㕖Ᏹߦන⚐ߥࠕ࡞ࠧ࠭ࡓߩߚ⸃ⓨ㑆ߩᄢ߈ߐߦᲧߴṶ▚ᤨ 㑆ߩჇട߇㕖Ᏹߦዊߐߚߢࠆ㧚ឭ᩺ᚻᴺߪㆮવ⊛ࠕ࡞ࠧ࠭ࡓࠍࡌࠬߦߒߡ ࠆߚᢙ㨯ઍᢙߩ⸳ቯࠍᄌൻߒߥ㒢ࠅṶ▚ᤨ㑆ߪ࿕ቯߢࠆ㧚ߚߛߒ ᢙ㨯ઍᢙࠍ࿕ቯߔࠆߎߣߪត⚝⢻ജࠍ㒢ቯߒߡߒ߹߁ߢࠅ㧘⸃ⓨ㑆ߩᄢ߈ߐߦ ኻߒߡត⚝⢻ജ߇ዊߐߔ߉ࠆ႐วߪචಽߥ⸃߇ᓧࠄࠇߥ㧚 5.7 ߅ࠃ߮ 5.9 ߪឭ᩺ᚻᴺߣ᰼ᒛࠅᴺߩ⸃ត⚝⢻ജߩᏅࠍ␜ߒߡࠆ㧚ㆡว⸃ ߣߪᦨㆡߥ⚵ߺวࠊߖߢߪߥ߇⾈ᚻోຬ߇⇐ଔᩰౝߢ⾼ߢ߈ࠆឭ៤⚵ߺว ࠊߖߩߢࠆ㧚 5.7 ߢߪ᰼ᒛࠅᴺ߇ 23%ߒ߆㒢᧦ઙࠍḩߚߒߚ⚵ߺวࠊߖࠍዉ ߢ߈ߡߥߩߦኻߒឭ᩺ᚻᴺߢߪ 73%ㆡว⸃એߩ⸃ࠍዉߒߡࠆ㧚 5.9 ߢ ߽᰼ᒛࠅᴺߪ 24%ߒ߆㒢᧦ઙࠍḩߚߒߚ⚵ߺวࠊߖࠍዉߢ߈ߡߥߩߦኻߒ ឭ᩺ᚻᴺߢߪ 60%ㆡว⸃એߩ⸃ࠍዉߒߡࠆ㧚ߎߎߢ․╩ߔࠆߪ⾈ᚻ 11㧘 ᄁࠅᚻ 6 ߩ㗴ߢߪᦨㆡ⸃ዉഀว߇⾈ᚻ 10㧘ᄁࠅᚻ 5 ߩ㗴ࠃࠅ㕖Ᏹߦዊߐߊ ߥߞߡࠆὐߢࠆ㧚⸃ⓨ㑆߇ᄢ߈ߊߥࠆߢ⸃ត⚝߇ࠃࠅ࿎㔍ߦߥߞߡࠆߚߢ ࠆ㧚᰼ᒛࠅᴺߪ⸃ⓨ㑆ߩჇᄢߦኻߒߡ߶ߣࠎߤ⸃ត⚝⢻ജ߇ᄌൻߒߡߥ㧚ឭ᩺ ᚻᴺߢߪ㗴ߩᄢ߈ߐߦኻߒߡᢙ㨯ઍᢙߩ⸳ቯ୯ࠍᄌൻߐߖ㧘ࠃࠅ⸃ត⚝⢻ജ ࠍቯߐߖࠆᔅⷐ߇ࠆ㧚. 31.
(38) 5.2 ห⾼ߦ߅ߌࠆታᤨ㑆ឭ៤ᒻᚑ ᧄ▵ߢߪઍᦧ⽷ࠍ↪ߚห⾼ࡑࠤ࠶࠻ߦ߅ߌࠆ⾈ᚻห჻ߩታᤨ㑆ឭ៤ᒻᚑ 㗴ࠍឭ᩺ߔࠆࠕ࡞ࠧ࠭ࡓߢ⸃ߒ㧘ઁߩࠕ࡞ࠧ࠭ࡓߣᲧセߔࠆߢᧄࠕ࡞ࠧ ࠭ࡓߩ․㐳ࠍㅀߴࠆ㧚. 5.2.1 ห⾼ߦ߅ߌࠆታᤨ㑆ឭ៤ᒻᚑ㗴 ᧄ▵ߢߪઍᦧ⽷ࠍ↪ߚห⾼ࡑࠤ࠶࠻ߦ߅ߌࠆ⾈ᚻห჻ߩታᤨ㑆ឭ៤ᒻᚑ 㗴ߦߟߡ⺑ߒ㧘5.2 ▵ߩታ㛎ߦ↪ࠆ㗴ࠍ⺑ߔࠆ㧚 ᧄ㗴ߪᄁࠅᚻߩଔᩰ࠹ࡉ࡞ߣ⾈ᚻߩ⇐ଔᩰ㧘ෳട⠪ߩෳട࠲ࠗࡓ࠹ࡉ࡞ ߦࠃߞߡቯߐࠇࠆ㧚৻ቯᢙߩᄁࠅᚻߪߘࠇߙࠇߩຠߦኻߒߡ⽼ᄁᢙߣනଔߩ㑐 ଥࠍ␜ߒߚࠍឭ␜ߔࠆ㧚ߎࠇࠍଔᩰ࠹ࡉ࡞ߣ߁㧚߹ߚ㧘ᄁࠅᚻߪߘࠇߙࠇ߇ ຠߦኻߒߡᡰᛄ߁ߩ᧪ࠆ㒢ᐲ㗵ࠍឭ␜ߔࠆ㧚ߎࠇࠍ⇐ଔᩰߣ߁㧚ోߡߩ⾈ ᚻߪ⇐ଔᩰએਅߩ㊄㗵ߢขᒁࠍᚑ┙ߐߖࠆᔅⷐ߇ࠆ㧚߹ߚ㧘⾈ᚻߪ⇐ଔᩰ߆ ࠄታ㓙ߩ⾼ଔᩰࠍᒁߚ୯ࠍല↪ߣߒߡᓧࠆ㧚ขᒁଔᩰ߇⇐ଔᩰࠃࠅ߽ዊߐ߶ ߤᓧࠄࠇࠆല↪ߪᄢ߈㧚 ᧄ㗴ߢߪෳട⠪ߪࠄࠇߡߥ࠲ࠗࡒࡦࠣߢࡑࠤ࠶࠻ߦෳട㧛ㅌࠍߔࠆ㧚 ห⾼ߪෳട⠪ੱᢙߢ⾈ᚻߩ⾼ଔᩰ߇ᄌൻߔࠆߚേ⊛ߥੱᢙߩᄌൻߪᦨㆡ ߥឭ៤ᒻᚑࠍࠃࠅ࿎㔍ߦߔࠆ㧚. 5.2.2 ታᤨ㑆ឭ៤ᒻᚑ㗴ߩ․ᕈ߅ࠃ߮⸃ࠕ࡞ࠧ ࠭ࡓߩ․ᕈ ᧄ▵ߢߪታᤨ㑆ឭ៤ᒻᚑ㗴ࠍ␜ߒ㧘ᧄ㗴ߩ․ᕈߣ⸃ࠕ࡞ࠧ࠭ࡓߩ㆑ࠍ ␜ߔ㧚 ᧄ▵ߢᛒ߁㗴ߪ⾈ᚻ 11㧘ᄁࠅᚻ 6 ߣߔࠆ㧚㗴ࠍ 5.10㧘 5.11 ߅ࠃ߮. 32.
(39) 5.12 ߦ␜ߔ㧚 5.10 ᄁࠅᚻߩଔᩰ࠹ࡉ࡞ࠍ㧘 5.11 ߪ⾈ᚻߩ⇐ଔᩰࠍ㧘 5.12 ߪෳട⠪ߩ࠲ࠗࡓ࠹ࡉ࡞ࠍ␜ߒߡࠆ㧚. 5.10 ᄁࠅᚻߩଔᩰ࠹ࡉ࡞ 商品A 商品B 商品C 商品D 商品E 商品F 品数 単価 品数 単価 品数 単価 品数 単価 品数 単価 品数 単価 1-4 1,700 1 2,000 1-4 2,000 1-3 1,520 1 2,000 1-2 1,800 5 1,310 2 1,900 5 1,350 4-5 1,400 2-3 1,600 3-4 1,400 3 1,450 6 1,300 4-5 1,500. 5.11 ⾈ᚻߩ⇐ଔᩰ. 買い手 留保価格 買い手 留保価格 買い手A 1,700 買い手G 1,680 買い手Ｂ 1,650 買い手H 1,900 買い手Ｃ 1,310 買い手I 1,780 買い手D 1,550 買い手J 1,380 買い手E 1,720 買い手K 1,480 買い手F 1,800. 5.12 ห⾼ࡑࠤ࠶࠻ߩ࠲ࠗࡓ࠹ࡉ࡞. 時間（ sec） イベント 0 共同購入マーケット開始 6 買い手Kマーケットに参加 8 商品A締切 12 買い手Aマーケットから退出 15 共同購入マーケット終了. 33.
(40) એߦ␜ߐࠇࠆታᤨ㑆ឭ៤ᒻᚑ㗴ࠍឭ᩺ᚻᴺ㧘න⚐ㆮવ⊛ࠕ࡞ࠧ࠭ࡓ㧘᰼ᒛࠅ ᴺߢṶ▚ߒ㧘ߘߩ⚿ᨐࠍᲧセߔࠆ㧚 ឭ᩺ᚻᴺ߅ࠃ߮න⚐ㆮવ⊛ࠕ࡞ࠧ࠭ࡓߦ↪ߡࠆㆮવ⊛ࠕ࡞ࠧ࠭ࡓߩࡄࡔ ࠲ߪᢙ 200㧘ઍᢙ 200 ߢⴕ㧘₸ߪ 0.5㧘⓭ὼᄌ⇣₸ߪ 0.01 ߦ⸳ቯߒߚ㧚 ోߡߩࡊࡠࠣࡓߪ JAVA ߢ㐿⊒ߒ㧘ࠪࡒࡘ࡚ࠪࡦⅣႺߪ OS㧦WindowsXP㧘 CPU㧦Celelon 1GHz㧘ࡔࡕ㧦256MB ߢⴕߞߚ㧚 ฦࠕ࡞ࠧ࠭ࡓߩᤨ㑆ㆫ⒖ࠍ࿑ 5.1㧘ࡑࠤ࠶࠻⚳ੌᤨߩല↪ߩว⸘ࠍ 5.13 ߦ␜ ߔ㧚. ࿑ 5.1 ฦࠕ࡞ࠧ࠭ࡓߩᤨ㑆ㆫ⒖. 34.
(41) 5.13 ࡑࠤ࠶࠻⚳ੌᤨߩല↪ߩว⸘. 提案手法 単純GA 欲張り法. 2,770 2,200 0. ࿑ 5.1 ߆ࠄߘࠇߙࠇߩࠕ࡞ࠧ࠭ࡓߩ․ᓽ߇ࠊ߆ࠆ㧚න⚐ㆮવ⊛ࠕ࡞ࠧ࠭ࡓߪឭ ᩺ᚻᴺߣห᭽⍴ᤨ㑆ߢᦨㆡ⸃㧘߽ߒߊߪḰᦨㆡ⸃ߩዉ߇น⢻ߢࠆ㧚ߒ߆ߒߥ߇ࠄ ࡑࠤ࠶࠻㐿ᆎᓟ 6㧘8㧘12 ⑽ᓟߩෳട⠪ᢙᄌൻߩ⋥ᓟ㧘ዉߒߚ⸃߇࠶࠻ߐࠇ ࠆߚߦᦨೋ߆ࠄṶ▚ࠍߒߥ߅ߒߡࠆߎߣ߇ࠊ߆ࠆ㧚ෳട⠪ੱᢙᄌൻ߆ࠄචಽߥᤨ 㑆߇ࠇ߫ౣ߮ᦨㆡ⸃ߩዉ߽น⢻ߛ߇⍴ᤨ㑆ౝߢෳട⠪ᢙ㧘✦ಾᤨ㑆ࠍㄫ߃ࠆߣච ಽߥ⸃߇ᓧࠄࠇߥ߹߹ขࠅᒁ߈߇ᚑ┙߽ߒߊߪਇᚑ┙ߒߡߒ߹߁㧚ࡑࠤ࠶࠻㐿ᆎ ᓟ 8 ⑽ὐߢຠ A ߇✦ಾᤨ㑆ࠍㄫ߃ߡࠆ߇ߎߎߢචಽߥ⸃߇ᓧࠄࠇߡߥ㧚ߘ ߩ⚿ᨐ 5.13 ߢ߽ࠊ߆ࠆࠃ߁ߦࡑࠤ࠶࠻⚳ੌᤨߦല↪ߩว⸘୯߇චಽᄢ߈ߥ୯ߦ ߥߞߡߥ㧚 ᰼ᒛࠅᴺߪ㕖Ᏹߦ⍴ᤨ㑆ߢṶ▚ࠍ⚳ੌߐߖࠆ߇᧪ࠆ㧚ߒ߆ߒߥ߇ࠄត⚝⢻ജ߇ 㗴ߦଐሽߔࠆߚ㧘ⶄ㔀ߥ㗴ࠍ⸃ߢ߈ߥ㧚㔚ሶห⾼ߦ߅ߌࠆታᤨ㑆ឭ៤ ᒻᚑ㗴ߢߪෳടੱᢙ߇േ⊛ߦᄌൻߒߘߩㇺᐲ㗴߇ᄌൻߔࠆ㧚ᓥߞߡ㗴⸃⢻ജ ߇㗴ߦଐሽߔࠆ᰼ᒛࠅᴺߪታᤨ㑆ឭ៤ᒻᚑߦߪㆡߒߡߥߣ߃ࠆ㧚࿁ߩ㗴 ߢߪ 5.13 ࠍߡಽ߆ࠆࠃ߁ߦຠߩ✦ಾᤨ㑆㧘ࡑࠤ࠶࠻ߩ⚳ੌᤨ㑆ߦ߅ߡข ࠅᒁ߈ࠍᚑ┙ߐߖࠆ⾈ᚻߩឭ៤⚵ߺวࠊߖࠍዉߔࠆ߇᧪ߥ߆ߞߚ㧚. 5.2.3 ࠕ࡞ࠧ࠭ࡓߩ⹏ଔ ᧄ▵ߢߪታᤨ㑆ߢߩห⾼ࡑࠤ࠶࠻ߦ߅ߌࠆታᤨ㑆ឭ៤ᒻᚑ㗴ࠍឭ᩺ᚻᴺ㧘 න⚐ㆮવ⊛ࠕ࡞ࠧ࠭ࡓ㧘᰼ᒛࠅᴺߢ⸃ߒ㧘ߘࠇߙࠇߩ⸃ត⚝ᕈ⢻ࠍᲧセߒ㧘ឭ᩺ ᚻᴺߩ↪ᕈࠍ␜ߔ㧚. 35.
(42) ᧄ▵ߩታ㛎ߢᛒ߁㗴ߪએਅߩㅢࠅߢࠆ㧚 1. ࠄ߆ߓ⾈ᚻ 12㧘ᄁࠅᚻ 6 ࠍੂᢙߦࠃߞߡቯߒߡ߅ߊ 2. ⾈ᚻ 10㧘ᄁࠅᚻ 5 ߢห⾼ࡑࠤ࠶࠻ࠍ㐿ᆎߔࠆ 3. 5.14 ߢ␜ߐࠇࠆ⏕₸ߢᲤ⑽ෳട⠪ߩㅌࠗࡌࡦ࠻ࠍߎߔ 㧔ߚߛߒ⾈ᚻ㨯ᄁࠅᚻ߇ᣂߚߦෳടߔࠆࠗࡌࡦ࠻ߪᣂߚߥ⾈ᚻ㨯ᄁࠅᚻ߇ ߥ႐วߪήⷞߔࠆ㧕 4. ࡑࠤ࠶࠻㐿ᆎ߆ࠄ 20 ⑽ᓟߦోߡߩຠߩ✦ಾᤨ㑆ࠍㄫ߃ࠆ. 5.14 ࠗࡌࡦ࠻⏕₸. イベント 確率（％） 買い手が新たに参加する 5 売り手が新たに参加する 5 現在参加している買い手が退出する 5 現在参加している売り手が締切時間を迎える 5 参加者は変化しない 80. એߩ᧦ઙߢታᤨ㑆ឭ៤ᒻᚑ㗴ࠍ 100 ↪ᗧߒ㧘ឭ᩺ᚻᴺ㧘න⚐ㆮવ⊛ࠕ࡞ࠧ ࠭ࡓ㧘᰼ᒛࠅᴺߢ⸃ߒߚ㧚 ឭ᩺ᚻᴺ߅ࠃ߮න⚐ㆮવ⊛ࠕ࡞ࠧ࠭ࡓߦ↪ߡࠆㆮવ⊛ࠕ࡞ࠧ࠭ࡓߩࡄࡔ ࠲ߪᢙ 200㧘ઍᢙ 200 ߢⴕ㧘₸ߪ 0.5㧘⓭ὼᄌ⇣₸ߪ 0.01 ߦ⸳ቯߒߚ㧚 ోߡߩࡊࡠࠣࡓߪ JAVA ߢ㐿⊒ߒ㧘ࠪࡒࡘ࡚ࠪࡦⅣႺߪ OS㧦WindowsXP㧘 CPU㧦Celelon 1GHz㧘ࡔࡕ㧦256MB ߢⴕߞߚ㧚 ࡑࠤ࠶࠻⚳ੌᤨߦ߅ߌࠆല↪ߩว⸘ߩᐔဋ୯ࠍ 5.15 ߦ㧘ࡑࠤ࠶࠻⚳ੌᤨߦข ࠅᒁ߈߇ᚑ┙ߔࠆឭ៤ᒻᚑࠍዉߢ߈ߚ࿁ᢙࠍ 5.16 ߦ␜ߔ㧚. 36.
(43) 5.15 ࡑࠤ࠶࠻⚳ੌᤨߦ߅ߌࠆല↪ߩว⸘ߩᐔဋ୯. 提案手法 単純GA 欲張り法. 2899.8 1460 510. 5.16 ࡑࠤ࠶࠻⚳ੌᤨߦ߅ߌࠆㆡว⸃ዉ࿁ᢙ. 提案手法 単純GA 欲張り法. 78 49 21. 5.15 ߆ࠄឭ᩺ᚻᴺߪන⚐ㆮવ⊛ࠕ࡞ࠧ࠭ࡓ㧘᰼ᒛࠅᴺߦᲧߴߡല↪ߩᄢ߈ឭ ៤ᒻᚑ߇᧪ߡࠆߎߣ߇ࠊ߆ࠆ㧚߹ߚ㧘 5.16 ࠍߡ߽ಽ߆ࠆߣ߅ࠅ㧘න⚐ㆮવ ⊛ࠕ࡞ࠧ࠭ࡓ߿᰼ᒛࠅᴺߪࡑࠤ࠶࠻⚳ੌᤨߦ㒢᧦ઙࠍḩߚߒߚឭ៤⚵ߺวࠊ ߖࠍߟߌࠄࠇߚߩߪඨಽએਅߢࠆ㧚ᧄ㗴ߪേ⊛ߦෳടੱᢙ߇ᄌൻߔࠆߚ㧘 ࠆᤨὐߢߪ⾈ᚻోຬ߇⾼ߔࠆ߇ߢ߈ߥ㗴⸳ቯߦߥࠆߎߣ߇ࠆ㧚ߘߩߢ ឭ᩺ᚻᴺߪ 78%߽ߩㆡว⸃ࠍዉߒߡ߅ࠅ㧘ታᤨ㑆ឭ៤ᒻᚑߦߪ↪ߢࠆ߇␜ߐ ࠇߡࠆ㧚. 5.3 ⇐ଔᩰߦၮߠߊห⾼ߦ߅ߌࠆ ឭ៤ᒻᚑ ᧄ▵ߢߪ⇐ଔᩰ⸳ቯߦၮߠߊห⾼ࡑࠤ࠶࠻ߦ߅ߌࠆ⾈ᚻห჻ߩታᤨ. 37.
(44) 㑆ឭ៤ᒻᚑ㗴ࠍឭ᩺ߔࠆࠕ࡞ࠧ࠭ࡓߢ⸃ߒ㧘ઁߩࠕ࡞ࠧ࠭ࡓߣᲧセߔࠆߢ ᧄࠕ࡞ࠧ࠭ࡓߩ․㐳ࠍㅀߴࠆ㧚. 5.3.1 ⇐ଔᩰߦၮߠߊห⾼ߦ߅ߌࠆ ឭ៤ᒻᚑ㗴 ᧄ▵ߢߪ⇐ଔᩰ⸳ቯߦၮߠߊห⾼ࡑࠤ࠶࠻ߦ߅ߌࠆ⾈ᚻห჻ߩታᤨ 㑆ឭ៤ᒻᚑ㗴ߦߟߡ⺑ߒ㧘5.3 ▵ߩታ㛎ߦ↪ࠆ㗴ࠍ⺑ߔࠆ㧚 ᧄ㗴ߪᄁࠅᚻߩଔᩰ࠹ࡉ࡞ߣ⾈ᚻߩ⇐ଔᩰ࠹ࡉ࡞㧘ෳട⠪ߩෳട࠲ࠗࡓ ࠹ࡉ࡞ߦࠃߞߡቯߐࠇࠆ㧚৻ቯᢙߩᄁࠅᚻߪߘࠇߙࠇߩຠߦኻߒߡ⽼ᄁᢙߣ නଔߩ㑐ଥࠍ␜ߒߚࠍឭ␜ߔࠆ㧚ߎࠇࠍଔᩰ࠹ࡉ࡞ߣ߁㧚߹ߚ㧘ᄁࠅᚻߪߘࠇ ߙࠇ߇ຠߐࠇߡࠆోߡߩຠߦኻߒߡᡰᛄ߁ߩ᧪ࠆ㒢ᐲ㗵ࠍឭ␜ߔࠆ㧚ߎࠇ ࠍ⇐ଔᩰ࠹ࡉ࡞ߣ߁㧚ຠߦኻߒߡᡰᛄ߁ߩ᧪ࠆ㒢ᐲ㗵ࠍ⇐ଔᩰߣ߁㧚 ోߡߩ⾈ᚻߪ⇐ଔᩰએਅߩ㊄㗵ߢขᒁࠍᚑ┙ߐߖࠆᔅⷐ߇ࠆ㧚߹ߚ㧘⾈ᚻߪ ⇐ଔᩰ߆ࠄታ㓙ߩ⾼ଔᩰࠍᒁߚ୯ࠍല↪ߣߒߡᓧࠆ㧚ขᒁଔᩰ߇⇐ଔᩰࠃࠅ ߽ዊߐ߶ߤᓧࠄࠇࠆല↪ߪᄢ߈㧚 ᧄ㗴ߢߪෳട⠪ߪࠄࠇߡߥ࠲ࠗࡒࡦࠣߢࡑࠤ࠶࠻ߦෳട㧛ㅌࠍߔࠆ㧚 ห⾼ߪෳട⠪ੱᢙߢ⾈ᚻߩ⾼ଔᩰ߇ᄌൻߔࠆߚേ⊛ߥੱᢙߩᄌൻߪᦨㆡ ߥឭ៤ᒻᚑࠍࠃࠅ࿎㔍ߦߔࠆ㧚߹ߚ㧘⾈ᚻߪోߡߩຠߦኻߒߡߦ⇐ଔᩰࠍ ⸳ቯߔࠆߚ㧘ᦨㆡߥឭ៤ᒻᚑߪ㕖Ᏹߦ࿎㔍ߢࠆ㧚. 38.
(45) 5.3.2 ⇐ଔᩰߦၮߠߊห⾼ߦ߅ߌࠆ ឭ៤ᒻᚑ㗴ߩ․ᕈ߅ࠃ߮⸃ࠕ࡞ࠧ࠭ࡓߩ․ ᕈ ᧄ▵ߢߪ⇐ଔᩰ⸳ቯߦၮߠߊห⾼ߦ߅ߌࠆታᤨ㑆ឭ៤ᒻᚑ㗴ࠍ␜ߒ㧘 ᧄ㗴ߩ․ᕈߣ⸃ࠕ࡞ࠧ࠭ࡓߩ㆑ࠍ␜ߔ㧚 ᧄ▵ߢᛒ߁㗴ߪ⾈ᚻ 12㧘ᄁࠅᚻ 6 ߣߔࠆ㧚㗴ࠍ 5.17㧘 5.18 ߅ࠃ߮ 5.19 ߦ␜ߔ㧚 5.17 ᄁࠅᚻߩଔᩰ࠹ࡉ࡞ࠍ㧘 5.18 ߪ⾈ᚻߩ⇐ଔᩰ࠹ࡉ࡞ ࠍ㧘 5.19 ߪෳട⠪ߩ࠲ࠗࡓ࠹ࡉ࡞ࠍ␜ߒߡࠆ㧚. 5.17 ᄁࠅᚻߩଔᩰ࠹ࡉ࡞. 商品A 商品B 商品C 商品D 商品E 品数 単価 品数 単価 品数 単価 品数 単価 品数 単価 1 2,000 1-3 1,800 1 2,000 1-4 1,700 1-3 2,000 2 1,900 4-5 1,400 2-3 1,600 5 1,310 4-5 1,350 3-5 1,450 6 1,300 4-5 1,500. 39.
(46) 5.18 ⇐ଔᩰ࠹ࡉ࡞ 商品A 商品B 商品C 商品D 商品E 商品F 商品A 商品B 商品C 商品D 商品E 商品F 商品A 商品B 商品C 商品D 商品E 商品F. 買い手A 買い手Ｂ 買い手Ｃ 買い手D 1,780 1,310 1,550 1,780 1,550 1,380 1,780 1,550 1,650 1,700 1,550 1,650 1,550 1,650 1,650 1,700 1,700 1,780 1,720 1,800 1,680 1,550 1,680 1,310 買い手E 買い手F 買い手G 買い手H 1,780 1,700 1,780 1,650 1,380 1,720 1,550 1,720 1,650 1,900 1,310 1,780 1,700 1,720 1,700 1,700 1,550 1,650 1,650 1,550 1,380 1,680 1,680 1,680 買い手I 買い手J 買い手K 買い手L 1,780 1,900 1,550 1,550 1,800 1,380 1,680 1,800 1,550 1,700 1,780 1,550 1,650 1,720 1,550 1,720 1,720 1,780 1,650 1,780 1,380 1,680 1,380 1,700. 5.19 ห⾼ࡑࠤ࠶࠻ߩ࠲ࠗࡓ࠹ࡉ࡞. 時間（ sec） イベント 0 共同購入マーケット開始 10 買い手K参加 15 商品F追加 20 商品A締切 25 買い手L参加 30 共同購入マーケット終了. 40.
(47) એߦ␜ߐࠇࠆታᤨ㑆ឭ៤ᒻᚑ㗴ࠍឭ᩺ᚻᴺ㧘േ⊛⸘↹ᴺ㧘᰼ᒛࠅᴺߢṶ▚ߒ㧘 ߘߩ⚿ᨐࠍᲧセߔࠆ㧚 ឭ᩺ᚻᴺߦ↪ߡࠆㆮવ⊛ࠕ࡞ࠧ࠭ࡓߩࡄࡔ࠲ߪᢙ 200㧘ઍᢙ 200 ߢⴕ㧘₸ߪ 0.5㧘⓭ὼᄌ⇣₸ߪ 0.01 ߦ⸳ቯߒߚ㧚ోߡߩࡊࡠࠣࡓߪ JAVA ߢ 㐿⊒ߒ㧘ࠪࡒࡘ࡚ࠪࡦⅣႺߪ OS㧦WindowsXP㧘CPU㧦Celelon 1GHz㧘ࡔࡕ㧦 256MB ߢⴕߞߚ㧚 ฦࠕ࡞ࠧ࠭ࡓߩᤨ㑆ㆫ⒖ࠍ࿑ 5.2㧘ࡑࠤ࠶࠻⚳ੌᤨߩല↪ߩว⸘ࠍ 5.20 ߦ␜ ߔ㧚. 4500 4000 効用の合計値. 3500 3000 提案手法 動的計画法 欲張り法. 2500 2000 1500 1000 500 0 0. 5. 10. 15 20 時間（ sec）. 25. 30. ࿑ 5.2 ⇐ଔᩰߦၮߠߊห⾼ߦ߅ߌࠆታᤨ㑆ឭ៤ᒻᚑߩᤨ㑆ㆫ⒖. 41.
(48) 5.20 ࡑࠤ࠶࠻⚳ੌᤨߩല↪ߩว⸘୯. 提案手法 動的計画法 欲張り法. 4,200 3,500 3,300. ࿑ 5.2 ߆ࠄߘࠇߙࠇߩࠕ࡞ࠧ࠭ࡓߩ․ᓽ߇ࠊ߆ࠆ㧚േ⊛⸘↹ᴺߪត⚝ᚻᴺߩ৻ߟ ߢ⍴ᤨ㑆ߢᦨㆡ⸃㧘߽ߒߊߪḰᦨㆡ⸃ߩዉ߇น⢻ߢࠆ㧚ߒ߆ߒߥ߇ࠄឭ᩺ᚻᴺࠃ ࠅ⸃ߩត⚝ߦᤨ㑆߇߆߆ࠆ㧚ᧄ▵ߢᛒߞߚ㗴ߢߪࡑࠤ࠶࠻㐿ᆎᓟ 10㧘15㧘20㧘 25 ⑽ߢෳട⠪ᢙ߇ᄌൻߒߡ߅ࠅ㧘േ⊛⸘↹ᴺߪ㗴ᄌൻᤨߦṶ▚ࠍ߿ࠅ⋥ߒߡࠆ ߚෳടੱᢙߩᄌൻ߇⪺ߒ႐วචಽߥળ߇ዉߢ߈ߡߥ㧚 ᰼ᒛࠅᴺߪ㕖Ᏹߦ⍴ᤨ㑆ߢṶ▚ࠍ⚳ੌߐߖࠆ߇᧪ࠆ㧚ߒ߆ߒߥ߇ࠄត⚝⢻ജ߇ 㗴ߦଐሽߔࠆߚ㧘ⶄ㔀ߥ㗴ࠍ⸃ߢ߈ߥ㧚㔚ሶห⾼ߦ߅ߌࠆታᤨ㑆ឭ៤ ᒻᚑ㗴ߢߪෳടੱᢙ߇േ⊛ߦᄌൻߒߘߩㇺᐲ㗴߇ᄌൻߔࠆ㧚ᓥߞߡ㗴⸃⢻ജ ߇㗴ߦଐሽߔࠆ᰼ᒛࠅᴺߪታᤨ㑆ឭ៤ᒻᚑߦߪㆡߒߡߥߣ߃ࠆ㧚 5.20 ࠍࠆߣߘࠇߙࠇߩᚻᴺߪ㒢᧦ઙࠍḩߚߒߚ⚵ߺวࠊߖࠍ⊒ߒߡࠆ㧚 ឭ᩺ᚻᴺߪਛߢ߽ఝ⑲ߥ୯ࠍߒߡࠆ߇ಽ߆ࠆ㧚. 42.
(49) ╙6┨ ⚿⺰ 6.1 ᚑᨐ ᧄ⺰ᢥߢߪ㔚ሶห⾼ߦ߅ߌࠆ⾈ᚻห჻ߩᦨㆡឭ៤ᒻᚑᡰេᯏ᭴ࠍ᭴▽ߒߚ㧚 ᧄ⺰ᢥߢឭ᩺ߔࠆ㔚ሶห⾼ߪઍᦧ⽷ࠍ↪ࠆ㧚ઍᦧ⽷ࠍ↪ߚ㔚ሶห⾼ࡑ ࠤ࠶࠻ߢߪ⾈ᚻߩല↪߇ᦨᄢߦߥࠆࠃ߁ߦ⾈ᚻห჻ߩឭ៤ᒻᚑࠍߔࠆᔅⷐ߇ ࠆ㧚ᧄ⺰ᢥߢឭ᩺ߒߚታᤨ㑆ឭ៤ᒻᚑࠕ࡞ࠧ࠭ࡓߪ⍴ᤨ㑆ߢᦨㆡ⸃㧘߽ߒߊߪḰᦨ ㆡ⸃ࠍዉߔࠆ߇ߢ߈㧘ታᤨ㑆ߢߩឭ៤ᒻᚑߦ߅ߡ↪ᕈࠍ␜ߔ߇ߢ߈ߚ㧚 ᧄ⺰ᢥߢឭ᩺ߒߚឭ៤ᒻᚑࠕ࡞ࠧ࠭ࡓߦߪએਅߩ․㐳߇ࠆ㧚 z. ⍴ᤨ㑆ߢᦨㆡ⸃㨯Ḱᦨㆡ⸃ࠍዉߔࠆ߇ߢ߈ࠆ. z. 㔍⸃ߥ⚵ߺวࠊߖ㗴ߢࠆឭ៤ᒻᚑ㗴ࠍ㗴ߦଐሽߔࠆߎߣߥߊ⸃ߢ߈ࠆ. z. േ⊛ߥෳടੱᢙߩᄌൻߦኻᔕߒ㧘ߔ߫߿ߊࡑࠤ࠶࠻ෳട⠪ߩឭ៤ᒻᚑ߇น⢻ߢ ࠆ. z. ⾈ᚻߪຠߐࠇߡࠆᴛጊߩຠߦኻߒߡߦ⇐ଔᩰࠍ⸳ቯߔࠆ߇ߢ߈㧘 ⶄ㔀ߥ㗴ߢ߽⚃⪲߇ᄢ߈ߥឭ៤ᒻᚑࠍน⢻ߣߒߡࠆ. ᧄࠕ࡞ࠧ࠭ࡓߪઍᦧ⽷ࠍ↪ߚ㔚ሶห⾼ߦ߅ߌࠆታᤨ㑆ឭ៤ᒻᚑ㗴ࠍ⸃ ߢ߈㧘ᧄࠕ࡞ࠧ࠭ࡓߩ⸃ត⚝⢻ജߪઁߩ⸃ត⚝ࠕ࡞ࠧ࠭ࡓࠃࠅ⦟ᚑ❣ࠍߒߡ ࠆ㧚ታ㛎ࠍㅢߒߡᧄࠕ࡞ࠧ࠭ࡓߩ↪ᕈࠍ␜ߒߚ㧚. 43.
(50) 6.2 ᓟߩ⺖㗴 㔚ሶห⾼ߦ߅ߌࠆ⾈ᚻห჻ߩឭ៤ᒻᚑ㗴ߪ⚵ߺวࠊߖᦨㆡൻ㗴ߢࠆ㧚 ⾈ᚻห჻ߩᦨㆡឭ៤ᒻᚑ㗴ߪ NP 㗴ߢࠅ㧘⸃ⓨ㑆ߩᄢ߈ߐߪࡑࠤ࠶࠻ߦෳ ടߔࠆ⾈ᚻߣᄁࠅᚻߩᢙߢቯߐࠇࠆ㧚ࠗࡦ࠲ࡀ࠶࠻ߢߪᴛጊߩੱ㑆߇หᤨߦෳ ടߔࠆߎߣ߇੍ᗐߐࠇࠆߚᧄࠕ࡞ࠧ࠭ࡓࠍ⸃ⓨ㑆ߩჇᄢߦኻᔕߐߖࠆᔅⷐ߇ ࠆ㧚 ᧄࠕ࡞ࠧ࠭ࡓߪㆮવ⊛ࠕ࡞ࠧ࠭ࡓࠍࡌࠬߣߒߚ⸃ត⚝ࠕ࡞ࠧ࠭ࡓߢࠆ㧚 ㆮવ⊛ࠕ࡞ࠧ࠭ࡓߩ⸃ត⚝⢻ജߪᢙߦଐሽߔࠆ㧚㗴ߩ⸃ⓨ㑆ߩᄢ߈ߐߦኻߒ ߡᢙ߇චಽߢߥߣ߈㧘ㆮવ⊛ࠕ࡞ࠧ࠭ࡓߩ⸃ត⚝⢻ജߪචಽߦ⊒ើߐࠇߥ㧚 㔚ሶห⾼ࡑࠤ࠶࠻ߦ߅ߡෳട⠪ੱᢙߩᄌൻᤨߦ⸃ⓨ㑆ߩჇᄢߦวࠊߖߡ ᢙࠍᄌൻߐߖࠆᯏ᭴߇ᓟߩ⺖㗴ߢࠆ㧚. 44.
(51) ⻢ㄉ ᧄ⺰ᢥࠍ߹ߣࠆߦߚࠅ㧘ᄙߊߩᣇߏߩޘᜰዉ߅ࠃ߮ᡰេࠍߚߛ߈߹ߒߚ㧚߅ ߦߥߞߚ⊝᭽ߦᗵ⻢ߩ᳇ᜬߜࠍ⸥ߒ߹ߔ㧚. ᧄ⎇ⓥࠍㅴࠆߦߚߞߡᜰዉᢎቭߢࠆർ㒽వ┵⑼ቇᛛⴚᄢቇ㒮ᄢቇ⍮⼂⑼ቇ⎇ ⓥ⑼⮮ㅴᢎߦᗵ⻢⥌ߒ߹ߔ㧚⮮ᢎߦߪࡊࡠࡐࠩ࡞⊒㧘ਛ㑆⊒೨ߦᄢᄌ ✺ኒߥࠕ࠼ࡃࠗࠬࠍߚߛ߈㧘⎇ⓥࠍቢᚑߐߖࠆ㊀ⷐߥߏᜰዉࠍߚߛ߈߹ߒߚ㧚߹ ߚ㧘ቇળᛩⓂ⺰ᢥ㧘ቇળ⊒⾗ᢱߩߏᜰዉߚߛߚὐߦ߽ᷓߊᗵ⻢⥌ߒ߹ߔ㧚. ฬฎደᎿᬺᄢቇᄢቇ㒮Ꮏቇ⎇ⓥ⑼દ⮮ቁⴕഥᢎߦߪ⎇ⓥᣇะᕈߩᜰዉ߿ቇળ⺰ᢥ ᛩⓂ㧘ቇળ⊒✵⠌ߦ߅ߡᄢᄌ㊀ⷐߥߏᜰዉࠍߚߛ߈߹ߒߚ㧚ᷓߊᗵ⻢⥌ߒ߹ߔ㧚. ฬฎደᎿᬺᄢቇᄢቇ㒮Ꮏቇ⎇ⓥ⑼᧻የᓼᦶߐࠎߦߪቇળ⺰ᢥᛩⓂ㧘ቇળ⊒ߦ߅ ߡᄢᄌᄙߊߩᤨ㑆ߣഭജࠍഀߡߚߛ߈߹ߒߚ㧚ᗵ⻢⥌ߒ߹ߔ㧚. ർ㒽వ┵⑼ቇᛛⴚᄢቇ㒮ᄢቇ⍮⼂⑼ቇ⎇ⓥ⑼⮮⎇ⓥቶ㈩ዻߩ⠀ጊᔀᓀߐࠎ㧘ᐔ↰ ᢅਯߐࠎ㧘ᧁ㦖ᐔߐࠎ㧘ᬢะ᧲ߐࠎ㧘દ⮮⋥Ꮖำ㧘ዊᩊ╬ำ㧘ᷡ᳓ஜำ߅ࠃ߮ߘߩ ઁߩ⮮⎇ⓥቶ㈩ዻߩᣇ✵⊒߿ࡒߪޘ⠌ߦ߅ߡ⎇ⓥߦ㑐ߔࠆ᭽ߥޘᗧࠍ㗂 ߈߹ߒߚ㧚ߎߎߦᗵ⻢ߩᗧࠍߒ߹ߔ㧚. 45.
(52) ෳ⠨ᢥ₂ [1] http://www.bidders.co.jp/ [2] http://www.rakuten.co.jp/groupbuy/ [3] Bui, N. T. : On Multi-Dimensional Encoding/Crossover, International Conference on Genetic Algorithms (ICGA-1995), pp.49-56, 1995. [4] Eshelman, J. L. & Scha.er, D. J.: Crossover’s Niche, International Conference on Genetic Algorithms (ICGA-1993), pp.9-14, 1993. [5] Hyodo, M., Matsuo, T. & Ito, T. : An Optimal Coalition Formation among Buyer Agents based on a Genetic Algorithm, Industrial & Engineering Applications of Arti.cial Intelligence and Expert Systems (IEA/AIE-2003). Lecture Notes in Arti.cial Intelligence (LNAI) 2718, pp.759-767, Springer-Verlag, 2003. [6] Hyodo, M., Matsuo, T. & Ito, T. : An Optimal Coalition Formation Algorithm for Electronic Group Buying, The Society of Instrument and Control Engineers Annual Conference, 2003. [7] Kitano, H., (Ed.) : Genetic Algorithms, Sangyotosho, 1993. (in Japanese) [8] Layton-Brown, K., Shohan Y. & Tenneholtz, M.:Bidding Club:. 46.
(53) Institutionalized Collusion in Auction, in the proceeding of ACM Conference on Electronic Commerce(EC’00), pp253-259, 2000. [9] Matsumoto, M., Kanoh, H. & Nishihara, S. : Solving Constraint Satisfaction Problems by Hybrid Genetic Algorithms Based on Min-con.icts Heuristic, Information Processing Society of Japan Journal, Vol.38, No.5, pp.962-969, May 1997. (in Japanese). [10] Matsuo, T. & Ito, T. : A Decision Support System for Group Buying based on Buyers’ Preferences in Electronic Commerce, the EleventhWorld Wide Web International Conference (WWW-2002), 2002. [11] Matsuo, T. & Ito, T. : A Buyers Integration Support System based on Users’ Multi Attribute Utilities for Internet Group Buying, the 12th World Wide Web International Conference (WWW-2003), 2003. [12] Matsuo, T., Hyodo, M. & Ito, T. : A Buyer Allocation Support System in First-Price Auctions, The Society of Instrument and Control Engineers Annual Conference, 2003. [13] Tanese, R. : Distributed Genetic Algorithms, International Conference on Genetic Algorithms (ICGA- 1989), pp.434-439, 1989. [14] Sen, S. & Dutta, S. : Searching for optimal coalition structures, the Fourth International Conference on Multiagent Systems pp.286-292, 2000. [15] Sen, S., Mahendra, S. & John, H. : Learning to coordinate without sharing information, the Twelfth National Conference on Arti.cial Intelligence, pp.426- 431, 1994.. 47.
(54) [16] Syswerda, G. : Uniform Crossover in Genetic Algorithms, International Conference on Genetic Algorithms (ICGA-1989), pp.2-9, 1989. [17] Yamamoto, J. & Sycara, K. : A Stable and Efficient Buyer Coalition Formation Scheme for EMarketplaces, Fifth International Conference on Autonomous Agents (Agents 2001), 2001.. 48.
(55) ⊒ ⺰ ᢥ [1]Hyodo, M., Matsuo, T. & Ito, T. : An Optimal Coalition Formation among Buyer Agents based on a Genetic Algorithm, Industrial & Engineering Applications of Artificial Intelligence and Expert Systems (IEA/AIE-2003). Lecture. Notes. in. Artificial. Intelligence. (LNAI). 2718,. pp.759-767,. Springer-Verlag, 2003. [2]⮮ᱜ᮸,᧻የᓼᦶ,દ⮮ቁⴕ: ㆮવ⊛ࠕ࡞ࠧ࠭ࡓߦၮߠߊ㔚ሶห⾼ߦ߅ߌࠆታᤨ㑆ឭ៤ ᒻᚑߦߟߡ, ᖱႎಣℂቇળ╙ 65 ࿁ో࿖ᄢળ, 2003.. [3]Masaki Hyodo, Tokuro Matsuo, Takayuki Ito: An Optimal Coalition Formation Algorithm for Electronic Group Buying, Society of Instrument and Control Engineers (SICE) Annual Conference 2003 in Fukui, 2003.. [4]⮮ᱜ᮸,᧻የᓼᦶ,દ⮮ቁⴕ,⮮ㅴ: 㔚ሶห⾼ߦ߅ߌࠆታᤨ㑆ឭ៤ᒻᚑᡰេࠕ࡞ࠧ࠭ࡓ ߦߟߡ, 㔚ሶᖱႎㅢାቇળੱޟᎿ⍮⢻⎇ޠⓥળ, 2003.. [5]⮮ᱜ᮸,᧻የᓼᦶ,દ⮮ቁⴕ,⮮ㅴ: ㆮવ⊛ࠕ࡞ࠧ࠭ࡓࠍ↪ߚ Web ᖱႎߦၮߠߊᣏⴕᣣ⒟ ቯᡰេࠪࠬ࠹ࡓߦߟߡ, ᐔᚑ 15 ᐕᐲ㔚᳇㑐ଥቇળർ㒽ᡰㇱㅪวᄢળ, 2003.. [6]⮮ᱜ᮸,᧻የᓼᦶ,દ⮮ቁⴕ,⮮ㅴ: ⇐ଔᩰ⸳ቯߐࠇߚ㔚ሶห⾼ߦ߅ߌࠆ⾈ᚻߩ ឭ៤ᒻᚑߦߟߡ, ᖱႎಣℂቇળ╙ 66 ࿁ో࿖ᄢળ, 2004.. 49.
(56)
関連したドキュメント
そこで本研究では, 都市下水処理UASB 槽内に生息する嫌気 性原生動物 Metopus sp.体内の共生微生物叢を明らかにする ため, 16S rRNA 遺伝子に基づく遺伝子解析及び
Vandetanib in patients with previously treated RET-rearranged advanced non-small-cell lung cancer (LURET): an open-label, multicentre phase 2 trial. Lancet
Key Words : CIM(Construction Information Modeling),River Project,Model Building Method, Construction Life Cycle Management.
今日のお話の本題， 「マウスの遺伝子を操作する」です。まず，外から遺伝子を入れると
マーカーによる遺伝子型の矛盾については、プライマーによる特定遺伝子型の選択によって説明す
Their basic components are the representation of candidate solutions to the problem in a “genetic” form, the creation of an initial, usually random population of solutions,
In this paper, taking into account pipelining and optimization, we improve throughput and e ffi ciency of the TRSA method, a parallel architecture solution for RSA security based on
We generalized Definition 5 of close-to-convex univalent functions so that the new class CC) includes p-valent functions.. close-to-convex) and hence any theorem about
