A coalition structure algorithm for large-scale collaborative pickup and delivery problem. (November 2020) - Farvaresh, Hamid; Shahmansouri, Samira
Abstract: This paper considers the collaboration among a set of carriers having large-scale pickup-and-delivery problems with time windows. We develop an algorithm for determining the most profitable coalition structure subject to maximum cardinality constraint per coalition. To evaluate the proposed algorithm, a set of instances, generated based on existing benchmarks, were solved. The findings indicate that collaboration can result in substantial cost-saving. An in-depth analysis of post-solution results using machine learning techniques was presented to identify the critical factors of cost-saving and to find under what conditions of spatio-temporal features of the requests a high/low cost-saving would be possible to achieve. Highlights: A hierarchical heuristic algorithm for determining coalition structure in large-scale collaborative pickup and delivery problems. Determining the most profitable sub-coalitions while considering the maximum cardinality constraint. Proposing a multi-thread computing scheme to parallelize the computing-intensive steps of the proposed algorithm. Employing cooperative game-theoretic concepts to allocate the coalition outcomes to members. An in-depth analysis of post-solve results using machine learning techniques to identify key factors of coalition cost-saving.