問題タブ [jsprit]

私は輸送の最適化と OptaPlanner には不慣れですが、約 1,400 台の車両が 9,000 の場所からピックアップし、特定の時間に 500 の目的地に配達する必要があるという問題に取り組む必要があります。私の目標は、車両を利用して複数の目的地にピックアップし、目的地に複数の車両を使用する輸送計画を作成することです。自転車のメッセンジャー/ TSPPD with OptaPlanner の質問は、私のニーズに対応できる構造を示唆しているようです。

私は Java は初めてですが、プログラミングは初めてではありません。過去に C、C++、および SQL でプログラミングしたことがあります。jsprit も調べて、最適なパスを探しています。Drools が魅力的なのは、絶え間なく変化する制約を整理するまとまりのある方法を提供しているように見えるからです。時間と距離のマトリックスを作成し始めました。これはすぐに完成するはずです。

コメント、考え、提案は大歓迎です！良い方向性があれば、それを始めたいだけです。

jsprit でジョブ (この場合はサービス) 間の関係を処理することは可能ですか?

たとえば、1 つのジョブは、1 つ以上の他のジョブと同時に開始する必要があります。または、あるジョブが別のジョブの終了前に開始されてはなりません (通常のシーケンス)。

そうでない場合、そのような種類の制限を処理できる他の Java ライブラリを知っていますか?

ありがとうございました！

複数の VRP を解決するために jsprit を使用しようとしていますTimeWindows。したがって、「TimeWindowsNotAvailable」クラスをサービスに関連付けるマップを含む新しい Constraint-Class を作成しました。

「TimeWindowsNotAvailable」クラスにはTimeWindows、サービスを実行できない場所のリストが含まれています (たとえば、顧客が家にいないなど)。主な問題は、newAct.getArrTime()が常に 0.0 であることですが、VRP の解では が 0.0 ではないことがわかりますarrTime。

この問題を解決する方法を知っている人はいますか、それとも複数のTimeWindows実装がはるかに難しいですか?

ハード制約により、同じルートで 2 つまたは複数の出荷を行うことは可能ですか?

そうでない場合、そのような種類の制限を処理できる他の Java ライブラリを知っていますか?

ありがとうございました！

私はアルゴリズムを探しています.jspritまたはoptaplannerプロジェクトは私の問題を解決するためにあるようです. 私たちは Java のみを扱います。エントリ ポイントである jsprit の自転車の例を見てきましたが、今度は患者の輸送に関する問題を解決する必要があります。

• ストレッチャーは、ベッド、車椅子、または有効な患者を運ぶことができます。同じ地域に行き、同じ地域から来れば、車いすと有効な車を同時に運ぶことができます。
• 長距離の場合、ベッドにはストレッチャーが 2 つ必要です
• ベッドムーバー（ベッドに固定された電気トラックの一種）1台のストレッチャーを交換
• ベッドムーバーは長距離で最も効率的ですが、短距離でも使用できる場合があります
• ベッドムーバーは、ベッドを助けるだけです（車椅子でも有効な患者でもありません）
• 終了すると、ベッドムーバーはその場にとどまるか、空の公園エリアに戻ります（おそらく1..nの場所）

一般的なルール ：

• エージェントごとの合計輸送時間は、互いに可能な限り等しくなければなりません (公平)
• トランスポートは時間枠で処理され、遅延はできるだけ短くする必要があります (優先度によって異なります)。
• 毎回新しい輸送依頼が来ます
• 2台のストレッチャーよりもベッドムーバーを使用する方が良い

この種の問題を解決する方法を教えてください。可能だと思いますか？

よろしく

私はルート最適化の初心者であり、jsprit を使用して次のビジネス要件を解決するための助けをいただければ幸いです。jsprit の基本を学ぶのに役立つ Stefan Schröder からフィードバックをもらいました。最初にビジネス要件を説明し、その後いくつか質問をします。

目的は、1 か月で完了する必要があるメンテナンス ジョブのリストをスケジュールすることです。1 か月分の毎日のスケジュールを作成する必要があります。ここでの目的は、1 日あたり最大数のジョブを実行することです。

• リージョンごとに 4 つのデポがあります
• 各地域には約 70 の倉庫があり、合計で 300 の倉庫があります。
• その地域内の各デポと倉庫の間の距離がわかっている
• 地域ごとに異なるタイプの車両が 3 ～ 4 台、合計 12 台あります。
• 地域内の車両は、その地域内の倉庫にのみサービスを提供できます
• 地域内の車両には、たまたま終点となる同じ始点があります
• 車両には、容量、集荷、または配送の要件はありません
• 車両は、保守作業を行う作業員の輸送にのみ使用されます
• 各車両の平均速度がわかります
• 約80のメンテナンスジョブタイプがあります
• 各ジョブ タイプの既知の所要時間 (分単位)
• メンテナンス ジョブは特定の時間に開始する必要はありません
• 毎月、実行する必要がある約 200 のメンテナンス ジョブがあります。
• これらのジョブは、どの倉庫でも可能です
• 同じ日または別の日に同じ倉庫で複数のジョブが発生する可能性があります
• 1 日 8 時間のシフトが 3 回あります。午前6時～午後2時、午後2時～午後10時、午後10時～午前6時
• 車両は、シフトの開始時にデポ倉庫を出発し、8 時間のシフト内でできるだけ多くの倉庫を訪問します。
• 次の倉庫に移動するか、デポ倉庫に戻る前に、ジョブが実行されている間、車両は倉庫で待機する必要があります。

