1. 项目概述：当数学建模遇上城市治安

几年前，我还在读研时，和队友一起参加了全国研究生数学建模竞赛。那年的赛题“警车配置及巡逻方案”，至今让我印象深刻。它不像纯理论推导那样抽象，而是把一个真实的城市管理难题，用数学语言清晰地摆在了我们面前：给你一个城市的道路网络、案发数据，你如何用有限的警车资源，设计一套巡逻方案，才能最有效地预防犯罪、快速响应警情？这本质上是一个资源优化配置问题，但在当时，它完美地融合了图论、优化算法、概率统计和仿真模拟，让我们这些“纸上谈兵”的学生第一次感受到了数学建模解决实际问题的巨大魅力。

这个题目之所以经典，是因为它触及了城市公共安全管理的核心痛点。警力资源永远是有限的，而城市的角落是无限的。是让警车均匀分布，还是重点布防？是固定路线巡逻，还是动态响应调度？巡逻的频率和范围如何设定，才能在案发时最快赶到现场？这些问题背后，都需要严谨的数学模型来提供决策支持。对于参赛者而言，这不仅考验数学功底，更考验将复杂现实问题抽象、简化和求解的综合能力。无论你是管理科学、交通运输、应用数学还是计算机专业的学生，都能在这个题目中找到发挥的空间。接下来，我将结合当年的解题思路和后续的一些思考，拆解这道赛题的核心解法与延伸应用。

2. 问题拆解与核心思路设计

面对“警车配置及巡逻方案”这样一个开放式问题，第一步也是最关键的一步，就是建立清晰的问题分析框架。我们不能一头扎进公式和代码里，必须先理解题目到底在问什么，以及我们可以用什么工具来回答。

2.1 核心需求解析：效率、覆盖与响应

题目通常会给出一张城市道路网络图（节点代表路口，边代表道路，有权重如长度或通行时间）、历史案发数据（案发地点、频率）以及警车的数量、速度等约束条件。我们的目标可以分解为三个相互关联又可能冲突的子目标：

1. 最大化覆盖效率 ：警车的巡逻路线应尽可能覆盖更多的道路和区域，特别是案发率高的重要区域，起到威慑和预防作用。
2. 最小化响应时间 ：当任何一点发生案件时，离它最近的警车能在规定时间内（比如3分钟）到达现场。这是硬性要求，直接关系到应急处置能力。
3. 优化资源配置 ：在满足上述要求的前提下，如何配置最少量的警车，或者给定警车数量时，如何设计巡逻方案使其综合效能最高。

这三个目标就像是一个“不可能三角”，你需要做出权衡。例如，为了最快响应，你可能需要将警车分散布置，但这会降低对非重点区域的巡逻覆盖频率；反之，如果让警车集中巡逻重点区域，边缘地区的响应时间就可能超标。我们的模型，就是要在这个三角中找到一个最佳的平衡点。

2.2 模型构建的总体思路

基于上述目标，一个典型的建模思路是分层处理：

第一层：静态配置优化（警车应该部署在哪里？） 这相当于解决警车的“基地”或“初始位置”问题。我们可以将城市区域网格化或基于道路网络节点化，把警车配置问题转化为一个“设施选址”问题。常用的模型包括：

• 最大覆盖模型 ：在警车数量固定下，选择部署点，使得在指定响应时间内能覆盖的人口或案发点最多。
• P-中位模型 ：选择P个部署点，使得所有需求点（案发点）到其最近部署点的平均距离（或加权距离）最小。
• 考虑权重的模型 ：不同区域的历史案发率不同，高发区应有更高的覆盖优先级。因此，在目标函数中，应以案发频率作为权重，优先覆盖高风险节点。

这一步的输出，是得到了警车的初始驻守点或负责的“责任区”。

第二层：动态巡逻路径规划（警车在责任区内怎么走？） 确定了责任区后，我们需要为每辆警车规划巡逻路线。这不是简单的旅行商问题（TSP），因为巡逻是持续、循环的行为。我们需要设计一条或多条闭合回路，让警车周期性地巡行。关键考量点包括：

• 路径长度与巡逻周期 ：路线总长度应与警车速度结合，形成一个合理的巡逻周期（如30分钟一圈）。周期太短，警车总在很小范围转悠；周期太长，对某条路的巡查间隔太久。
• 道路重复率 ：理想情况下，责任区内所有道路都应被覆盖到。但有些支路可能无法纳入主回路，这就需要设计辅助路线或允许一定程度的重复行驶。
• 随机性与不可预测性 ：固定的巡逻路线容易被规避。因此，高级的模型会引入随机元素，比如在几条预设路线中随机选择，或在某个节点随机选择下一个方向，以增加巡逻的不可预测性。

