View article

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 …