The A Priori Dynamic Traveling Salesman Problem with Time Windows

In this paper we examine the traveling saleman problem with time windows for various degrees of dynamism. In contrast to the static problem, where the dispatcher can plan ahead, in the dynamic version, part or all of the necessary information becomes available only during the day of operation. We seek to minimize lateness and examine the impact of this criterion choice on the distance traveled. Our focus on lateness is motivated by the problem faced by overnight mail service providers. We propose a real-time solution method that requires the vehicle, when idle, to wait at the current customer location until it can service another customer without being early. In addition, we develop several enhanced versions of this method that may reposition the vehicle at a location different from that of the current customer based on a priori information on future requests. The results we obtained on both randomly generated data and on a real-world case study indicate that all policies proved capable of significantly reducing lateness. Our results also show that this can be accomplished with only small distance increases. The basic policy outperformed the other methods primarily when lateness and distance were equally minimized and proved very robust in all environments studied. When only lateness was considered, the policy to reposition the vehicle at a location near the current customer generally provided the largest reductions in average lateness and the number of late customers. It also produced the least extra distance to be traveled among the relocation policies.