第三层：动态响应与调度模拟（发生案件时怎么办？） 当模拟案件发生时，系统需要根据警车的实时位置（正在巡逻中），动态计算哪辆车前往处置最合适（通常是最短时间），并更新该警车后续的巡逻计划。这可能涉及路径的重规划。这一步通常需要通过仿真来评估方案的整体效果。

注意 ：在实际竞赛中，由于时间有限，我们可能无法建立一个完美融合三层的复杂模型。一个实用的策略是： “静态配置为主，动态巡逻为辅，用仿真检验效果” 。即先花主要精力建立一个优秀的静态配置模型，然后为之设计合理的巡逻路线，最后通过随机生成案发事件进行仿真，统计响应时间达标率和覆盖率等指标，来评价方案优劣。

3. 关键技术点与模型实现细节

有了整体思路，我们来深入几个核心的技术环节，看看具体如何用数学和编程实现。

3.1 图论基础：城市网络的抽象

一切的基础是将城市地图转化为数学上的“图”。我们使用 G(V, E, W) 来表示：

• V : 顶点集合，代表路口，数量为n。
• E : 边集合，代表道路，数量为m。
• W : 边的权重，通常代表道路长度或平均通行时间。

邻接矩阵与距离矩阵 ： 这是两个最关键的数据结构。邻接矩阵 A （n×n）表示顶点间的直接连接关系，如果路口i和j有道路直接相连，则 A[i][j] = 1 或道路长度，否则为无穷大或0。而距离矩阵 D （n×n）则存储任意两个路口之间的最短路径距离，这需要通过 弗洛伊德算法 或 迪杰斯特拉算法 预先计算出来。 D 矩阵是后续所有优化计算的基石，因为警车的响应时间直接取决于最短路径距离。

# 以Python为例，使用networkx库可以方便处理图
import networkx as nx
import numpy as np

# 假设我们有路口列表和道路列表（带长度）
G = nx.Graph()
G.add_weighted_edges_from([(0,1,1.2), (0,2,0.8), (1,3,1.5)]) # (路口i, 路口j, 距离)
# 计算所有节点对最短路径长度
lengths = dict(nx.all_pairs_dijkstra_path_length(G))
# 转换为距离矩阵
nodes = list(G.nodes)
n = len(nodes)
D = np.zeros((n, n))
for i in nodes:
    for j in nodes:
        D[i][j] = lengths[i][j]

3.2 核心模型一：带权重的最大覆盖选址模型

这是解决警车初始部署的强有力模型。其数学模型可以表述为：

决策变量 ：

• x_j = 1 如果在路口j部署一辆警车（作为基地），否则为0。
• y_i = 1 如果需求点i（路口）能在响应时间T内被至少一辆警车覆盖，否则为0。

参数 ：

• P : 可供部署的警车总数量。
• w_i : 需求点i的权重，这里可以用该路口历史案发频率或周边案发密度来表示。
• a_{ij} : 覆盖系数，如果从候选点j到需求点i的最短时间 D[i][j] <= T （响应时间阈值），则 a_{ij}=1 ，否则为0。

目标函数与约束 ：

Maximize: Σ (w_i * y_i)          # 最大化加权覆盖需求
Subject to:
Σ x_j <= P                       # 警车数量限制
y_i <= Σ (a_{ij} * x_j)          # 只有i被至少一个选中的j覆盖时，y_i才能为1
x_j ∈ {0, 1}, y_i ∈ {0, 1}       # 0-1决策变量

这个模型是一个经典的0-1整数规划问题，可以直接使用优化求解器（如CPLEX, Gurobi）或利用启发式算法（如遗传算法、模拟退火）进行求解。求解结果 x_j 就告诉我们警车应该部署在哪些路口。

实操心得 ：在竞赛中，直接调用商用求解器可能受限。我们当时采用了 遗传算法 来求解。编码方式很简单：用一个长度为n（路口数）的二进制染色体，1代表该路口部署警车。适应度函数就是上述目标函数。但需要注意，必须加入约束处理（如修复算子，当染色体中1的个数超过P时，随机将一些1变为0），否则会得到不可行解。这种方法虽然不能保证全局最优，但在有限时间内能得到非常不错的可行解。

3.3 核心模型二：巡逻路径的生成与优化

