Metaheuristics for the vehicle routing problem with loading constraints

We consider a combination of the capacitated vehicle routing problem and a class of additional loading constraints involving a parallel machine scheduling problem. The work is motivated by a real‐world transportation problem occurring to a wood‐products retailer, which delivers its products to a number of customers in a specific region. We solve the problem by means of two different metaheuristics algorithms: a Tabu Search and an Ant Colony Optimization. Extensive computational results are given for both algorithms, on instances derived from the vehicle routing literature and on real‐world instances. © 2007 Wiley Periodicals, Inc. NETWORKS, Vol. 49(4), 294–307 2007