基于贪心算法的轮椅使用者路径规划方法

周泳江 罗睿 易磊 杨诗霞

摘 要 随着社会老龄化，以残障人士为典型的无障碍出行愈发受到关注。创建无障碍出行环境，既是社会文明进步的重要标志，也是城市功能和城市品质提升的必然要求，同时也是我国进入老龄化社会发展的现实需要。为了顺应时代潮流，应在现有的地图导航上做出改进，在原有高德地图的路线规划算法上增添了对出行友好度的定义，让出行路线对轮椅使用者而言更加轻松。

关键词 轮椅使用者 出行导航 无障碍 公共交通

中图分类号：TN96 文献标识码：A 文章编号：1007-0745（2020）02-0001-03

中国轮椅使用者联合会发布的数据显示，目前我国轮椅使用者总数超过8500万，其中肢体轮椅使用者数近2500万，未来轮椅使用者数量将继续增长[1]。在城市中，轮椅使用者等行动不便人群日常出行遭遇“残疾路”，面对的是复杂的路况以及楼梯台阶。目前社会对于轮椅使用者的出行主要停留在完善轮椅使用者出行设施方面，增加无障碍厕所、提供无障碍通道等。对于轮椅使用者出行导航方面，我国现有的导航APP主要针对的是能独立出行的普通人士，且地图导航APP没有针对轮椅使用者出行的优化，更没有开发针对轮椅使用者出行的APP或者小程序[2]。

对于轮椅出行者的出行问题可以简化为点与点之间的连接，是一个自顶而下的选择，符合贪心算法的特点。轮椅出行者的出行问题的优化测度需要进行一定的改变，结合实际情况的分析，根据轮椅使用者出行的特点，对贪心算法启发性规则进行修改，最终得出一种基于贪心算法的改进轮椅使用者出行的方法。轮椅使用者出行路线的优化体现在，要结合使用者的出行需要、行程时间安排、体力状况等，来生成一条最适合使用者的最佳出行线路。该算法把轮椅使用者的需求、身体状况及其心理作为约束条件，最终找出一条满足轮椅使用者需求的最佳出行路线。

1 基于贪心算法的路径规划

对于轮椅使用者出行问题，Dijkstra 算法[3]是一种盲目的搜寻，虽然可以得出结果但是对于特定限制的问题，得出的结论并不适用;对于A*算法[4]，虽然能根据启发规则得到满足要求的结论，但是无法满足轮椅使用者出行的需求。

在介绍算法之前，先对一些相关名词进行解释：

补给点：每一个区域的控制点以及无障碍设施设置的地理位置;

友好度：对于每一个补给点，结合道路条件、无障碍设施的合理性和安全性等多方面因素评价得出的总体评分。

对于上述的问题，基于贪心算法的路径规划采用贪心算法对单位距离范围内友好度收益最大的补给点进行选取，作为无障碍出行的补给点集合，根据选取的补给点集合创造相对应的邻接矩阵;根据设置的限定条件，逐一搜索集合内单位距离友好度收益最大且满足要求的补给点，算法停止最终条件为下一补给点为最终目的地，则终止算法并输出结果。

1.1 轮椅使用者的出行需求

轮椅使用者出行中需要兼顾时间和距离的平衡，也需要考虑轮椅使用者的身体状况和出行存在的问题，轮椅使用者的出行主要存在以下几个问题[5]：

（1）轮椅使用者的自身身体状况不佳;

（2）轮椅使用者的出行不只是一个简单的点对点的三维移动，而是一种对着空间有更加苛刻要求和诸多限制的移动;

（3）轮椅使用者的出行心理与正常人存在差异，当出行需求受阻，他会产生自卑心理;

（4）轮椅使用者对出行的安全更加看重。

通过对上述问题的分析，可以得出轮椅使用者的需求：身体状况不同、出行距离和时间尽量短、安全因素的考虑等。

1.2 数学模型的建立

根据轮椅使用者的出行需求，将身体状况、心理因素、出行距离和安全性作为约束条件[6]，对模型作出以下假设：

（1）起终点之间距离在一定范围之内;

（2）轮椅使用者在进行垂直空间变换时须借助无障碍设施;

（3）每个补给点最多被使用一次;

（4）各补给点间的位置距离可获取;

（5）每个补给点根据道路及设施有一个等级评分。

根据上述假设建立如下的函数模型：

在上述的数学模型中，包涵了目标函数和约束条件，每个参数的代表含义如下：

1.3 路径算法的描述

对于贪心算法最主要的是找出最优的量度标准，对于大众一般的出行量度标准是距离和时间，但是对于轮椅使用者出行的量度标准不仅仅是时间和距离，还有更多其他的因素需要考虑，对一般的出行量度标准做了一定的修改，使其更加符合轮椅使用者出行。

对算法的介绍如下：

（1）初始化备选库、已选库和收益库。其中备选库用来存放待考察的补给点，已选库存放符合要求的补给点，收益库用来存放各个补给点的友好度收益。

（2）把补给点0加入已选库，并将补给点0的邻接点加入备选库。

（3）判断加入的补给点是否为目标点，如果是则直接输出已选库;否则向下执行。

