Abstract
Nowadays, in order to keeping competitive advantages, overnight carriers are searching for more stable orders. On the other hand, carriers also concentrate on developing abilities to deal with real-time demands continuously. The common goal of overnight carriers is satisfying needs of customers as possible while keeping operating costs competitive.The purpose of this thesis is to construct a Probabilistic Traveling Salesman Problem model with Time Window constraints (PTSPTW) to cope with probabilistic demands. Meanwhile, the idea of Double Horizon is incorporated into the model to maintain the flexibility of the a priori route for future possible immediate requests. A two stage heuristic algorithm is proposed to solve the PTSPTW. The conclusion is that the flexibility of the a priori route is helpful not only to satisfy more demands but also to reduce total traveling time of the vehicle in the problem with real-time demands, especially the cases which the weight of real-time demands is high. Besides, in the problems with narrow time window or high request probabilities, the a priori route with more flexibility has more advantages.