移動図書館問題 移動施設のサービス停留点を最適配置する問題 移動図書館問題 移動施設のサービス停留点を最適配置する問題 ３G ０２３１２３ 棚橋 則子
それぞれの意見 ・利用者側 いつも自分の家の前で止まってほしい。 ・移動図書館側 一軒一軒の家の前では止まれない。 それぞれの意見 ・利用者側 いつも自分の家の前で止まってほしい。 ・移動図書館側 一軒一軒の家の前では止まれない。 停留点の数は限る必要がある。 総移動距離はある一定距離以下に 抑えなければいけない。
問題１ 一定以下にした時、 利用者全体にとって最も便利なように サービス停留点を配置するには、 どのように配置すればよいのか？ 問題１ 移動図書館の移動距離を 一定以下にした時、 利用者全体にとって最も便利なように サービス停留点を配置するには、 どのように配置すればよいのか？
・移動距離がある一定の距離以下 ・停留点の数も一定 ・移動距離がある一定の距離以下 ・停留点の数も一定 可能な停留点の配置は絞られてくるが、 それでもまだ様々な配置は可能。 配置によって、利用者の利便性も変わる。 ↓ 可能な配置の中で、どのような配置が 一番利便性が高いのか？
問題１の制約条件 １ 停留点数 ｎ は一定 ２ 一日の総移動距離は限界距離Ｋ以下 ↓ ３ 一回の移動距離は 以下
・停留点のから次の停留点までの移動距離も ・利用者は、直線距離で一番近い停留点に 移動図書館がきた時に利用する。 ・停留点のから次の停留点までの移動距離も 直線で近似できるものとする。 ・利用者の利便度は、平均距離で計る。 ↓ 利用者の平均距離が最小となるような 停留点の配置を求める問題となる。
停留点サービス移動施設の 経路、停留点を母点とするボロノイ図 停留点サービス移動施設の 経路、停留点を母点とするボロノイ図
・利用者の最近隣停留地までの総距離 ・問題１を定式化
利用者が均一にいる線的地域に サービス停留点が２つある場合のＴの求め方 利用者が均一にいる線的地域に サービス停留点が２つある場合のＴの求め方
・総距離Ｔの求め方 ・制約条件
利用者均一の線的地域に ２ヶ所停留する場合の数学的定式化（問題２） 利用者均一の線的地域に ２ヶ所停留する場合の数学的定式化（問題２） ＊このように、制約がついている問題を、 「制約条件付き非線形最小化問題」という。
左図より、 のとき 最小値 をとる
・罰金額（ｔは罰金率）
・制約条件付き非線形関数 ↓変換 ・パラメーター t の制約条件なし非線形関数（ｔ＝１）
罰金率 ｔ と Ｌ の最小値の関係
ペナルティー法 一般に、問題２のような「制約条件付き 非線形関数」を、このようにパラメーター ｔ を 用いて「制約条件なし非線形関数」に ペナルティー法 一般に、問題２のような「制約条件付き 非線形関数」を、このようにパラメーター ｔ を 用いて「制約条件なし非線形関数」に 変換すると、変換された関数の最小値は ｔが大きくなるにつれて、もとの制約条件付き 非線形関数の最小値に近づく。 このような解き方を、ペナルティー法という。
一般の場合の問題も、変数が多変数となるだけで 考え方は全く同じ。 ↓変換
探索的方法
利用者が均一にいて、停留点数が２０、 出発点と終着点があらかじめ決まっている場合の配置 利用者が均一にいて、停留点数が２０、 出発点と終着点があらかじめ決まっている場合の配置
利用者が均一にいて、停留点数が２０、 出発点と終着点が一致して固定されてない場合の配置 利用者が均一にいて、停留点数が２０、 出発点と終着点が一致して固定されてない場合の配置
大宮市の人口ドットマップ
大宮市の最適停留点配置