Research And Application On Load Planning Of Hub-and-spoke Network For Road Express

Road express is a kind of transportation business through highway to meet the need of high-level service and rapid transportation.With the development of economy and technology, goods circulate more and more rapidly,and multi-varieties,small-batch and high-time-effectiveness products are continuously increasing.General road transportation can not meet the need of freight market and road express becomes the best way of road transportation because of its quickness,accurateness and door-to-door service.Road express companies serve mainly for less-than-truckload freight and small parcels and they attach importance to time-definite service.The size of the shipment in less-than-truckload networks provides ample opportunities for consolidation.Road express companies have focused on hub-and-spoke based consolidation to realize economies of scale.Load planning is a branch of medium-term tactical planning on the hub-and-spoke network.Load planning focuses on freight routing,vehicle routing and empty balancing problems to lower business costs while maintaining a definite service level.Nowadays researchers from European and American countries have studied deeply in this field.So do researches from Taiwan.The characteristics shared by these districts are:they are all developed districts;companies of them are advanced and their transportation policies are flexible.Therefore,companies in these districts always use vehicles with fixed capacity and some freight is transported by tractors and trailers-one tractor can draw one or several trailers.Hence,previous literatures pay little attention to the influence on the business costs caused by different vehicle types.However,in China,the development of economy in different districts does not balance and the freight volume in different terminals of single company differs from each other greatly.It is necessary for road express companies to adopt vehicles with various capacities to increase vehicle utilization and decrease costs.Because of the costs and the policies,the way of using tractors and trailers is hard to be accepted in China. Thus,it will be a new problem to study how to choose vehicle types when we go with load planning for companies in China.In addition,since fixed costs,such as labor costs,have been going up increasingly in China, the costs of keeping vehicles are continuously rising.Meanwhile,the supply of fleet capacity is excess within the whole freight market.In order to increase the flexibility of business and reduce costs,many freight companies prefer to sign contracts with vehicle owners to use their trucks in many ways such as attached or hired vehicles and keep only several vehicles as their own. However,the way of hiring or using attached vehicles is worse than that of keeping vehicles as their own in the aspect of transportation safety and scheduling convenience.How to balance among costs,safety and convenience is a realistic problem which many road express companies must face.At present,it is hard to find literatures referring studies in this field.Therefore that is worth to be studied deeply.This thesis focuses on hierarchical hub-and-spoke networks with stopovers and hybrid hub-and-spoke networks with direct routes.For the situation of mixed vehicle types and various ways of vehicle usage in China,optimization theory and methodology is used and analysis and mathematical descriptions are provided on the load planning problem for hub-and-spoke networks.Solutions are found according to engineering application research characteristics and its efficiency is verified by computing with real business data.The two modes of operation for road freight transportation - truckload transportation and less-than-truckload transportation are discussed in this thesis.Then it is pointed out that in order to deliver freight to specific consignees on time as guaranteed,companies have to increase truck utilization by consolidating freight,instead of dispatching trucks according to the policy of "go when full" so that on a majority of the routes the truck is as full as possible at the time it must depart.Only in this way,freight carries are able to decrease operation costs.In this thesis, concept of hub-and-spoke network was introduced,structure was described,classification was summarized as well as the operating program was elaborated.In addition,two of the most important elements of hub-and-spoke network - terminals and hubs were introduced.Generally speaking,there are several hubs in a hub-and-spoke network.Each terminal connects with only one hub in a network with single assignment.The hierarchical hub-and-spoke network researched in thesis is a sort of hub-and-spoke network with stopovers.In order to avoid the difficulties of modeling and optimizing large-scale problems,we divided a network into a number of sub-networks and these sub-networks are classified as Common Subnets or Trunk-line Subnets.Each of the hubs,along with its terminals and routes between them compose a Common Subnet.All the hubs and routes among the hubs compose a Trunk-line Subnet.Such a division makes coupling degree great inside a subnet and small between two different subnets.Aiming to minimize the cost,this research presented a group of mathematical models for Common Subnets and Trunk-line Subnets respectively.In these models,the truck counts of various types and the route assignments are decision variables.Since decision variables in each subnet are independent on each other,it is entirely possible to solve the models separately.According to the constraints inside the mathematical models and using a branch-and-bound algorithm,we determined the upper bounds and the lower bounds of followings in a Common Subnet to narrow searching space:the count of routes,the count of terminals on a single route and the count of scheme of vehicle type combination for each route.Since then,an enumeratation was carried out to list every possible value of the count of routes and a genetic algorithm was used to solve the mathematical models of this Common Subnet for each value of route count.Optimization results of different route count in the same Common Subnet are compared,and the best result is selected as the final one for this Common Subnet.A branch-and-bound algorithm was used to optimize the Trunk-line Subnet.Optimization results of all subnets were put together and regarded as the final optimization results for the whole network.The transportation network of a Chinese road express company was computed as an example.Aider optimizing,the cost of this network is reduced about 15.3%than before.The results showed that once the constraints of driving time are satisfied,it is easier to get optimal schemes when there are fewer routes in the same subnet. That is to say,vehicles with greater capacity should be used when there are more terminals along a route,and then,more optimal plans could be obtained.If there are some direct routes from some terminal to others,a hub-and-spoke network becomes a hybrid hub-and-spoke network.Some direct routes were added to a hierarchical hub-and-spoke network to form a hybrid one which we research on.On the basis of the optimization of hierarchical hub-and-spoke network,several direct routes were increased to a hierarchical hub-and-spoke network using two sorts of improved greedy algorithms and it is regarded as the principle that the reduction of cost was the biggest whenever a direct route was added.Alter analyzing,this thesis presumed that it is beneficial to add direct routes for a terminal pair,between which the distance is shorter or the freight volume is larger.Therefore, two greedy algorithms based on distance and volume respectively were presented and applied to compute for the real case.The results verified the guess that it was more beneficial for decreasing costs to add direct routes between two terminals whose distance is shorter or volume is greater than to add routes between others.Furthermore,the results revealed that the greedy algorithm based on volume can reduce more costs than that based on distance.On the basis of optimization of hierarchical hub-and-spoke network,operating costs can be decreased by 4.86 percent by adding direct routes between terminals.At present,most of freight companies in China used vehicles by various means.The thesis analyzed the management characteristics of self-prepared vehicles,attached vehicles and hired vehicles,summarized the cost composition of these ways of vehicle usage,and compared costs, safety and convenience of these means.A group of multi-objective programming mathematical models were established,in which transportation safety and scheduling convenience were considered together with costs.The main objective method,the Lagrangian relaxation,the hierarchical genetic algorithm and the branch-and-bound method were combined to optimize the multi-objective programming problem.A principle was provided to set safety parameters and convenience parameters,and the real data of a road express company in China were adopted to computing.The results showed that,compared with using self-prepared trucks,using mixed ways of vehicle usage could reduce the operation costs at the price of losing some safety and convenience.They also showed that the size of cost reduction was related with safety parameters and convenience parameters whose values depended on the need of the decision-makers.Keywords:road express;hub-and-spoke network;load planning;genetic algorithm;greedy algorithm;multi-objective programming;vehicle type choosingAt present,most of freight companies in our country used vehicles by various means.The thesis analyzed management characteristics of self-prepared vehicles,attached vehicles,hired vehicles,then summarized the cost composition of these ways of vehicle usage,and compared them in the aspects of costs,safety and convenience.This thesis put safety and convenience together with costs to establish a group of mathematical models and solved them using main objective method.