A deterministic annealing algorithm for the simultaneous routing of loaded and empty container movements

Abstract

Our problem is to create efficient vehicle routes fulfilling both loaded and empty container transport requests. Based on demand and supply, optimal empty container allocations are determined by an allocation model. The resulting problem is a full truckload pickup and delivery problem with time windows. An initial solution is obtained by a parallel insertion heuristic. After finding a local optimum, several local search operators are embedded in a deterministic annealing algorithm to improve the solution. Results show that we are able to find good solutions in a small amount of time.