基于最大覆盖模型的救护车车辆调度问题研究

黄美林 冯 倩 王 雷 蒋 伟

（重庆交通大学 经济与管理学院，重庆 400074）

1 问题描述与模型的建立

时间是衡量救护车出车效率的一个重要指标，现伊萨卡市要求将响应时间控制在6分钟内，并计算出需要的救护车数量以实现此目标，除此之外救护车的位置需明确。若在伊萨卡市难以在6分钟内到达的地区，可以增加最坏情况下的响应时间，以提高救护车的效用。

首先根据伊萨卡市地图特点，将地图建立3×3网格，分块化处理并为其编号为N=1…9，将复杂的城市区域简单化，利用救护车行驶模型对伊萨卡市现有的4个救护车站点进行验证是否满足6分钟以内到达指定地区的限制条件。伊萨卡市已知有4个救护车站点，求出各救护车到呼叫点的行驶距离dij。救护车到达呼叫点的时间t应在6分钟以内，将时间转化为距离s，假设该救护车的时速v为55km/h(0.57miles/min)。每个呼叫点只需一辆救护车响应。根据以上约束以及目标函数为最短路建立模型：

2 车辆调度优化模型

首先根据伊萨卡市的地图，对伊萨卡市进行模块化，再根据救护车到达呼叫点的时间约束，利用最大覆盖模型，寻找到最有数量的救护车站点数量以及位置。以最少的救护车站点去满足所有呼叫需求点，所以目标函数为路径最短。每个呼叫需求点i只有一辆救护车响应。每辆救护车的响应时间必须在6分钟以内，其可转化为行驶距离。

人们在遇到紧急情况首先会想到呼叫救护车急救，而影响呼叫量有很多因素，我们将老年人的呼叫量、突发疾病的呼叫量、经济收入中等偏上人群的呼叫量、意外事故引起的呼叫量及护理机构引起的呼叫量作为影响因素。通过相关性分析，检验这些影响因素对呼叫量的相关程度，并对相关程度进行重要程度D计算，从而将影响因素定量化。

其中，D为影响因素的重要程度，dlevel为等级数，dtotal为总等级数。

将重要程度进行归一化处理。根据伊萨卡市一年的呼叫数，计算平均每天的呼叫数。根据归一化结果以及平均每天呼叫数计算各救护车站点里的救护车数量。由于每个救护车站点的救护车数量有限，若呼叫需求小于该站点救护车的数量，则该站点的车辆满足调度。若呼叫需求过多，该站点的救护车全部出动，此时满足不了需求，则需要考虑从其他站点调配救护车前往救援，但仍需要满足在6分钟内到达需求点。基于救护车行驶距离最短模型求解的站点，仍以救护车行驶距离最短为目标函数。所有站点的救护车行驶的距离均要满足在6分钟行驶的距离内。每个呼叫点仅有一辆救护车响应。根据以上约束建立车辆调度模型：

其中，minZ′=∑x j dij+∑x k dik+∑xl dil为目标函数，其表示救护车行驶距离最短，x j,x k,xl均为0-1变量；x j⋅d ij≤s，x k⋅dik≤s，xl⋅d il≤s表示所有站点的救护车行驶的距离均要满足在6分钟行驶的距离内；表示每个呼叫点仅有一辆救护车响应。

3 结果分析

利用MATLAB进行求解救护车行驶距离模型，所有约束满足。此时，通过减少站点数量来寻找最优站点数量，减少成本。经过分析可以发现，一个站点是不可能在6分钟以内到达所有可能的呼叫点，所以我们将站点减少至2和3，带入模型求解。由于对角线为最长距离，分别对两条对角线的距离进行计算，得到两条对角线的距离为8.17英里和8.21英里，救护车需要在6分钟内到达呼叫点，则该最大距离为3.42英里，因此在该城市内2个救护车急救站点不能满足需求。当建立3各救护车站点时，每个救护车急救站点相邻区域的距离均在3.42英里内，因此建设3个救护车急救站点满足该城市6分钟内响应。

运用贪婪算法求解最大覆盖模型，求的结果为只需要在1、7、10区域设置3个救护车站点就能够覆盖伊萨卡市所有可能的需求呼叫点，根据影响因素计算各救护车站点的救护车数量为1区域5辆，7区域9辆，10区域6辆，利用遗传算法求解车辆调度模型，根据计算结果可以得到，有一部分区域只有特定的一个站点能到达而另一部分可由两个站点到达。因此，为保证尽可能少的站点和救护车，站点应优先满足第一部分区域的覆盖即区域1区域-6、区域10区域-9、区域10-区域11、区域7-区域14区域-4,、区域7-区域15区域-16-区域5 。在此基础上，区域1的站点的4条分别可到达区域13、3、14、6的备用路线以及区域10的站点能分别到达5条区域8、12、13、15、16的路线可用作在呼叫量大于救护车数量时临时派遣前往。

4 总结

本文首先根据已知的救护车站点位置以及救护车行驶距离模型检验是否满足响应时间在6分钟以内的约束，结果表明满足。经过分析可知，当救护站点为1时是不可能满足响应时间在6分钟以内，所以分别检验救护站点为2和3时的响应情况，当救护站点为3时满足救护车响应时间在6分钟以内。

利用最大覆盖模型对伊萨卡市呼叫需求点进行更加详细的区域划分，并根据影响因素计算各救护车站点的救护车数辆，建立车辆调度模型，当该区域救护车全部出车时，从其他区域调车的情况。