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

東京理科大学工学部情報工学科の池口徹教授、對馬帆南氏(博士後期課程2年)、日本工業大学 先進工学部情報メディア工学科の松浦隆文准教授の研究グループは、複数車両が再配置を行う「バイクシェアリングシステム・ルーティング問題(mBSSRP)」の準最適解を短時間で求めるために、新しい探索戦略を提案し、ポート数が多数になった場合でも、この戦略により合理的な時間内に良好な実行可能解を得ることができることを示しました。

バイクシェアリングシステムでは、多数の自転車が往復だけでなく片道でも利用されることで生じる各ポートの自転車台数の偏りが問題となっています(図)。これを解決するため、さまざまなアルゴリズムが提唱されてきました。池口教授らは、これまで解決されなかった再配置作業の時間的制約や実行可能性などを踏まえ、この問題をmBSSRPとして定式化しました。しかし、ポート数が大規模になると、現実的な時間内に最適解を求めることができないことが課題でした。

今回の研究では、再配置作業時間などのさまざまな制約を満たし、かつ実行可能な解を導き出す手法を開発することに成功しました。この手法により、小規模な問題に対しては、より短時間で最適解を得ることができるようになりました。さらに、大規模な問題に対しては、実行可能解を探すだけではなく、実行不可能な解空間についての探索も行うという従来とは異なるアプローチにより、良好な近似解を得ることを可能にしました。

バイクシェアリングシステムにおける自転車の偏りを解消することは、導入が急速に進む現代社会で喫緊の課題です。本研究の結果により、自転車配送車による自転車の再配置作業を効率よく実行する手順を提示することができました。この成果は、今後の社会において、便利で快適なバイクシェアリングシステムの構築と運用を可能にする重要な基礎となることが期待されます。

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

研究の背景

バイクシェアリングシステム(BSS)は、近年、街の中心部における交通渋滞の緩和、CO₂排出量の削減、公衆衛生の向上を目的として、世界の多くの都市で導入されています。BSSの研究は、自転車の偏りを解決するための効率的な再配置作業方法の提案だけではなく、需要のある地域へのポートの設置など、BSSをさらに発展させることも目的として進められています。これまで複数の自転車配送車による最適な自転車の再配置作業計画を提示するために、さまざまなアルゴリズムが提案されてきましたが、作業時間制限などの制約が考慮されていないという問題がありました。
池口教授は、元々、さまざまな組合せ最適化問題の効率的な解法の開発に関する研究に取り組んでいましたが、BSSは今後世界的にも広がるとの考えから、現実社会おいて解決すべき重要な課題の一つと捉え、研究を進めてきました。教授らの研究グループでは、以前の研究でmBSSRPと呼ばれる新しい自転車シェアリングシステム・ルーティング問題を定式化しました。mBSSRPでは、複数の自転車配送車が制限時間内に一度だけすべてのポートを訪れ、自転車の回収・補充を行ないます。ポート数が少なく小規模であれば、汎用の混合整数線形計画(MIP)ソルバを用いて最適解が得られることを明らかにしました。しかし、ポート数が大規模になると、現実的な時間内に最適解を得ることはできず、これが課題となっていました。これに対して同研究グループから提案された自転車配送車の再配置作業計画に対する局所探索法は、短時間で巡回路を構築することに成功したものの、実行可能な最適解を得られていませんでした。

研究結果の詳細

今回の研究では、実行可能な解空間と実行不可能な解空間の両方を探索するために、まず、mBSSRPの制約条件の緩和を行いました。mBSSRPでは、自転車の再配置に関する制限時間、自転車配送車に積載できる自転車数、各ポートへの配送回数に厳しい制約があります。今回の研究では、これらの制約を取り除き，これらの制約を違反した場合、ペナルティとしてmBSSRPの目的関数に追加されます。これをmBSSRP-Sと呼びます。このように緩和した場合でも、ポートの数が大規模になった場合、汎用ソルバでは現実的な時間で最適解を求めることができませんでした。
そこで、これまで提案したメタヒューリスティックな手法を用いて、mBSSRPの実行可能な解空間と不可能な解空間を動的に探索する制御手法を導入したアルゴリズムを提案いたしました。これにより、mBSSRPおよびmBSSRP-Sの最適解を現実的な時間内で求めることに成功しました。
数値実験を行った結果、従来の実行可能空間のみの探索に比べて、mBSSRPの実行可能解空間と実行不可能解空間の両方を探索することで、ポート数が小規模な問題に対してはより短時間で最適解を得ることができました。また、ポート数が大きい問題に対しても、現実的な時間内に良好な実行可能解を得ることができました。
この実行可能解空間と実行不可能解空間の両方を探索する戦略は、実行可能解空間のみを探索する従来の手法とは異なり、規模の大小に関わらず、厳しい制約の課された実社会のさまざまな問題に対しても現実的な時間内で実現可能な解を得ることができる新しい手法となることが期待されています。

研究を主導した池口教授は「バイクシェアリングシステムは、今後世界的にも広がると考えられています。配置が偏った自転車に対して配送車の最適配置問題を効率よく解くための手法を開発することは、我々の現実社会における実課題としても解決すべき重要な課題と考えています。今回提案した手法により、便利で快適なバイクシェアリングシステムの構築・運用が可能となります」と今後の研究の応用に期待を示しています。

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