| 講演名 | 2020-01-23 自転車再配置問題に対する実行可能解と実行不可能解の探索を動的に変化させる解法の提案 對馬 帆南(日本工大), 木村 貴幸(日本工大), 松浦 隆文(日本工大), |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 我々は，バイクシェアリングシステムの各ポートの自転車台数を調整するために，複数の自転車回収車を 用いた自転車再配置問題(mBSSRP)を提案している.しかし，mBSSRP は回収車の時間制約，自転車の積込み・補充制約が厳しため，一部の問題例に対して，これまでに提案した解法では実行可能解を見つけることが困難であった.そこで，時間制約と積込み・補充制約を制約条件から取り除き，制約の違反量に応じたペナルティを付加した目的関数を最小化するソフトな制約付き mBSSRP(mBSSRP-S)を提案している.mBSSRP-S を解くことで，mBSSRPの制約条件を満たす良好な近似解の探索を行なう.mBSSRP の良好な解を見つけるためには，mBSSRP-S におけるペナルティに対する重み係数を適切な値に設定しなければいけない.そこで，効果的な探索を実現するために，探索状態に応じて動的に重み係数を調整する手法を提案している.本報告では，更に性能を向上させるために提案した動的な重み調整を改良した手法を提案する.数値実験の結果，提案法は問題規模の小さい全ての問題例に対して最適解を求めることができ，従来の動的なパラメータ制御手法よりも短い巡回路を構築できることを確認した. |
| 抄録(英) | To adjust the number of bicycles at each ports in the Bike Sharing System, we have already defined a multiple-Vehicle Bike Sharing System Routing Problem (mBSRRP) and proposed a heuristic method. However, the method cannot search the solutions of the mBSSRP effectively for any instances, because a time limit constraint, a capacity constraint and a supply constraint in the problem are strict. Therefore, we proposed a soft-constrained mBSSRP (mBSSRP-S) that removes the time constraint, the capacity constraint, and the supply constraint from the mBSSRP and minimizes the objective function with a penalty according to the amount of violation of the constraints. By solving the mBSSRP-S, we find a good solution that satisfy the constraints of the mBSSRP. However, for finding the good solutions of mBSSRP, we must adjust the weight of penalty to an appropriate value. In this paper, we propose a method that dynamically adjusts the weight of penalties. As a result of numerical experiments, we confirmed the proposed method can find an optimal solution of the mBSSRP for many instances. |
| キーワード(和) | バイクシェアリングシステム / 自転車再配置問題 / ヒューリスティック解法 / 組合せ最適化 |
| キーワード(英) | bicycle sharing system / multiple-vehicle bike sharing system routing problem / heuristics method / combinatorial optimization problem |
| 資料番号 | NLP2019-86 |
| 発行日 | 2020-01-16 (NLP) |
| 研究会情報 | |
| 研究会 | NLP / NC |
|---|---|
| 開催期間 | 2020/1/23(から3日開催) |
| 開催地（和） | 宮古島マリンターミナル |
| 開催地（英） | Miyakojima Marine Terminal |
| テーマ（和） | NC, NLP, 一般 |
| テーマ（英） | |
| 委員長氏名（和） | 黒川 弘章(東京工科大) / 庄野 逸(電通大) |
| 委員長氏名（英） | Hiroaki Kurokawa(Tokyo Univ. of Tech.) / Hayaru Shouno(UEC) |
| 副委員長氏名（和） | 夏目 季代久(九工大) / 鮫島 和行(玉川大) |
| 副委員長氏名（英） | Kiyohisa Natsume(Kyushu Inst. of Tech.) / Kazuyuki Samejima(Tamagawa Univ) |
| 幹事氏名（和） | 木村 貴幸(日本工大) / 立野 勝巳(九工大) / 吉本 潤一郎(奈良先端大) / 安部川 直稔(NTT) |
| 幹事氏名（英） | Takayuki Kimura(Nippon Inst. of Tech.) / Katsumi Tateno(Kyushu Inst. of Tech.) / Junichiro Yoshimoto(NAIST) / Naotoshi Abekawa(NTT) |
| 幹事補佐氏名（和） | 島田 裕(埼玉大) / 佐村 俊和(山口大) / 篠崎 隆志(NICT) / 瀧山 健(東京農工大) |
| 幹事補佐氏名（英） | Yutaka Shimada(Saitama Univ.) / Toshikaza Samura(Yamaguchi Univ.) / Takashi Shinozaki(NICT) / Ken Takiyama(TUAT) |
| 講演論文情報詳細 | |
| 申込み研究会 | Technical Committee on Nonlinear Problems / Technical Committee on Neurocomputing |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 自転車再配置問題に対する実行可能解と実行不可能解の探索を動的に変化させる解法の提案 |
| サブタイトル（和） | |
| タイトル（英） | A Control Method for Searching for A Feasible and An Infeasible Solution Space of A multiple-Vehicle Bike Sharing System Routing Problem |
| サブタイトル（和） | |
| キーワード(1)（和/英） | バイクシェアリングシステム / bicycle sharing system |
| キーワード(2)（和/英） | 自転車再配置問題 / multiple-vehicle bike sharing system routing problem |
| キーワード(3)（和/英） | ヒューリスティック解法 / heuristics method |
| キーワード(4)（和/英） | 組合せ最適化 / combinatorial optimization problem |
| 第 1 著者 氏名（和/英） | 對馬 帆南 / Honami Tsushima |
| 第 1 著者 所属（和/英） | 日本工業大学(略称：日本工大) Nippon Institute of Technology(略称：NIT) |
| 第 2 著者 氏名（和/英） | 木村 貴幸 / Takayuki Kimura |
| 第 2 著者 所属（和/英） | 日本工業大学(略称：日本工大) Nippon Institute of Technology(略称：NIT) |
| 第 3 著者 氏名（和/英） | 松浦 隆文 / Takafumi Matsuura |
| 第 3 著者 所属（和/英） | 日本工業大学(略称：日本工大) Nippon Institute of Technology(略称：NIT) |
| 発表年月日 | 2020-01-23 |
| 資料番号 | NLP2019-86 |
| 巻番号（vol） | vol.119 |
| 号番号（no） | NLP-381 |
| ページ範囲 | pp.13-18(NLP), |
| ページ数 | 6 |
| 発行日 | 2020-01-16 (NLP) |