Model And Method Research For Mission Planning And Scheduling Considering Spatio-temporal Optimization

Mission planning and scheduling(MPS)problem appears in many aspects of Transportation Geography,such as inland waterway transport,land vehicle transport and so on.Solving this problem efficiently is of great significance to enhance government power of society management and promote social and economic development.However,the existing research on MPS are not practical enough,or the effect of solution technology is not satisfactory.Based on these considerations,this paper introduces temporal and spatial constraints into the MPS problem,studies the mission planning and scheduling problem with spatio-temporal constraints(MPSST).We propose a mixed integer linear programming(MILP)model of this problem,and propose an exact model based on Combinatorial Benders Decomposition(CBD).Further,according to the in-depth analysis of the problem attributes,MPS-ST is decomposed into discrete mission sequence optimization problem and two-dimensional mission packing problem from the perspective of combinatorial optimization.A fast packing(FP)algorithm is used to solve mission packing,and an adaptive large neighborhood search(ALNS)algorithm is proposed to optimize the mission sequence.The destruction operators and repair operators with heuristic information are designed in ALNS to guide the search process of the algorithm according to the characteristics of this problem.From the perspective of mixed integer optimization,MPS-ST is decomposed into continuous scheduling timetable optimization and two-dimensional mission packing problem.The same FP algorithm is used to deal with two-dimensional packing constraints.An improved moth-flame optimization(MMFO)algorithm is proposed to optimize the scheduling timetable.The dimensional evolution mechanism of the population is introduced into the MMFO,making this algorithm be able to solving the MPS-ST problem with uncertain batch processing times.The evolution process is controlled by simulated annealing criterion,which improves the exploration and exploitation of the solution space.The test instances under different traffic conditions are generated based on the real traffic data to comprehensively compared the proposed exact models and heuristic algorithms.At the same time,two kinds of variable neighborhood descent(VND)algorithms,genetic algorithm(GA)and simulated annealing(SA)algorithm are introduced as the baseline comparison algorithms.The results show that MILP and CBD can obtain the optimal solution of small-scale MPS-ST instances in an effective time.Among them,the calculation time of CBD is shorter than MILP,but neither of them can effectively solve medium and large-scale instances within an acceptable time.The ALNS algorithm has comparable solution results to MILP and CBD on small-scale instances.On medium-to-large-scale instances,the solution effect of ALNS is better than that of MILP and CBD,and the solution results of ALNS on all instances are better than MMFO,VND,GA and SA algorithms,which further shows that MMFO algorithm from the mixed integer optimization perspective has advantages in computational time,the solution quality is still poor.And the ALNS algorithm from the combinatorial optimization perspective can efficiently solve the MPS-ST problem.