連載第一回目から三回目は、メタヒューリスティックな解法とOptaPlannerの基礎をシフトスケジュールを題材に解説しました。連載第四回目では、巡回セールスマン問題などの経路最適化をOptaPlannerで解く方法を解説します。
サンプルコートはこちらからダウンロードできます。（135KB)
1 経路最適化とは
前回までは、シフトスケジュールを作成する際の仕事と人の最適な組合せをOptaPlannerで解く方法について解説してきました。この組合せ最適化問題の見方を少し変えることで経路のような順序の最適化問題にも利用することができます。
例えば、スタート地点、ゴール地点、地点A、B、C、D、Eの7地点が存在し、スタート地点から出発しA～E地点を必ず1回経由しながらゴール地点へ向かう場合、どのようなルートが考えられるでしょうか。
地点から地点への移動に制限が無く移動コストを考える必要が無ければ、様々なパターンが考えられると思います。例えば [スタート]-[A]-[B]-[C]-[D]-[E]-[ゴール] や[スタート]-[E]-[D]-[C]-[B]-[A]-[ゴール]です。 スタート地点から次の地点へ移動する際、選択肢は5つあります。各地点は1回だけという制限はありますから次に移動する際は残っている4地点から選択することになります。よって、これを続けるとA～E地点を経由するパターンは以下のように計算することができます。
5×4×3×2×1=120通り
実際に人がスタート地点からゴール地点にA～E地点を1回ずつ経由しながら歩いていく場合、多くの人は最短ルートでA～E地点を回ってゴールに到着したいと思うでしょう。120通りであれば、ExcelやJavaなどを使って全てのパターンでの歩く距離を算出し最も短いルートを見つけ出すのは簡単なことだと思います。
しかし、途中の地点が20地点あった場合はどうなるでしょうか。答えは約243京通りになり、1秒間に1億パターンを計算できても約790年間計算機を回す必要があります。
ですので、地点が増えると全パターンから最も良いルートを探し出すのは困難になってきます。これは前回までのシフトスケジューリングと同じ現象ですが、経路最適化を解く場合にもメタヒューリスティックな解法を利用することが出来ます。
この経路最適化は「巡回セールスマン問題」として多くの人が聞いたことがあると思います。この問題は昔から多くの人が挑戦し様々は解法が発案され、実際に業務の改善に利用されています。以下の書籍には巡回セールスマン問題の歴史や活用場面も書かれており、巡回セールスマン問題の奥深さが分かる非常に面白い書籍です。
青土社「驚きの数学 巡回セールスマン問題」
https://www.seidosha.co.jp/index.php?9784791767106
2 経路最適化を組合せで表現する
実際に経路最適化をOptaPlannerで解く場合、シフトスケジュールの組合せを表現する際に用いた1:Nの関係では経路最適化の問題を表すのは困難です。そこでChained Variable実装パターンを利用します。この実装パターンを利用すると、以下のようなクラス図の「一つ前」になるインスタンスをOptaPlannerに探索させることが出来ます。
[先頭]のインスタンスをスタート地点、[後続]のインスタンスをA～E地点とすると、以下のような地点の連鎖（チェーン：Chain）を表現することができます。
個々に見ると、[A地点]には[スタート地点]を、[B地点]には[A地点]を、という組合せを決めていると見ることが出来ます。つまり地点の組合せを作っており、OptaPlannerによる組合せ最適化で適切な経路を解くことが出来ます。
上記では[B地点]には[A地点]・[C地点]には[B地点]・[D地点]には[C地点]という組合せですが、[B地点]には[C地点] ・[C地点]には[A地点]・[D地点]には[B地点]とすることで以下の経路に変えることができます。経路を維持しながら順序を入れ替えるには何点か考慮が必要ですが、OptaPlannerがChained Variable実装パターンに合わせて適切に組合せを入れ替えます。
3 経路最適化をOptaPlannerで表現する
地点の組合せによる経路最適化はOptaPlannerのサイトで公開されている「vehiclerouting」デモで実装されています。今回はそのデモをベースにしています。また、「vehiclerouting」デモでは、連鎖を表現するためにインタフェースを利用していましたが、今回は実験的に抽象クラスを利用しています。この辺りは実際の問題のドメインに合わせて設計して頂ければと思います。
3.1 トラックによる荷物回収時の経路最適化
「vehiclerouting」は複数台のトラックで複数の荷物を回収してくる問題で、出来るだけ最短ルートで出来るだけたくさんの荷物を回収できるルートを探し出すデモになっています。
複数のトラックで複数の荷物を回収したいので、以下のようにトラックを先頭にし、回収する荷物の順番を表現できるようにしたいと思います。
前述では、先頭は[スタート地点]、後に続くのは[＊地点」と場所を表すものでしたが、トラックには出発地点（拠点）が、各荷物にも出荷される場所が属性情報として保持されています。よって、名前の表現は異なりますが地点を回るルートを表現している点では同じです。
実際に地図上に描画すると以下のようになります。（上記では一つ前への矢印、下記では実際に回るルート順序なので矢印の方向は逆になります）
3.2 Chained Variable実装パターンでトラック、荷物を実装する
これをOptaPlannerのクラス設計で表現すると以下のようになります。
Chained Variable 実装パターンで連鎖を表現する際の「先頭」にあたるのがTimeWindowedStepクラスです。本サンプルではトラックだけですのでVehicleクラスを派生クラスとして作成しています。
Chained Variable 実装パターンで連鎖を表現する際の「後続」にあたるのがChainedTimeWindowedStepクラスで、「一つ前の地点」を保持する必要があるため関連（previousStep）を作成しています。また、Chained Variable 実装パターンとするためChainedTimeWindowedStepはTimeWindowedStepの派生となっており、以下のような関係を表すことが出来ます。
previousStepはPlanningVariableアノテーションが付けられています。つまり、「一つ前の地点」はOptaPlannerによって組合せを試行錯誤する対象となっています。
ChainedTimeWindowedStepクラス 61行目
@PlanningVariable(valueRangeProviderRefs = { "vehicleRange", "cargoRange" }, graphType = PlanningVariableGraphType.CHAINED)
public TimeWindowedStep getPreviousStep() {
return this.previousStep;
}
valueRangeProviderRefs属性にはvehicleRangeとcargoRangeを指定しています。つまり「一つ前の地点」はトラック（Vehicle）または荷物（Cargo）のどちらでもOKで、どちらかを組合せるという事です。上記例で[Cargo 1]の一つ前は[Vehicle 1]、[Cargo 3]の一つ前は[Cargo 1]となっているように、トラック（Vehicle）または荷物（Cargo）を組合せることで経路が完成します。
3.3 移動中の休憩を実装する
トラックが朝出発して荷物の回収を終えて夕方に帰ってくる場合、お昼休みのための時間は確保しておかなければなりません。ですので、ある荷物の回収とある荷物の回収の間の休憩用のタイミングを表現するためにBreakクラスを作成しています。
BreakクラスもChainedTimeWindowedStepの派生になっているため、荷物（Cargo）と同じように扱うことが可能で、以下のように休憩のタイミングを表現します。
3.4 InverseRelationShadowVariableアノテーションで地点間の双方向を実現する
OptaPlannerでは「一つ前の地点はどこか？」を割当てることで経路を作ります。よって一つ前の地点（previousStep）はJavaのプロパティで取得可能です。しかし実際に制約式を作成したり、割当結果を活用したりする際は「次の地点はどこか？」を取得できる方が便利なことが多いと思います。そこで、TimeWindowedStepクラスにはChainedTimeWindowedStepへの関連（nextStep）を作成しています。
しかし、組合せを試行錯誤する対象であるpreviousStepが決まれば、nextStepは自動的に決まるはずなので探索する対象ではありません。
そこで、InverseRelationShadowVariableアノテーションをnextStepプロパティに付けることで、OptaPlannerがpreviousStepを設定した際、自動的にnextStepにも対応するインスタンスを設定してくれます。
TimeWindowedStepクラス 106行目
@InverseRelationShadowVariable(sourceVariableName = "previousStep")
public ChainedTimeWindowedStep getNextStep() {
return this.nextStep;
}
sourceVariableName属性には対応するプロパティ名のpreviousStepを指定しておくことで、関係を指定します。
例えば、OptaPlannerが組合せを探索している際に[Cargo 3]の一つ前（previousStep）に[Cargo 1]を指定すると、OptaPlannerは自動的に[Cargo 1]の一つ次（nextStep）には[Cargo 3]を設定してくれます。よって、以下のようにpreviousStepとnextStepの関連が設定されます。また、最後の地点の場合は次が存在しないのでnextStep はnullとなります。
3.5 CustomShadowVariableアノテーションで連鎖する状態変化に対応する
実際に制約式を作成したり割当結果を活用したりする際は、荷物を回収するトラックや、トラックが荷物のところに到着する時間などが必要になると思います。これらの値は関連をたどることで取得することが可能なのでCargoクラスの内部に実装することも可能ではあります。しかし、それを行うとOptaPlannerでは大きな不具合が発生します。
OptaPlannerでは、DRLのパフォーマンスを向上させるため、インスタンスのプロパティ値が変化したことにより再確認する必要があるルールだけを再評価し、ペナルティ値を差分更新します。ですので、どのインスタンスが変化したのかOptaPlannerに知らせる必要があります。Planning VariableやInverse Relation Shadow VariableはOptaPlanner自身が値を変化させるのでプロパティ値の変化を知ることが出来ますが、それ以外のプロパティ値の変化や、関連により他のインスタンスのプロパティ値の変化した場合は理解できていません。ですので、明示的にプロパティ値が変化したことをOptaPlannerに通知する必要があります。
「荷物がどのトラックに回収されるか」を例にすると、経路を探索し組合せを変化させると以下のように元々[Vehicle 1]に回収される[Cargo 3]が[Vehicle 2]で回収されるようになることがあります。
Cargoのvehicleプロパティはその荷物がどのトラックに回収されるかを取得できるので、上記のような場合はvehicleプロパティが変化しOptaPlannerへの通知が必要となります。
そこでOptaPlannerでは組合せを変化させた場合に呼び出されるVariableListenerにて、組合せの変化に伴って変化するプロパティを外部から設定します。
組合せの変化に伴って変化するプロパティにCustomShadowVariableアノテーションを付け、組合せが変化した際に呼び出すVariableListenerと、どの組合せが変化した際にVariableListenerを呼び出すか設定します。
ChainedTimeWindowedStepクラス 79行目
@Override
@CustomShadowVariable(variableListenerClass = VehicleUpdatingVariableListener.class, sources = { @CustomShadowVariable.Source(variableName = "previousStep") })
public Vehicle getVehicle() {
return this.vehicle;
}
public void setVehicle(final Vehicle vehicle) {
this.vehicle = vehicle;
}
上記の設定によりVehicleUpdatingVariableListenerクラスは、ChainedTimeWindowedStepそのものが新しく追加されたり削除されたりした場合や、ChainedTimeWindowedStepの一つ前（previousStep）が変化した際に呼びされます。
VehicleUpdatingVariableListenerクラスのafterVariableChangedメソッドは一つ前の地点（previousStep）が変更された後に呼びされ、第二引数は対象となったChainedTimeWindowedStepそのものです。これにより、対象となったChainedTimeWindowedStepの変化後のpreviousStepの情報を用いて自身を担当するトラックを判断、更新する必要があればChainedTimeWindowedStepのvehicleプロパティを更新しています。
VehicleUpdatingVariableListenerクラス 34行目
@Override
public void afterEntityAdded(final ScoreDirector scoreDirector,
final ChainedTimeWindowedStep cargo) {
this.updateVehicle(scoreDirector, cargo);
}
VehicleUpdatingVariableListenerクラス 46行目
@Override
public void afterVariableChanged(final ScoreDirector scoreDirector,
final ChainedTimeWindowedStep cargo) {
this.updateVehicle(scoreDirector, cargo);
}
VehicleUpdatingVariableListenerクラス 64行目
protected void updateVehicle(final ScoreDirector scoreDirector,
final ChainedTimeWindowedStep sourceCargo) {
TimeWindowedStep previousStep = sourceCargo.getPreviousStep();
Vehicle vehicle = previousStep == null ? null : previousStep
.getVehicle();
ChainedTimeWindowedStep shadowCargo = sourceCargo;
while (shadowCargo != null && shadowCargo.getVehicle() != vehicle) {
scoreDirector.beforeVariableChanged(shadowCargo, "vehicle");
shadowCargo.setVehicle(vehicle);
scoreDirector.afterVariableChanged(shadowCargo, "vehicle");
shadowCargo = shadowCargo.getNextStep();
}
}
例えば、[Cargo 3]の一つ前の地点を[Cargo 1]から[Cargo 2]に、[Cargo 5]の一つ前の地点を[Cargo 2]から[Cargo 1]に入れ替えた場合、組合せ更新後の[Cargo 3]の一つ前の地点は[Cargo 2]であり担当するトラックは[Vehicle 2]です。しかし、[Cargo 3]のvehicleプロパティは何も操作されていないので担当するトラックは[Vehicle 1]のままです。よって、vehicleプロパティに[Vehicle 2]を設定してやります。
さらに、[Cargo 5]についても同様に[Vehicle 2]から[Vehicle 1]に更新しますが、後続の[Cargo 6]についても同じように[Vehicle 2]から[Vehicle 1]に更新しなければなりません。これがwhileの中で行っている事です。
「荷物のところにトラックが到着する時間」についても同様です。一つ前の地点の割当が更新されると移動時間が変化するためChainedTimeWindowedStepへの到着時間（arrivalTime）を更新、OptaPlannerにも変更を通知します。
また、ChainedTimeWindowedStepへの到着時間が変わると後続のChainedTimeWindowedStepへの到着時間へも影響が出るため、Whileの中で後続のChainedTimeWindowedStepの到着時間を再計算し設定し直しています。
ChainedTimeWindowedStepクラス 99行目
@CustomShadowVariable(variableListenerClass = ArrivalTimeUpdatingVariableListener.class, sources = { @CustomShadowVariable.Source(variableName = "previousStep") })
public Integer getArrivalTime() {
return this.arrivalTime;
}
ArrivalTimeUpdatingVariableListenerクラス 34行目
@Override
public void afterEntityAdded(final ScoreDirector scoreDirector,
final ChainedTimeWindowedStep cargo) {
this.updateVehicle(scoreDirector, cargo);
}
ArrivalTimeUpdatingVariableListenerクラス 46行目
@Override
public void afterVariableChanged(final ScoreDirector scoreDirector,
final ChainedTimeWindowedStep cargo) {
this.updateVehicle(scoreDirector, cargo);
}
ArrivalTimeUpdatingVariableListenerクラス 64行目
protected void updateVehicle(final ScoreDirector scoreDirector,
final ChainedTimeWindowedStep sourceCargo) {
// 一つ前の地点を出発する時間を取得
TimeWindowedStep previousStep = sourceCargo.getPreviousStep();
Integer departureTime = previousStep == null ? null : previousStep
.getDepartureTime();
ChainedTimeWindowedStep shadowCargo = sourceCargo;
// この地点への到着時刻を計算
Integer arrivalTime = this.calculateArrivalTime(shadowCargo,
departureTime);
while (shadowCargo != null
&& ObjectUtils.notEqual(shadowCargo.getArrivalTime(),
arrivalTime)) {
// 計算した到着時間を設定する
scoreDirector.beforeVariableChanged(shadowCargo, "arrivalTime");
shadowCargo.setArrivalTime(arrivalTime);
scoreDirector.afterVariableChanged(shadowCargo, "arrivalTime");
// 次の地点の到着時間を計算するために
departureTime = shadowCargo.getDepartureTime();
shadowCargo = shadowCargo.getNextStep();
arrivalTime = this.calculateArrivalTime(shadowCargo, departureTime);
}
}
private Integer calculateArrivalTime(final ChainedTimeWindowedStep cargo,
final Integer previousDepartureTime) {
if (cargo == null) {
return null;
}
if (previousDepartureTime == null) {
// 前の地点の出発時間が無い場合
// 出荷準備が可能な時間、または、移動に必要な時間の、の大きい方を選択する
return Math.max(cargo.getReadyTime(),
cargo.getTravelTimeToPreviousStep());
}
// 移動距離を移動に必要な時間とし、前の地点の出発時間に移動に必要な時間を足す
return previousDepartureTime + cargo.getTravelTimeToPreviousStep();
}
4 経路を最適化するための制約式を作成する
DRLの基本的な記述方法とルールの解釈については第二回目を参照してください。
4.1 トラックの最大積載量
出来るだけたくさんの荷物を回収してくることが求められますが、トラックに積める荷物には限界があります。各トラックが担当する荷物の総量がトラックの最大積載量を越える場合にはペナルティを与え、より良い組合せを定量的に評価できるようにします。
まずトラック（Vehicle）を参照し、そのトラックに属する荷物（Cargo）の大きさ（size）の合計値がトラックの最大積載量（capacity）を越えたとき、オーバーした分の荷物のサイズをHardな制約のペナルティとして追加しています。
scoreRules.drl 40行目
/*
* 集荷を担当する顧客が出荷する荷物の総量が、トラックの積載可能数をオーバーしないこと
*/
rule "vehicleCapacity"
when
$vehicle : Vehicle($capacity : capacity, dummy == false)
$sizeTotal : Number(intValue > $capacity) from accumulate(
Cargo(
vehicle == $vehicle,
$size : size),
sum($size)
)
then
scoreHolder.addHardConstraintMatch(kcontext, new BigDecimal($capacity - $sizeTotal.intValue()));
end
4.2 休憩の回数とタイミング
移動中に休憩（Break）も必ず一回入るようにします。
breakTimeCountルールでは、まずトラック（Vehicle）を参照し、そのトラックに属する休憩の個数が1個以外であれば差分をHardな制約のペナルティとして追加しています。この際、休憩の数が1個により近ければ追加されるペナルティを少なくし、より良い状態である事を定量的に判断できるように 「(休憩の個数-1)の二乗」をペナルティとしています。
休憩（Break）のreadyTimeには休憩取得可能開始時間、dueTimeには休憩取得可能終了時間が設定されていますので、休憩は指定の時間内に取得しているようにします。
breakTimeArrivalTimeルールでは、Breakに到着する時間（arrivalTime）は休憩取得可能開始時間（readyTime）より遅くなるように、readyTimeよりarrivalTimeが小さくなった場合にペナルティを追加しています。
breakTimeDueTimeルールでは、到着時間（arrivalTime）に休憩時間（breakTime）を足した休憩が終わる時間が休憩取得可能終了時間（dueTime）よりも早くなるようにペナルティを与えています。
scoreRules.drl 57行目
/**
* 休憩時間の合計は1回取っていること
*/
rule "breakTimeCount"
when
$vehicle : Vehicle(dummy == false)
$breakCount : Number(intValue != 1 ) from accumulate(
$break : Break(vehicle == $vehicle),
count($break)
)
then
scoreHolder.addHardConstraintMatch(kcontext, new BigDecimal(-1 * (int)Math.pow($breakCount.intValue() - 1,2)));
end
/**
* 休憩時間は指定された時間内に取得していること
*/
rule "breakTimeArrivalTime"
when
//休憩取得可能時間の開始よりも、先に入るのはNGとする
Break(readyTime > arrivalTime, vehicle != null, vehicle.dummy == false, $arrivalTime : arrivalTime, $readyTime : readyTime)
then
scoreHolder.addHardConstraintMatch(kcontext, new BigDecimal($arrivalTime.intValue() - $readyTime));
end
rule "breakTimeDueTime"
when
//休憩取得可能時間の終了よりも、休憩終了が遅くなるのはNGとする
Break(arrivalTime != null, arrivalTime + breakTime > dueTime, vehicle != null, vehicle.dummy == false, $arrivalTime : arrivalTime, $dueTime : dueTime, $breakTime : breakTime)
then
scoreHolder.addHardConstraintMatch(kcontext, new BigDecimal($dueTime - ($arrivalTime.intValue() + $breakTime)));
end
今回のサンプルでは、荷物を回収する道筋の任意の場所（コンビニやファミレス等々）で休憩を取ってもらうという考えです。ですので、休憩（Break）は荷物（Cargo）のようにある地点まで移動する時間は必要なく、またある特定の地点で休憩を取る必要もないと仮定しています。
よって、BreakではgetLocationメソッドで一つ前の地点のLocationを返すようにしています。
Breakクラス 68行目
@Override
public Location getLocation() {
// 休憩はその場所で取るので、一つ前のLocationを返してあげる
return this.getPreviousStep().getLocation();
}
また、休憩に入るための移動距離自体は無いので0を返すようにしています。
Breakクラス 82行目
@Override
public int getTravelTimeToPreviousStep() {
// 休憩は移動時間は必要ないので
return 0;
}
これにより、荷物（Cargo）と休憩（Break）が混ざっている場合でも、正しく到着時間（休憩の場合は休憩に入る時間）をArrivalTimeUpdatingVariableListenerで算出・設定できるようにしています。
4.3 集荷は指定した時間内に
荷物（Cargo）は指定された時間までに回収に行かなければなりません。ですので、その荷物のところへの到着時間（arrivalTime）は回収期限（dueTime）よりも先でなければなりません。
scoreRules.drl 91行目
/*
* 集荷のリミット時間より到着時間が大きくなると、集荷が間に合っていないのでNGである
*/
rule "arrivalAfterDueTime"
when
Cargo(dueTime < arrivalTime, $dueTime : dueTime, $arrivalTime : arrivalTime, vehicle != null, vehicle.dummy == false)
then
scoreHolder.addHardConstraintMatch(kcontext, new BigDecimal($dueTime - $arrivalTime.intValue()));
end
また、荷造りが完了していないと積み込むことは出来ないので荷物には荷造完了時間（readyTime）があります。もし荷造完了時間よりも早く到着してしまった場合も、同じようにペナルティを追加する方法もありますが今回はあえて行っていません。
荷造完了時間よりも早く到着してしまった場合は荷造りが完了するまで待つしかありません。ですので、以下のように到着時間と荷造完了時間の大きい方に、荷物を積み込む時間を足したものを出発時間としています。この場合、荷造りを待つ時間が増えると出発が遅れ定時までに回収できる荷物は自然と減っていき、荷物を出来るだけたくさん集めるためのルール（後述のunassignedルール）のペナルティが増えてしまいます。
Cargoクラス 170行目
@Override
public Integer getDepartureTime() {
if (arrivalTime == null) {
return null;
}
// 早く到着してしまうと荷物の準備完了時間まで待つしかないので
// 到着時間と、荷物の準備完了時間、時間の大きい方に、
// 荷物の積み込み時間を足す
return Math.max(arrivalTime, readyTime) + serviceDuration;
}
4.4 拠点に定時内に戻ってくる
arrivalAfterDueTimeルールでは荷物を期限までに回収するようにしましたが、最後の荷物を回収し拠点に戻ってくる時間は確認していません。
最後の荷物は次の地点が存在しないので「nextStep == null」で取得できます。次に、拠点への到着期限（dueTime）、最後の地点の出発時間（departureTime）、最後の地点から拠点までの移動時間（travelTimeToVehicleDepot）の取得を行い、最後の地点の出発時間（departureTime）に最後の地点から拠点までの移動時間（travelTimeToVehicleDepot）を足したものが拠点への到着期限（dueTime）より大きくなった場合にペナルティを追加しています。
scoreRules.drl 101行目
/*
* 集荷を終えて拠点に戻ってきたとき、時間内に戻ってきていること
*/
rule "arrivalDepotDueTime"
when
//Chained方式なので、最後のnextCargoはNULLになっており、割当が出来ていない荷物はvehicleがnullになるので
//最後の荷物を取得する
ChainedTimeWindowedStep(nextStep == null , vehicle != null, vehicle.dummy == false,
$dueTime : vehicle.dueTime, //拠点に戻ってくるリミットの時間
$departureTime : departureTime, //最後の地点を出発する時間
$travelTimeToVehicleDepot : vehicle.getDepot().getLocation().getTravelTime(location), //最後の地点（ChainedTimeWindowedStep自身）と出発地点（vehicle）の移動時間
$dueTime < $departureTime + $travelTimeToVehicleDepot) //出発地点に戻ってきた時間が、制限時間以上のとき
then
scoreHolder.addHardConstraintMatch(kcontext, new BigDecimal($dueTime - ($departureTime + $travelTimeToVehicleDepot)));
end
4.5 出来るだけ最短なルートを見つけ出す
トラックが地点を回って荷物を回収する際、効率良く巡回したいので移動距離を出来るだけ短くしたいと思います。Cargo、Break共に移動距離はdistanceToPreviousStepで取得できるように実装してあるので、distanceToPreviousStepルールではdistanceToPreviousStepの値を全てペナルティとして追加しています。これにより、より短い巡回ルートを定量的に評価可能です。
しかし、最後の地点から拠点への直接的な関連は定義していないため、distanceToPreviousStepの合計では最後の地点から拠点への距離が含まれません。よってdistanceFromLastCargoToDepotルールでは最後の地点と拠点を利用して最後の移動距離を求め、ペナルティとして追加しています。
scoreRules.drl 121行目
/*
* 一つ前の地点からの距離の総量が小さくなるようにする
*/
rule "distanceToPreviousStep"
when
$cargo : ChainedTimeWindowedStep(previousStep != null, $distanceToPreviousStep : distanceToPreviousStep, vehicle != null, vehicle.dummy == false)
then
scoreHolder.addSoftConstraintMatch(kcontext, new BigDecimal(-1 * $distanceToPreviousStep));
end
/*
* 最後に地点から、出発地点への距離も加える
*/
rule "distanceFromLastCargoToDepot"
when
//Chained方式なので、最後のnextCargoはNULLになっており、割当が出来ていない荷物はvehicleがnullになるので
//最後の荷物を取得する
$cargo : ChainedTimeWindowedStep(nextStep == null , vehicle != null, vehicle.dummy == false)
then
Vehicle vehicle = $cargo.getVehicle();
scoreHolder.addSoftConstraintMatch(kcontext, new BigDecimal(-1 * $cargo.getDistanceTo(vehicle)));
end
4.6 トラック間の負荷を平準化
回収する荷物の個数がトラック間で大きな差が出ると従事する人の不公平感が生まれるので、トラックごとの荷物の回収個数を平準化します。
トラックが回収する荷物のサイズを合計し、事前に求めた平均サイズとの差分の二乗値をペナルティとして追加しています。これはシフトスケジューリングの負荷平準と同じ方法です。
scoreRules.drl 144行目
/*
* トラックごとの回収する荷物の合計を平準化
*/
rule "vehicleSizeLevel"
when
SolutionParameter($countAverage : countAverage)
$vehicle : Vehicle(dummy == false)
$sizeTotal : Number() from accumulate(
Cargo(
vehicle == $vehicle,
$size : size),
sum($size)
)
then
scoreHolder.addSoftConstraintMatch(kcontext, new BigDecimal(-1 * (int)Math.pow($countAverage - $sizeTotal.intValue(),2)));
end
4.7 制約を守りながら出来るだけ荷物を集める
全ての荷物を回収して戻ってくる事が理想ですが、トラックの積載量の問題や拠点に戻ってくる時間が決まっているため、全ての荷物を回収できない場合もあります。それでも可能な限り荷物を回収し、かつ出来るだけ短い距離で巡回したいと思います。
PlanningVariableアノテーションのgraphType属性「CHAINED」とnullable属性「true」は併用できない仕様なので、連鎖（チェーン：Chain）の問題を解く場合は一つ前の地点（previousStep）には必ず何かが設定されることになります。つまり、 Cargoクラスのインスタンスは必ずVehicleを先頭にした並びのどこかに入ります。
この状態では、制約上どうしても回収できない荷物も巡回ルートに含まれることとなり、制約（トラックのキャパシティなど）をクリアすることが出来なくなります。また、この状態でOptaPlannerは探索を続けるため、トラックの間で荷物の押し付け合いが続くことになります。
このような場合、逃げ道を作り制約を守れるようにします。今回の問題の場合は何の制約もない架空のトラック（dummy == true）を1台追加します。荷台のサイズ・稼働可能時間・地点間を移動に要する時間など全て制約を無視できる架空のトラックです。どうにも回収できない荷物はその架空のトラックに担当させることで、他のトラックは制約内で可能な限り最短ルートで出来るだけ多くの荷物を回収してくることが可能となります。
前述までのルールでVehicleは「dummy == false」の条件が付けられてきましたが、これを入れることで架空のトラックについてはペナルティ計算の対象から除外しています。
ここで一点注意しなければならない事として、架空のトラックはどのような荷物を押し付けられても全ての制約を無視できるので、荷物を集めることに関してペナルティは発生しません。ですので、全ての荷物を架空のトラックに押し付けてしまえばペナルティ値が「0」となり、最も良い組合せ（経路）と判断されてしまいます。これでは、実際には誰も荷物を回収に行かなくなってしまいます。
ですので、架空のトラックに担当させる荷物は出来るだけ少なくするという制約だけは必要になります。
scoreRules.drl 162行目
/*
* 架空トラック(いかなる制約も無視できる)が担当する荷物は出来るだけ少なくする
*/
rule "unassigned"
when
$vehicle : Vehicle(dummy == true)
$unassignedSizeTotal : Number() from accumulate(
Cargo(
vehicle == $vehicle,
$size : size),
sum($size)
)
then
scoreHolder.addSoftConstraintMatch(kcontext, new BigDecimal(-1000 * $unassignedSizeTotal.intValue()));
end
このような架空の存在を利用すると、制約上どうしても守れない場合の逃げ道を作り可能な範囲でルールを守った現実的な組合せを出すことも可能となります。第2回目のシフトスケジューリングの問題の際はnullable属性をtrueにすることで割当が出来ない場合を表現しましたが、同じく架空のメンバーを追加しておくことでも対応できます。
5 割当結果を可視化する
5.1 作成された経路を可視化する
サンプルを実行するには、第三回で紹介した環境にて jp.co.ogis_ri.optaplanner.vehiclerouting.App を実行してください。config.xmlのterminationタグに記述された条件を満たすと組合せの結果が以下のようにコンソールに表示されます。
2015-04-23 09:43:48.441 [main] DEBUG j.c.o.optaplanner.vehiclerouting.App - TaskName:TaskName0 ElapsedTime:267679ms BestScore:0hard/-42357soft 2015-04-23 09:43:52.295 [main] DEBUG j.c.o.optaplanner.vehiclerouting.App - TaskName:TaskName0 ElapsedTime:271533ms BestScore:0hard/-42334soft 2015-04-23 09:43:53.107 [main] DEBUG j.c.o.optaplanner.vehiclerouting.App - TaskName:TaskName0 ElapsedTime:272345ms BestScore:0hard/-42318soft 2015-04-23 09:44:20.764 [main] INFO o.o.c.i.l.DefaultLocalSearchPhase - Local Search phase (1) ended: step total (443), time spent (300002), best score (0hard/-42318soft). 2015-04-23 09:44:20.764 [main] INFO o.o.core.impl.solver.DefaultSolver - Solving ended: time spent (300002), best score (0hard/-42318soft), average calculate count per second (2569). 2015-04-23 09:44:20.764 [main] DEBUG j.c.o.optaplanner.vehiclerouting.App - TaskName:TaskName0 ElapsedTime:300002ms BestScore:0hard/-42318soft 緯度 経度 サイズ 準備完了時間 集荷期限時間 積込に必要な時間 1.0976270017875613 1.4303787304242177 3 0 5000 100 1.2055267649276735 1.0897663786188283 3 0 5000 100 0.8473096079696325 1.2917882318610459 3 0 5000 100 0.8751744120578349 1.7835460024092487 3 0 5000 100 1.927325525064954 0.766883029868159 3 0 5000 100 ・ ・ ・ 1.4791015819343634 0.9809176316927872 3 5000 10000 100 0.4548292660875526 0.5087129499106275 3 5000 10000 100 0.11605832148844986 0.8688332583855898 3 5000 10000 100 緯度 経度 容量 稼働可能開始時間 稼働可能終了時間 0.5 0.5 200 0 10000 1.5 1.5 200 0 10000 1.5 0.5 200 0 10000 0.5 1.5 200 0 10000 class Capacity Size Ready Arrival Due DepartureTime ServiceDuration BreakTime Latitude Longitude Vehicle 200 0.5 0.5 Cargo 3 0 196 5000 296 100 0.4177535067516227 0.32261905060111173 Cargo 3 0 439 5000 539 100 0.3179391723277454 0.2207502923832032 Cargo 3 0 648 5000 748 100 0.42076511258340377 0.2578526064958018 ・ ・ ・
出力された結果からは適切な経路が作成されているか判断できないので、この出力結果をルート_デモ.xlsmに貼り付けることで経路を可視化できます。
- [荷物データ]シート：「緯度 経度 サイズ 準備完了時間 集荷期限時間 積込に必要な時間」から続く出力を貼り付け
![ルート_デモ.xlsm [荷物データ]シート](./img/pic201505-17.png)
- [車両データ]シート：「緯度 経度 容量 稼働可能開始時間 稼働可能終了時間」から続く出力を貼り付け
![ルート_デモ.xlsm [車両データ]シート](./img/pic201505-18.png)
- [結果貼り付け]シート：「class Capacity Size Ready Arrival Due DepartureTime ServiceDuration BreakTime Latitude Longitude」から続く出力を貼り付け（トラック毎に空白行が入るので 忘れずコピー）
![ルート_デモ.xlsm [結果貼り付け]シート](./img/pic201505-19.png)
- 最後に[結果を描画]ボタンをクリックします。
![ルート_デモ.xlsm [結果を描画]ボタン](./img/pic201505-20.png)
経路が表示されます。黒・赤・緑・青の大きい丸は各トラックの拠点となります。
最短経路の探索にしては入り組んでいますが、これは荷物を回収できる時間に制約があるためです。
試しに、時間の制約を無くすためにarrivalAfterDueTimeルールとarrivalDepotDueTimeルールをコメントアウトすると、以下のようにより最短ルートと思われる経路になります。
5.2 ベンチマークで処理速度を可視化する
ベンチマークを行うにはjp.co.ogis_ri.optaplanner.vehiclerouting.BenchmarkAppを起動してください。サンプルでは焼きなまし法（Simulated Annealing）、Late Acceptance、禁断探索法(Tabu Search)を試行できるようにしています。
サンプルでは禁断探索法が他に比べ早くに良い経路を見つけ出しており、アルゴリズムにより探索の速度が異なることが分かります。
6 まとめ
今回はトラックの経路の最適化を例にしましたが、経路のような順序を試行錯誤する業務は様々存在します。そのようなときは、OptaPlannerが活用が出来ないか検討されてみてはいかがでしょうか。
『Opta Planner』は、Redhat JBoss BRMS『Business Resource Planner』のコミュニティ版です