Subjects: Geosciences >> Geography submitted time 2022-03-29
Abstract：
Regionalization is to divide a large geographic area into a number of homogenous and spatially contiguous regions. It has been widely used in fields such as geography, cartography, ecology, environment management, socio-economy, and urban planning. Since the general regionalization problem has been proven to be NP-Hard, various models and solution methods for regionalization have be proposed since 1960s. The regionalization methods can be classified into four categories: exact, clustering-based, heuristic, and tree-based. However, the commonly used regionalization algorithms are difficult to solve the problem in an effective and efficient manner simultaneously. An improved iterative local search algorithm is proposed in this paper for the regionalization problem. There are six key mechanisms in the new algorithm: the search of moving boundary units to improve the current solution; the center-based approach to accelerate the computation of solution objective; the solution perturbation to escape from the state of local optimum; the frequent update of regional centers to reevaluate the solution; the population-based search to explore larger solution space; and the region repair to keep spatially contiguous regions. The regionalization experimentations on 55 benchmark instances show that the proposed algorithms outperforms ARISEL algorithm and SKATER algorithm in terms of sum-squared errors and adjusted Rand index. A case study of the climate regionalization using 60 attributes illustrates that the improved ILS is effective to delineate climate regions that are compatible with the precipitation, temperature and landform patterns.
Peer Review Status:
Awaiting Review
Subjects: Geosciences >> Geography Subjects: Management Science >> Management Engineering submitted time 2021-06-09
Abstract： This article proposes a matheuristic algorithm for the single-source facility location problem (SSCFLP) and its variants: SSCFLP with K facilities (SSCKFLP), SSCFLP with connective service areas (CFLSAP), and SSCFLP with K facilities and connective service areas (CKFLSAP). The algorithm starts from an initial solution, and then iteratively improves the solution by searching large-scale neighborhood of current solution. The neighborhood is defined by determining a subset of candidate facilities and a subset of customers: (1) randomly select a customer; (2) select Q nearest facilities and their customers from the current solution; (3) select nearest candidate facilities of all the customers; and (4) randomly drop some candidate facilities if too many facilities are selected in previous step. The size of neighborhood is critical to the performance of the algorithm: it is hard to solve an extra-large neighborhood and it is difficult to find a better solution in a small neighborhood. The value of Q is suggested according to the number of facilities in current solution. The current solution might be improved by finishing the following steps: (1) formulate a sub-problem model using the selecting facilities and customers; (2) solve the model and update the current solution using sub-problem solution; and (3) for CFLSAP or CKFLSAP, repair the non-connective service areas, and improve solution with local search operators. Two set of instances were generated to test the algorithm. Experimentation shows that the instances of SSCFLP and its variant problems can be solved by the proposed matheuristic algorithm effectively and efficiently. The solutions found by the proposed algorithm approximate optimal solutions or the lower bounds with average gaps of 0.01% for SSCFLP, 0.22% for CFLSAP, 0.00% for SSCKFLP, and 0.08% for CKFLSAP. Solution results show that the solution objective would be slightly increased by adding the contiguity constraints on SSCFLP or SSCKFLP. The optimal facility locations of SSCFLP/SSCKFLP might be different from those of CFLSAP/CKFLSAP. " "
Peer Review Status:Awaiting Review
Subjects: Geosciences >> Geography submitted time 2021-05-19
Abstract： This article proposes a matheuristic algorithm for the classical single-source facility location problem (SSCFLP). The algorithm starts from an initial solution, and then iteratively improves the solution by searching the large-scale neighborhoods. The initial solution is generated by a Lagrangian heuristic and the large neighborhoods are explored by solving sub-problems. The performance of the algorithm was tested on 5 set of benchmark instances. Experimentation showed that the instances could be solved effectively and efficiently. For the largest set of instances, the proposed matheuristic algorithm performs better than existing methods in terms of the solution quality, the computational time, the number of optimal solutions and the number of better solutions.
Peer Review Status:Awaiting Review
Subjects: Geosciences >> Geography submitted time 2021-05-19
Abstract： This article presents a hybrid algorithm for the service area problem. The design of service areas is one of the essential issues in providing efficient services in both the public and private sectors. For a geographical region with a number of small spatial units, the service area problem is to assign the service-demand units to the service-supply units such that each facility has a service area. The basic criteria for the service areas are the highest service accessibility, the contiguous service areas, and that the service demand does not exceed the service supply in each service area. A hybrid algorithm for the service area problem is proposed by extending iterative local search (ILS) algorithm with three schemes: population-based ILS, variable neighborhood descent (VND) search, and set partitioning. The performance of the algorithm was tested using 60 well-designed instances. Experimentation showed that the instances could be solved effectively and efficiently. The solutions found by the hybrid algorithm approximate optimal solutions or the lower bounds with an average gap of 0.15%.
Peer Review Status:Awaiting Review
Subjects: Geosciences >> Geography Subjects: Mathematics >> Control and Optimization. submitted time 2021-02-24
Abstract： Districting problems have been widely applied in geography, economics, environmental science, politics, business, public service and many other areas. The equal districting problem (EDP) arises in applications such as political redistricting, police patrol area delineation, sales territory design and some service area design. The important criteria for these problems are district equality, contiguity and compactness. A mixed integer linear programming (MILP) model and a hybrid algorithm are proposed for the EDP. The hybrid algorithm is designed by extending iterative local search (ILS) algorithm with three schemes: population-based ILS, variable neighborhood descent (VND) local search, and set partitioning. The performance of the algorithm was tested on five areas. Experimentation showed that the instances could be solved effectively and efficiently. The potential applications of the EDP in emergency services are also discussed.
Peer Review Status:Awaiting Review
Subjects: Geosciences >> Geography submitted time 2021-01-19
Abstract： 空间可达性是衡量公共服务设施公平性的重要指标，在医疗、教育、休闲等公共服务的布局规划中得到广泛应用。然而，现有可达性模型难以充分反映服务供需关系，计算指标也缺乏物理意义。本文提出新的可达性计算方法取代现有方法。该方法基于最优供需分配模型，将设施服务分配给需求者，根据分配结果计算空间可达性指标。给定服务设施与需求的空间分布，以最小化旅行成本为目标，顾及设施服务能力，采用经典的运输问题模型确定最优的服务供需分配方案，进而度量服务的空间可达性。以郑州市某区社区卫生服务为例，求解 25个中心与1333个居住小区的最优服务配置。使用最优配置结果确定每个设施的服务范围、每个居住小区使用服务的旅行时间，以及特定时间阈值的服务覆盖比率。与流行的两步移动搜索法相比，新方法的计算指标具有明确的物理意义。本文提出的可达性评价方法无需参数，计算高效，结果易于解释，在公共服务评价及设施布局规划方面具有应用潜力。
Peer Review Status:Awaiting Review
Hits
Hits
Downloads
Comment