We develop a Dantzig-Wolfe decomposition-based approach for solving the capacitated part-routing problem with routing flexibilities, setup times, and setup costs. Large instances of the problem are solved to near-optimality using the proposed approach. The computational performance of the approach is compared with that of the existing Lagrangean relaxation-based approach in terms of solution quality and computational times.

Dantzig-Wolfe decomposition, Lagrangean relaxation, Large-scale optimization, Manufacturing
International Transactions in Operational Research
Sprott School of Business

Nsakanda, A, Diaby, M. (Moustapha), & Cao, Y. (Yuheng). (2011). Solving capacitated part-routing problems with setup times and costs: A Dantzig-Wolfe decomposition-based solution approach. International Transactions in Operational Research, 18(1), 71–86. doi:10.1111/j.1475-3995.2010.00774.x