Valid inequalities for the non-unit demand capacitated minimum spanning tree problem with arc time windows and flow costs

Abstract

In this paper, we introduce the non-unit demand capacitated minimum spanning tree problem with arc time windows and flow costs. The problem is a variant of the capacitated minimum spanning tree problem with arc time windows (CMSTP_ATW). We devise a mixed integer programming (MIP) formulation to model the problem and solve it using CPLEX. Furthermore, we propose three sets of inequalities, and we prove that they are valid. These valid inequalities tighten the model and lead to better lower bounds. To examine the quality of the solutions obtained, we convert the original data sets of Solomon (1987, “Algorithms for the Vehicle Routing and Scheduling Problem with Time Window Constraints.” Operations Research 35 (2): 254–265. https://doi.org/10.1287/opre.35.2.254) to approximate the non-unit demand CMSTP_ATW instances and provide results for the problems with 100 nodes. We execute extensive computational experiments, and the results show the positive effect of the inclusion of valid inequalities in the MIP.

KEYWORDS:

• Capacitated minimum spanning tree
• arc time windows
• mixed integer programming formulation
• valid inequalities
• flow costs

Acknowledgements

The authors would like to thank the anonymous reviewers, the Associate Editor and the Special Issue Editor for their acute comments and constructive suggestions that helped improve the content and the presentation of the manuscript.

Disclosure statement

No potential conflict of interest was reported by the author(s).

Data availability statement

The data that support the findings of this study are available from the corresponding author, [M.N.K.], upon request.

Correction Statement

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

Additional information

Notes on contributors

Manolis N. Kritikos

Manolis Kritikos is Professor of Operations Research and Information Systems at the Department of Management Science and Technology, Athens University of Economics and Business (AUEB). He obtained his Ph.D. in Management Science from AUEB and his MSc in Operations Research and Information Systems and BSc in Mathematics, both from the University of Athens. His doctoral research has been funded by the EDAMBA (European Doctoral Programme Association in Management and Business Administration) programme, with host institute the Rotterdam Business School. He is serving as Director of the Management Science Laboratory (MSL) of AUEB. His research interests include combinatorial optimisation, mathematical programming models, design and analysis of algorithms for operational research problems and performance measurement. In recent years, he published papers on top-ranked journal including OMEGA, Expert Systems with Applications, the International Journal of Production Economics, Journal of the Operational Research Society, International Transactions in Operational Research, Socio-Economic Planning Sciences, Applied economics, and Operational Research. He is associate editor of the Journal of Statistics and Management Systems. He was awarded the Certificate of Outstanding Contribution in Reviewing by the ELSEVIER for his contribution to the quality of the ESWA Journal. He has served as a consultant on Information Systems at the Greek Ministry of Development. From 2015 to 2021, Manolis Kritikos was Secretary General of Mathematical Society of SouthEastern Europe (MASSEE).

George Ioannou

Dr. George Ioannou is Professor of Operations Management at the Department of Management Science and Technology of the Athens University of Economics and Business (AUEB). He was the Chief Executive Officer of the Hellenic Energy Exchange Group (2019–2022), a Senior Manager at Deloitte Consulting and the Director of the Management Science Laboratory of AUEB (2012–2019). He has served as Director of the International MBA Programme of AUEB and Assistant Professor at the Department of Industrial and Systems Engineering of Virginia Tech. He received his diploma in Mechanical Engineering from the National Technical University of Athens, and his M.Sc./DIC in Robotics and Automation from Imperial College, UK. He was a GRA at the Institute for Systems Research (University of Maryland, USA) where he received his Ph.D. in Mechanical Engineering. He is the recipient of the Microsoft Excellence in Education Award and the outstanding achievement award of the Hellenic Association of Energy Economics, and has been honoured with many Excellence Awards for his MBA courses and innovative developments. He was a member of the Board of Directors of Hellenic Railroads SA, of the Innovation Council at the Ministry of Development, of AUEB’s Senate and of AmCham’s Innovation Committee, and has served as Head of the Evaluation Committee of ΣΥΖΕΥΞΙΣ ΙΙ (Information Society SA).