5
단일 디포로 차량 라우팅 문제를 연구 중입니다. 문제 정의는 다음과 같습니다. m 개의 사이트로 이동해야하는 n 개의 vechile이 있습니다. 각 사이트에는 특정 용량의 차량 만 사이트를 제공 할 수있는 것과 같이 특정 제약 조건이 있습니다. 일부 사이트는 특정 시간대에 서비스를 제공해야합니다. 또한 차량은 용량이 다르고 시작과 종료 시간이 다릅니다.차량 라우팅에서 그래프 이론 사용 문제
아이디어는 디포에서 차량의 이동 시간을 최소화하는 것입니다.
문제의 비용 매트릭스를 구성하는 중입니다. 그래프 이론의 전문가는 아니지만 고전적인 여행 세일즈맨 (Traveling Salesman) 문제에 빠지면 문제를 해결하기 위해 해밀턴 사이클을 사용할 수 있음을 알고 있습니다. 그러나 다중 여행 세일즈맨 문제에 빠지기 때문에 해밀턴 사이클을 사용하여 문제를 해결할 수있는 방법을 알고 싶습니까? 아니면 문제를 해결하기 위해 특별히 설계된 다른 프로세스가 있습니까?
도움을 주시면 감사하겠습니다.
몇 대의 차량과 사이트가 있습니까? 강력한 경험적 방법으로 다소 바보 같은 역 추적을 사용할 수 있습니다. 예, NP 완성이며 Dijkstra에서 발견 된 몇 가지 경로처럼 일부 부분 만 더 똑똑하게 해결할 수 있습니다. –
문제를 비트로 분해했습니다. 첫 번째 부분은 사이트에 가장 높은 용량/기술 요구 사항을 가진 차량을 사이트와 일치시킨 후 차량의 허용 시간이 만료 될 때까지 차량 경로의 다른 모든 사이트를 포함합니다. 그런 다음 얻은 그래프에서 가장 짧은 해밀턴 사이클을 찾습니다. 모든 사이트가 할당 될 때까지 모든 사용 가능한 차량에 대해 반복합니다. 짐작할 수 있듯이 생성 된 경로가 최적이 아닙니다. – Purusartha