| 講演名 | 2019-05-11 ソフトな制約付き自転車再配置問題に対する解法の研究 對馬 帆南(日本工大), 木村 貴幸(日本工大), 松浦 隆文(日本工大), |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | バイクシェアリングシステムの各ポートの自転車台数を調整するために，我々は，複数の自転車回収車を用 いた自転車再配置問題(mBSSRP)を提起し，CROSS-exchange の実行をタブーサーチ法で制御する手法を提案している.mBSSRP の目的は，デポを出発した回収車は制限時間内にデポに戻り，かつ，回収車の容量を超えて自転車を積込むことはできないなどの制約条件下で，回収車の総移動時間を最小化することである.しかし，この制約条件が厳しいために，探索過程において実行可能な近傍解が得られず，新たな解へ遷移できないといった問題が生じていた. そこで，本研究では制限時間と容量制約を違反しても良いソフトな制約と捉え，実行不可能解への遷移も可能な手法を提案する.具体的には，制限時間の超過時間，容量制約違反量をペナルティーとして目的関数に加える.数値実験の結果，実行不可能解も探索することで，実行可能解のみを探索する場合よりも優れた解を探索できることを確認した. |
| 抄録(英) | To restore the number of bicycle in each port of the bike sharing system, we have formulated a multi- ple-Vehicle Bike Sharing System Routing Problem (mBSSRP), and proposed a heuristic method. In the mBSSRP, all vehicles must satisfy a time limit constraint and a capacity constraint. In numerical simulation, for some instances, the proposed method cannot find a good solution. One of the reasons is that a current solution of the proposed method in a searching process can not move to a new solution because feasible neighborhood solutions cannot be obtained. Therefore, to find a good solution of the mBSSRP, in this paper, we propose a method that can move to an infeasible neighborhood solution. Specifically, an over time from the time limit and an excess amount from the capacity of vehicle are added to the objective function of the mBSSRP as a penalty. As a result of numerical experiments, we confirmed that we can find better solutions of the mBSSRP by searching for the infeasible solutions. |
| キーワード(和) | バイクシェアリングシステム / 組合せ最適化 / 自転車再配置問題 / CROSS-exchange / タブーサーチ法 |
| キーワード(英) | Bike sharing system / Combinatorial optimization / multiple-Vehicle Bike Sharing System Routing Problem / CROSS-exchange / Tabu search method |
| 資料番号 | NLP2019-12 |
| 発行日 | 2019-05-03 (NLP) |
| 研究会情報 | |
| 研究会 | NLP |
|---|---|
| 開催期間 | 2019/5/10(から2日開催) |
| 開催地（和） | J:COM ホルトホール大分 |
| 開催地（英） | J:COM HoltoHALL OITA |
| テーマ（和） | 一般 |
| テーマ（英） | etc. |
| 委員長氏名（和） | 高橋 規一(岡山大) |
| 委員長氏名（英） | Norikazu Takahashi(Okayama Univ.) |
| 副委員長氏名（和） | 黒川 弘章(東京工科大) |
| 副委員長氏名（英） | Hiroaki Kurokawa(Tokyo Univ. of Tech.) |
| 幹事氏名（和） | 山内 将行(広島工大) / 木村 貴幸(日本工大) |
| 幹事氏名（英） | Masayuki Yamauchi(Hiroshima Inst. of Tech.) / Takayuki Kimura(Nippon Inst. of Tech.) |
| 幹事補佐氏名（和） | 木村 真之(京大) / 島田 裕(埼玉大) |
| 幹事補佐氏名（英） | Masayuki Kimura(Kyoto Univ.) / Yutaka Shimada(Saitama Univ.) |
| 講演論文情報詳細 | |
| 申込み研究会 | Technical Committee on Nonlinear Problems |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | ソフトな制約付き自転車再配置問題に対する解法の研究 |
| サブタイトル（和） | |
| タイトル（英） | Study of A Solving Method for a Multiple Vehicle Bike Sharing System Routing Problem with Soft Constraints |
| サブタイトル（和） | |
| キーワード(1)（和/英） | バイクシェアリングシステム / Bike sharing system |
| キーワード(2)（和/英） | 組合せ最適化 / Combinatorial optimization |
| キーワード(3)（和/英） | 自転車再配置問題 / multiple-Vehicle Bike Sharing System Routing Problem |
| キーワード(4)（和/英） | CROSS-exchange / CROSS-exchange |
| キーワード(5)（和/英） | タブーサーチ法 / Tabu search method |
| 第 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) |
| 発表年月日 | 2019-05-11 |
| 資料番号 | NLP2019-12 |
| 巻番号（vol） | vol.119 |
| 号番号（no） | NLP-19 |
| ページ範囲 | pp.65-70(NLP), |
| ページ数 | 6 |
| 発行日 | 2019-05-03 (NLP) |