Efficient Implementation of Improvement Procedures for Vehicle Routing with Time-Dependent Travel Times

In this paper, efficient implementations of the classical improvement procedures for vehicle routing with time-dependent travel times are introduced. Specifically, the updating of tour-related variables (e.g., arrival and latest departure times) is incorporated in these implementations so that the computational complexity of solution approaches that use the improvement procedures can be significantly reduced. These implementation methods are applicable to several vehicle-routing improvement heuristics, including Or-opt, two-opt, one-shift, and CROSS exchanges. Numerical experiments were conducted to assess the effectiveness of the proposed implementations. Experimental results indicate that the computational complexity of the proposed efficient implementations for both single- and multitour improvement procedures is significantly reduced in comparison with the conventional implementations. The proposed efficient implementation schemes are especially useful for vehicle-routing applications in intelligent transportation systems in which the first-in-first-out property for link travel times is satisfied.

• Record URL:
  • https://doi.org/10.3141/2089-09
• Summary URL:
  • http://scholar.google.com/scholar_lookup?title=Efficient+Implementation+of+Improvement+Procedures+for+Vehicle+Routing+with+Time-Dependent+Travel+Times&author=H.+Tang&publication_year=2008
• Availability:
  • Find a library where document is available. Order URL: http://worldcat.org/isbn/9780309126014
• Authors:
  • Tang, Hao
• Publication Date: 2008

Language

• English

Media Info

• Media Type: Print
• Features: Figures; References; Tables;
• Pagination: pp 66-75
• Monograph Title: Network Analysis for Policy and Logistics
• Serial:
  • Transportation Research Record: Journal of the Transportation Research Board
  • Issue Number: 2089
  • Publisher: Transportation Research Board
  • ISSN: 0361-1981

Subject/Index Terms

• TRT Terms: Departure time; Heuristic methods; Implementation; Intelligent transportation systems; Routing; Time dependence; Travel time; Trucking
• Uncontrolled Terms: Arrival time
• Subject Areas: Freight Transportation; Highways; Planning and Forecasting; I72: Traffic and Transport Planning;

Filing Info

• Accession Number: 01095585
• Record Type: Publication
• ISBN: 9780309126014
• Files: TRIS, TRB
• Created Date: Apr 28 2008 9:33AM