Most of the models for the vehicle routing problems studied in the literature assumed constant travel times. However, those approaches may give infeasible solutions when traffic congestion causes delays in travel time. To overcome such difficulty, there have been some researches considering the change of the travel time which is called the time dependent vehicle routing problem (TDVRP). TDVRP assumes that the travel time between two locations is not only affected by the distance traveled, but by many other factors including the time of the day. Therefore, the applications of TDVRP to real world problems may give solutions which reflect the reality more accurately.
In this thesis, we propose a branch-and-price algorithm to solve the TDVRP. An enumeration scheme with bounding procedures was used to identify a profitable route in the column generation procedure. The algorithm guarantees the “Non-passing” property to be held in the solutions. The algorithm was tested on problems composed of the Solomon’s benchmark instances for 25 and 50 nodes. Computational results are reported.
기존의 대부분의 차량경로문제의 연구에서 다룬 모형은 일정한 이동시간을 가정하고 문제를 형성하였다. 그러나 이러한 접근법은 현실 상황에서의 교통체증등의 이유로 이동시간이 변화하는 경우 구한 해가 불가능한 해가 된다는 현실적인 어려움이 존재하였다. 이러한 어려움을 극복하고자 이동시간의 변화를 고려한 차량경로문제라는 새로운 분야의 연구가 진행 되었다. 이동시간의 변화를 고려한 차량경로 문제는 이동시간을 단순히 거리에 비례하는 것이 아닌 여러 교통 변화에 관련한 요소를 통하여 이동시간을 계산하게 되어 기존의 차량경로 문제의 해 보다 더욱 현실상황을 반영한 해를 얻을 수 있게 된다. 본 논문에서는 분지평가법을 이용하여 이동시간을 고려한 차량경로 문제를 풀었다. 분지평가법은 보다 효율적인 차량 경로를 찾아서 문제를 푸는 열생성기법을 기반으로 분지한계법의 방식을 적용하는 방식으로 기존의 차량경로 문제의 최적해를 효율적으로 푸는 알고리즘으로 많이 쓰인 방식이다.
이동시간을 고려한 차량경로 문제의 경우 기존의 차량경로 문제와 달리 알고리즘상에 늦게 출발한 차가 동일 이동구간 사이에 앞서 출발한 차를 추월하는 문제가 발생하게 되고 이를 방지하는 계산이 시간마다 변화하기 때문에 최적해를 구하는 부분에 있어서 어려움이 존재하였다. 본 논문에서는 열생성기법의 적용 시 효율적인 차량경로를 찾을 때 추월방지 특성을 보장하는 계산을 동적 계획법의 방식을 이용해서 풀이 함으로써 기존의 이동시간의 변화를 고려한 차량경로 문제의 연구에서 다루지 못한 부분을 해결하여 최초로 최적의 해를 구하는 알고리즘을 제시할 수 있었다.
