講演抄録/キーワード |
講演名 |
2019-10-22 08:50
カープーリング最適化問題に対する局所探索法を用いたグループ決定法による解法の検討 ○高橋昂靖・青木俊親・木村貴幸(日本工大) CAS2019-23 NLP2019-63 |
抄録 |
(和) |
一台の車を共有し,他者と通勤等を行うことをカープールと呼ぶ.近年,効率的なカープールサービスを実現するために,Uber や Lyft など,数多くのマッチングアプリケーションが提供されている.このようなアプリケーションでは参加者同士の素早いマッチングが求められているが,参加者数が増加するとマッチングの組合せ数が増加し,参加者同士のマッチングに時間がかかる恐れがある.このような背景からカープールをモデル化した,カープーリング最適化問題が既に提案されている.カープーリング最適化問題は運転手と乗客が同一の目的地を持つ問題 (Many-Source Single-Destination 以下, MSSD) と運転手と乗客が異なる目的地を持つ問題 (Many-Source Many-Destination 以下, MSMD) の二つに大別される.また,我々は既にMSMD 問題に対して,乗客グループを予め決定することで車の総移動距離が短くなる経路を短時間で探索する手法を提案しているが,MSSD問題に対しては手法の有効性を示していない.そこで本稿では,MSSD問題に対する提案手法の有効性について調査した.また,MSSD問題とMSMD問題に 対する提案手法の性能を調査した.数値実験より,提案手法はカープーリング最適化問題のいずれの問題に対しても短時間で総移動距離の短い経路を探索可能であることを確認した. |
(英) |
Sharing a car while commuting with others is called carpool. Recently, many carpool applications such as Uber and Lyft have been proposed to carpool with others. These carpool applications require high speed matching of each participant. However, the matching time between participants increases exponentially if a large number of passengers join in a carpool group. From this background, carpooling optimization problems which model carpool applications have already been proposed. The carpooling optimization problems are further classified into Many-Source Single-Destination, called MS-SD problem, and Many-Source Many-Destination, called MS-MD problem. To solve the carpooling optimization problems, we have already proposed searching method using grouping procedure that determines carpool groups of passengers for MSSD problems. However, we have not investigated the effectiveness of proposed method for the MSSD problem. In this study, we evaluate the proposed method for the MSSD and the MSMD problems. Numerical experiments show that our methods quickly find approximate solution for each carpooling optimization problem. |
キーワード |
(和) |
組合せ最適化 / カープール / 局所探索法 / / / / / |
(英) |
Combinatorial Optimization / Carpool / Local Search / / / / / |
文献情報 |
信学技報, vol. 119, no. 238, NLP2019-63, pp. 1-6, 2019年10月. |
資料番号 |
NLP2019-63 |
発行日 |
2019-10-15 (CAS, NLP) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
CAS2019-23 NLP2019-63 |
研究会情報 |
研究会 |
NLP CAS |
開催期間 |
2019-10-22 - 2019-10-23 |
開催地(和) |
岐阜大学 |
開催地(英) |
Gifu Univ. |
テーマ(和) |
数理モデリング,数値シミュレーション,一般 |
テーマ(英) |
Mathematical modeling, numerical simulation etc. |
講演論文情報の詳細 |
申込み研究会 |
NLP |
会議コード |
2019-10-NLP-CAS |
本文の言語 |
日本語 |
タイトル(和) |
カープーリング最適化問題に対する局所探索法を用いたグループ決定法による解法の検討 |
サブタイトル(和) |
|
タイトル(英) |
A Study of Grouping Procedure Using Local Search Method for Carpooling Optimization Problems |
サブタイトル(英) |
|
キーワード(1)(和/英) |
組合せ最適化 / Combinatorial Optimization |
キーワード(2)(和/英) |
カープール / Carpool |
キーワード(3)(和/英) |
局所探索法 / Local Search |
キーワード(4)(和/英) |
/ |
キーワード(5)(和/英) |
/ |
キーワード(6)(和/英) |
/ |
キーワード(7)(和/英) |
/ |
キーワード(8)(和/英) |
/ |
第1著者 氏名(和/英/ヨミ) |
高橋 昂靖 / Kosei Takahashi / タカハシ コウセイ |
第1著者 所属(和/英) |
日本工業大学 (略称: 日本工大)
Nippon Institute of Technology (略称: Nippon Institute of Tech) |
第2著者 氏名(和/英/ヨミ) |
青木 俊親 / Toshichika Aoki / アオキ トシチカ |
第2著者 所属(和/英) |
日本工業大学 (略称: 日本工大)
Nippon Institute of Technology (略称: Nippon Institute of Tech) |
第3著者 氏名(和/英/ヨミ) |
木村 貴幸 / Takayuki Kimura / キムラ タカユキ |
第3著者 所属(和/英) |
日本工業大学 (略称: 日本工大)
Nippon Institute of Technology (略称: Nippon Institute of Tech) |
第4著者 氏名(和/英/ヨミ) |
/ / |
第4著者 所属(和/英) |
(略称: )
(略称: ) |
第5著者 氏名(和/英/ヨミ) |
/ / |
第5著者 所属(和/英) |
(略称: )
(略称: ) |
第6著者 氏名(和/英/ヨミ) |
/ / |
第6著者 所属(和/英) |
(略称: )
(略称: ) |
第7著者 氏名(和/英/ヨミ) |
/ / |
第7著者 所属(和/英) |
(略称: )
(略称: ) |
第8著者 氏名(和/英/ヨミ) |
/ / |
第8著者 所属(和/英) |
(略称: )
(略称: ) |
第9著者 氏名(和/英/ヨミ) |
/ / |
第9著者 所属(和/英) |
(略称: )
(略称: ) |
第10著者 氏名(和/英/ヨミ) |
/ / |
第10著者 所属(和/英) |
(略称: )
(略称: ) |
第11著者 氏名(和/英/ヨミ) |
/ / |
第11著者 所属(和/英) |
(略称: )
(略称: ) |
第12著者 氏名(和/英/ヨミ) |
/ / |
第12著者 所属(和/英) |
(略称: )
(略称: ) |
第13著者 氏名(和/英/ヨミ) |
/ / |
第13著者 所属(和/英) |
(略称: )
(略称: ) |
第14著者 氏名(和/英/ヨミ) |
/ / |
第14著者 所属(和/英) |
(略称: )
(略称: ) |
第15著者 氏名(和/英/ヨミ) |
/ / |
第15著者 所属(和/英) |
(略称: )
(略称: ) |
第16著者 氏名(和/英/ヨミ) |
/ / |
第16著者 所属(和/英) |
(略称: )
(略称: ) |
第17著者 氏名(和/英/ヨミ) |
/ / |
第17著者 所属(和/英) |
(略称: )
(略称: ) |
第18著者 氏名(和/英/ヨミ) |
/ / |
第18著者 所属(和/英) |
(略称: )
(略称: ) |
第19著者 氏名(和/英/ヨミ) |
/ / |
第19著者 所属(和/英) |
(略称: )
(略称: ) |
第20著者 氏名(和/英/ヨミ) |
/ / |
第20著者 所属(和/英) |
(略称: )
(略称: ) |
講演者 |
第1著者 |
発表日時 |
2019-10-22 08:50:00 |
発表時間 |
25分 |
申込先研究会 |
NLP |
資料番号 |
CAS2019-23, NLP2019-63 |
巻番号(vol) |
vol.119 |
号番号(no) |
no.237(CAS), no.238(NLP) |
ページ範囲 |
pp.1-6 |
ページ数 |
6 |
発行日 |
2019-10-15 (CAS, NLP) |
|