이익을 극대화하는 알고리즘 : 해결 방법/접근 방법? (Advanced NP-Complete)

Question

이 사람이 힘들어서 모든 도움이 정말 감사합니다! 나는 그것을 알고

는 NP-완료되고, 따라서 다항식 시간에 해결 될 수는 없지만, 등이에 감소 어떤 NP 완성 문제의 유형 분석에 도움, 그것은 당신을 생각 나게 유사한 문제,

을 찾고

이야기는 다음과 같습니다. 나는 n 트럭으로 아이스크림 트럭 사업을 소유하고있다. m 배송이 중단되는 곳이 있습니다. 각 위치 m _i은 p _i입니다. 아이스크림을 사면 모두가 떠난다. p _i 많은 사람들이 아이스크림을 얻기 위해 더 많은 사람들이 늘어남에 따라 시간이 지남에 따라 증가합니다.

주어진 날에 수익을 극대화하기 위해 트럭을 다음으로 보낼 곳을 어떻게 알 수 있습니까? 명심해야 할

것 : 사람들이 한 트럭

트럭은 시간이 걸릴 도착 후 떠날 즉, 한 번만 이익을 얻을 것이다 비슷한 시간에 같은 장소에서 중지

• 두 트럭 각 정류장에서 또 다른
• 페이지에 한 장소에서 시간이 지남에 _내가 증가를 얻을 수 있지만, 일부 정지는 빨리 다른 사람보다 증가 즉, 일부 지역은 근처 쇼핑몰 (위치, 위치, 위치)
있습니다

내가 ILP 등 판매 사람의 문제를 여행하는 multimachine 일정 문제로이 감소 시도했지만, 주요 문제는 그 페이지 _{내가 모든 위치에서} (즉, TSP에서의 거리 또는 스케쥴링 문제에서의 작업 길이)은 계속적으로 증가하고있다.

미리 감사드립니다.

Answer 1

Assignment Problem. 변종처럼 들리 겠지만 한 가지 방법은 Auction Algorithm (쉽게 병렬화 할 수있는 이점이 있습니다) 또는 Hungarian algorithm입니다.

나는 문제가 복잡하다는 것을 알고 있습니다 (항상 있습니다!). 그러나 경매 알고리즘은 꽤 유연합니다. 당신은 트럭과 고객 사이에 꽤 복잡한 비용 기능을 가질 수 있습니다. 또한 알고리즘을 조정하여 여러 트럭이 용량 제약을받는 여러 고객에게 서비스하도록 할 수 있습니다.