Research On Modeling And Optimization Method For The Transportation Problem With Stepwise Fixed Cost

The fixed-cost transportation problem(FCTP)is a typical NP-hard combinatorial optimization problem extracted from production and logistics operations,and hence it has important theoretical significance to study this problem.In previous studies on FCTP,most of them assumed that the capacity of the conveyance is large enough,and fixed cost is only related to whether there is a load on the transport route.However,in the actual transport activities,conveyance usually has the maximum capacity limit.In order to transport a large amount of goods between supply and demand sites,it is usually necessary to use a number of conveyances,and each conveyance is associated with a fixed cost.In this thesis,we abstract a new type of generalized transportation problem,named transportation problem with stepwise fixed cost(SFCTP).The features of SFCTP are that the conveyance has the capacity limit,and each transport is associated with a fixed cost that is unrelated to freight volume.On the basis of analyzing the characteristics of SFCTP,this thesis studies the modeling method,the bounding method and the heuristic algorithm based on the mathematical programming.The main contents of this thesis are as follows:1)This thesis analyzes that the characteristics of transportation costs between supplies and demands are the stepwise function related with freight volume.Taking the transportation volume and the number of conveyances needed between each supply and demand sites as the decision variables,we formulated the problem as a mixed integer programming model.The objective is to minimize total transportation costs including fixed cost associated with the number of conveyances used and the variable cost associated with delivered freight volumn.Furthermore,we derive the property of the optimal solution which provides the basis for designing the neighborhood structure used in the local search process.2)The LP relaxation of the original model can only provide a looser lower bound,and hence it is difficult to evaluate the quality of the obtained feasible solution.In this thesis,we reformulate the original model as a new equivalent model by the variable discretization strategy,and then propose two kinds of valid inequalities(rounding inequalities and set covering inequalities)to compress the solution space of the LP relaxation and tighten the lower bound.Because there is a huge number of variables(columns)and the number of constraints(rows)involved in the reformulate model,it is difficult to solve it directly even for its LP relaxation.In this thesis,we propose a row-and-column generation algorithm to solve the reformulated model.The algorithm starts with a restricted master problem which contains only a limited number of rows and columns,and then generates the necessary rows and columns dynamically.The computational results on a variety of instances show that the LP relaxation of the reformulate model can provide a tighter lower bound than the LP relaxation of the orignal model.3)In order to solve the large-scale problem effectively,we proposes a solution method to combine the exact method based on the mathematical programming with the heuristics based on the intelligent optimization.In particular,the proposed method is based on the framework of iterated local search(ILS),and applies a set of high-quality dual solutions generated by the row-and-column generation algorithm to the perturbation phase to guide the global search direction.The motivation of using dual solutions to the perturbation phase is to overcome the blindness of the conventional random based perturbation.The thesis makes a large number of computational experiments on randomly generated instances,and the result show that the improved ILS algorithm can obtain a near optimal solution with the optimality within 2.37%,which is significantly better than the conventional ILS algorithm.