A Tabu Search heuristic for the vehicle routing problem with two-dimensional loading constraints

This article addresses the well-known Capacitated Vehicle Routing Problem (CVRP), in the special case where the demand of a customer consists of a certain number of two-dimensional weighted items. The problem calls for the minimization of the cost of transportation needed for the delivery of the goods demanded by the customers, and carried out by a fleet of vehicles based at a central depot. In order to accommodate all items on the vehicles, a feasibility check of the two-dimensional packing (2L) must be executed on each vehicle. The overall problem, denoted as 2L-CVRP, is NP-hard and particularly difficult to solve in practice. We propose a Tabu Search algorithm, in which the loading component of the problem is solved through heuristics, lower bounds, and a truncated branch-and-bound procedure. The effectiveness of the algorithm is demonstrated through extensive computational experiments. (C) 2007 Wiley Periodicals, Inc.