Bin packing approach for identifying minimum cost coalition structure

Abstract

Humanitarian logistics involves the crucial effort of delivering aid to affected populations during crises such as natural disasters or disease outbreaks. The success of these operations relies on managing goods, services, information, and resources across multiple planning stages. Timely response is essential for survival and recovery, and the required scale and complexity often exceed the capabilities of a single organization. When multiple organizations work together in a relief effort, they form what is known as a coalition, which can improve efficiency, effectiveness, and impact. The opportunity for cooperation raises an important question: how can these organizations best partner with one another to form coalitions? This challenge of determining the most effective arrangement of organizations into coalitions, called the optimal coalition structure, is critical for improving the effectiveness of humanitarian aid delivery. This thesis focuses on solving the optimal coalition structure problem when the costs incurred by cooperating organizations have particular features that are common in humanitarian settings. Specifically, this work considers setting in which cost is a function of coalition size, and marginal costs decrease as size increases up to a point, after which marginal costs increase. Thus, the cost exhibits economies of scale in part of the function’s range, and diseconomies at the upper end of the range. Such cost functions are non-subadditive. The goal of the optimal coalition structure problem is to find the set of coalitions that minimizes the total costs. To address the challenge of efficiently organizing coalitions, this thesis introduces a heuristic solution approach inspired by the bin packing problem. Bin packing is a classical operations research problem that aims to fit objects of different sizes into the fewest number of containers, each with a specified capacity. Similarly, the bin packing approach to the optimal coalition structure problem views each organization as an item with a given size and attempts to pack these organizations into as few coalitions (bins) as possible. Bin capacity is chosen to take advantage of the range in the cost function with economies of scale. The bin packing approach aims to determine an optimal, or near-optimal, coalition structure with less computation time than solving the optimal coalition structure problem directly. The novel approach presented by this research contributes to the understanding of optimal coalition structure problems for scenarios with non-subadditive costs. This study provides a practical tool to enhance cooperation among relief organizations by reducing the time required to find a near-optimal solution to the coalition structure problem. Also, this study sets the stage for future research, particularly in developing strategies for equitable cost distribution among organizations within coalitions and further refining the bin packing approach to achieve results that are even closer to optimal solutions. Through its contributions, this thesis not only advances academic knowledge in the field of humanitarian logistics, but also presents actionable insights for improving disaster response operations.