Vehicle Routing Problem with Time Windows: Minimizing Route Duration

摘要

The author investigates the implementation of edge-exchange improvement methods for the vehicle routing problem with time windows with minimization of route duration as the objective. The presence of time windows as well as the chosen objective cause verification of the feasibility and profitability of a single edge-exchange to require an amount of computing time that is linear in the number of vertices. It is shown how this effort can, on the average, be reduced to a constant.