The Research On Application Of Metaheuristic For VRP With Two-dimensional Loading Constraints

With the popularization of 5G network,the development of modern logistics technologies makes it possible to build a more intelligent and integrated logistics system.In this context,reasonable usage of information technology would be helpful to optimize and make some adjustments to the existing logistics system in the operational way,which could be the key to relieve the huge pressure from the increasing demands for logistics services.In this paper,by making utilization of Linear Programming,Algorithm Analysis&Design,Intelligent Optimization Algorithm,and other related theories,we focused on improving the operational efficiency and economic benefits of the logistics industries from three aspects,including designing more optimal vehicle route sets,increasing the carriage loading rate,and promoting the loading and unloading efficiency.Based on the analysis of several real business scenarios in urban logistics,four practical vehicle routing problems were proposed.In consideration of the pick-up service provided by the vehicles and the case of one fleet consisting of multiple vehicle types,we proposed two extended VRP problems:the first is a vehicle routing problem with two-dimensional packing and backhauls constraints;the second is a vehicle routing problem with two-dimensional packing,multiple vehicle types,and backhauls constraints.Considering the real demands of customers for emergency supplies in the event of sudden natural disasters,we proposed a vehicle routing problem with two-dimensional packing constraints,which aims at minimizing the total waiting time of the customers.In view of the fact that different kinds of products need to be classified and then transported separately in urban logistics,we proposed a multi-compartment vehicle routing problem with two-dimensional packing constraints.In order to further solve the four problems proposed in this paper,we presented a unified metaheuristic search framework.In comparison with the metaheuristic algorithms proposed in the literature for solving the various vehicle routing problems,this unified search framework has more advantages,especially when solving the problems proposed in this paper,due to its tailor-made characteristics in the way of solution generation,solution space,individual evaluation,and population management.Specifically,in this search framework,the relaxation of constraints and the call to split algorithm make it more efficient to generate initial solutions;the fitness evaluation method and dynamic penalty coefficient can urge the solutions transform from the status of infeasible to feasible.The existence of infeasible solution population makes the new individuals have a greater probability to move forward to the right direction when going through the stage of generation and mutation.In addition,on the basis of previous studies,we succeeded in designing several new two-dimensional packing algorithms by adopting a variety of strategies.The new packing algorithms could design a better cargo loading scheme within an acceptable time range.Finally,the two-dimensional vehicle routing problem with backhauls is successfully solved by the unified search framework.The resulting experimental results verified the effectiveness of the search framework in solving the combinatorial problems of vehicle routing and two-dimensional bin packing.In summary,based on analysis of real logistics scenarios and customers’ needs,this paper proposed several combinatorial problems integrating vehicle routing and two-dimensional bin packing,and further gave a unified metaheuristic search framework to solv’e such problems.This kind of practical research problems and the corresponding efficient&effective algorithms have positive significance to promote the efforts to enhance the operational efficiency of urban logistics system.