Shapley-based side payments and simulated annealing for distributed lot-sizingÕ

Abstract

The coordination of lot-sizing decisions in an inter-organizational supply chain allows the involved companies to find a global production plan with lower total costs compared to individual and non-coordinated plans. Usually, the involved companies (referred to as agents in the following) are independent, self-interested and have private information. This contribution studies a distributed lot-sizing problem where each item may be produced by at least two agents. A collaborative planning approach based on simulated annealing is used to coordinate the individual plans of the agents. In collaborative planning mechanisms a general design challenge is the acceptance of a new incumbent solution during the negotiation process because it requires the elicitation and aggregation of the agents’ preferences. To deal with this challenge, we integrate the calculation of side payments based on the Shapley value into the negotiation. The computation of the Shapley-based side payments is demanding due to the NP-hardness of the characteristic function, which is represented in terms of the lot-sizing model at hand. Three different ways of computing Shapley-based side payments are presented. Our computational study shows significant differences with respect to the runtime and to a lesser extend with respect to the quality of the found solutions. Most importantly, the approaches using side payments outperform an approach without side payments in 225 out of 272 cases.

Cite this work

No public copy is stored for this record, so only the metadata is cited.

Stored only when both papers are in the corpus — 12 citations exist upstream.

Papers that cite the same references — the relational fallback while embeddings are still backfilling.