Application Of Lagrangian Heuristic Algorithm In Assembly Line Scheduling And Vehicle Routing Proble

The flow shop scheduling problems(FSSP)and the vehicle routing problems(VRP)are combinatorial optimization problems widely used in manufacturing and modern logistics systems.Both of them are NP-hard problems with multi-objective,multi-constraint and large-scale characteristics,which are the frontier research hotspots in the field of combinatorial optimization.Lagrangian heuristic algorithm(LHA)is a novel algorithm,which combines Lagrangian relaxation technique and heuristics and combines the advantages of both of them to provide a lower bound for the problem and obtain a high-quality feasible solution to the problem in a short time.In this paper,we address the application of LHA in FSSP and VRP,and our main work is as follows.A two-stage hybrid Lagrangian heuristic algorithm(HLHA)is proposed to solve the no-wait flow shop scheduling problem with sequence-dependent setup times and release times(NFSSP＿SDSTs＿RTs).In the first stage,an improved Lagrangian relaxation technique is used to obtain the pairwise model for the problem characteristics,and an improved sub-gradient algorithm is proposed to iteratively update the Lagrangian multipliers to obtain a compact lower bound and a feasible solution with the same structure as the lower bound.In the second stage,large neighborhood search and Tabu search are introduced,and a heuristic optimization procedure is proposed to optimize the feasible solution.Through experimental comparisons and data analysis under different scale instances,it is verified that HLHA can effectively solve NFSSP＿SDSTs＿RTs.A three-stage Lagrangian heuristic algorithm(TSLHA)is proposed for solving the green vehicle routing problem with simultaneous pickup and delivery(GVRPSPD).In the first stage,an improved Lagrangian relaxation technique is used to obtain the dual model for the problem characteristics.In the second stage,an improved sub-gradient algorithm is proposed to iteratively update the Lagrangian multipliers to obtain a compact lower bound.A repair mechanism is also introduced to repair the lower bound to a feasible solution using a repair heuristic in each iteration.In the third stage,a local search algorithm is designed to optimize the feasible solution in order to obtain a nearoptimal solution with high quality.Through experimental comparisons and data analysis under different scale instances,it is verified that TSLHA can effectively solve GVRPSPD.