基于元启发式方法的高效商店分配与路径规划的Web-GIS框架

《Annals of GIS》：A Web-GIS framework for efficient store allocation and routing using metaheuristic approaches

　　

近年来，实体购物消费者对降低出行成本与产品价格的系统需求日益增长。本研究旨在设计并实现一套开源的、基于Web的位置服务（Location-Based Service, LBS）系统，以辅助消费者定位能够以最低综合成本提供所需产品的商店。研究以伊朗德黑兰市作为案例研究区域。与现有聚焦于配送或单目的地导航的LBS及车辆路径研究不同，本工作首次提出了专门面向多站点、价格敏感型实体购物行程的开源Web-GIS框架，这是发展中国家密集城市环境中一个明显未被充分探索的消费者群体。该系统采用开源技术以降低开发与运维成本。为优化购物路径，研究人员提出了一种启发式商店分配方法，将计算复杂度从阶乘O(n!)降低至多项式O(n * m)，其中m为每种产品的平均商店数量。随后，采用遗传算法（Genetic Algorithm, GA）求解旅行商问题（Travelling Salesman Problem, TSP），实现了总行驶距离的显著缩减。在一个包含6个产品位置的测试案例中，优化路径将距离从195 km（随机顺序）降至146 km。最终，为实现逐向导航，采用A*算法，与Dijkstra算法相比响应时间平均降低70%，且准确度差异极小。结果表明，所提出的框架能够有效降低购物成本并提升城市用户的效率。此外，开源Web-GIS技术的使用确保了未来开发的可扩展性、可维护性与低成本实施。

随着城市化进程加速与数字化转型深入，消费者行为正经历深刻变革。尽管电子商务已成为主导力量，实体购物在许多社会中仍具重要地位，尤其对于价格敏感且关注特定产品的消费者群体而言。这类消费者通常寻求能以最优价格提供所需产品且交通成本最低的实体商店，但在类似德黑兰这样的城市中，寻找此类商店涉及空间认知、不确定性决策与物流优化等复杂任务。地理信息系统（Geographic Information System, GIS）与Web技术的融合催生了能够支持空间决策的智能系统，其中开源技术构建的Web-GIS平台因其实时空间数据访问、交互式用户界面与可扩展架构而尤为珍贵，特别适用于专有软件成本过高的资源受限环境。

在此背景下，路径优化与高效服务需求的日益增长推动了人工智能（AI）与启发式算法在空间计算中的应用。将Web-GIS框架与遗传算法、A*搜索等元启发式方法相结合，为提升城市购物体验提供了引人注目的解决方案。尽管既有研究在Web-GIS系统与路径优化技术方面已取得显著进展，但多数研究集中于配送优化、应急响应或旅游规划，而城市零售消费者面临的多站点购物独特挑战——即需在商店分配中平衡产品价格、燃油成本与路径效率——在集成系统中尚未得到充分探索。具体而言，鲜有研究将降低搜索复杂度的启发式分配、用于TSP的遗传算法以及用于导航的A*算法整合于面向城市消费者的用户友好型LBS平台中。

本研究旨在填补上述空白，其核心目标为设计并实现一套基于Web的LBS系统，以促进成本高效的实体零售购物。研究人员以德黑兰市道路网络为数据集，构建了一个三层次架构系统：（1）表现层，采用OpenStreetMap实现地图显示，用户可注册购物清单、识别附近含所需产品的商店并查看建议路线；（2）应用层，负责接收与分析用户请求、执行算法（如用于路径优化的遗传算法与用于路径规划的A*算法）并生成适当输出；（3）数据层，包含道路网络、商店位置、产品及用户信息等空间数据，采用MySQL以保证查询速度。系统通过PHP语言实现，结合Leaflet、OpenStreetMap等开源工具，确保可扩展性与成本效益。

