Integrating Side Payments into Collaborative Planning for the Distributed Multi-level Unconstrained Lot Sizing Problem

Collaborative planning mechanisms coordinate the decisions of multiple, autonomous, and self-interested decisions makers under asymmetric information. The approach proposed in this paper extends collaborative planning for the distributed multi-level uncapacitated lot-sizing problem by integrating compensation payments. Compensation or side payments provide an incentive for individual decision makers to accept inferior local solutions that may direct the search to superior global solutions for a coalition of decision makers. The approach uses neighborhood search, voting-based solution acceptance criteria and takes into account varying side payments which are negotiated. Based on 272 benchmark instances the computational study shows that the presented approach is able to achieve substantial progress compared to earlier methods. It therefore is beneficial to incorporate side payments into negotiation processes based on collaborative search.

1. Introduction

Methods for collaborative planning support a coalition of self-interested decision makers (briefly, agents) coordinating their individual plans [1]. Coordinated planning is important when a global optimum cannot be achieved if the agents pursue their local plans independently from each other. In that case, a coordinated solution generated by collaborative planning leads to added benefits. These added benefits can be allocated to the agents such that each agent is better off compared to the non-coordinated case.