Many routing and logistics optimisation problems can be modelled as multi-commodity flow. When flows merge, peak demands could be satisfied; and demerging allows more efficient use of resources in periods of lower demands. Optimization models may need additional controls over how flows merge/demerge. In particular an unacceptable situation in practice is the demerging of some merged flows only to recombining them into different, but equivalent in terms of total merged flow values, combinations of merged flows again. The additional controls may be modelled by means of binary fixed charge variables, but they would increase the computational burden tremendously.
The problem of unnecessary coupling/decoupling in train unit scheduling based on integer multicommodity flows is one example. This deficiency could be overcome by fixed-charge variables, but the practicality of this approach is restricted for medium/large instances. Based on previous research, we present a further heuristic branching method for removing unnecessary coupling/decoupling without using fixed-charge variables. Based on flow potentials, this method heuristically removes candidate arcs that are ''underutilized'', such that the number of unnecessary coupling/decoupling operations is reduced. It can deal with non-interchangeable units and unbalanced arcs, compared with our previous research. Moreover, a train station sub-model is also proposed to further enhance the solutions. Computational experiments based on real-world instances have shown the usefulness of the proposed methods, which may have application for other problems in routing and logistics optimisation.
- Poster