여러 소스 - 여러 목적지

내가 목적지 집합과 다른 원산지 집합을 가지고 있다고 가정 해 보겠습니다. 각 목적지를 원점으로 연결해야합니다. 각 차량의 출발점부터 출발점까지 차량의 세트가 시작됩니다. 모든 차량의 속도가 제공됩니다.

네트워크에서 단 하나의 차량이 한 시간 단위로 교차로를 통과 할 수 있으므로 네트워크의 교차점에 차량이 둘 이상인 경우 차량이 교차점을 기다리거나 걸릴 수 있습니다 다른 길.

주된 목적은 목적지에 도달하기 위해 모든 차량의 전체 지체를 최소화하는 것입니다.

아이디어를 해결하는 방법에?

2016-09-23 Sudhani

'주된 목적은 모든 차량이 목적지에 도달 할 때까지의 전체적인 지체를 최소화하는 것입니다 .' 그 점을 분명히 밝히고, 그 중 몇 가지 의미를 생각해 볼 수 있습니다 (차량 평균 시간, 중간 시간, 가장 느린 차량 시간 , ....), 다른 사람들은 아마도 더 많은 것을 생각할 수 있습니다. – amit

목적은 목적지에 도달 한 마지막 차량의 지체를 최소화하는 것입니다. 즉 모든 차량이 각 목적지에 도달하는 데 필요한 최대 시간이 최소화되어야합니다. – Sudhani

이 완벽한 솔루션을 아닌가요하지만 난 하강 방향을 제공 할 것입니다 희망 :

난 당신이 "Maximum Flow Problem"흐름 네트워크에
차량의 'n'을 수 감안할 때

처럼 사용한다고 생각을
S - 소스를 정의하십시오.
차량의 O1, O2, O3 ..., On - Origins을 정의하십시오. 원래 가정하는 방식으로 제 교차로
정의 에지 S- (O1, O2, O3 ... ON) - 싱크
E 정의 차량의 총 수와 같은 각각의 원점 당 용량 = 1, 목적지
에지를 정의 (D1, D2, D3 ..., DN) - E - - 용량은 대상에 1
개의 꼭지점에 의해 정의 된 각각의 교차점 (
는 D1, D2, D3 ... DN이 정의 in) and edge cap = 1

이것은 모든 트럭에 적합한 경로를 찾는 데 도움이되지만 모든 "중고"교차로를 통과하는 oid ...
나는 닫힌 직후에 흐르는 후 지정된 교차로의 용량을 증가한다고 생각합니다.

출처

2016-09-23 09:41:08

접근 방식을 주셔서 감사합니다, 나는 확실히 그것을 구현합니다. – Sudhani

여러 소스 - 여러 목적지

답변

관련 문제