mathematical-optimization - 巡回セールスマン（TSP）スキップシティ

Question

巡回セールスマンの問題に似た問題を解決したいのですが、この場合、都市を訪れるコストが高すぎる場合、セールスマンはその都市をスキップできます。

この問題を解決する方法を教えてください。

Answer 1

1 つの方法は、このDrools Plannerの車両ルーティングの例をコピーして貼り付け、次のようにハックすることです。

2 つの乗り物があります: 1 つの実際の乗り物 (= ツアー) と 1 つの未使用の乗り物 (= 使用されていない都市)。顧客 == 都市。容量ルールを削除します。

次に、スコア ルールを変更して、使用済み車両 (未使用車両ではなく) の都市 (= 顧客) の距離のみを合計するようにします。

rule "distanceToPreviousAppearance"
    when
        $customer : VrpCustomer(previousAppearance != null, $distanceToPreviousAppearance : distanceToPreviousAppearance, vehicleIsUsed == true)
    then
        insertLogical(new IntConstraintOccurrence("distanceToPreviousAppearance", ConstraintType.NEGATIVE_SOFT,
                $distanceToPreviousAppearance,
                $customer));
end

rule "distanceFromLastCustomerToDepot"
    when
        $customer : VrpCustomer(previousAppearance != null, vehicleIsUsed == true)
        not VrpCustomer(previousAppearance == $customer)
    then
        VrpVehicle vehicle = $customer.getVehicle();
        insertLogical(new IntConstraintOccurrence("distanceFromLastCustomerToDepot", ConstraintType.NEGATIVE_SOFT,
                $customer.getDistanceTo(vehicle),
                $customer));
end

同様に、中古車が訪れたすべての都市の訪問ボーナスを合計するルールを追加し、ConstraintType.POSITIVE_SOFT (加重対移動距離) で最大化を試みることができます。

もちろん、このようにハックするべきではありません。これは単なる要点です。代わりに、要件に合わせて名前を変更し、再設計してください。