Some customers are accessible by both vehicle types, whereas others solely by trucks.
After introducing an integer programming formulation for the problem, we describe a two-phase heuristic method which extends a classical vehicle routing algorithm. Since it is necessary to solve a combinatorial problem that has some similarities with the generalized assign-ment problem, we propose an enumerative procedure in which bounds are obtained from a Lagrangian relaxation. The routine provides very encouraging results on a set of test problems. Combinatorial optimization, vehicle routing problem, Lagrangian relaxa-tion.