为每个部署好的警车规划巡逻路线，可以看作是在其责任区内寻找一个或一组较优的环。责任区可以通过Voronoi图划分：每个警车基地负责离它最近的所有路口和道路。

中国邮递员问题 ： 如果目标是让警车经过责任区内 每条道路至少一次 ，然后返回起点，这就是 中国邮递员问题 。如果道路网络所有路口度数均为偶数（欧拉图），则存在欧拉回路，可以一笔画不重复地走完所有边。但现实路网通常是奇度顶点。这时需要添加重复边（即警车需要重复巡逻某些路段），使得所有顶点度数为偶。添加重复边的总长度要最短，这可以通过解决奇度顶点之间的最小权匹配问题来实现。

多回路巡逻 ： 对于较大的责任区，一辆警车走完所有边可能周期太长。此时需要将其划分为多个较小的子区，每个子区由一个巡逻回路覆盖。这可以建模为 车辆路径问题 的一个变种。一个实用的启发式方法是：

1. 将责任区内所有道路视为必须服务的“客户”。
2. 使用聚类算法（如谱聚类、基于距离的聚类）将这些道路分配到K个簇中，K由期望的巡逻周期决定。
3. 对每个簇，求解一个中国邮递员问题，得到一条巡逻回路。

# 简化的巡逻路径生成思路（基于欧拉回路）
import networkx as nx
from networkx.algorithms import euler

# 假设sub_G是某警车责任区的子图
# 1. 检查并修复为欧拉图
def make_eulerian(graph):
    # 找到所有奇度顶点
    odd_vertices = [v for v, d in graph.degree() if d % 2 == 1]
    # ... 此处应实现最小权匹配算法，为奇度顶点对添加重复边 ...
    # 简化：随机配对，并添加最短路径作为重复边（非最优，仅示意）
    for i in range(0, len(odd_vertices), 2):
        u, v = odd_vertices[i], odd_vertices[i+1]
        sp = nx.shortest_path(graph, u, v, weight='weight')
        for j in range(len(sp)-1):
            graph.add_edge(sp[j], sp[j+1], weight=graph[sp[j]][sp[j+1]]['weight'])
    return graph

eulerian_sub_G = make_eulerian(sub_G.copy())
# 2. 生成欧拉回路
circuit = list(euler.eulerian_circuit(eulerian_sub_G, source=depot_node))
# circuit即为一条覆盖子图所有边的巡逻回路

3.4 仿真评估：方案好坏的试金石

静态模型设计得再漂亮，也需要动态仿真来检验。我们需要模拟一个较长的时间段（如一周），在这个时间段内：

1. 案发事件生成 ：根据历史案发数据（空间分布和频率），用随机过程（如非齐次泊松过程）在随机时间和随机地点生成案件。
2. 警车状态模拟 ：每辆警车按照其巡逻路线循环移动。我们需要维护每辆车的实时位置（在某条边的具体位置）。
3. 动态调度逻辑 ：当案件发生时，立即计算所有警车到达案发地点的预计时间（考虑当前位置和剩余路径）。选择预计时间最短的警车前往处置。该警车中断当前巡逻，沿最短路径驶向案发点。
4. 指标统计 ：
   • 平均响应时间 ：所有模拟案件响应时间的平均值。
   • 响应时间达标率 ：响应时间小于阈值T的案件比例。
   • 道路覆盖率 ：在模拟时间内，所有道路被巡逻车经过的频率分布。
   • 警车负荷均衡度 ：各警车处理案件数量的方差，避免有的车忙死有的车闲死。

通过调整模型参数（如警车数量、巡逻速度、响应阈值T）并运行多次仿真，我们可以比较不同方案的优劣，甚至进行参数敏感性分析。

4. 方案实现中的挑战与优化技巧

在实际编程和求解过程中，我们会遇到不少挑战。下面分享一些我们当时踩过的坑和总结的技巧。

4.1 数据预处理与尺度问题

题目给出的数据往往不是“干净”的。路口坐标、道路连接关系可能有误或缺失。案发数据可能是经纬度点，需要匹配到最近的道路或路口上。 地理编码 和 地图匹配 是前期繁重但至关重要的工作。

技巧：网格化与聚合 当路口和案发点数量极大时，直接计算距离矩阵 D （O(n³)复杂度）会非常慢。一个有效的降维方法是 网格化 。将城市区域划分为大小合适的网格（如500m×500m），每个网格视为一个“超级节点”。网格内的案发点合并，案发频率相加作为该网格的权重。道路则根据其经过的网格进行近似。这样，节点数从成千上万个路口减少到几百个网格，计算量大大降低，且更符合警力调度中“区域”管理的概念。

