Applying Column Generation to the Discrete Fleet Planning Problem


Bosman, M.G.C. and Bakker, V. and Molderink, A. and Hurink, J.L. and Smit, G.J.M. (2010) Applying Column Generation to the Discrete Fleet Planning Problem. In: STW.ICT Conference 2010, 18-19 Nov 2010, Veldhoven, The Netherlands (pp. pp. 200-204).

open access
Abstract:The paper discusses an Integer Linear Programming (ILP) formulation that describes the problem of planning the use of domestic distributed generators, under individual as well as fleet constraints. The planning problem comprises the assignment of time intervals during which the local generator must produce or not. In [1] this ILP is shown to be NP-complete in the strong sense. Heuristic methods have been developed to find solutions in reasonable time.

In this work a different technique is used to overcome the complexity problems. We use column generation to search the possible decision vectors in a faster way. The ILP is slightly adjusted to facilitate the column generation technique to search in a clever way through the set of possible solutions.

To measure the results, the column generation technique is compared to an earlier developed heuristic method. Both the quality of the objective function and the speed of the methods are compared.
Item Type:Conference or Workshop Item
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:
Link to this item:
Conference URL:
Export this item as:BibTeX
HTML Citation
Reference Manager


Repository Staff Only: item control page