2 명의 운송인에 의한 가장 짧은 배달 시간

Question

알고리즘 문제를 다루고 있습니다. 나는 하나의 중앙 노드를 가진 알려진 그래프 알고리즘을 가지고있다. 목표는이 중앙 노드에서 두 개의 운송 업체에 의해 지정된 다른 노드로 물품을 전달하는 것입니다. 모든 운송 업체는 최대 한 단위의 상품이 그 당시에는 각 노드를 방문한 후 다음 노드의 중앙 노드로 돌아옵니다. 가능한 한 최단 시간을 계산해야합니다.

내 접근 방식은 노드 사이의 다른 거리를 고려하여 다른 모든 노드에 대한 최단 경로를 찾기 위해 중앙 노드에 dijkstra algorithm을 사용하는 것이 었습니다. 그런 다음 트랜스 포터가 이동해야하는 모든 노드 (때로는 특정 노드까지 한 번 이상)에서 앞뒤로 거리가 있기 때문에 값이 두 배가됩니다. 나는 값을 두 그룹으로 나누었습니다. 합계는 가능한 한 서로 가깝습니다. 왜냐하면 두 개의 운송인이 있고 더 큰 것을 인쇄했기 때문입니다.

그러나 솔루션은 완벽하지는 않습니다. 나는 다른 것을 만들어야합니다. 첫 번째 운송인이 일을 끝내는 지 안다면 8 단위가 더 빨리 나옵니다. 배달 중 어딘가에서 두 번째 운송인에게 좋은 물건을 준비 할 수 있습니다. 그러면 중앙 노드까지 갈 필요가 없지만 덜 수 있습니다. 그렇다면 그들의 총 시간은 같을 것이지만 둘 다 더 짧다고 생각합니다. 불행히도, 이것은 항상 가능하지는 않습니다 (예를 들어, 한 노드에 한 번만 배달 등). 프로그램에이 부분을 추가해야합니다.

Answer 1

실제로 우리는 휴리스틱 또는 건설적인 방법과 같은 몇 가지 방법으로 해결할 수있는 "차량 경로 지정"문제에 대해 작업하고 있습니다.

이 방법에 대한 유용한 정보는 here을 참조하십시오.