Mathematical formulations for multi-period network design with modular capacity adjustments

Abstract

Network design problems are at the heart of several applications in domains such as transportation, telecommunication, energy and natural resources. This paper proposes a new multi-period network design problem variant, in which modular capacities can be added or reduced along the planning horizon in order to adapt to demand changes. The problem further allows to represent economies of scales in function of the total arc capacity, a detail that has typically been overlooked in the literature. This paper particularly emphasizes the different alternatives to formulate the problem. We propose two different mixed-integer programming formulations and analyze further modeling alternatives. We theoretically compare the strength of all formulations and evaluate their computational performance in extensive experiments. The results suggest that a recent modeling technique using more precise decision variables yields the strongest formulation, which also results in significantly faster solution times. The use of this formulation may therefore be beneficial when considering similar problem variants. Finally, we also evaluate the economical benefits of the features introduced in this new problem variant, indicating that both the selection of the capacity levels and the capacity adjustment along time are likely to result in significant cost savings.

Keywords:

• Dynamic multi-period network design
• modular capacity changes
• mixed-integer programming

Acknowledgements

The Fonds de recherche du Québec – Nature et technologies authors are grateful to the MITACS Globalink program, which has sponsored the research internships of the first and the third author, as well as to the Natural Sciences and Engineering Research Council of Canada (NSERC) and the Fonds de recherche du Québec Nature et Technologies (FRQNT), who provide grants to the second author. The authors would also like to thank Calcul Québec and Compute Canada for providing the computing infrastructure used for the experiments.

Data availability statement

The data that have been used in the experiments and support the findings of this study are available from two of the authors, Warley Almeida and Sanjay Dominik Jena, upon reasonable request.

Disclosure statement of interests

No potential conflict of interest was reported by the authors.

Correction Statement

This article has been corrected with minor changes. These changes do not impact the academic content of the article.

Notes

1 More information about the Beluga cluster in https://docs.computecanada.ca/wiki/Beluga/en.

2 The integrality gap of a formulation for a given problem instance is defined as $\frac{v^{*}-v_{LP}}{v^{*}},$ where v_LP is the objective function of the optimal LP relaxation solution and $v^{*}$ is the optimal integer solution.

3 The cost per mile has been obtained from http://www.rtsfinancial.com/guides/trucking-calculations-formulas.

Additional information

Funding

This work has been partially funded by the Natural Sciences and Engineering Research Council of Canada (NSERC) and the Fonds de recherche du Québec Nature et Technologies (FRQNT).