The A Priori Dynamic Traveling Salesman Problem with Time Windows

Larsen, Allan; Madsen, Oli B. G.; Solomon, Marius M.
November 2004
Transportation Science;Nov2004, Vol. 38 Issue 4, p459
Academic Journal
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.


Related Articles

  • Dynamic version of Traveling Salesman Problem. Jindal, Pawan; Kumar, Amit; Kumar, Shishir // International Journal of Computer Applications;Apr2011, Vol. 19, p37 

    In the classical version of Traveling salesman problem, the targets which have to be visited are stationary but in real life there are large numbers of instances where the targets are in motion. In this paper, Moving target TSP with resupply is being studied and new algorithm is designed for...

  • A Note on the Ichoua, Gendreau, and Potvin (2003) Travel Time Model. Ghiani, Gianpaolo; Guerriero, Emanuela // Transportation Science;Aug2014, Vol. 48 Issue 3, p458 

    In this paper we exploit some properties of the travel time model proposed by Ichoua, Gendreau, and Potvin [Ichoua S, Gendreau M, Potvin J-Y (2003) Vehicle dispatching with time-dependent travel times. Eur. J. Oper. Res. 144:379-396], on which most of the current time-dependent vehicle-routing...

  • THE USE OF MODERN INFORMATION TECHNOLOGY IN RESEARCH ON TRANSPORT ACCESSIBILITY. BARTOSIEWICZ, Bartosz; WIƚNIEWSKI, Szymon // Transport Problems: an International Scientific Journal;2015, Vol. 10 Issue 3, p87 

    Transport accessibility can be analyzed using a number of different methods. The problem with each of them is the difficulty of obtaining data to measure this phenomenon The focus of this article and its main goal are to present methods and tools for gathering data on road traffic; thanks to...

  • Investigating optimal aggregation interval sizes of loop detector data for freeway travel-time estimation and prediction. Dongjoo Park; Soyoung You; Jeonghyun Rho; Hanseon Cho; Kangdae Lee // Canadian Journal of Civil Engineering;Apr2009, Vol. 36 Issue 4, p580 

    With recent increases in the deployment of intelligent transportation system (ITS) technologies, traffic management centers have the ability to obtain and archive large amounts of data regarding the traffic system. These data can then be employed in estimations of current conditions and the...

  • Ant Colony System with Heuristic Function for the Travelling Salesman Problem. Alobaedy, Mustafa Muwafak; Ku-Mahamud, Ku Ruhana // Journal of Next Generation Information Technology;Apr2013, Vol. 4 Issue 2, p39 

    Ant colony system which is classified as a meta-heuristic algorithm is considered as one of the best optimization algorithm for solving different type of NP-Hard problem including the travelling salesman problem. A heuristic function in the Ant colony system uses pheromone and distance values to...

  • Research on Information Applied Technology with Swarm Intelligence for the TSP Problem. Fangguo He // Advanced Materials Research;2014, Issue 886, p584 

    As a swarm intelligence algorithm, particle swarm optimization (PSO) has received increasing attention and wide applications in information applied technology. This paper investigates the application of PSO algorithm to the traveling salesman problem (TSP) on applied technology. Proposing the...

  • Comparison of Heuristics for Resolving the Traveling Salesman Problem with Information Technology. Wei Gong; Mei Li // Advanced Materials Research;2014, Issue 886, p593 

    Traveling Salesman Problem (Min TSP) is contained in the problem class NPO. It is NP-hard, means there is no efficient way to solve it. People have tried many kinds of algorithms with information technology. Thus in this paper we compare four heuristics, they are nearest neighbor, random...

  • Variable Speed Limit to Improve Safety near Traffic Congestion on Urban Freeways. Youngtae Jo; Yoon Kim; Inbum Jung // International Journal of Fuzzy Systems;Jun2012, Vol. 14 Issue 2, p278 

    Recently, the convergence of information technology with biotechnology, nano-technology, or other technologies has been creating a new paradigm. In the field of transportation, intelligent transport systems (ITSs)-a convergence of information technologies and transportation systems-have been...

  • Webinar to Highlight Transportation Systems Management and Operations Improvement SHRP2 Tool.  // AASHTO Journal: Weekly Transportation Report;12/6/2013, p2 

    The article offers information on a January 8, 2013 Webinar on a second Strategic Highway Research Program product, the Capability Maturity Model which is developed to help transportation agencies seeking to execute operations programs that improve travel time reliability.


Read the Article


Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics