Vehicle routing with multiple deliverymen: Modeling and heuristic approaches for the VRPTW

In real life distribution of goods, relatively long service times may make it difficult to serve all requests during regular working hours. These difficulties are even greater if the beginning of the service in each demand site must occur within a time window and violations of routing time restrictions are particularly undesirable. We address this situation by considering a variant of the vehicle routing problem with time windows for which, besides routing and scheduling decisions, a number of extra deliverymen can be assigned to each route in order to reduce service times. This problem appears, for example, in the distribution of beverage and tobacco in highly dense Brazilian urban areas. We present a mathematical programming formulation for the problem, as well as a tabu search and an ant colony optimization heuristics for obtaining minimum cost routes. The performance of the model and the heuristic approaches are evaluated using instances generated from a set of classic examples from the literature.