Avoiding unnecessary demerging and remerging of multi‐commodity integer flows

• Published in: Networks 2020-09, Vol.76 (2), p.206-231
• Main Authors: Lin, Zhiyuan, Kwan, Raymond S. K.
• Format: Article
• Language: English
• Subjects: fixed‐charge multi‐commodity flow; flows on bipartite graphs; heuristic branching; Heuristic methods; Integers; Operating costs; train unit scheduling; unnecessary flow demerging/remerging
• ISSN: 0028-3045; 1097-0037
• DOI: 10.1002/net.21969

Resource flows may merge and demerge at a network node. Sometimes several demerged flows may be immediately merged again, but in different combinations compared to before they were demerged. However, the demerging is unnecessary in the first place if the total resources at each of the network nodes involved remains unchanged. We describe this situation as “unnecessary demerging and remerging (UDR)” of flows, which would incur unnecessary operations and costs in practice. Multi‐commodity integer flows in particular will be considered in this paper. This deficiency could be theoretically overcome by means of fixed‐charge variables, but the practicality of this approach is restricted by the difficulty in solving the corresponding integer linear program (ILP). Moreover, in a problem where the objective function has many cost elements, it would be helpful if such operational costs are optimized implicitly. This paper presents a heuristic branching method within an ILP solver for removing UDR without the use of fixed‐charge variables. We use the concept of “flow potentials” (different from “flow residuals” for max‐flows) guided by which underutilized arcs are heuristically banned, thus reducing occurrences of UDR. Flow connection bigraphs and flow connection groups (FCGs) are introduced. We prove that if certain conditions are met, fully utilizing an arc will guarantee an improvement within an FCG. Moreover, a location sub‐model is given when the former cannot guarantee an improvement. More importantly, the heuristic approach can significantly enhance the full fixed‐charge model by warm‐starting. Computational experiments based on real‐world instances have shown the usefulness of the proposed methods.