Combinatorial Packing Problem: Models And Algorithms

Vehicle outbound packing problem involves large data scale, high degree of statistical difficulty and multi-constraints. Its complexity, required processing speed and accuracy are far beyond artificial processing ability. However, third party logistic companies generally have low degree of information and program development, along with big difference of personnel quality and high management difficulty, so they still adopt manual operation, leading to low efficiency. Due to large scheduling scale, manpower cost can not be ignored. Meanwhile, the computing scope and speed can not meet demand of the large-scale calculation. Therefore, it is of great significance to develop a simple and effective model, and raise the problem's practical value.Based on vehicle outbound packing process, to improve the status quo, we leave some constrains and objectives for subsequent processing, find core constraints and objectives of outbound packing scheduling, and define the problem as an one-dimensional combinatorial packing problem. The problem can be described as n items which belong to l types of the same (unit) size. There are w vehicles, each vehicle has several loading combinations for these l types, different vehicles with different load combinations. Each vehicle only can choose one combination and load items in strict accordance with the loading combination. The optimization goal is to load the most items.The thesis aims to provide a basic model. Model's application value, problem solving time, utilization of resources and setting reasonable parameters for the problem are key points of the problem. Therefore, based on analysis of the problem, we first establish a linear mixed integer programming, along with branch and bound algorithm model, as the solving time and scale can't meet the needs of the application. Then we propose a heuristic algorithm based on greedy techniques. Finally, we use ILOG Cplex to find the optimal solution. Through numerical experiments we verify the correctness of the model and algorithms'efficiency. Meanwhile, parameter sensitivity analysis proves that:⑴Vehicle utilization increases with the increase of load combinations, but declines slowly when it reaches the peak point;⑵Computer memory consumption and solution time decline as the number of types increases , however, the number of items loaded declines sharply.This thesis proposes one-dimension combinatorial packing problem, and provides a different method to solve packing problem. The model and algorithms have significance for practical application.