自転車再配置問題に対する実行可能解と実行不可能解の探索を動的に変化させる解法の提案

摘要

我々は，バイクシェアリングシステムの各ポートの自転車台数を調整するために，複数の自転車回収車を用いた自転車再配置問題（mBSSRP）を提案している．しかし，mBSSRPは回収車の時間制約，自転車の積込み·補充制約が厳しため，一部の問題例に対して，これまでに提案した解法では実行可能解を見つけることが困難であった．そこで，時間制約と積込み·補充制約を制約条件から取り除き，制約の違反量に応じたペナルティを付加した目的関数を最小化するソフトな制約付きmBSSRP（mBSSRP-S）を提案している．mBSSRP-Sを解くことで，mBSSRPの制約条件を満たす良好な近似解の探索を行なう．mBSSRPの良好な解を見つけるためには，mBSSRP-Sにおけるべナルティに対する重み係数を適切な値に設定しなければいけない．そこで，効果的な探索を実現するために，探索状態に応じて動的に重み係数を調整する手法を提案している．本報告では，更に性能を向上させるために提案した動的な重み調整を改良した手法を提案する．数値実験の結果，提案法は問題規模の小さい全ての問題例に対して最適解を求めることができ，従来の動的なパラメータ制御手法よりも短い巡回路を構築できることを確認した．