An heuristic search for the routing of heterogeneous trucks with single and double container loads

This paper addresses a new routing problem, where container loads must be shipped from a port to importers and from exporters to the port by trucks carrying one or two containers, without separating trucks and containers during customer service. We describe the problem, formulate an optimization model and propose a metaheuristic. It determines the initial solution by a variant of the Clarke-and-Wright algorithm and improves it by a sequence of local search phases. The comparison of the performance of the solutions yielded by the metaheuristic and that of a carrier’s decisions show the validity and interest of the proposed method.