4.2 算法选择与求解效率

• 精确解 vs. 启发式解 ：对于整数规划模型，除非规模很小，否则寻求精确最优解非常耗时。在72小时的竞赛中， 启发式算法 （如遗传算法、模拟退火、禁忌搜索）是更实际的选择。它们能在可接受时间内给出高质量可行解。
• 遗传算法设计要点 ：
  • 编码 ：除了直接的二进制编码，对于巡逻路径问题，可以采用顺序编码表示路径节点序列。
  • 交叉与变异 ：设计针对问题的算子。例如，在路径规划中，使用部分映射交叉（PMX）或顺序交叉（OX）来生成子代路径。
  • 适应度函数 ：它是算法的指挥棒。不仅要包含核心目标（如覆盖权重），还应加入对约束违反的惩罚项（如响应时间超限、警车超数量），将约束优化问题转化为无约束问题。
• 分阶段求解 ：不要试图用一个模型解决所有问题。采用“配置-路径-仿真”的分阶段策略，每个阶段聚焦一个子问题，降低复杂度。

4.3 引入随机性与动态性

固定巡逻路线有其弊端。为了增强方案的鲁棒性和现实性，可以考虑：

• 随机化巡逻 ：为每辆警车预设3-5条不同的巡逻回路。在每个巡逻周期开始时，随机选择一条。这增加了不确定性。
• 基于案发预测的动态调整 ：如果模型允许，可以引入简单的案发时间预测（如白天商业区高发，夜晚娱乐区高发），让警车在案发概率高的时段，更倾向于在其附近巡逻。
• 空闲巡逻策略 ：当没有警情时，警车除了按固定路线巡逻，还可以向其责任区内近期未被巡逻到的道路进行“查漏补缺”式的移动。

5. 模型评价、扩展与实战思考

一个完整的数模论文，不仅要有模型和结果，还要有深刻的评价与讨论。

5.1 方案的多维度评价体系

评价一个警车配置与巡逻方案，不能只看一两个指标。一个全面的评价体系应包括：

• 效率指标 ：平均响应时间、达标率、加权覆盖率。
• 经济指标 ：所需警车总数、总巡逻里程（与油耗、损耗相关）。
• 公平性指标 ：不同区域（如市中心与郊区）响应时间的差异程度，避免资源过度倾斜。
• 鲁棒性指标 ：模拟某条道路突发拥堵或某辆警车临时故障时，方案性能的下降程度。可以通过蒙特卡洛仿真，随机注入扰动来测试。
• 警员负荷 ：各警车/警员的巡逻时长、处理案件数是否均衡。

在论文中，应使用表格对比不同参数下方案的各项指标，并给出雷达图等可视化图表进行综合展示。

5.2 模型的潜在扩展方向

这道经典赛题有丰富的扩展空间，体现了从学术到实战的演进：

• 多类型警车 ：引入巡逻车、处警车、特种车辆等，不同车辆速度、功能、管辖范围不同。
• 多目标优化 ：正式使用多目标优化算法（如NSGA-II）来求解，得到一组Pareto最优解（即响应时间、覆盖率、成本无法同时改进的解集），供决策者根据偏好选择。
• 集成实时交通信息 ：将动态交通流量纳入模型，警车调度时选择的是实时最快的路径，而非静态最短路径。
• 与预测性警务结合 ：利用机器学习模型预测短期未来的案发热点，并据此动态调整巡逻重心，实现“情报主导巡逻”。

5.3 从竞赛到现实的差距与思考

最后，必须清醒认识到，竞赛模型是对现实的极度简化。真实世界的警力调度还要考虑无数复杂因素：警员交接班、加油站位置、单行道、左转限制、学校区域、大型活动安保、跨区域协作、以及最重要的—— 人的经验和直觉 。数学模型提供的永远是一个 辅助决策的参考 ，而非不容置疑的“最优解”。它的价值在于，能够处理人脑难以驾驭的海量数据，在错综复杂的约束中找到那些可能被忽略的、反直觉的较优方案，并为决策提供量化的依据和不同场景下的模拟推演。

参加这类竞赛最大的收获，就是学会了如何用结构化的思维去拆解一个庞杂的现实问题，如何用数学语言描述它，并最终用计算工具去探索解决方案。这个过程里对 问题定义、模型假设、算法实现和结果分析 的完整训练，其价值远超题目本身。直到今天，当我面对其他领域的资源调度和路径优化问题时，当年在“警车配置”赛题中学到的这套方法论，依然是最趁手的工具之一。