An investigation into a new class of vehicle routing problem with backhauls

A new version of the vehicle routing problem with backhauls is presented. In this new problem backhauls are not restricted to be visited once all linehaul customers have been served, neither are backhaul customers fully mixed with linehaul customers. In this problem the user based on his or her experience, the vehicle capacity, the type of products and the type of vehicle used, can define the position along a route from which the first backhaul customer may be visited. An insertion-type heuristic is put forward for this class of problems. An analysis of the improvement in route cost obtained by allowing a relaxation in the restriction of the mix of linehaul and backhaul customers is reported. (C) 2002 Elsevier Science Ltd. All rights reserved.