Solution to the Vehicle Routing Problem with Time Windows and Multiple Depots by Column Generation



Solution to the Vehicle Routing Problem with Time Windows and Multiple Depots by Column Generation

Authors

MUNOZ J, Catholic University of Chile, Chile

Description

The aim of this paper is to propose an algorithm to solve the problem of designing a set of minimum cost routes, originating and terminating in one of a set of possible depots, for an undetermined fleet (the size of it is also optimised) which serves a se

Abstract

The aim of this paper is to propose an algorithm to solve the problem of designing a set of minimum cost routes, originating and terminating in one of a set of possible depots, for an undetermined fleet (the size of it is also optimised) which serves a set of customers with known demands The vehicles have a defined capacity that cannot be exceeded. Each customer must be served within the time window defined by the earliest and latest times allowed for by the customer.

The problem is solved using the partial column generation method on a set partitioning problem solved by Simplex and Branch and Bound. In the satellital problem of this method, columns are generated by a shortest path algorithm in a negative cost cyclic network. Numerical results for several illustrative cases are discussed.

Publisher

Association for European Transport