| Based on "Internet+Logistics",Non-truck Operating Common Carriers(NTOCCs)and the current market status in China,the Subsection and Subcontracting Transit Network Design Problem(SSTNDP)is studied.SSTNDP considers about vehicle backhaul discount,the earliest and latest arrival time of commodity,and the transshipment synchronization.In SSTNDP,firstly,the distribution of commodity flow is decided.Each commodity departs from its origin,transfers at several nodes and arrives at its destination before deadlines.Secondly,vehicle is scheduled.NTOCCs will rent vehicles for each segment to transport the distributed commodity flow.In the whole procedure,the distribution of commodity and the schedule of vehicle are interrelated.The time synchronization of commodities,and of commodities and vehicles are both required.A mixed integer programming model based on arc is built for SSTNDP.The model aims at minimizing vehicle rent cost and commodity handling cost.The five scales of test instances for SSTNDP are constructed by standard instances.At first,a valid equality is added into the mixed integer programming model based on arc in order to strengthen constraints and improve effectiveness.Then,Branch and Price(BP)algorithm is designed to solve SSTNDP.The algorithm is composed of column generation and branch.In column generation,the mixed integer programming model based on arc is developed into a linear restricted master model based on commodity paths.The sub problem is constructed by the dual model of restricted master model.The sub problem is solved by dynamic programming.The commodity paths with negative reduced cost are moved into the restricted master problem until the restricted master problem can’t be improved any more.Two kinds of in base strategies,single path in base and multi path in base,are studied according to the number of commodity paths added into restricted master model.In branch procedure,two kinds of branch strategies,arc branch and vehicle branch,are given according to the commodity path variables and vehicle variables.In arc branch,arc branch based on network and arc branch based on divergence point are discussed.Based on the two kinds of arc branch strategies and the two kinds of search strategies,breadth first search and depth first search,four kinds of combination strategies based on arc branch are constructed.Based on arc branch,vehicle branch,and the two kinds of search strategies,four kinds of combination strategies based on arc branch and vehicle branch are constructed.Moreover,based on the algorithm of generating commodity paths neighborhoods and the restricted master model in BP,the approximate algorithm is designed to solve SSTNDP.Next,the results of mixed integer programming model after adding valid equality,BP algorithm and approximate algorithm are compared with CPLEX.The computation results show that,firstly,for adding valid equality in restricted master model,it can dramatically improve computation effectiveness.Secondly,for BP algorithm,(1)in column generation,multi path in base performs better than single path in base.(2)whether breadth first search or depth first search is adopted,arc branch based on divergence point is better than arc branch based on network.(3)when arc branch based on divergence point adopts breadth first search,vehicle branch using breadth first search performs better than using depth first search.(4)when arc branch based on divergence point adopts depth first search,vehicle branch using depth first search performs better than using breadth first search.(5)the combination of arc branch and vehicle branch performs worse than only using arc branch based on divergence point whether in column generation or in branch.However,the combination of arc branch and vehicle branch is easier to find different feasible integer solutions.(6)in small scale instances,BP algorithm acquires the same integer solutions as CPLEX,which proves the accuracy of BP algorithm.Thirdly,for approximate algorithm,it performs better than CPLEX in solving large scale instances.At last,the sensitivity is analyzed based on vehicle backhaul discount and commodity transshipment.Firstly,the testing results without backhaul discount and with backhaul discounts 0.2,0.4,0.6 are compared,which shows that,the larger the backhaul discount is,the lower the vehicle rent cost and empty rate are.Secondly,the results of direct transportation and transshipment for commodity are compared,which shows that,the cost is largely reduced after transshipment.Moreover,the results of single and multi transshipment are compared,which shows that,the cost is distinctly reduced without limited transshipment times.With above sensitivity analysis,some recommendations can be provided for logistic entities.Firstly,for transportation entities,vehicle sources with backhaul discounts should be considered in priority especially when there is commodity flow in shuttle.For vehicle rent entities,the vehicle backhaul discount can be made to improve vehicle utilization rate.Secondly,for transportation entities,the vehicle rent cost can be reduced by commodity transshipment.The multi transshipment is encouraged when there are no limited transshipment times. |