（4）计算各个补给点的收益。

计算每个补给点的友好度，具体公式如下：

是设施服务的友好度，包括道路平整度、设施合理性和道路剩余价值三部分组成。

每个补给点的友好度收益计算公式为：

（5）比较备选库里面每个补给点的友好度收益，将友好度收益最大的补给点加入已选库，并初始化备选库和收益库。

（6）重复步骤（3），继续计算直到补给点到达目标点才结束。最后输出已选库的结果。

具体的算法流程圖，如下图1所示：

2 程序界面介绍

该程序的搭建接入高德地图API，使用部分高德地图的原始数据进行程序框架的搭建，在此基础上对页面进行调整[7]。加入Weather天气查询服务，根据城市名称或区域编码返回城市4天的天气预报信息。搜索服务采用Autocomplete插件，根据输入关键字提示匹配信息，可将Poi类型和城市作为输入提示的限制条件，并增设无障碍导航按钮。反馈报警界面采用InfoWindow类信息窗体，在网页上弹出提醒窗体和一个信息展示窗体。通过增设三个功能，分别为天气播报界面、无障碍路线查询界面和反馈报警界面，使其具备轮椅使用者出行导航程序的使用特色。

3 案例对比分析

基于高德地图JS API搭建web前端，将本算法加入到该前端，使其作为程序运行，在假设条件下将本算法程序与高德地图进行对比。假设现有一个轮椅使用者初次到四川大学华西医院治疗，准备从四川大学华西医院（东门）到华西坝（地铁站）乘坐地铁回家，但不熟悉周边路径情况。

根据实际情况观测，国学巷、小天竺街视界良好但路面不平，校西路路面平整且道路宽广，华西坝地铁站A出入口配有一个行人通道和一个方向向上的自动扶梯，华西坝地铁站B出入口配有一个行人通道和一个无障碍电梯。高德地图导航选择的国学巷、小天竺街以及华西坝地铁站A出入口作为规划路线，此路线不但道路条件不良，而且没有充分利用无障碍设施，对于轮椅使用者十分不方便且需要他人帮助才能顺利到达终点。本算法程序则充分考虑轮椅使用者的各个方面，选择校西路、华西坝地铁站B出入口作为补给点，将道路条件良好、无障碍设施齐全的道路选作规划路线。

通过两种导航路线对比，发现本算法基于友好度的规划导航路线更适合轮椅使用者。相较于其他导航算法有以下两个优点：

（1）本算法不同于其它步行导航算法，不再以时间最短或者费用最低为目标，而是综合考虑轮椅使用者的各方面情况：身体状况、安全需求、无障碍设施、出行舒适度、出行便捷性等等，将考虑因素作为部分约束条件，合理利用无障碍设施，选择一条适合轮椅使用者出行的最优路线。

（2）本算法将友好度作为导航路线选择标准之一，能够让轮椅使用者独立出行程度达到最优化，增强轮椅使用者独立出行的能力，使他们更加积极地面对社会，让他们不再认为自己肢体的缺陷是一种累赘或者负担，积极改变他们内心深处的负面想法。

4 结论

对轮椅使用者而言，无障碍设施是参与社会生活的重要保证，使其更加便利地使用设施就是锦上添花。此算法的应用势必会使得轮椅使用者出行越来越便利化。对轮椅使用者的重视，是一座城市的现代化水平和文明程度的具体体现[8]。

对于轮椅使用者出行导航的研究[9]，未来将继续增强导航安全性并加入公交导航，让他们在出行方式的选择上更加多元化，让他们也能够独立出行与远距离出行。凭借着更加便捷和更加人性化的轮椅使用者导航APP，进而提高他们的生活幸福感和存在感。随着互联网服务高速发展，轮椅使用者导航服务肯定有非常大的应用和发展空间。

参考文献：

[1] 吕世明.我国无障碍环境建设现状及发展思考[J].残疾人研究.2013（02）：3-8.

[2] 洪泽.助老助残轮椅室外自主导航行为设计与融合方法研究[D].扬州大学，2018.

[3] 刘建美，马寿峰，马帅奇.基于改进的Dijkstra算法的动态最短路计算方法[J].系统工程理论与实践，2011，31（06）：1153-1157.

[4] Abdulrasool D，Sabra S.Mobile-embedded smart guide for the blind[C].Dijon，France： Sprinr  Verbg， 2011：571-578.

[5] 秦海春.智能轮椅自主导航行进控制技术研究[D].合肥工业大学，2014.

[6] Kenteris M，Gavalas D，Pantziou G，et al. Near-optimal persomlized daily itineraries for a mobile  tourist guide[C].Riccione，Italy： Institute of Electrical and Electronics Eiigmeers Inc，2010.

[7] 倪琴，周國祥.基于无障碍设计的Android手机导航方法[J].合肥工业大学学报（自然科学版），2015，38（04）：490-494.

[8] 郝帅. 面向轮椅人士的基于可达性的出行规划系统[D].电子科技大学，2016.

[9] 聂雷刚，李咏梅，余元辉.基于聚类分析算法的智能旅游规划[J].电脑开发与应用，2012，25（02）：28-30.

西华大学 汽车与交通学院，四川 成都