Research On Algorithms For Geospatial Optimization Problem Based On Deep Learning

Geospatial optimization is a research area that combines combinatorial optimization from mathematics with geographic information science.Its aim is to solve practical problems related to spatial layout,resource allocation,and planning.Spatial optimization problems can be formulated as optimization problems and then solved using mathematical optimization methods.However,research into algorithms for addressing these NP-hard problems has never ceased.In recent years,an increasing number of scholars have explored solving various combinatorial optimization problems using deep learning methods,although studies on problems such as the multiple traveling salesman problem and facility location problem are still scarce.Different optimization problems have varying characteristics.Therefore,it is important to understand how to use these characteristics to select suitable deep learning models and design new network structures.This holds significant research value for solving spatial optimization problems.This study conducts algorithmic research on four spatial optimization problems: the multiple traveling salesman problem,the p-Center problem,the p-Median problem,and the maximum coverage location problem.The specific research content and main contributions are detailed below.(1)A bipartite graph neural network has been designed with the aim of overcoming the difficulties encountered when attempting to represent constraints and variables in mixed integer linear programming.The network is capable of decoupling the complex interaction between constraints and variables in mixed integer linear programming problems,and incorporates an attention mechanism to assist the network in focusing on important variables.During the training process,imitation learning is employed to learn strong branching strategies,replacing complex calculations with quick approximations to accelerate the branching process and solve Standard-MTSP,Minmax-MTSP,and Bounded-MTSP problems.By comparing three different machine learning methods,it has been demonstrated that the integration of bipartite graph networks with attention mechanisms can more effectively learn strong branching strategies.(2)The difficulty of mining the deep features of user points and facilities in the facility location problem has been identified as a significant challenge.An end-to-end method has been proposed to directly address the p-Center problem by combining the greedy method with the Graph Convolutional Networks(GCN).First,it implements an exact minimum dominating set algorithm and an approximate greedy algorithm to solve the problem.Then,the GCN utilizes the twodimensional coordinates of nodes,adjacency matrix,and clustering results from the greedy algorithm as inputs.It extracts node embedding features to learn the graph’s topological structure,resulting in new clustering outcomes.The central points and minimum distances are then determined based on these new results.The experiments demonstrate that this method reduces solution time compared to the exact algorithm based on the minimum dominating set and improves solution accuracy compared to the greedy algorithm.(3)The difficulty of learning the relationship between user points,candidate facility points,and median point sets in the neighborhood search algorithm is addressed by proposing an adaptive interactive attention model.This model is integrated into a local search algorithm that has been improved based on deep reinforcement learning to solve the p-median problem.The location problem includes two types of nodes: user points and facility points,with allocation relationships existing between them.The attention model addresses both types of nodes,unlike traditional models that mainly focus on single types of nodes.Therefore,an interactive attention encoder was developed to learn the connections between nodes.It outputs encoded features of user and facility points as inputs for the decoder.During decoding,it is necessary to select two nodes from the median point set and the remaining candidate facility point set.As a result,a node removal decoder and a node insertion decoder were designed separately.They select nodes for swap operations based on inter-node interactive information and historical selection results.This is followed by iterative processes to improve the solution.(4)In order to address the limitations of traditional methods,which are characterized by high complexity and computational cost,as well as the dynamic nature of the coverage status of nodes in the Maximum Covering Location Problem(MCLP),a dynamic coverage attention model has been proposed.This model affects the probability that a candidate facility will be selected based on the facility that has been selected.The MCLP was modelled as a Markov decision process and trained using the REINFORCE reinforcement learning algorithm.Experiments have shown that this method is effective in solving the MCLP.Additionally,the algorithm was extended to solve p-median and p-center problems and compared with various solvers,heuristic algorithms,and attention models.Finally,the trained model was used to solve an emergency facility location case,providing a scientifically sound plan for the layout of emergency centres.To summarise,this paper explores using deep learning to solve spatial optimization problems.It proposes a series of feasible algorithms that align with the characteristics of the problems,providing new ideas and methods for solving these problems.In the future,new network structures and solving paradigms for different spatial optimization problems will be further explored.Additionally,this text will explore the practical application of these methods in solving real-world problems,aiding in urban planning decisions.