Abstract: Hub-and-Spoke network design problem with fixed hub arc cost has a wide range of applications within the third party logistics, postal services and airline transportation. Current researches concentrated on hub location while this paper emphasizes on the fixed hub arc costs which reflects a fact that the transportation on hub arc must be provided with large-scale vehicles and therefore pay extra fixed costs. This paper constructs a mixed 0-1 integer programming model, and provided a heuristic algorithm based on Lagrangian relaxation。 We also extend the problem by add the route distance constraint which is very important on emergency logistics and express delivery. We solve the extended problem by modifying the original algorithm.

Key words: hub-and-spoke network, hub arc, collaborative transportation, Lagrangian