研究方法的核心在于三阶段优化管道的设计。第一阶段为启发式商店分配策略。研究人员提出基于贪婪启发式的商店分配算法：对每个产品，选择使累积成本（产品价格+从上一家商店或用户位置出发的燃油成本）最小的商店；产品按稀缺性（商店数量最少者优先）预排序以智能扩展搜索空间。该算法将计算复杂度从穷举搜索的阶乘O(n!)降至多项式O(n * m)，其中m为每种产品的候选商店平均数量。验证表明，该启发式方法实现了超过99%的时间缩减，而准确度损失低于1.5%，配对t检验显示与穷举搜索无显著差异（t = ?2.17, p = 0.12）。

第二阶段采用遗传算法求解TSP以优化商店访问顺序。染色体采用整数编码，每个选定商店为一个基因，染色体长度随选定商店数量变动。适应度函数定义为各基因间路径长度之和，即巡游长度（tour length）。选择方法为锦标赛选择，交叉操作采用均匀交叉配合修复机制（uniform crossover with repair），通过随机0/1掩码选择亲代基因并以缺失基因替换重复基因以确保有效排列，突变操作采用交换突变（swap mutation）。与随机基线相比，遗传算法平均减少约26%的行驶距离；与经典近邻启发式（Nearest Neighbor, NN）相比，额外实现10–13%的距离缩减，且具有统计显著性。

第三阶段为基于A*算法的实时导航。在包含163,216条有向边和89,430个节点的德黑兰市真实道路网络上，A*算法采用欧几里得距离作为启发函数（h(n)），该启发式对于城市网格而言既可采纳又具一致性，保证了最优性。算法通过预处理边连通性与方向性信息，将搜索限制于起点与终点之间的直接走廊，从而克服计算延迟。与Dijkstra算法的比较显示，A*算法在响应时间方面表现显著优势（配对t检验：t = 12.45, p < 0.001），平均响应时间从6.6–7.4秒降至1.9–2.3秒，降幅达70%，同时探索节点数减少约80%，而路径长度准确度无显著差异（t = 0.05, p = 0.98）。

研究结果部分，研究人员对50个不同真实购物场景进行了广泛测试，涉及3至8种不同产品，涵盖 varying price distributions, store locations, and user starting points。灵敏度分析考察了燃油效率（8–20 L/100 km）变化与5产品清单扩展情形，方差分析（ANOVA）显示参数变化下路径选择稳定（F = 12.3, p < 0.01），成本方差小于5%，平均节省总成本22% ± 3%。系统整体评估通过创建含三种指定产品的购物清单，在两种燃油消耗与价格情景下进行处理，验证了系统在成本最小化与计算效率间的平衡。一项针对25名德黑兰居民的非正式调查显示，系统生成的路线与商店选择与其直观节省成本的策略高度一致，尤其当燃油价格较高时。

讨论与结论部分，研究人员指出，商店分配算法成功基于特定目标分配商店且准确度可接受；遗传算法在Web环境与PHP框架内有效实现了TSP求解；A*算法在略微牺牲准确度的情况下显著降低了响应时间，其优势源于Dijkstra算法需检查所有边的结构特性，使其不适用于大型网络。研究同时指出MySQL数据库在空间功能方面的局限性，建议未来迁移至PostgreSQL/PostGIS以提升性能。

研究结论指出，寻找最低成本所需产品始终是实体购物者的核心关切之一。本研究设计并实现的位置服务系统能够满足实体购物者的需求，通过识别含所需产品的商店并安排访问顺序，最终实现总成本（产品成本与燃油消耗）的降低。评估表明，所采用的算法在各自环节均表现出色：启发式分配方法具有可接受的准确度；遗传算法作为元启发式方法再次展现了其在Web环境下求解TSP的能力；A*算法在路径规划方面效率显著。开放源代码编程语言与工具的使用进一步降低了系统的初始 setup costs，使其具有良好的实用性、可访问性与定量效率。

研究发表在《Annals of GIS》。