A construction heuristic for the capacitated Steiner tree problem

Many real-life problems boil down to a variant of the Minimum Steiner Tree Problem (STP). In telecommunications, Fiber-To-The-Home (FTTH) houses are clustered so they can be connected with fiber as cost-efficiently as possible. The cost calculation of a fiber installment can be formulated as a capacitated STP. Often, STP variants are solved with integer linear programs, which provide excellent solutions, though the running time costs increase quickly with graph size. Some geographical areas require graphs of over 20000 nodes—typically unattainable for integer linear programs. This paper presents an alternative approach. It extends the shortest path heuristic for the STP to a new heuristic that can construct solutions for the capacitated STP: the Capacitated Shortest Path Heuristic (CSPH). It is straightforward to implement, allowing many extensions. In experiments on realistic telecommunications datasets, CSPH finds solutions on average in time O(|V|²), quadratic in the number of nodes, making it possible to solve 50000 node graphs in under a minute.

Forecasting global aluminium flows to demonstrate the need for improved sorting and recycling methods

The probable emergence of a global aluminium scrap surplus in the coming decade is one of the main incentives for the aluminium recycling industry to invest in new methods and technologies to collect, sort and recycle aluminium scrap. However, due to the considerable uncertainty in the evolution of the global scrap surplus, it is difficult for policymakers and the recycling industry to accurately estimate the economic and environmental advantages of implementing enhanced sorting and recycling methods. The International Aluminium Institute (IAI) has developed a model to track and forecast the global flows of aluminium, but this model is not extensive enough to estimate the scrap surplus evolution. Therefore, this paper introduces an alloy series resolution to the supply and demand of aluminium in the IAI's global flow model and estimates the composition of the recovered scrap flows to improve the estimate of the technical potential of secondary alloy production. The estimated scrap surplus evolution is subjected to a sensitivity analysis, considering the most critical parameters, including the speed of electrification in the automotive sector, the recovered scrap's composition and the lifetime of aluminium products. In addition, the estimated composition of the recovered aluminium scrap in the model is compared to composition measurements of alumimium scrap collected at a Belgian recycling facility as a means of validation. This study allows to estimate that the global aluminium scrap surplus will emerge soon and reach a size of 5.4 million tonnes by 2030 and 8.7 million tonnes by 2040, if currently adopted aluminium sorting and recycling methods are not improved.