Using Benders Decomposition for Solving Ready Mixed Concrete Dispatching Problems

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.