ニュース＆イベント NEWS & EVENTS

東京理科大学工学部情報工学科の池口徹教授、對馬帆南氏(博士後期課程2年)、日本工業大学先進工学部情報メディア工学科の松浦隆文准教授の研究グループは、バイクシェアリングシステムにおいて複数の配送車を用いて各ポートの自転車台数を短時間で調整する「バイクシェアリングシステム経路問題 (mBSSRP)」を解決するためのアルゴリズムを、これまでに開発・提案しています。本研究では、実行可能解を求める前後で異なる2つの探索戦略を用いることで、このアルゴリズムの性能を維持しつつ計算コストを抑え短時間で効率的な再配置作業を実現できる手法の開発に成功しました。本研究をさらに発展させることで、自転車需要の予測やポートの新規設置場所の提案など、バイクシェアリングシステムのさらなる効率化が期待されます。

バイクシェアリングシステムでは、利用者が自転車を借りたポートと異なるポートに返却することにより、ポートごとの自転車台数に偏りが生じます。そのため、配送車が各ポートの自転車台数を調整する必要があり、効率的な運用アルゴリズムが模索されてきました。本研究グループは、以前からmBSSRPの解決に注力しており、再配置作業時間などの制約を踏まえた上で、より作業時間が短くなる配送車の巡回経路の導出法の確立に成功しています。一方で、この方法は計算コストが大きいことから、従来の性能を維持しつつ、計算コストを抑えた新たな手法が求められていました。

本研究では、「mBSSRPの実行可能解を求める前に近傍解数を減らすことにより、短時間で実行可能解を求める手法」と「実行可能解を求めた後で解くべき問題を変更することにより、短時間で優れた解を求める手法」を提案し、それらの性能を評価しました。その結果、近似解法の近傍解数を減らした手法と実行不可能な解空間での探索を削除した手法の組み合わせにより、短時間で良好な実現可能な解を導出できることが明らかとなりました。この手法を活用することにより、従来の性能を維持したまま計算コストを抑えることができます。また、この手法を実際のバイクシェアリングシステムに適用することで、利用者の満足度の高いシステムの構築および運用が期待されます。

本研究の成果は、2022年3月4日に国際学術誌「Applied Sciences」にオンライン掲載されました。

研究の背景

バイクシェアリングシステムでは、利用者が自転車を好きなポートでレンタルし、利用後は好きなポートで返却できます。おもに人口密度の高い都市部で導入されており、交通渋滞の緩和やCO₂、NO_xの排出量の抑制に貢献しています。

利用者が自転車を借りたポートと異なるポートに返却することによって、ポートごとの自転車台数に偏りが生じるため、配送車が定期的に再配置作業を行う必要があります。そのため、mBSSRPにおけるアルゴリズムの効率化が検討されてきました。池口教授の研究グループは、過去にこの問題において、良好な実行可能解を導出する手法を報告しています。この手法では、問題の規模の大小に関わらず、良好な実行可能解を得ることができました (※1)。しかしながら、mBSSRPには多くの厳しい制約が存在することから、一部の問題例に対して実行可能解が得られない課題がありました。

そこで、mBSSRPの実行可能解を得るために、mBSSRPから制約を取り除き、違反した制約をペナルティとして目的関数に加えるソフト制約付きmBSSRP(mBSSRP-S)と、実行可能解空間と実行不可能解空間の両方を探索する探索戦略を提案しました。数値実験の結果、mBSSRP-SはmBSSRPを直接解くよりも良好な性能が得られることが示されました。しかし、mBSSRP-SはmBSSRPの実行不可能解を含むため、計算コストが増加します。

そこで本研究では、従来の性能を維持した状態で計算コストを削減し、短時間で実現可能な解を探る手法の確立を目的として、新たな手法の提案と評価を行いました。

(過去のプレスリリース)

※1:「より効率的なバイクシェアリングの運用を可能にする新しい数学的手法の提案」
URL: https://www.tus.ac.jp/today/archive/20211026_3175.html

研究結果の詳細

本研究では「mBSSRPの実行可能解を求める前に近傍解数を減らして、短時間で実行可能解を求める手法」と、「実行可能解を求めた後に解くべき問題(mBSSRPまたはmBSSRP-S)を変更して、短時間で優れた近似解を求める手法」という2つの探索戦略を提案しました。

1つ目の探索戦略については、過去に提案した手法 (1A-S) に加え、近似解法(Or-opt法、CROSS-exchange法)の近傍解数を減らした2つの手法 (1B-S, 1C-S) で数値実験を行い、性能比較を行いました。その結果、1C-Sが1A-Sと同等の性能を有し、かつ短時間で実現可能な解を導出できることがわかりました。これは、1C-Sが近傍解としてOr-opt法の通常順序挿入とCROSS-exchange法の通常順序交換のみを探索していることに起因します。

2つ目の探索戦略については、過去に提案した手法 (2A-S, 2A-H) に加え、4つの手法 (2B-S, 2B-H, 2C-S, 2C-H) で、数値実験と性能評価を行いました。その結果、2C-Hが最も優れた手法であることがわかりました。これは、ハードな制約条件下でOr-opt法の正規順序挿入とCROSS-exchange法の正規順序交換のみを探索しており、実行不可能な解空間での計算を排除していることに起因します。以上の結果より、実行可能解を求める前には1C-Sを、実行可能解を求めた後には2C-Hを使用し、近似解を導出する手法が最も効果的であることがわかりました。

本研究の成果について、研究を主導した池口教授は「バイクシェアリングシステムは、従来の交通網とは異なる新たな移動手段として世界各国で普及が進んでおり、国内でも多くの都市で導入が始まっています。環境や健康の観点から自転車利用が見直されており、今後も広がりを見せると思われます。本論文では、バイクシェアリングシステムにおける自転車の偏りを解消するための回収車の最適巡回問題を効率よく解くための手法を提案しています。この意味で、便利で快適なバイクシェアリングシステムの構築・運用が可能となります」と話しています。

※本研究は日本学術振興会の科研費(JP19K04907, JP21H03514, JP20H00596, JP21H03514)の助成を受けて実施したものです。

論文情報

雑誌名

Applied Sciences

論文タイトル

Searching Strategies with Low Computational Costs for Multiple-Vehicle Bike Sharing System Routing Problem

著者

Honami Tsushima, Takafumi Matsuura and Tohru Ikeguchi

DOI

10.3390/app12052675