mathematical-optimization - 旅行推销员 (TSP) 跳过城市

Question

我想解决一个类似于旅行推销员问题的问题，但在这种情况下，如果访问城市的成本太高，销售人员可以跳过城市。

请给我一些关于如何解决这个问题的指导。

Answer 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（加权与行驶距离）将其最大化。

当然，你不应该像这样破解它：这只是要点。相反，请根据您的要求重命名和重新设计它。