Multi commodity network design problem with minimum flow constraints

This research presents a fast heuristic method for solving large-scale real-life Stock Rebalancing problems with minimum transfer constraints on the arcs, as well as a maximum supply and demand limitation on the nodes, which can be considered as a variation of the multi-commodity network design (MCND) problems. The proposed Rank-based Greedy Heuristic with Swapping (RGHS) ranks all feasible flow combinations according to a profit criteria. Then, the algorithm greedily considers the combinations until demand and supply constraints are met, followed by a flow swapping mechanism to further improve the solution. Furthermore, the RGHS is extended to a Reduced Set Hybrid Model (RSHM) that combines the heuristic approach with a commercial solver on the reduced solution space. The proposed methods are evaluated against the published Modified Greedy (MG) algorithm that showed good results on benchmark instances with a significantly improved computation time compared to other state-of-the-art methods. This study contributes by proposing a fast algorithm tailored for the real-life instances on considerably larger instances compared to existing literature, and introduces the concept of minimum transfer restrictions in contrast to the more common maximum capacities. This paper reports the results on various large-scale real-life instances and larger simulated instances and shows the scalability and solution quality compared to existing methods.