A comparison between the fixed and flexible hub assignment approaches when solving the express shipment service network design problem

In the transportation industry, the express integrators are the only providers that offer a door-to-door overnight delivery of packages in regions as large as Europe or the US. To achieve such services, the express integrators need to design efficient transportation networks. Defining an efficient schedule of flights that enables the delivery of this service is known as the Express Shipment Service Network Design (ESSND) problem. In the ESSND problem, the packages are typically hauled first from their origin cities to hubs. At the hubs, the packages are sorted (i.e. re-ordered by destination). Then they are hauled to their destination cities. In multi-hub regions, three main types of decisions need to be made in the ESSND problem. The first type is to determine the hub assignments, i.e. the hub in which each package will be sorted. The second type is to determine the routes to fly with each aircraft. The third type is to decide how to load the aircrafts so to carry the packages from their origins to hubs and then to their destinations. Although the three decisions are highly interrelated, most works from the literature assume a fixed hub assignment, i.e. they consider the hub assignment as an input and thus as fixed. It can be said that using a fixed hub assignment has become the standard method for solving the ESSND problem. This is because, given a hub assignment, the ESSND can be solved to optimality for realistic instances in short times (less than one hour). However, generating a hub assignment is a problem in itself that, to the best of our knowledge, has not yet been explored in the literature, and that has a high impact in the network, as two hub assignments can lead to solutions with large cost differences. In this research, we first propose an ESSND model with flexible hub assignment - i.e. a model that integrates the hub assignment, routing and flow decisions - and compare its performance with the state-of-the-art models with the same approach using 45 realistic instances (7 aircraft types, 77 cities and 2 hubs). The results show that our model produces solutions 20% less expensive and with much smaller optimality gaps. Second, to study the value of integrating the hub assignment decision in the ESSND model, we develop four heuristic methods to generate hub assignments. Then, we compare the results of our approach with those of the state-of-the-art model with fixed hub assignment when fed with assignments found by the heuristics we propose with 61 realistic instances (7 aircraft types, 77 cities, and between 2 and 4 hubs). The results show that our model finds better solutions for 51 instances, with costs improvements of around 3% on average. Acknowledgment: This project was funded by the Brussels-Capital Region and Innoviris.