The A-priori Traveling Salesman Problem with Time Windows

Allan Larsen, Oli B.G. Madsen, Marius M. Solomon

    Research output: Contribution to journalJournal articleResearchpeer-review


    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.
    Original languageEnglish
    JournalTransportation Science
    Issue number4
    Pages (from-to)459-472
    Publication statusPublished - 2004

    Cite this

    Larsen, A., Madsen, O. B. G., & Solomon, M. M. (2004). The A-priori Traveling Salesman Problem with Time Windows. Transportation Science, 38(4), 459-472.