A Heuristic Based on Integer Programming for the Vehicle Routing Problem with Backhauls

Vehicle Routing Problem with Backhauls is an extension of vehicle routing problem. In this problem, customers are divided into two sets as linehaul and backhaul customers. All goods are delivered to linehaul customers before goods are brought from backhaul customers. In this study, a heuristic based on integer programming is proposed. Firstly linehaul and backhaul customers are clustered to vehicles with the proposed integer model. Then clusters are routed as Travelling Salesmen Problem with Backhaul (TSPB) with TSPB integer model. Finally the route is improved by local search. A set of benchmark problem from literature is solved.