Solving multitrip vehicle routing under order incompatibilities: A VRP arising in supply chain management

In this study, we introduce a new class of vehicle routing problems (VRP): the multidepot multitrip VRP with order incompatibilities. The problem is motivated by a specific two‐echelon distribution system arising in supply chain management, where products come to the depots from different factories by semitrailers and these semitrailers are also used for short‐haul distribution, that is, the load from different factories is not consolidated at the depots. This VRP is rather challenging as it combines several synchronisation constraints occurring in other well‐known standard VRP. In this article, we describe several problem variants, we model the problem as a set partitioning problem, and we show how the heuristic concept of concurrent (LS/LNS) neighborhood search which has shown to be rather effective for other complex VRP‐classes can be customized. Our computational study shows that this approach is effective and efficient for this VRP‐class, too.