The Vehicle Routing Problem with Time Windows is a generalization of the well known capacity constrained Vehicle Routing Problem. A homogeneous fleet of vehicles has to service a set of the customers and fulfill their demands. The service of the customers can only start within a well-defined time interval denoted the time window. The objective is to determine routes for the vehicles that minimizes the accumulated cost (or distance) with respect to the above mentioned constraints. Currently the best approaches for determining optimal solutions are based on column generation and Branch-and-Bound, also known as Branch-and-Price. This paper presents two ideas for run-time improvements of the Branch-and-Price framework for the Vehicle Routing Problem with Time Windows. Both ideas reveal a significant potential for using run-time refinements when speeding up an exact approach without compromising optimality.
|Journal||Journal of Systems Science and Systems Engineering|
|Publication status||Published - 2004|
- column generation
- shortest path
- time windows
- Vehicle routing