01095585

Component

https://doi.org/10.3141/2089-09

http://scholar.google.com...Tang&publication_year=2008

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.

01121598

English

pp 66-75

2008

Transportation Research Record: Journal of the Transportation Research Board

9780309126014

Print

Figures (7) ; References (16) ; Tables (1)

Departure time; Heuristic methods; Implementation; Intelligent transportation systems; Routing; Time dependence; Travel time; Trucking

Arrival time

Freight Transportation; Highways; Planning and Forecasting; I72: Traffic and Transport Planning

TRIS, TRB

Jan 29 2008 4:21PM

• Combination of Multiple Ant Colony System and Simulated Annealing for the Multidepot Vehicle-Routing Problem with Time Windows
• Dynamic Shortest-Path Algorithm for Continuous Arc Travel Times: Implication for Traffic Incident Management
• Equity and Efficiency Analysis of Pricing Strategies in a Bimodal Network with Heterogeneous User Groups
• Heuristic Framework for Optimizing Hurricane Evacuation Operations
• Incorporating Environmental Justice Measures into Equilibrium-Based Network Design
• Integrating Equity Objectives in a Road Network Design Model
• Location Routing Approach for the Humanitarian Prepositioning Problem
• Maximal Dynamic Expected Flows Problem for Emergency Evacuation Planning
• New Methodology for Optimizing Transit Priority at the Network Level
• Optimizing Distance-Based Fares and Headway of an Intercity Transportation System with Elastic Demand and Trip Length Differentiation
• Planning Approximations to the Average Length of Vehicle Routing Problems with Varying Customer Demands and Routing Constraints
• Solution Algorithm for Long-Haul Freight Network Design Using Shipper–Carrier Freight Flow Prediction with Explicit Capacity Constraints