Competition in the logistics sector significantly increases driven by high cost pressure and new legal regulations. In particular, the new rules for CO2 emissions increase the pressure on logistics companies to improve their network efficiency. On the strategic level, the network efficiency of small package shippers (SPS) mainly depends on the locations of hubs and depots. Since customer demand as well as customer locations vary within the planning horizon of a strategic decision, which is about 10-15 years, a reasonable approximation of those values and a powerful planning tool are required.