Truck route planning in nonstationary stochastic networks with time windows at customer locations

Most existing methods for truck route planning assume known static data in an environment that is time varying and uncertain by nature, which limits their widespread applicability. The development of intelligent transportation systems such as the use of information technologies reduces the level of uncertainties and makes the use of more appropriate dynamic formulations and solutions feasible. In this paper, a truck route planning problem called stochastic traveling salesman problem with time windows (STSPTW) in which traveling times along roads and service times at customer locations are stochastic processes is investigated. A methodology is developed to estimate the truck arrival time at each customer location. Using estimated arrival times, an approximate solution method based on dynamic programming is proposed. The algorithm finds the best route with minimum expected cost while it guarantees certain levels of service are met. Simulation results are used to demonstrate the efficiency of the proposed algorithm.