A coalition structure algorithm for large-scale collaborative pickup and delivery problem. (November 2020)

• Record Type: Journal Article
• Authors: Farvaresh, Hamid; Shahmansouri, Samira
• Is Part Of: Computers & industrial engineering. Volume 149(2020)
• Publication Date: 2020-11
• Subjects: Collaborative pickup and delivery problem -- ALNS -- Coalition structure -- Cooperative game theory; Engineering -- Data processing -- Periodicals; Industrial engineering -- Periodicals; 620.00285
• DOI: 10.1016/j.cie.2020.106737
• Languages: English
• ISSNs: 0360-8352

Abstract

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.