私の基本的な理解は、保守作業は jsprit でサービスとして定義でき、車両ごとに開始/返却時間を設定できるということです。また、コスト マトリックスを使用して、車両と倉庫の関係に時間と距離を追加することもできます。私が持っている質問は次のとおりです。

1. 各メンテナンス ジョブはサービスとして定義する必要があります。その結果、VRP ソルバーに渡されるサービス オブジェクトが 200 になりますよね?
2. VehicleTypeImpl には、addCapacityDimension()、setCostPerDistance()、および setCostPerTime() メソッドがあります。これらは正確には何であり、上記のケースをどのように適用しますか?
3. Service.Builder には addSizeDimension() メソッドがあります。それは何をするためのものか？
4. costMatrixBuilder には、TransportDistance と TransportTime を追加するメソッドがあります。これらのメソッドで使用される単位と、それらをどのように使用できますか?
5. デポごとに Coordinate を定義し、VehicleImpl ごとに setStartLocationCoordinate() メソッドに渡す必要があります。これは正しいですか？
6. vehicleBuilder には setLatestArrival( double maxDuration); があります。ここで使われているユニットは？

上記のケースを解決するための助けに感謝します。

ありがとう、アダム

EDIT1：

いくつかの質問

A. setEarliestStart() および setLatestArrival() メソッドは double 値を受け入れますが、これらのメソッドに実際の日付として最も早い出発と最も遅い到着を指定するにはどうすればよいですか? たとえば、開始時刻は 2014 年 11 月 28 日の午後 2 時で、終了時刻は同日の午後 10 時です。

B. サービス時間を分単位で指定する方法はありますか?

C. VehicleTypeImpl.Builder.setMaxVelocity(double inMeterPerSeconds) メソッドは最大速度を想定していますが、車両の平均速度を指定する方法はありますか?

D. すべての車両は 3 シフトで作業する必要があります。これは、同じ車両を 3 回定義する必要があるということですか? シフトごとに 1 つずつ、さまざまな最早出発時刻と最遅到着時刻を指定します。

E. ジョブは月のいつでも実行できるため、各ジョブの時間枠は月の始まりと終わりとして Service.Builder.setTimeWindow() メソッドに渡されますか?

同じタイプで同じ場所から出発する 2 台の車両を使用して VRP を作成しようとしています。最も費用効果の高い方法で、問題の各車両のルートを作成するソリューションが必要です。GraphHopper を使用して、各サービス拠点間の道路距離と時間を計算し、その情報を使用して輸送コスト マトリックスを作成しています。

私の問題は、すべてのサービスが 1 つのルートに配置され、2 番目の車両が使用されないことです。出力では、問題に 2 台の車両が含まれていることがわかりますが、ソリューションには 1 台の車両による 1 つのルートのみが表示されます。

車両の容量とサービスのサイズを設定すると、両方の車両を使用できます。指定しないと無視されることは理解していますが、すべてのサービスが同じ車両を使用することになりますか?

何か不足していますか？

必要に応じてコード サンプルを投稿できます。

ありがとう！

私は jsprit にかなり慣れていないので、複数のルートで車両のルーティングを行う簡単な方法があるかどうか疑問に思っていました。

例: 0 ～ 5 ポンドの重さの荷物 (～100 個) を大量に供給している 1 つのデポと、一度に 15 ポンドを運ぶことができる 1 台の車両。240 分の時間枠があるので、車両を複数回運行させたいと考えています。移動するたびに、車両はデポからさらに多くの荷物を受け取ることができます。

どんな助けでも大歓迎です。

以前に解決した問題を再解決するシナリオでは (もちろん、いくつかの新しいデータを使用して)、一度与えられた車両の最初の割り当てを再割り当てすることは通常不可能です。ドライバーはすでに進行中であり、新しいソリューションでは次のことを考慮する必要があります。

• 仕事は彼のままでなければなりません（別の車両に割り当てることはできません）
• 彼に最初に割り当てられたアクティビティは、今後のソリューションでもそのままにしておく必要があります

簡単にするために、ここでは 1 台の車両のシナリオを使用し、2 番目の箇条書きのみを課そうとします (つまり、特定のアクティビティがソリューションの最初になるようにします)。

これは私が制約を定義した方法です：

これは私がアルゴリズムを構築する方法です：

結果は良くありません。割り当てられた 1 つのジョブ (必要なアクティビティを含むもの) のソリューションしか得られません。デバッグでは、ジョブ挿入の反復で、問題を完全に解決するように見える多くの実行可能なオプションが考慮されることは明らかですが、最終的には、アルゴリズムによって返される最適なソリューションには他のジョブが含まれていません。

更新:さらに驚くべきことは、5 台以上の車両を使用するシナリオで制約を使用すると、正常に機能することです (最悪の結果は 1 台の車両の場合です)。

必要に応じて、より多くの情報を喜んで添付します。

ありがとうザック