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

• We study a drayage problem where containers are not left at customer locations.
• We model a routing problem with multiple visits, backhauls and heterogeneous trucks.
• We show to what extend a standard solver can be used to address this problem.
• We propose a metaheuristic where a sequence of local search phases is performed.
• The metaheuristic improves the performance of a carrier’s decisions.

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.