Split Delivery Heterogeneous Fleet Vehicle Routing Problem With Two-dimensional Loading Constraints

With the rapid development of e-commerce,the demand for logistics and transportation is rising rapidly.New logistics companies have sprung up.The problem on how to reduce logistics and transportation costs has also become critical to improving the development of the logistics industry.In recent years,some scholars have applied new cutting-edge technologies to solve logistics planning problems and have derived the research field of smart logistics.As a classic NP-Hard problem,the packing and vehicle routing problems have been widely studied in the field of logistics and transportation.In many applications,packing and vehicle routing problems need to be considered at the same time in logistics transportation,and there are usually have heterogeneous fleet of vehicles of different types.Therefore,the heterogeneous vehicle routing problems with two-dimensional loading constraints has great research value and practicability.Based on the application of an automotive manufacturing company,this paper studies the split delivery vehicle routing problem with two-dimensional loading constraints.Based on the characteristics of the problem,we propose a two-stage heuristic algorithm,which consists of the generation of the whole cabinet in the first stage,and the generation of of the tail cabinet and the routing optimization in the second stage.In the first stage,the algorithm of block generation combined with forwardlooking tree search is used to solve the packing problem;in the second stage,the rapid packing strategy based on skyline is adopted,and the wasted space is innovatively applied,and the methods of tabu search and dynamic programming are used to optimize the routing respectively.The algorithm sets up a random perturbation mechanism to jump out of the local optimum.In the computational experiment,this thesis constructs an set of test instances based on the actual data set of the company.The effectiveness of the proposed method is evaluated by the comparison with the calculation results of the CPLEX solver.The performance of the two-stage algorithm is analyzed by comparing the results of the two-stage heuristic algorithm with the results of the single-stage algorithm including only the skyline packing and path optimization.In addition,the algorithm in this paper can be applied to solve four variants of the problem,which are defined based on whether two different constraints are included.The constraints are "whether an item is allowed to rotate" and "whether the goods are loaded in the order of site visits".And,we analyzed the influence of different constraints on the optimization goal.Finally,with the experimental results,the convergence analysis of the algorithm is carried out.In addition,the visualization of the packing scheme is also realized,which brings convenience to the actual packing operation.