Toward a more flexible VRP with pickup and delivery allowing consolidations

Abstract

One important requirement of modern supply chain management is the frequent exchange of containers via multiple cross-docks which requires spatial and time synchronisations between different types of vehicle. Moreover, as collaborations in logistics between several companies become popular, more flexible and extended models must be solved to consider the different needs of the companies. This is of high importance in a new logistics concept, the Physical Internet, which is expected to considerably improve the way logistics are handled in the current supply chain management.

To optimise the aforementioned requirements, a rich vehicle routing problem with pickup and delivery including numerous attributes is modelled and solved. A mathematical formulation is proposed and implemented in CPLEX to solve the problem. Given the complexity of the problem, solving large instances with exact methods is very time-consuming. Therefore, a multi-threaded meta-heuristic based on Simulated Annealing is developed. A set of new operators coupled with a restart strategy and memory are developed to help improve the performance.

Computational results on a generated data-set showed that the proposed meta-heuristic is superior to the CPLEX solver in terms of solvability and computational time. The proposed meta-heuristic was also compared with the best-known results by current state-of-the-art methods on a classical benchmark on pickup and delivery problems with time windows (with up to 200 customers). The experimental results showed that the proposed method was able to match the best-known results in many of these large scale instances