| 講演名 | 2020-06-05 大規模自転車再配置問題に対する動的な重み係数調整を用いた解法の性能調査 對馬 帆南(東京理科大), 松浦 隆文(日本工大), 池口 徹(東京理科大), |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 我々は既に，バイクシェアリングシステム (BSS) において，自転車回収車が短い時間で駐輪ポートの自転 車台数を調整する経路を決定するために複数の回収車による自転車回収車再配置問題 (mBSSRP) と発見的解法を提 案している.しかし，mBSSRP の制約条件が厳しいため，一部の問題例に対して実行可能解が得られない場合も存在 する.そこで，mBSSRP の一部の制約を取り除き，その制約に対する違反を重み付きの違反量として mBSSRP の目 的関数に加えたソフト制約付き自転車再配置問題 (mBSSRP-S) を提案している.さらに，mBSSRP-S を解くことで mBSSRP の優れた解を得るために，mBSSRP の実行可能解と実行不可能解を効率的に探索できる動的な重み係数調 整法を提案している.数値実験により，ポート数が 50 程度の問題例に対して，mBSSRP の良好な近似解が得られる ことを報告しているが，実際に運営されている BSS のポート数は数百である.そこで本報告は，ポート数が多い大規 模な BSS に対する提案解法の性能を調査する.数値実験の結果，大規模問題に対しても動的に重み係数を調整しなが ら mBSSRP-S を解く方法は有効であることを確認した. |
| 抄録(英) | In a bike sharing system (BSS) , we proposed a multiple-Vehicle Bike Sharing System Routing Problem (mBSSRP) to determine short tours to adjust bicycles using vehicles in short time. However, it is difficult to construct feasible solutions for some instances due to strict constraints of mBSSRP. Therefore, we proposed a multiple-Vehicle Bike Sharing System Routing Problem with Soft Constraints (mBSSRP-S) that removes some constraints from mBSSRP and adds those violations to objective function of mBSSRP as penalties. Furthermore, we proposed a dynamic weight adjustment method to efficiently explore both feasible and infeasible solution space of mBSSRP by solving mBSSRP-S. Numerical experiments have shown that we obtained good solutions for instances with about 50 ports. However, the number of ports in real BSSs in more than hundreds. Thus, in this study, we investigate the performance for large-scale instances. As results of numerical experiments, we confirm that good solutions of mBSSRP are obtained for the large-scale instances. |
| キーワード(和) | 大規模バイクシェアリングシステム / 組合せ最適化問題 / 自転車再配置問題 / タブーサーチ |
| キーワード(英) | large-scale bike sharing system / combinatorial optimization problem / multiple-vehicle bike sharing system routing problem / tabu search |
| 資料番号 | NLP2020-14,CCS2020-4 |
| 発行日 | 2020-05-29 (NLP, CCS) |
| 研究会情報 | |
| 研究会 | CCS / NLP |
|---|---|
| 開催期間 | 2020/6/5(から1日開催) |
| 開催地（和） | 湘南工科大学 |
| 開催地（英） | Shonan Institute of Technology |
| テーマ（和） | 一般 |
| テーマ（英） | |
| 委員長氏名（和） | 塩川 茂樹(神奈川工科大) / 夏目 季代久(九工大) |
| 委員長氏名（英） | Shigeki Shiokawa(Kanagawa Inst. of Tech.) / Kiyohisa Natsume(Kyushu Inst. of Tech.) |
| 副委員長氏名（和） | 浅井 哲也(北大) / 赤井 恵(北大) / 高坂 拓司(中京大学) |
| 副委員長氏名（英） | Tetsuya Asai(Hokkaido Univ.) / Megumi Akai(Hokkaido Univ.) / Takuji Kosaka(Chukyo Univ.) |
| 幹事氏名（和） | 川喜田 佑介(神奈川工科大) / 中田 一紀(TDK) / 立野 勝巳(九工大) / 松下 春奈(香川大) |
| 幹事氏名（英） | Yusuke Kawakita(Kanagawa Inst. of Tech.) / Kazuki Nakada(TDK) / Katsumi Tateno(Kyushu Inst. of Tech.) / Haruna Matsushita(Kagawa Univ.) |
| 幹事補佐氏名（和） | 中野 秀洋(東京都市大) / 安東 弘泰(筑波大) / 松原 崇(神戸大) / 眞田 耕輔(三重大学) / 佐村 俊和(山口大) / 加藤 秀行(大分大) |
| 幹事補佐氏名（英） | Hidehiro Nakano(Tokyo City Univ.) / Hiroyasu Ando(Tsukuba Univ.) / Takashi Matsubara(Kobe Univ.) / Kosuke Sanada(Mie Univ.) / Toshikaza Samura(Yamaguchi Univ.) / Hideyuki Kato(Oita Univ.) |
| 講演論文情報詳細 | |
| 申込み研究会 | Technical Committee on Complex Communication Sciences / Technical Committee on Nonlinear Problems |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 大規模自転車再配置問題に対する動的な重み係数調整を用いた解法の性能調査 |
| サブタイトル（和） | |
| タイトル（英） | Dynamically changing penalties method for Large-Scale multiple-Vehicle Bike Sharing System Routing Problem |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 大規模バイクシェアリングシステム / large-scale bike sharing system |
| キーワード(2)（和/英） | 組合せ最適化問題 / combinatorial optimization problem |
| キーワード(3)（和/英） | 自転車再配置問題 / multiple-vehicle bike sharing system routing problem |
| キーワード(4)（和/英） | タブーサーチ / tabu search |
| 第 1 著者 氏名（和/英） | 對馬 帆南 / Honami Tsushima |
| 第 1 著者 所属（和/英） | 東京理科大学(略称：東京理科大) Tokyo University of Science(略称：TUS) |
| 第 2 著者 氏名（和/英） | 松浦 隆文 / Takafumi Matsuura |
| 第 2 著者 所属（和/英） | 日本工業大学(略称：日本工大) Nippon Institute of Technology(略称：NIT) |
| 第 3 著者 氏名（和/英） | 池口 徹 / Tohru Ikeguchi |
| 第 3 著者 所属（和/英） | 東京理科大学(略称：東京理科大) Tokyo University of Science(略称：TUS) |
| 発表年月日 | 2020-06-05 |
| 資料番号 | NLP2020-14,CCS2020-4 |
| 巻番号（vol） | vol.120 |
| 号番号（no） | NLP-55,CCS-56 |
| ページ範囲 | pp.19-22(NLP), pp.19-22(CCS), |
| ページ数 | 4 |
| 発行日 | 2020-05-29 (NLP, CCS) |