特にこのタイプの交通機関の人気が最近高まっており、価格が着実に下がっているので、タクシーサービスを使用したことがない人はおそらく非常に少ないでしょう。 個人的な経験から、これは、たとえば小さな子供と一緒に診療所に行くのに便利な方法であると言えます。
タクシーを使って何を払うのか疑問に思ったことはありませんか？
間違いなく、主な部分はドライバーの時間と車のコストの料金ですが、この料金があなたが道路にいる間にのみ適用されると仮定するのはかなり急です。 タクシーの運転手が次の注文まで長い時間待たなければならない場合、誰が彼の時間と簡単な車を支払うのでしょうか？ -最後に、私たちはあなたと一緒です。 タクシーの運転手は、労働市場での価値よりも低い日の報酬に正当に同意せず、同時に平均5命令または25命令を実行します。 ダウンタイムが誰にとっても有益ではなかった時間と、それをどのように削減できるかについて興味がありました。 以下に、この問題に関する私自身の研究の結果を共有したいと思います。
現代のタクシー運転手はどのように機能しますか？
彼は、ディスパッチャーまたはタクシードライバーの申請書から注文を受け取り、乗客を必要な場所に連れて行き、ほとんどの場合、着陸地点の近くで次の注文を待ちます。
このポリシーが悪いのはなぜですか？
市内のあまりにも多くのエリアに、次の注文のために長い時間並んでいなければならないタクシー運転手が多すぎるという状況につながる可能性があります。
他の地域では無料の車が不足しているため、一部の注文が失われます。 最も深刻な形では、説明されている問題は毎日の移動の結果として発生します。朝、タクシー運転手は、労働人口の流れとともに、居住地域から「流れ去り」、その時点で彼らのサービスの需要が増加し、反対に注文密度が低下している中心部に蓄積します。特に家に帰りたい人はほとんどいません。
以前の結論はもっともらしい推論であるか、それとも何らかの形で実際にテストされているか？
初めてこのことを考えたとき、私を連れてきたタクシー運転手とコミュニケーションをとるのは、常識と経験不足に頼っていました。 ただし、タクシーサービスの作業を最適化するアルゴリズムの最初のスケッチを受け取ったその瞬間に、もちろん自分の仮説をテストし、ソリューションの有効性を評価したかったのです。 明らかな理由により、Uber、Gett、または「国内の」Yandex.Taxiなどの主要な市場プレーヤーのいずれも、必要な情報を公開したくない。 幸いなことに、遠くのシカゴの行政機関は、長年にわたって市内のタクシーサービスの大部分のすべての旅行に関するデータを収集し、公開しています（詳細については、「データノート」を参照）。
2016年のシカゴの状況はどうでしたか？
職場でのすべてのタクシー運転手が費やした時間のうち、私の推定によると（彼らの方法論はサービス時間の推定に関する注意事項に詳しく説明されています）、せいぜい46％だけが注文の実行に占有されていました。 毎日の移住の影響のマイナスの兆候については、平均して、行政区域内の利用可能な車の数は、現時点での受注数の30％前後です。
何をどのように改善できますか？
言うまでもなく、次の2つの明確なアクションがあります。
1）車の数が多すぎる地域から、車が不足または期待される地域への車の移動を手配する。
2）各地域で、注文待ちのマシンの最適な数を維持します。
もちろん、利益を最大化するより一般的なタスクを提示することは可能ですし、その解決の過程で、「不利な」ルートの一部を提供することさえ拒否しますが、競合するプレイヤーが「不利な」ルートでサービスを提供する場合、そのような戦略は一般的に有益なユーザーへのコミットメントの損失を伴う会社に満ちています。 この可能性を考えると、利用可能なすべての注文を提供する試みは、最低コストで十分に合理的であると思われます。
適切なトラフィック再配布アルゴリズムにはどのような要件を提示する必要がありますか？
ここで、私の意見では、次の条件が望ましいです。
a）乗り換えに費やされる合計時間は乗客によって支払われないため、できるだけ小さくすることをお勧めします（たとえば、私が書いたプログラムでは、グラフの特別な最小化アルゴリズムがこれに使用されますが、それについては後で）。
b）ドライバーの豊富さは、ほとんどの場合、ドライバーによって実行された注文の量に直接依存するため、アルゴリズムを実装するためのオーバーヘッドコストがドライバーのそれぞれに均等にかかることが望ましいです。 また、別のエリアへの移動命令を受けたドライバーは、15分かかるとそれを実現する可能性が高く、50分である場合は無視する可能性が高いことに留意する必要があります。
c）各地域の無料車の数の不足の程度は日中変動するため、アルゴリズムは十分な効率で不均衡を解消し、移動の流れを計画する際に、将来の状況を考慮してそれらを計算する必要があります。
d）アルゴリズムの計算の複雑さにより、アルゴリズムを実行できるようになります。
物事をはるかに簡単にする小さなトリック
目の前に並んでいる20人の兵士を想像してください。 最初の前の場所が占有され、最後の場所が空けられるようにするにはどうすればよいですか？ 一つの方法は、最後に立っている人に前に進むように頼むことです。 同じことをするが、20倍速い別の方法は、すべての兵士に1ポジションだけ移動するように依頼することです。 タクシー車に適用されるこのアイデアは、次のことを意味します。余剰エリアAから遠隔赤字エリアBに直接移動する代わりに、AからBにつながるエリアのチェーンに沿って1か所だけ車を「移動」できます。一方では、マップ上の赤字の変化率と比較して、ほぼ瞬時に不均衡を解消できます。他方では、ドライバーは「シフト」に毎回15分以内で過ごす必要があります。
トラフィック再配布アルゴリズムを実装するための数学的方法は何ですか？
（ここで、私が開発したアルゴリズムの技術的な詳細を詳細に説明します。結果のみに関心がある読者は、記事のこの部分をスキップできます。）
最小コストの供給ストリームの生産-消費ネットワークの検索グラフで、 問題を既知の問題に還元してみましょう。 タクシー車の需要と市内でのそれらの分布は時刻と曜日に依存するため、曜日と時間間隔1時間ごとに以下の方法で個別の列を作成します。 グラフの頂点は行政区になります。 注文後に予想されるマシンの数Iが予想される注文数Uを超えたものは、S = I-Uの容量を持つ生産センターの役割を果たし、残り-S = U-Iの容量を持つ消費センターの役割を果たします。Sの値は不均衡と呼ばれますピーク（地区）。 15分を超えない時間tで平均してAからBに到達できる場合（およびその場合のみ）、tはこのリブのコストです（詳細については「注地域間の移動時間の推定」）。 生産-消費ネットワークの古典的な問題では、許容流量の制限にグラフの端がありますが、検討中のケースでは、タクシー運転手のみが交通渋滞を引き起こすことができると仮定することは困難ですが、運転手を「シフト」するために同じ間隔で2回は悪い形になるでしょう私たちの側で。 最後のコメントまでに、上からの「せん断」フローはIを超えてはなりません。
最小コストのフローを見つける標準タスクにアルゴリズムを適用できるようにグラフを変換する方法はありますか？
任意の頂点を選択して、2つの新しい頂点に置き換えて、最初の頂点に元のエッジをすべて含め、2番目の頂点に元のエッジをすべて残すようにします。最初の不均衡をSに、2番目の不均衡を0に帰します。 元のグラフの各頂点でこのような変換を行った後、最小コストフロー問題のフォーム標準に変換しますが、これだけではありません。
すべての「消費の中心」のニーズを満たし、すべての「生産の中心」の力を実現するフローを見つけるタスクは一般に解決可能であるため、すべての頂点の合計不均衡は明らかにゼロでなければなりません。 タクシーサービスグラフの最後のプロパティが満たされることを期待できますか？ タクシーの必要性が高まっている朝の時間に作成されたグラフでは、全体の不均衡は負になり、夜の不均衡はその逆になります。 タクシーサービスがこの問題にどのように対処できるか想像してみましょう。関与する車の数が常に需要に適切に対応するタクシードライバーの作業スケジュールを導入するのが妥当です。 これを考慮に入れるために、私のアルゴリズムでは、グラフに追加の「家」頂点を追加し、高コスト（40分）のエッジが各地区に行き、重要ではないことを確認しました。
ところで、最小コストのストリームを見つける問題を数値的に解決する必要がある場合、ウィキペディアや、時代遅れのFord-Bellmanアルゴリズムやループする可能性のあるネットワークシンプレックスメソッドなどのさまざまなフォーラムなどの疑わしいソースに頼ることを強くお勧めします。 この記事には、実行時間に関する優れたアルゴリズムが記載されています。
記事に添付されているプログラムの「内部」では、私のバージョンのEdmonds – Karpアルゴリズムが機能します。
シカゴ市で再配布アルゴリズムを実装する場合の比較オーバーヘッドは何ですか？
平均して、タクシー運転手はシカゴで注文を完了するために1週間に2億7500万秒を費やし、3億1500万秒を見越してアイドル状態にありますが、再配布アルゴリズムはわずか3000万秒しかかかりません。
理想的な輸送組織のすべての時間コストは、注文のリードタイムまたは交通再配分アルゴリズムの要件であると考えることは可能ですか？
残念ながらいいえ！ たとえば、月曜日の9日から10日の午前中の特定の地域で、25の注文が予想され、乗客が下船して15が空いて、さらに10が余剰地域から移動したとします。 無料で必要な車の数はこの期間中にバランスが取れているように思えますが、すべての注文を完了することができると期待する価値はありますか？ 予想される数字が実際の数字と一致する場合でも、一般的に言えば、無料の自動車が到着する順序とその用途は任意です。 注文時の無料車の可用性を保証するために、後者は常に少量の供給を維持する必要があります。 再配布の遅延中に（15分程度）高い確率で枯渇しないマシンの在庫は、（分布のポアソン性）この期間の予想される注文数の約2平方根です。
予想外に、このようなキューで失われる時間は、再配布アルゴリズムに費やされる時間よりもはるかに長く、1週間あたり約1億1400万秒です。 それを減らす方法はありますか？
あなたは何かを思いつくことができます。 アイデアの1つは、特定のエリアに乗客を配達するタクシー車が1分あたり平均間隔で到着する場合、到着時に無料の車がない場合でも、次の注文を拒否しないでください：最大3分後きっと現れるでしょう。 確かに、この待ち合わせ戦略にはマイナスが1つあります。車の「フィード時間」が長くなります。 私のアルゴリズムでは、各エリアのキューサイズを、5分以内に到着する車の平均数だけ減らしました。 このような措置により、「ファイリング時間」が5分増加することはまれですが、計算のためのキューの合計ダウンタイム損失は2倍以上減少し、週に5,000万秒に減少します。
最終結果は何ですか？
シカゴの場合、計算（以下のリンクにあります）に従って、無料の自動車を再配布するためのアルゴリズムと個々のエリアでのキューのサイズの管理を組み合わせて使用すると、旅客輸送に起因する時間の割合が46％から77％に増加します。 計算が正しければ、シカゴでの実装により年間約1500万ドル、モスクワの規模の都市で約1億ドルの節約になります。これは現在、道路上にとどまり、誰にも利益をもたらさないお金です。
このタスクに関連するコードプロジェクトは、 ここから入手できます 。
データノート
計算では、2016年全体のデータを使用しました。 2か月前、データセットにはさらに多くのフィールドがあり、それらの間には正確な座標と注文の支払いに関する多くの情報がありました。 どうやら、それらの一部はタクシーサービスの商業的利益に隠されていました、そしていくつかは彼らの個人的な生活の問題のために。 その時点で利用可能であったすべてのフィールドが必要というわけではなく、最終的に作業を開始したファイルはこちらにあります 。 その中の1つのエントリは以下で構成されます。
- 注文番号暗号、
- 車のコード番号、
- 乗降の日付と時刻、時計上の最も近いマークに丸められ、15分の倍数、
- 長いマイル
- 秒単位のリードタイム
- シカゴの行政区域、上陸、それに応じて上陸、
- 着陸地点と着陸地点のおおよその地理座標。
このファイルのサイズは約8ギガバイトで、そのうちの3分の2が不適切に長い暗号を占めています。 データを操作しやすくするために、辞書の順序付け時に暗号をシリアル番号に置き換え、一部の数値をテキスト形式から数値に変換し、レコードをユーザークラス「日付単位」クラスのオブジェクトとして保存しました。 その過程で、完全に非現実的なデータを含む少数のレコードを破棄しました。 コンパクトなパッケージ化により、同じ量の情報のスペースが750メガバイトに削減されました。 後者のファイルは、 参照 、およびこのプログラムのストレージ形式などでも見つけることができます。
サービス時間の見積もりに関する注意
私が受け取った週の平均リードタイムは、各旅行の記録に示されているリードタイムを52で割った合計です。ご覧のとおり、魔法はありません。 ダウンタイムを見つけるために、最初に各マシンの完了した注文の時間順リストを作成し、次の注文の開始時間から前の注文の時間を引いて、いわゆる「タイムアウト」の新しいリストを受け取りました。 ここで2つの困難が生じました。 データに関するメモで述べたように、乗船と降車の時刻に関するエントリはリアルタイムではなく、ダイヤル上の最も近いマークへの丸め、15分の倍数です。 2番目の問題は、勤務シフト間の休憩をダウンタイムと見なさないことでした。 ランダムな30台のマシンの「タイムアウト」の分布をアンロードすることで2つ目を決定しました。15〜45分のオーダーの待機時間が特徴的な現象であり、1時間ごとのダウンタイムが非常に一般的でした。 これから、ダウンタイムの計算には1時間半未満の「タイムアウト」のみを含め、残りは無視する必要があると結論付けました。 考慮に入れたすべてのタイムアウトを合計することで、最初の問題を回避しました。 なぜこれを行うことができますか？ これは確率理論の興味深いタスクです-長さLの鉛筆がルーラー上にランダムに配置され、その端の座標を最も近い整数に丸めた場合、これらの丸められた値の差の数学的な期待値は正確に鉛筆の長さになります
地区間の移動時間の見積もりに関する注意
このような評価の最初のアイデアは、特定の時刻および曜日について、ある地域から別の地域への旅行の利用可能なすべての記録の時間を平均することでした。 しかし、荷物の梱包、下船、乗客の搭乗、および車を送る必要がない狭い通りに沿った家のポーチへの通路のために、あらゆる種類の時間のために、この値はわずかに過大評価されるように思われました。 したがって、注文時間は、一定の遅延定数と、注文で指定された距離に比例する値であると単純に仮定しました。 最小二乗法（ このプログラムを参照）を適用して定数を切り取り、2番目の項のみを平均しました。 注文時間の定数の割合が3分の1を超える場合、3分の1だけを減算しました。