A vehicle routing and scheduling problem is one of the most celebrated topics of all combinatorial optimization problems. Recently, much work in routing problems has been done to develop realistic models and algorithms that can handle complications in practice. In this point of view, traffic congestion is an important component deserving serious attention in urban routing systems. This thesis has explicitly considered traffic congestion in vehicle routing problems. For the addition of the traffic congestion factor to conventional routing problems, we have formally assumed that internode travel time is a function of the starting time at the leaving node, while it is assumed as constant in conventional routing problems.
The causes of traffic congestion can be divided into two categories: predictable factors(for example, rush hour) and unpredictable factors (for example, traffic accidents). In case of predictable traffic congestion, relatively precise estimates of the traffic loads can be obtained. On the contrary, in case of unpredictable traffic congestion, it is very difficult to forecast the change of the traffic loads. Therefore, it is desirable that vehicle routing problems under traffic congestion are analyzed in two points of view: planning and controlling. In planning phase, generally, dispatchers produce a basic route schedule by considering the estimated load pattern only. And then, when unexpected events occur during the execution of the route, he or she adjusts the route schedule already made in order to cope with these changes.
First, we have focused on static vehicle routing problems with time windows and time-varying congestion, which can be used in planning phase. Due to added complication if time-varying congestion, it is often challenging to solve resulting problems, in fact, even to find feasible solutions. In this thesis, we have identified a simple yet robust monotonicity property of arrival time, non-passing property, which allows us to solve this class of routing problems by slightly modifying existing heuristics-the savings, the insertion and Or's method. Three feasibility check routines built upon this property considerably reduce computational burden.
Next, we have dealt with the dynamic case of vehicle routing problems with time windows and time-varying congestion to aid decision makers for the real-time control. In contrast to the static cases, the dynamic routing problems consider the change of the input data during the execution of the route schedule. However, the dynamic change of input data may often make the current schedule infeasible. In real-time control of routing systems, therefore, we should give more attention to fact finding a feasible route rather than optimal one. To solve this problem, we have introduced three tour-improvement-type heuristics, which can be easily applied to the continual revision of the route schedule. And then, we have proposed solution procedures based on these tour-improvement heuristics for two dynamic situations-unpredictable traffic congestion and new customer's requests.
정수계획법 중의 차량운행문제(Vehicle Routing Problem)는 이론적인 측면뿐만 아니라 실용적인 측면에서도 많이 연구되어 온 과제이다. 이러한 차량운행문제에 관한 최근의 주요한 연구방향 중의 하나는 현실적인 요소를 감안하여 모형을 세우고, 나아가 그 해법을 개발하는 것이다. 이러한 관점에서 볼 때, 대도시생활에서는 교통혼잡(Traffic Congestion)이란 무시될수 없는 중요한 고려사항이라 하겠다. 본 논문은 교통혼잡을 명시적으로 고려한 차량운행문제에 관한 연구이다. 본 논문에서 대상으로 하는 모형에서는 교통혼잡을 고려해서, 두지점간의 차량운행시간을 출발지점의 출발시각의 함수관계로 가정하였다.
교통혼잡이 발생하는 원인을 살펴보면, 크게 두가지로 나눌 수 있다. 첫째는 예측가능한 경우로, 출퇴근 시간의 교통혼잡이 한 예가 되겠다. 다음으로는 예측이 어려운 경우로 교통사고로 인한 교통정체와 같은 경우가 여기에 속한다. 전자의 경우는 실제로 그 유형을 상당히 정확하게 예측할 수 있는 반면에, 후자의 경우는 미리 예측한다는 것이 거의 불가능하다고 볼 수 있다. 따라서, 본 논문에서는 이 두가지 경우를 나누어서 각각에 대한 모형을 정립하고 그 해법을 개발하였다.
먼저, 본 논문에서는 예측가능한 교통혼잡만을 고려한 차량운행문제의 해법에 관하여 연구하였다. 그런데, 실제로 기존의 문제에 교통혼잡 요인이 더해지면 문제의 최적해는 물론이고 그 가능해를 구하는 것 조차도 어려워진다. 이에 우리는 우선 이러한 문제를 해결하기 위하여 도착시간에 관한 단조증가 성질을 가정하였다.
다음으로 이 성질 하에서 성립되는 세개의 가능해 조건들을 도출해 내고, 그 조건들을 이용하는 해법을 개발하였다. 실제로 계산시간면에서 이 가능해 조건들이 큰 도움이 되는 것을 컴퓨터 계산 실험을 통하여 알 수 있었다. 다음으로, 운행 중에 예측불가능한 사건이 발생하는 경우의 차량운행문제(동적차량문제)에 관한 연구를 시도하였다. 이와 같은 운행중의 변화는 종종 현재의 운행계획을 실천할 수 없는 것으로 만든다. 이러한 경우에는 무엇보다도 현 운행계획을 수정하여 실행가능한 계획을 빨리 구하는 것이 제일 중요한 일이라 하겠다. 본 논문에서는 이러한 목적에 부합되는 해법과 가능해 조건들을 소개하고, 운행중에 고객의 신규 요청이 있는 경우와 예측 하지못한 운행지연이 발생한 경우에 이들을 적용해 보았다.
