Ant Colony Optimization for the Two-Dimensional Loading Vehicle Routing Problem

In this paper a combination of the two most important problems in distribution logistics is considered, known as the two-dimensional loading vehicle routing problem. This problem combines the loading of the freight into the vehicles, and the successive routing of the vehicles along the road network, with the aim of satisfying the demands of the customers. The problem is solved by different heuristics for the loading part, and by an ant colony optimization (ACO) algorithm for the overall optimization. The excellent behavior of the algorithm is proven through extensive computational results.The contribution of the paper is threefold: first, on small-size instances the proposed algorithm reaches a high number of proven optimal solutions, while on large-size instances it clearly outperforms previous heuristics from the literature. Second, due to its flexibility in handling different loading constraints, including items rotation and rear loading, it allows us to draw qualitative conclusions of practical interest in transportation, such as evaluating the potential savings by permitting more flexible loading configurations. Third, in ACO a combination of different heuristic information usually did not turn out to be successful in the past. Our approach provides an example where an ACO algorithm successfully combines two completely different heuristic measures (with respect to loading and routing) within one pheromone matrix.