여행 세일즈맨 (TSP) 건너 뛰기 도시

Question

여행 판매원 문제와 비슷한 문제를 해결하고 싶지만이 경우 도시 방문 비용이 너무 높으면 영업 사원이 도시를 건너 뛸 수 있습니다.

이 문제를 해결하는 방법에 대해 알려주세요.

Answer 1

한 가지 방법이처럼 복사/Drools Planner의 this vehicle routing example을 붙여 해킹하는 것입니다 :

2 개 차량을이 있습니다 : 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 (가중 거리와 이동 거리)로 최대화하려고 시도합니다.

물론 이런 식으로 해킹하면 안됩니다. 이것은 단지 요지입니다. 대신 요구 사항에 맞게 이름을 변경하고 다시 설계하십시오.