Distance and Capacity Constrained Vehicle Routing in Distribution Networks: A New Branch-and-Cut-and-Price Heuristic

This paper presents a new local search heuristic for the Distance and Capacity Constrained Vehicle Routing Problem (DCVRP). The problem involves estimation of the smallest possible number of vehicles required to visit a number of nodes exactly once and identification of the vehicle routes that minimize the total distance of the tours. The suggested heuristic uses a branch-and-cut-and-price approach to the problem, which provides efficient and reliable solutions in complex networks with a large number of pickup and delivery nodes. The heuristic produces quality solutions by reducing the number of searchable node combinations, from N! to approximately 2N. The output consists of a set of complete routes that minimise total cost. Results on a problem of contagious waste collection prove that the suggested heuristic yields feasible solutions in short computing times. A quick DCVRP heuristic producing good solutions can be very helpful to policy makers whose aim is to promote rational and cost-efficient local development plans. It is also useful to logistics companies that provide pickup and delivery services and want to make effective use of their resources.