Abstract:This work studies a new practical combinatorial optimization problem (known as 2L-VRPB) which combines the classic Vehicle Routing Problem with Backhauls (VRPB) and two-dimensional Bin Packing Problem (2L-BPP). The 2L-VRPB aims to find the route set at the minimum cost for a homogeneous fleet of vehicles to satisfy the delivery requirements of linehaul customers and the pickup demands of backhaul customers. This study investigates two versions of the 2L-VRPB. Both versions are loaded with unrestricted loading, but one is packed with rotation while the other is not. These two variants are frequently employed in the industry of appliance maintenance service and grocery, but they have been less examined in the literature. To solve these two variants, we propose a metaheuristic integrating an enhanced memetic algorithm with a combinatorial packing heuristic. The packing algorithm checks the loading feasibility by employing five basic packing heuristics with two additional improvement strategies. Extensive computational experiments show that the proposed metaheuristic is a practical and effective solution to both VRPB and 2L-VRPB.