일반적인 스케줄링 문제

일반적인 예약 문제

충성스러운 독자 중 한 명이 일반적인 예약 문제를 해결하는 방법을 묻습니다. 상황은 다음과 같습니다. 하나의 버스를 사용하는 경로는 60 분마다 운행되도록 예약되어 있지만 시간에 따라 완료하는 데 최대 70 분이 소요될 수 있습니다. 물론, 60 분마다 운행 할 예정인 버스가 실제로 완료하는 데 70 분이 걸리는 경우, 버스는 항상 늦게되어 결국에는 여행이 빠지게됩니다. 이 문제를 해결할 수있는 방법에는 네 가지가 있습니다.

전반적으로이 문제는 스케줄러가 자주 실행되지 않는 경로를 예약하는 데 어려움을 나타냅니다. 선택할 수있는 여행이 많기 때문에 자주 운행하는 노선의 버스에 블록을 쉽게 할당 할 수 있습니다. 선택할 수있는 여행이 매우 적기 때문에 자주 운행하지 않는 노선의 버스에 블록을 할당하는 것은 어렵습니다. 경우에 따라 유일한 대안은 운전자를 압박하거나 오랜 시간 동안 운전자를 해고시키는 것입니다.

이 문제는 교통 혼잡 및 탑승객 증가로 버스 운행 속도가 낮아짐에 따라 향후 증가 할 것으로 보입니다. 1980 년, 1990 년 또는 2000 년에 완벽하게 우아한 일정을 잡는 솔루션은 2011 년에 더 이상 작동하지 않을 수 있습니다. 드물게 운행하는 노선은 보통 낮은 탑승률 때문에 때때로 직원이 간과하지만 (때로는 "로저 라인"이라고 함), 아마도 그들이 낮은 라이더 쉽을 갖는 이유는 그들이 참조 된 스케줄링 문제를 겪기 때문이다. 이러한 스케쥴링 원리의 적용은 히트 리얼리티 쇼 "The Biggest Loser"의 버스 경로 버전처럼 작동 할 수 있습니다.

노선에 버스 추가

이 문제를 해결하기 위해 가장 먼저 할 일은 버스를 노선에 추가하는 것입니다. 위에서 설명한 예에서 한 버스가 왕복을 완료하는 데 70 분이 걸리면 한 버스가 70 분 전진을 제공하거나 두 버스가 35 분 전진을 제공 할 수 있습니다. 이것이 가장 쉬운 솔루션이지만 가장 비쌉니다. 버스를 운영하는 데 시간당 100 달러가 소요되고 하루에 8 시간 동안이 노선에 추가 버스를 추가하는 경우, 예약 문제를 해결하기 위해 하루에 800 달러 * 연중 주당 254 주 = 연간 $ 200, 000 +를 추가로 지출합니다. 수요가 아니라 현재 구성에서 경로를 구동 할 수 없기 때문에 서비스를 추가하고 있습니다.

버스 정류장 제거

이 문제를 해결하기 위해 할 수있는 두 번째 일은 버스 정류장을 제거하는 것입니다. 버스 정류장을 제거하는 것은 버스가 실제로 정지하는 모든 버스 정류장이 버스의 운행 시간에 30 초를 더한 것으로 추정되므로 버스 작동 속도를 높이는 유일한 방법입니다 (버스 정류장 위치에 대한 메모리 새로 고침). 정거장을 제거하는 것이 정치적으로 위험하다는 점을 알고 있지만 평균 정거장 간격이 600 피트 미만인 경로는 정거장을 제거하기에 좋은 대상입니다.

노선 변경

우리가 할 수있는 두번째 일은 경로 자체를 바꾸는 것입니다. 이 스케쥴링 문제에 빠질 수있는 많은 서큘 레이터 서비스는 특정 지역 주변의 구불 구불 한 노선을 운영합니다 (여기서는 로스 앤젤레스 DASH 노선을 생각하고 있습니다). 경로를 똑 바르게하면 경로를 완료하는 데 필요한 시간이 줄어들뿐만 아니라 목적지를보다 직접 연결하여 기수가 향상 될 것입니다 (버스 경로를 디자인하는 방법에 대한 입문서를 읽어보십시오).

다른 경로와 경로 연계

물론, 위의 솔루션은 이미 두 목적지를 연결하는 직선으로 운행되는 노선에서는 작동하지 않으며, 기존 노선이 매우 생산적인 승객 인 경우 어떠한 경우에도 작동하지 않을 수 있습니다. 이 경우 가장 좋은 솔루션은 인터 리 닝일 가능성이 높습니다. 인터 라이닝에서 우리는 하나의 버스 경로를 공통 종단을 공유하는 다른 버스 경로와 연결합니다. 두 개의 버스 노선이 모두 60 분마다 운행된다고 상상해보십시오. 한 번은 왕복을 완료하는 데 70 분이 걸리고 (휴식이 포함되어 있다고 가정) 한 번은 왕복을 완료하는 데 50 분이 걸립니다. 별도로, 70 분이 걸리는 여행은 계속 늦게 진행되어 결국 여행을 놓칠 수 있으며, 다른 여행에는 과도한 양의 휴식이있을 것입니다. 그들은 함께 완벽하게 작동합니다. 인터 라이닝이 작동하려면 두 경로가 공통 종점을 공유하고 동일한 전진로에서 작동해야하며 하나는 추가 가동 시간이 필요하고 다른 하나는 불필요한 휴식 시간이 있어야합니다.