Research On 2L-Split Delivery Heterogeneous Fleet Vehicle Routing Problem

In recent years,under the influence of the slowdown of economic growth,the logistics industry has gradually shifted from the incremental market to the stock market.Cost reduction and efficiency increase has become one of the main concerns of logistics enterprises.At the same time,China's manufacturing industry is also facing the pressure of transformation and upgrading.As an important part of the manufacturing supply chain,logistics will play an important role in improving the efficiency of the whole supply chain by using the operation research optimization technology.In this paper,the problem of vehicle loading and transportation is studied when the Logistics Department of the automobile manufacturing enterprise collects and transports the parts provided by the upstream supplier in the whole vehicle production chain.Combined with the actual situation,the loading problem of parts is simplified into two-dimensional rectangular packing problem,and the transportation demand of the station is allowed to be split.The vehicle type restriction of the station and the heterogeneous fleet are considered.Thus,21-SDHFCVRP is proposed.To solve this problem,this paper establishes a mathematical model,designs a heuristic optimization algorithm,and wins the championship in the "2019 SAIC·future automobile creation Invitational Competition",which proves the effectiveness and practicability of the model and algorithm.Firstly,this paper reviews the literature of two-dimensional packing problem,vehicle routing problem and vehicle routing problem with two-dimensional packing constraints,and constructs a mathematical model based on arc through reasonable assumptions and analysis of the actual requirements of enterprises.In order to solve a large-scale real case,based on the idea of path first and then segmentation,a VNS algorithm based on the solution structure of the TSP is designed to optimize the path,and the heuristic path loading algorithm is used to segment the path and load.In the packing part,two improved algorithms,knapsack combination and pattern recognition,are designed based on the maximum space algorithm,and a set of two-dimensional packing algorithms is constructed by combining several classical packing algorithms.Finally,the results of the preliminary and final test are analyzed and compared with the heuristic algorithm of other competitors to verify the effectiveness of the algorithm.The work of this paper has a certain significance for logistics enterprise operation and academic research,and the algorithm proposed can effectively solve practical problems.