The two-region multi-depot pickup and delivery problem

Logistics networks are constantly evolving such that new and more varied structures arise and need to be studied. Carriers are aiming for opportunities to save costs by efficient planning. Motivated by this, we define the two-region multi-depot pickup and delivery problem. A region in this setting refers to an area where customers and depots are located. We differentiate two kinds of requests depending on whether their customers are located in the same region or not. Due to geographical characteristics, direct transportation between different regions is considered inefficient and a long-distance transportation mode needs to be used to connect them. Hence, we face a complex problem where interrelated decisions are to be made. We propose a decomposition into three subproblems, which relate to well-known problems in the literature. For solving the global problem, an adaptive large neighborhood search (ALNS) algorithm is developed. The algorithm mixes operators tailored to each of the different decisions of each subproblem. We demonstrate that these operators are efficient when applied to problems of their primal nature. In an extensive computational study, we show that the proposed ALNS dominates alternative ALNS schemes, where subproblems are treated sequentially. A detailed analysis of the solution convergence is provided. The proposed approach is a powerful tool to tackle complex decision problems in large distribution networks.