확률 제약 다중화물 네트워크 설계 문제에 대한 실현 가능성 절단

문제 정의: 우리는 수요 불확실성 하에서 확률 제약 다중화물 네트워크 설계 문제를 해결하기 위한 효율적인 정확 해법 접근법을 연구합니다. 확률 제약은 우리가 미래의 상품 수요를 충분히 자주 충족하는 네트워크를 구축해야 하며, 이로 인해 문제 해결이 도전적으로 변합니다. 방법론/결과: 우리는 벤더스 분해에 기반한 해법 접근법을 개발하고, 유효 불등식 및 절단 강화로 접근법을 가속화합니다. 우리는 특히 다양한 하위 문제 형식이 결과적으로 생성되는 실현 가능성 절단의 강도에 미치는 영향을 조사합니다. 우리는 FlowMIS라는 새로운 형식을 제안하고, 그 속성을 연구합니다. 또한, 우리는 수치적으로 FlowMIS가 표준 형식을 초월한다는 것을 보여줍니다: 모든 향상을 활성화한 우리의 완전한 해법 접근법에서 FlowMIS는 120개의 해결된 사례 중 67개를 가장 빠르게 해결하며, 기본 형식에 비해 평균 2.0배의 속도 향상을 기록합니다. 의미: FlowMIS는 네트워크 흐름 구조를 가진 하위 문제에 맞춘 강력한 실현 가능성 절단을 생성합니다. 이는 네트워크 설계 문맥에서 기존의 분해 기반 알고리즘의 해결 시간을 단축시키고, 더 큰 문제를 해결할 수 있는 능력을 제공합니다.