차량 일정 조정 문제
Vehicle rescheduling problem
차량 재조정 문제(VRSP)는 차량 고장이나 중대한 지연 등 일정 변경 후 여행 중인 고객에게 서비스를 제공하는 결합 최적화 및 정수 프로그래밍 문제다.2007년 리, 미르찬다니, 보렌슈타인이 제안한 [1]VRSP는 교통과 물류 분야에서 중요한 문제다.
최적의 솔루션을 결정하는 것은 조합 최적화의 NP-완전한 문제이기 때문에, 실제로 경험상 경험적 접근법과 결정론적 방법을 사용하여 VRSP에 대해 수용할 만한 좋은 솔루션을 찾는다.
개요
차량 재조정 문제에 대한 몇 가지 변형 및 전문화가 존재한다.
- 단일 디포 차량 재조정 문제(SDVRSP): 지연, 차량 고장 또는 기타 다른 이유로 인해 다수의 주행 일정을 조정해야 한다.목표는 지연과 운영 비용을 최소화하기 위해 창고의 추가 차량을 사용하여 기존 비행대의 최적 재조정 일정을 찾는 것이다.단일 디포 변동에서는 모든 추가 차량을 포함하고 모든 차량이 일정을 시작하고 종료하는 디포가 하나뿐입니다.
- 다중 디포 차량 재조정 문제(MDVRSP): SDVRSP와 유사하며, 추가 디포가 도입된다는 점을 제외한다.각각의 디포에는 가변 여분의 차량뿐만 아니라 용량 제약이 있다.일반적으로 차량 일람표에는 각 차량이 스케줄을 시작한 저장소로 돌아가야 하는 추가적인 제약조건이 있다.
- 개방형 차량 재조정 문제(OVRSP): 차량이 디포로 돌아갈 필요가 없다.
VRSP는 단일 디포 차량 스케줄링 문제 및 다중 디포 차량 스케줄링 문제와 관련이 있지만, 운용 중 재스케줄이 가능하도록 거의 실시간으로 VRSP를 해결해야 하는 반면, SDVSP와 MDVSP는 일반적으로 롱런하는 선형 프로그래밍 metho를 사용하여 해결되기 때문에 런타임 요건에 큰 차이가 있다.ds.[2]
VRSP가 사용되는 또 다른 분야는 수요가 크게 변화할[3] 때 노선을 재조정하기 위한 물품 운송 분야다.
참고 항목
참조
- ^ Li, Jing-Quan; Mirchandani, Pitu B.; Borenstein, Denis (2007). "The vehicle rescheduling problem: Model and algorithms". Networks. 50 (3): 211–229. doi:10.1002/net.20199.
- ^ Pepin, Ann-Sophie; Desaulniers, Guy; Hertz, Alain; Huisman, Dennis (February 2009). "A comparison of five heuristics for the multiple depot vehicle scheduling problem". Journal of Scheduling. 12 (1): 17–30. doi:10.1007/s10951-008-0072-x.
- ^ Spliet, Remy; Gabor, Adriana F.; Dekker, Rommert (March 2014). "The vehicle rescheduling problem". Computers & Operations Research. 43: 129–136. doi:10.1016/j.cor.2013.09.009. hdl:1765/17350.
