The Cost of Continuity in the Collaborative Pickup and Delivery Problem

We assess the potential total profit in collaborative pickup and delivery problems, where carriers are willing to exchange transportation requests. For this, we design an adaptive large neighborhood search method that is used to generate solutions of publicly available but yet unsolved test instances. Our computational study reveals that collaboration profits might go up to 40% of the initial total profit, but typically come with unevenly distributed workloads. Such solution are of course not acceptable in practice. Thus, the aim of this study is to elaborate on the cost of continuity, i.e. the possibility for carriers to not deviate too much from their initial situations. Carriers might, for instance, not be willing to give up on some of their customers or want to stay with minimum profits. The rational behind keeping customers is that carriers might have long-term or particular valuable customer relationships, which they do not want to abandon. We discuss different types of continuity constraints and assess their impact on the total collaboration profit. Our computational study shows that even in the presence of continuity constraints remarkable total collaboration profits can be achieved.