Scientific Program > Talks by Speaker > Subramanian Anand

In the VRP with backhauls (VRPB) there are two sets of customers: linehaul and backhaul. The first one has delivery demands, while the second has pickup demands. The objective is to design a set of least-cost routes satisfying the following constraints: (i) each customer must be visited exactly once; (ii) a non-empty route must contain at least one linehaul customer; (iii) backhaul customers can only be served after all linehaul customers have been visited in a particular route; and (iv) the capacity of the vehicle cannot be exceeded. The problem can be seen as a special case of the asymmetric VRP with mixed backhauls (AVRPMB). We tackle the VRPB by: (i) directly applying a state-of-the-art AVRPMB matheuristic for the problem, in which a VRPB instance is transformed into an AVRPMB instance, i.e., the infeasible VRPB arcs (from backhaul to linehaul customers, and from the depot to backhaul customers) are penalized; and (ii) by adapting the same matheuristic for the VRPB itself. Such adaptation mainly consists of preventing infeasible moves to be unnecessarily evaluated during the local search and also by only allowing feasible solutions to be explored in all steps of the algorithm, as opposed to the first solution strategy. Both approaches were capable of obtaining all best-known solutions for the traditional benchmark instances and the result of one instance was improved. We also compared the scalability of both methods for instances with up to 1000 customers.