Program > By author > Zanda Simone

In this work, we introduce a new extension of the classical Capacitated Vehicle Routing Problem in which two types of customers must be served: the linehauls, to which good must be delivered from a depot and the backhauls, from which good must be collected and shipped back to the depot. In each route, all linehauls must be visited before all backhauls and each customer can be visited more than once. The objective is to serve customers with a homogeneous fleet of capacitated vehicles at minimum traveling cost. This problem, called hereafter, Split Vehicle Routing Problem with Clustered Backhauls (SVRPCB) is a combination of two extensions of the CVRP, broadly studied in the literature: the VRP with Clustered Backhauls and the VRP with Split Delivery, which, to our knowledge, have never been addressed together before. We present an Integer Linear Programming model for this problem and propose a GRASP metaheuristic, which consists of a constructive phase, based on a greedy randomized algorithm, combined with a local search. In the constructive phase, customers are inserted one by one in a greedy fashion, after their random selection from a Restricted Candidate List. The solution determined in the construction phase is improved in the local search phase. Next, a new solution is built in the construction phase and improved in the local search and so on. The best local optimum is finally taken. Preliminary results will be presented during the talk.