Optimization Problems for the Large-scale Courier Industry: Quarterly Logical Network Design and Daily Transportation

Abstract

This dissertation addresses important decision-making problems for the large-scale courier company. Most courier companies adopt hub and spoke networks for transportation. In a typical hub-and-spoke network demand flows must be transported from origin spokes to destination spokes via one or two hubs. The hubs collect flows from origin spokes and efficiently distribute them to destination spokes using economies of scale to reduce the total transportation cost. This study considers the capacitated hub-and-spoke network of a parcel courier company that consists of multiple hubs, hundreds of spokes and thousands of trucks. What distinguish our problem from other studies is the consideration of classification code. A classification code is a number (identifier) assigned to a group of destination spokes. Importantly, it is required that all parcels be classified based on their destination spokes at the origin spokes because the hub to which each parcel is sent is based on the connection between the hubs and its destination. As there are hundreds of destinations in the large-scale network, the classification task at the origin spokes is very labor intensive. To solve this problem, courier companies employ a classification code system, which significantly reduces the number of categories that need to be classified by making a limited number of destination spoke groups and assigning a classification code to each group. Therefore, classification code system is critical consideration for the courier company. Quarterly logical network design, which is a mid-to long-term planning, is the main stem of this study. The maximum efficiency that the network can potentially produce depends on the connection between the hubs and spokes. The problem of creating connections in the network employing the classification code system is completely different from the typical network design problems considered in previous studies. The reason is that the network structure completely changes depending on how the spokes are divided into groups and how the sortable code combination at individual hubs are constructed. This dissertation proposes a mathematical programming model and algorithm for the generation of a corresponding network flow design with classification code. The heuristic based approach is provides a solution to real-size network problems that the MIP model cannot solve. Experimental results from benchmark datasets generated based on real-world hub-and-spoke networks demonstrate the efficiency of our proposed algorithm. Daily transportation is another stem of the study and it is short-term planning. Daily transportation issues includes traffic balancing problem between the capacitated hubs, and the simultaneous truck loading problem in each origin spoke. In addition, dozens of real-world constraints are considered in the truck scheduling process. The traffic balancing problem is called hub routing problem in this dissertation. The solution for hub routing problem and the simultaneous truck loading problem should be calculated daily within a limited time. Therefore, we proposes heuristic algorithms providing good solutions within reasonable amount of time. A TP based heuristic algorithm was developed to enable daily transportation by finding a solution for hub routing problem. The algorithm determines the solution routes of the transportation volume departing form the origin spokes. A greedy heuristic algorithm was also developed to create a truck loading plan for each origin spoke. The TP based heuristic algorithm and greedy heuristic algorithm efficiently solve problems that were previously determined by the intuition of the filed manager. It is important for the courier industry to address both short-term and long-term decision problems well. Since daily transportation is performed based on a given network, its performance is also highly dependent on the result from the logical network design. Therefore, providing an efficient network structure may be more important than daily transportation even though daily issues are the immediate challenges for the courier industry. This dissertation focuses more on addressing logical network design problem, but even provides specific solution approaches to the daily transportation problems. We hope that the results of this research will bring beneficial insight or economic effect to across the courier industry.