The Multiple Trip Vehicle Routing Problem with Backhauls: Formulation and a Two-Level Variable Neighbourhood Search

•An introduction of a new VRP variant - MT-VRPB - an ILP formation of the problem.•CPLEX implementation to test the model and producing optimal solutions and bounds.•A sweep-first-assignment-second that produces initial feasible solution quickly.•A Two-Level VNS algorithm to solve the MT-VRPB efficiently.•A new MT-VRPB data set is generated that could be used for benchmarking.•The developed algorithm is useable for the classical VRPB.

In this paper a new VRP variant the Multiple Trip Vehicle Routing Problem with Backhauls (MT-VRPB) is investigated. The classical MT-VRP model is extended by including the backhauling aspect. An ILP formulation of the MT-VRPB is first presented and CPLEX results for small and medium size instances are reported. For large instances of the MT-VRPB a Two-Level VNS algorithm is developed. To gain a continuous balanced intensification and diversification during the search process VNS is embedded with the sequential VND and a multi-layer local search approach. The algorithm is tested on a set of new MT-VRPB data instances which we generated. Interesting computational results are presented. The Two-Level VNS produced excellent results when tested on the special variant of the VRPB.