The p-hub centre routing problem with emissions budget: Formulation and solution procedure

In recent years, the use of fossil fuels has led to a drastic increase in the emissions of CO2 and other greenhouse polluting gases. The transportation sector stands out as one of the main contributors to this pollution. Thus, several network design problems are being revisited to uncover cost and energy-efficient solutions. In this paper, we formulate and solve a p-hub centre routing problem under a CO2 emissions budget. The aim is to locate hub nodes, allocate client nodes in local tours of capacitated vehicles, and decide on vehicle speeds during transportation. The objective is to minimise the maximum time of service subject to a budget constraint on the total CO2 emissions cost of the hub network. To solve the introduced problem, we implement an efficient simulated annealing algorithm with a temperature-dependent penalty cost function, a fixed size prohibited solutions list, and a speed-based reparation heuristic. Additionally, we present a novel clustering-based construction heuristic to generate initial starting solutions for our algorithm, while hub location–allocation, vehicle routing, and speed optimisation operators are considered during the local search step. Extensive computational experiments on adapted AP data set instances show that the proposed solution approach outperforms a state-of-art solver in terms of CPU time and solution quality. Finally, we study the trade-off between the quality of service and the CO2 emission costs and discuss the effect of the CO2 budget on the design of hub networks.