본 논문은 NP-완전인 DSP에 대해 O(ｍ)의 다항시간으로 근사 해를 찾는 규칙을 제시한 휴리스틱 알고리즘을제안하였다. 제안된 알고리즘은 ｍ개의 주어진 운행계획에 대해, 최소의 운전기사인 ｎ명을 배정한 초기 배정 결과를 얻는다. 다음으로, 교환 또는 삽입의 5개 규칙들을 적용하여 초과시간 (OT)과 유휴시간 (IT)를 감소시켜 최소의비용 (TC)을 얻었다. 제안된 알고리즘은 최적 (또는 근사) 해를 찾는 규칙을 제안한 O(ｍ) 복잡도의 휴리스틱 다항시간 알고리즘임에도 불구하고, 5개의 실험 데이터에 적용한 결과 메타 휴리스틱 기법들과 필적하는 결과를 얻었다. 결론적으로, 본 논문에서는 CSP에 있어서 최적 해를 찾아가는 규칙이 전혀 없는 NP-완전이 아닌 다항시간의 규칙이 존재하는 P-문제가 될 수 있음을 보였다.
본연구는 NP-완전인 DSP에 대하여 O(ｍ)의 다항시간으로 근사 해를 찾는 규칙을 제시한 휴리스틱 알고리즘을 제안했다.