Dynamic vehicle routing under traffic congestion

Abstract

A vehicle routing and scheduling problem is one of the most celebrated topics of all combinatorial optimiation 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 veiw, 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...