# M1 平松 A chance-constrained dial-a-ride problem with utility-maximising demand and multiple pricing structures ABSTRACT 新規性　事業者側の決定に利用者選考を導入 実用性　最適な運賃やシステムについての結果が得られている 信頼性　ヒューリスティックス解とソルバーを用いた厳密解との比較，理論実験と実データによる実験を実施している 1. introduction VRPとDARPの違い 人を運ぶ(DARP)か荷物(VRP)を運ぶか 輸送サービスの質を考えないといけない 乗車時間が長いと利用者にとって負効用 利用者の負効用とのトレードオフ 全リクエストを運ぶ，全員を運ぶように最適化 最後の1人を運ぶことで，効用が下がってしまう サービスクオリティが下がる，将来的に利用者数が減少する恐れ 利用者選考を考慮していない 利用者選好を考慮する 効用が低いのを断る→利用者の効用を高め，事業者のコストを下げる 2. 既往研究の整理 運営コストと利用者の負効用のトレードオフ 1つの目的関数だと後者が考慮されない 重み付して足したものを目的関数として解くものもある 利益を考慮したDARP 利用者を受け入れるかどうかの意思決定，リクエストが拒否されることを考慮 あくまで供給側の都合 解法 整数計画問題なのでNP-hard，多項式時間では無理 局所探索のヒューリスティックス 3. 定式化 自家用車 効用関数，第1項は移動時間に伴う負効用，第3項移動に伴うコストの負効用 DRT 復路：用事が終わってから乗るまでの間の時間が大事 往路：到着時間が大事 それぞれ分けて定式化 効用の差の誤差項はロジスティク分布に従う DRT利用のダミー変数を導入して(*) パラメータベータの値が利用者のクラスで変わる 平松 2007のレビュー論文を読むと比較できてよい 羽藤 素晴らしい，自分で入れた 目的関数は，総収入から総コストを引いたもの，利益最大化 羽藤 制約条件の書き方は，元研究でもこう書いているのか 平松 台数で変わってくるところはある 違いは，効用関数の制約 元研究ではy_iがない 全員を運ぶのが前提か否か 4. 解法 LS-Hアルゴリズムを提案 初期解を生成 受け入れるユーザの探索 ルート探索 くり返して更新されなければ終了 羽藤 わかりやすいなあ 初期解 最早と最遅を絞る D_iが大きいものを先に階に入れる D_iは他のリクエストから離れているので，あとから入れるのは大変なので最初に 羽藤 This parameter depends on the size of zone? 平松 Yes. TT_iが短いほどリクエストの距離が短い，先に解に入れておく，乗車時間が短くなるので G_iが挿入の優先度を決める指標 優先度があまりにもひっくり返っているものを並び替える 順に車に挿入，どこにも挿入できないならば，プールする 挿入できるなら，最小コストにリクエスト入れる，訪問済 どの利用者を受け入れるか 3つの操作 add 最もよいところに追加 Rem リクエストを抜く swap あるリクエストを抜いて，まだ組み込めてないリクエストを同時にいれる すべての組み込めてないリクエストにadd すべてのリクエストに対してremでより良い解になるかをチェック 利益最大化の解を見つける その後にswap，まだ入っていないリクエストと入っているリクエストを入れ替える操作を試す 最適値が更新されなくなるまで繰り返す ルート探索 RA：すべての車両において，すべてのリクエストを他のクルマに移そうとする，実行可能なら移す RI：実行可能でないならば元に戻す くり返して収束するまで繰り返す MATH TH-Hアルゴリズム ルート探索を厳密解を求めるソルバーで代替 これらを比較 5. 数値実験 ・理論上の数値実験，格子状の平面 従来のDARPとCC-DARPの性能比較 1時間以内に終わった結果 従来のDARPでは運賃に対して収益が比例して増加 提案している手法では，運賃が高すぎると利用されなくなって収益が低下する結果に→現実的 運賃が一定の値を超えると収益が下がるということ 運賃設定と感度分析 中規模 MATH-Hは厳密解に近い解を得られている 大規模　両方厳密解に近い 運賃が小さいケース　LS-Hは収束するのに苦労 局所探索ではあるが80%で最適解が得られている→局所探索アルゴリズムの有効性 ニューヨークのタクシーデータ 理論実験と同様に運賃が一定値を超えると利益が低下 収益マネジメントが可能 ゾーンベースの運賃が利益，利用者数を最大化する 一律運賃では，時間価値の高い集団が価格弾力性が高い 6. 結論 機会制約をDARPに導入，効用関数を定義 局所探索でも厳密最適化に近い解が得られていた 収益マネジメントとして有用 今後 他の交通サービスを含めた利用者選択 厳密解を求めるアルゴリズムの改良 低運賃でも解が得られるように 所感 DARPに行動モデルを組み込むのは面白い 利用者の効用関数をもとに事業者が受け入れるかを決めている 複数の解法による解の比較 最適解に到達しやすい変数のみ近似解法を用いて求めるので計算時間を短縮？ 羽藤　最適解に到達しやすい変数のみ近似解法を用いて求めるのはSHAPみたい．最適解に対して感度のある，貢献できる変数を見つけて解法を構成する．面白い．全部の変数を入れてサロゲートで求めるのは簡単に思いつくが，変数側出したり入れたりの，近似解法でもなるほどなと思う．面白いなと．DARPの定式化自体に行動モデルを組み込むのは面白いというのは？ 平松　イメージだと，利用者の選択が先． 羽藤　効用関数の中にダイレクトに入れる 平松　長期的に公共交通が安定していくかの指標として，利用者の効用が高いかという時間変化を1つの効用関数で表現しているのが面白い． 大山　機会制約を入れるのは大事だが，アルゴリズムとの関係がよく分からない．効用関数を入れることでどこでどういう風に解かれていたのか． 平松　読んでて確かに気づかなかった． 大山　例えば，効用関数の中に旅行時間が入っている．旅行時間はルートの最適化によって決まるはず．すごく難しい問題．解き方としての工夫が，効用関数を入れることで必要が生じてくるのでは． 平松　最初の初期解を決めるときに，time windowを厳しくしている．効用関数に所要時間が入っているのを踏まえている． 羽藤　供給側がルートを変えると，AからBまで行くときにもうひとりを乗せるとルートが変わって，時間が変わる．効用も変わる．効用の値が変わるなら辞める．やめるならルートを取らなくていい，計算上入れ子になっているのが厄介．計算上どうしているのか． 平松　後々入れるとコストが大きくなるようなものを先に入れるようにしているのは，負効用が急にには大きくならないように初期解を決めているのではないか 大山　難しいので段階に分けてD_iで近似をしている．利用者が入ったときにコストがどのくらい上がるか厳密に計算しているというより，OD距離とかで近似的にすることで効率的にしているのではないか． 平松　距離なのでどういう風に迂回は入ってない．分散度合いみたいなインデックスなので，コストが大きくなるようなモノをあぶりだす指標として使っているのではないか？ 大山　問題のクラスと解法がくっつくとより面白い感じがする． 羽藤　そのまま使えそうだが，研究にはならない．めちゃくちゃすごい発展が生まれそうですよね？ Discussion 1避難DARP 増田 重村　避難においてDARPを使うシチュエーション．避難の場合だと，一気に全エリアに来る系だと特定のエリアから避難所への避難輸送になってしまいDARPっぽくない．豪雨などエリアが徐々に迫ってくる場合を考える．住民票など元々あるデータに基づいてリクエストを考える．乗車拒否の問題がまずそう．到着時間が伝えられていて乗車拒否があると，避難できなくなるリスクがある．全体の効用最大化だと逃げ遅れる人が出てくる．システムがなければ，どうにかして歩いて避難しようとするけれども，避難のシステムがあると，自宅で待っていて避難できなくなるのではないか． 西尾　効用関数は，運賃，時間，健康な人は使う必要ないので，健康ダミーを入れるといいのではないか．制約条件として台数も入ってくるのではないか．台数が少なすぎると全員が避難しきれない．多すぎると渋滞が生じる． 平松　本来は運ばれると思っていた人が待っていて，来なくて運ばれないのが問題．豪雨の予報通りに基づいて出発時間を決めて，本当にそうなるのか．早まることはないのか．早まったときの余裕時分を考慮．健康ダミーによる選別は考えやすい．自力では避難できない人の効用の設定は考えやすい．あとは同居者や家族がいるかどうかも必要だと思う．単身世帯だと効用が高くなるかとか．もっといろいろなシナリオ，パターンを考えないと． 羽藤　下流側の方が出発時刻を遅くしても避難できる．上流側は出発時刻を早くしても下流側が混んでいるとさばけない．避難容量は，道路容量とDARPの車両容量をどこでどう消費すればいいかを最適化問題としてみると面白いのではないか．車のcapacityをどういう風に回していくか．やってみないと分からない．ネットワークが災害で切断されるのが入ってくると評価が難しい．海岸の液状化で車でピックアップが難しいが，でも遠いので車で避難したい．車のcapacityは貴重なのでequityを考えてどう割り付けするか． 2付知DARP Laureen Laureen I think that Dial-a-Ride services where you can rejects is carefully focus on only one factor maybe it's better to focus on social equity when defining criteria to refuse trips, it may be interesting to consider factors (car, trip purpose etc...) The idea focuses on elderly people etc... Hato dependencyについて Hiramatsu utility function, dummy, purpose (すみません，ちゃんと聞き取ることができませんでした，ごめんなさい) 3えきまちDARP 手代木 駅に小型モビリティをおいて拾って届けていく 手代木　新幹線しか通っていない地方の駅に着目 羽藤　中津川？ 手代木　本数が少ないので，駅に行くとき帰るときの時間が固まる．候補が少ない？論文のアルゴリズムでは，受け入れユーザからルートであったが，効率よくないのではないか．一体的に受け入れユーザとルートを同時に考えるといいんじゃないか．リクエストをもらってモ乗れないとなるとかわいそうなので，OD距離が長い人ほど優先して乗れる．近い人は歩いてもらう． 平松　輸送ルートと誰を運ぶかを同時に考えるのが良いんじゃないかと思う．行先は大体ホテルだとすると行先は絞れるのではないか．輸送ルートが絞れているので先に決めて，誰を乗せるかあとから調整するといいんじゃないか 羽藤　タクシーの売上めっちゃ減りそう．浜センで昼になると車がないからいつも隣で食べるが，昼ご飯DARPがあると，それでお店に行って，食べ終わったときにまた乗って駅の遠くにある店舗と組んでやるとよさそう．相補性を活かす．出発時刻をそろえているからできる． 4おきなわDARP 倉澤 内谷　混雑を減らしていきたいという話を出発点で考えた．混雑を減らしたいときに，どういう人をターゲットにするか．今徒歩で移動している人をDRTで運んでも自動車で移動する人が増えるだけなので，今自動車で移動している人たちに対して乗り合いのモノに転換してもらう取り組みにしないといけない．乗り合い交通は交通弱者のためのものなので，うまく効用関数に混雑の効果を入れて考えるときに，バランスの取れた重み付けをする．バランスを取らないといけない．計算方法までは考えられていない．効用関数に混雑効果を入れる． 平松　効用関数に入れるとかだと，自動車交通の方で混雑の効果を入れるとできる．DRTを使うことの効用で，他の手段を使えない人の効用を高める．それは両立できる．自治体目線で社会的効用の最大化もできるのではないか 羽藤　シングルマザー世帯，高齢者の独居など多様なパターンがある．多様なパターンごとにまとめると効率的にDARPができそう．えきまちDARPのように，発時間や活動場所をそろえるみたいな，地域のactivity baseで揃えていくと面白いのではないか． 5舗装DARP アスファルトの舗装を順番にしていく 須賀　道路利用者を考慮して，昼と夜のどっちに工事をするか．働き方改革で昼間に工事をやりたいが，渋滞が生じる．スケジューリングが大事．状態が悪い方を直さないといけないが，少ない方を選ぶ問題．駅まで行く道を同じ時期にやると通れなくなるので，昼夜どちらに直すか，修繕道路のネットワークの組み合わせを変数に入れる．事業者側の賃金の予算制約．夜は高い． 小川　交通量を考えるときに均衡配分を考えることがあるが，双対問題で交通量を制約条件とした問題．道路の修繕のスケジューリングで，双対問題の最適化問題を考えて，交通量とリンクの通過速度の制約条件を考えると，アクセスを考慮しつつ交通量に応じたスケジューリングが考えられるのではないか． 平松　須賀さんのは，効用が高いモノから順に道路を選ぶが，目的関数の総収入に相当するものが何になるのかが分からない．修繕の進捗か？　小川さんの方は，リンク交通量を舗装すべき量に？ 小川　交通量は制約条件．操作するのは，道路が修繕箇所なのか．リンクコストになる． 平松　リンクコストになっている修繕コストを最小化するときに，制約条件として交通量を満たさないといけないということ？ 羽藤　修繕コストをリンクコストに反映させる．制約条件にして双対問題にすると，きれいに解ける．均衡配分で交通量にどれくらい影響をあたえるのかという問題と，修繕コストが昼やるか夜やるか，順番も含めて拡張するということ．土木学会論文賞もらえそう． 羽藤　DARPの応用性はどうですか 平松　効用関数の置き方にバリエーションが考えられるので，目的関数ではうまくできないいろいろな指標(避難の指標など)を入れられるのではないか． 羽藤　グループでやるとGeneralな話になりがちだが，数理的な部分を突き詰め無いと研究に進展がない．数理的な部分を話してくれているので，次回からもそうコメントするとよい．DARPでどういうところが共通で面白いのか，発展性のある議論に．