Research On Location Optimization Problem In Hub-and-Spoke Transportation Network

With the development of the economic globalization, Hub-and-Spoke transportation network, which takes hubs as the core, is an effective network structure for consolidating transport resources, improving resource utilizations and reducing transport costs. It also has become a main trend in the development of modern transportation network structure. Hubs with collection and switch functions and hub arcs with flow advantages are two important parts of Hub-and-Spoke transportation network. They have a great influence on the operation of the whole network. Thus, reasonable hub or hub arc location is extremely important. Hub location problem and hub arc location problem are two hotspots in the location optimization research of Hub-and-Spoke transportation network. Among them, it is the key points to build realistic location models and design efficient optimal algorithms. This dissertation carries out in-depth study on the multiple allocation p-hub median problem and the hub arc location problem with unfixed discounts. The main work includes:(1) Algorithms optimization of the multiple allocation p-hub median problemThere are lots of repetitive computations in the process of finding optimal hub set for traditional algorithms to solve the multiple allocation p-hub median problem, because each OD(Origin-Destination) flow transfer costs need to be calculated when they pass through any hub-pair in the set. Thus, we propose a method of storing and indexing. At first, transfer costs of each OD flow passing through any potential hub-pair are stored by preprocessing, and then required data would be indexed to find directly. For the index, we design a hash function to let every hub-pair be mapped to a unique integer. So a hash index is established for quick lookup. Combined with the storage and index method, we have accomplished the optimization of enumeration algorithm and tabu search algorithm. Computation experiments on the standard CAB(Civil Aeronautics Board) datasets show that, for different scales of the data, optimized algorithms are all able to get optimal solution, and 10%～25% solution time is saved compared with traditional algorithms. Besides, for hub numbers p, the larger the value of p, the more time the optimized algorithms saves.(2) Modeling and solving of hub arc location problem with unfixed discountsDifferent from hub location problem which optimal hub nodes need to be determined in the network, hub arc location problem mainly aims to identify sections of a network with flow advantages - hub arc, which is taken on a discount of transport costs to achieve the cost optimization of the whole network. Previous studies mostly adopt hub arcs with fixed discounts, therefore it cannot be effectively against the situation that flows on hub arcs in the real network have great differences. For that, we propose a hub arc location problem with unfixed discounts (HALPUD) which uses a piece-wise linear function to simulate the unfixed discounts. We establish a mathematical model of the HALPUD, discuss the optimal solution features, and design an algorithm based on Lagrangian relaxation. Computation experiments on the standard CAB datasets show that, for different scales of the problem and different piece-wise linear functions, the Lagrangian relaxation algorithm always has a nice solution efficiency and quality. Solutions are only about 5% larger than the lower bound of the HALPUD model.