PROBABILISTIC ANALYSES AND PRACTICAL ALGORITHMS FOR THE VEHICLE-ROUTING PROBLEM WITH TIME WINDOWS

In the Vehicle Routing Problem with Time Windows, a set of customers a re served by a fleet of vehicles of limited capacity, initially locate d at a central depot. Each customer provides a period of time in which they require service, which may consist of repair work or loading/unl oading the vehicle. The objective is to find tours for the vehicles, s uch that each customer is served in its time window, the total load on any vehicle is no more than the vehicle capacity, and the total dista nce traveled is as small as possible. In this paper, we present a char acterization of the asymptotic optimal solution value for general dist ributions of service times, time windows, customer loads and locations . This characterization leads to the development of a new algorithm ba sed on formulating the problem as a stylized location problem. Computa tional results show that the algorithm is very effective on a set of s tandard test problem.