시간 제한이 있는 픽업 및 배달 문제에 대한 정확한 알고리즘

시간 제한이 있는 픽업 및 배달 문제(PDPTW)는 시간 제한이 있는 차량 경로 문제의 일반화입니다. PDPTW에서는 중앙 창고에 위치한 동일한 차량 세트를 최적으로 라우팅하여 용량, 시간 제한, 쌍화 및 우선순위 제약을 충족해야 하는 일련의 운송 요청을 처리해야 합니다. 본 논문에서는 집합 분할과 유사한 정수 형식을 기반으로 한 PDPTW에 대한 새로운 정확한 알고리즘을 제시하고, 두 개의 이중 상승 해법과 컷 및 열 생성 절차를 결합하여 형식의 LP 완화의 거의 최적 이중 해를 찾는 경계 절차를 설명합니다. 최종 이중 해는 알려진 상한과 달성된 하한 사이의 차이보다 감소된 비용이 작은 경로만 포함하는 축소된 문제를 생성하는 데 사용됩니다. 결과 문제의 크기가 적당하면 정수 프로그래밍 해결기에 의해 해결되며, 그렇지 않으면 정수성 차이를 폐쇄하기 위해 분기 및 컷 및 가격 알고리즘을 사용합니다. 문헌의 주요 인스턴스에 대한 광범위한 계산 결과는 제안된 정확한 방법의 효과를 보여줍니다.