드라이버 스케줄링 문제

Driver scheduling problem

Driver Scheduling Problem(DSP; 드라이버 스케줄링 문제)는 운영 연구 및 이론 컴퓨터 과학에서 발생하는 문제의 유형입니다.

DSP는 다양한 법률 및 물류 기준의 제약 내에서 승객 또는 화물 [1][2]운송에 관련된 차량(예: 버스, 기차, 보트 또는 비행기)의 운전자나 조종사를 위한 일련의 임무(임무)를 선택하는 것으로 구성된다.

기준 및 모델링

이 매우 복잡한 문제에는 노동 및 회사 규칙과 관련된 몇 가지 제약과 다양한 평가 기준 및 목표가 포함됩니다.이 문제를 효율적으로 해결할 수 있다면 대중교통 회사의 [3]비용과 서비스 품질에 큰 영향을 미칠 수 있다.실현 가능한 의무가 충족되어야 하는 많은 다른 규칙이 있습니다.

  • 최소 및 최대 스트레칭 지속 시간
  • 최소 및 최대 휴식 시간
  • 최소 및 최대 작업 기간
  • 최소 및 최대 총 지속 시간
  • 최대 잔업 기간
  • 최대 차량 변경 횟수
  • 특정 차량의 최소 주행 시간

운용 조사에서는 이 문제에 대한 효율적인 솔루션으로 이어지는 최적화 모델과 알고리즘을 제공하고 있습니다.DSP를 해결하기 위해 제안된 가장 일반적인 모델로는 Set Covering Model(SPP/SCP)[4][5]과 Set Partitioning Model(STP)이 있습니다.SPP 모델에서는 각 작업물(작업)에 대해 하나의 의무만 적용됩니다.SCP 모델에서는 특정 작업물을 커버하는 여러 듀티를 가질 수 있습니다.두 모델 모두 커버해야 할 작업물 세트를 열로 배치하고, 특정 작업물 커버에 사용할 수 있는 미리 정의된 실행 가능한 작업물 세트를 열로 배열한다.DSP 해결은 이들 모델 중 하나에 기초하여 최종 일정의 총 비용을 최소화하면서 각 작업물을 커버하는 하나 이상의(SPP) 임무가 있음을 보장하는 일련의 실행 가능한 의무 선택이다.

「 」를 참조해 주세요.

레퍼런스

  1. ^ Voß, Stefan; Daduna, Joachim R. (2001). Computer Aided Scheduling of Public Transport. Springer. pp. 122–. ISBN 9783540422433. Retrieved 22 May 2013.
  2. ^ Salvendy, Gavriel (2001-05-25). Handbook of Industrial Engineering: Technology and Operations Management. John Wiley & Sons. pp. 813–. ISBN 9780471330578. Retrieved 22 May 2013.
  3. ^ Borndörfer, Ralf; Martin Grötschel; Marc E. Pfetsch (2006). "Public transport to the fORe". OR/MS Today. 33 (2): 30–40.
  4. ^ Lourenço, H.R.; Paixão, J.P.; Portugal, R. (2009). "Driver Scheduling Problem Modelling". Public Transport: Planning and Operations. 1 (2): 103–120. doi:10.1007/s12469-008-0007-0. hdl:10230/303.
  5. ^ Lourenço, H.R.; Paixão, J.P.; Portugal, R. (2001). "The crew-scheduling module in the GIST system". Economic Working Papers Series, Department of Economics and Business, Universitat Pompeu Fabra. 547.