Research On Models And Algorithms Of A Two-stage Combinatorial Bin Packing Problem Of Vehicle Outbound Logistics

The production and sales of China's automobile industry have been refreshing the world record for many years.It puts forward higher requirements on vehicle logistics.Whether the loading scheme is efficient and the dock assignment is balanced will lead to a great influence on the operating costs and benefits of industry.This thesis studies outbound system optimization of bin packing and dock assignment.Outbound logistics system should take an overall consideration of orders,available conveyances,customer evaluation index,distribution cost as well as warehouse dock resources etc.It has to balance cost and benefit in order to obtain an optimal loading scheme.Firstly,the thesis analyzes the flow process,basic information,constraints and objectives of the system.It divides the outbound system into two stages,bin packing and dock assignment.The first stage is a bin packing problem with constraints of loading capacity,route planning and customer satisfaction,and a 0-1 integer linear programming model is developed.The second stage is a dock assignment problem with variant arrival time of conveyances and unavailable time of docks,and an integer linear programming model is also built.The thesis defines parameters to establish a relation between the two models.The result of bin packing influences the sequence of dock assignment while the dock assignment influences the final carry out of bin packing.Subsequently,the thesis designs algorithms for solving the two models and the joint problem.On one hand,they are linear programming models so they can be solved by the CPLEX linear programming software.On the other hand,the thesis also designs heuristics according to the characteristics of models.Particularly,since the bin packing problem is very complicated,the thesis designs an improved branch and bound algorithm.It improves performance of the algorithm by approaches of the relaxation upper bound,dominant routes and order grouping.Finally,the thesis conducts numerical performance test for the heuristic algorithm and the improved branch and bound of bin packing,as well as the heuristic of dock assignment.It evaluates the algorithms through the value of the objective and running time.The joint solving process is based on above algorithms.Afterwards it carries example demonstration and analysis of the completed two-stage system and compares with the practical manual scheduling results.Meanwhile,the thesis designs multi-index plans,for different business scenarios.Performance tests and practical examples verify that models and algorithms are effective and significant.The research could also be applied to other industries and fields,such as car renting and similar expensive large goods transportation programs,and thus has great universality.