Stable coalition selection in collaborative truckload transportation procurement

In truckload shipper collaboration, a group of shippers purchasing the services of carriers come together and try to find tours which consist of regularly scheduled shipments with minimal empty truck movements with the aim of getting better rates from the carriers in return. Finding the best set of such tours is a challenging optimization problem, the solution of which yields the set of lanes and firms to be included in the collaboration, who will collaborate with whom, and the maximum amount of savings which can be achieved. Allocation of the total calculated cost to individual lanes determines the final savings for each participant. If the allocated costs are not accepted by the participants, the collaboration will face the risk of collapse. A stable cost allocation ensures that no subcoalition is better off by breaking away from the coalition. Therefore, it is crucial to develop such cost allocation. In the literature, minimizing the total cost and allocating the minimized cost are considered as two successive but distinct phases. In this research, we first present necessary and sufficient conditions for the problem we consider to have stable cost allocation. We then show that it could not be possible to find such allocation if the distinct-phase approach is used. Because of that, we develop mixed integer programming model which combines these distinct phases into together and yields both minimum cost and stable cost allocation. Besides we develop a branch-price and cut algorithm which combines row generation, column generation, and an upper bounding heuristic to find a stable cost allocation. In addition, we develop cost allocation methods based on nucleolus in order to find a stable cost allocation. We evaluate the performance of our solution procedures by generating instances randomly with specific rules. We show that our solution procedures provide stable cost allocation. Moreover, we also show that our proposed methods based on nucleolus yield better solutions in terms of stability. Furthermore we propose two additional cost allocation methods which aim to find a stable cost allocation.