Publications / 2014 Proceedings of the 31st ISARC, Sydney, Australia

Using Benders Decomposition for Solving Ready Mixed Concrete Dispatching Problems

Mojtaba Maghrebi, Vivek Periaraj, S. Travis Waller, Claude Sammut
Pages 680-688 (2014 Proceedings of the 31st ISARC, Sydney, Australia, ISBN 978-0-646-59711-9, ISSN 2413-5844)

Large scale dispatching problems are technically characterized as classical NP-hard problems which means that they cannot be solved optimally with existing methods in a polynomial time. Benders decomposition is recommended for solving large scale Mixed Integer Programming (MIP). In this paper we use the Bender Decomposition technique for reformulating the Ready Mixed Concrete Dispatching Problem (RMCDP). Benders decomposition involves separating the original RMCDP formulation into the master (lower bound) and sub-problems (upper bound). The master problem only deals with integer variables and the sub problem is usually a linear programming problem. Benders optimally cuts and Benders feasibility cuts are added to the master problem upon solving the sub-problem at each iteration.. The proposed method is tested on a single real instance and results are reported.

Keywords: Benders Decomposition, Ready Mixed Concrete (RMC), Dispatching