移動図書館問題 移動施設のサービス停留点を最適配置する問題

Presentation on theme: "移動図書館問題 移動施設のサービス停留点を最適配置する問題"— Presentation transcript:

1 移動図書館問題 移動施設のサービス停留点を最適配置する問題
移動図書館問題 　移動施設のサービス停留点を最適配置する問題 ３G　０２３１２３　棚橋　則子

2 それぞれの意見 ・利用者側 いつも自分の家の前で止まってほしい。 ・移動図書館側 一軒一軒の家の前では止まれない。
　　　　　　それぞれの意見 ・利用者側 　　いつも自分の家の前で止まってほしい。 ・移動図書館側 　　一軒一軒の家の前では止まれない。 　　停留点の数は限る必要がある。 　　総移動距離はある一定距離以下に 　　抑えなければいけない。

3 問題１ 一定以下にした時、 利用者全体にとって最も便利なように サービス停留点を配置するには、 どのように配置すればよいのか？
　　　　　　　　 問題１ 　移動図書館の移動距離を 一定以下にした時、 利用者全体にとって最も便利なように サービス停留点を配置するには、 どのように配置すればよいのか？

4 ・移動距離がある一定の距離以下 ・停留点の数も一定
　　　　・移動距離がある一定の距離以下 　　　　・停留点の数も一定 　可能な停留点の配置は絞られてくるが、 それでもまだ様々な配置は可能。 配置によって、利用者の利便性も変わる。 ↓ 可能な配置の中で、どのような配置が 一番利便性が高いのか？

5 　　　　　　問題１の制約条件 　　 １　停留点数 ｎ は一定 　　 ２　一日の総移動距離は限界距離Ｋ以下 ↓ 　　 ３　一回の移動距離は　　　　 以下　

6 ・停留点のから次の停留点までの移動距離も
・利用者は、直線距離で一番近い停留点に 移動図書館がきた時に利用する。 ・停留点のから次の停留点までの移動距離も 直線で近似できるものとする。 ・利用者の利便度は、平均距離で計る。 ↓ 利用者の平均距離が最小となるような 停留点の配置を求める問題となる。

7 停留点サービス移動施設の 経路、停留点を母点とするボロノイ図
停留点サービス移動施設の 　　　　　　経路、停留点を母点とするボロノイ図

8 ・利用者の最近隣停留地までの総距離 ・問題１を定式化

9 利用者が均一にいる線的地域に サービス停留点が２つある場合のＴの求め方
利用者が均一にいる線的地域に 　サービス停留点が２つある場合のＴの求め方

10 ・総距離Ｔの求め方 ・制約条件

11 利用者均一の線的地域に ２ヶ所停留する場合の数学的定式化（問題２）
利用者均一の線的地域に 　　　　　２ヶ所停留する場合の数学的定式化（問題２） 　＊このように、制約がついている問題を、 　　　　　　　「制約条件付き非線形最小化問題」という。

12 左図より、 　　　　　　　　　　　　のとき 最小値 　　　　　　　　　　　　をとる

13 ・罰金額（ｔは罰金率）

14 ・制約条件付き非線形関数 ↓変換 ・パラメーター t の制約条件なし非線形関数（ｔ＝１）

15 　　　 罰金率 ｔ と Ｌ の最小値の関係

16 ペナルティー法 一般に、問題２のような「制約条件付き 非線形関数」を、このようにパラメーター ｔ を 用いて「制約条件なし非線形関数」に
　　　　　　ペナルティー法 　一般に、問題２のような「制約条件付き 非線形関数」を、このようにパラメーター ｔ を 用いて「制約条件なし非線形関数」に 変換すると、変換された関数の最小値は ｔが大きくなるにつれて、もとの制約条件付き 非線形関数の最小値に近づく。 　このような解き方を、ペナルティー法という。

17 　 一般の場合の問題も、変数が多変数となるだけで
考え方は全く同じ。 ↓変換

18 　　　　　　　　探索的方法

19

20 利用者が均一にいて、停留点数が２０、 出発点と終着点があらかじめ決まっている場合の配置
利用者が均一にいて、停留点数が２０、 　出発点と終着点があらかじめ決まっている場合の配置

21 利用者が均一にいて、停留点数が２０、 出発点と終着点が一致して固定されてない場合の配置
利用者が均一にいて、停留点数が２０、 　出発点と終着点が一致して固定されてない場合の配置

22 　　　　　大宮市の人口ドットマップ

23 　　　　　大宮市の最適停留点配置