基于貪心算法的輪椅使用者路徑規劃方法

(西華大學 汽車與交通學院,四川 成都 610039)

中國輪椅使用者聯合會發布的數據顯示，目前我國輪椅使用者總數超過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）本算法將友好度作為導航路線選擇標準之一，能夠讓輪椅使用者獨立出行程度達到最優化，增強輪椅使用者獨立出行的能力，使他們更加積極地面對社會，讓他們不再認為自己肢體的缺陷是一種累贅或者負擔，積極改變他們內心深處的負面想法。

圖1 :路徑算法流程圖

4 結論

對輪椅使用者而言，無障礙設施是參與社會生活的重要保證，使其更加便利地使用設施就是錦上添花。此算法的應用勢必會使得輪椅使用者出行越來越便利化。對輪椅使用者的重視，是一座城市的現代化水平和文明程度的具體體現[8]。

對于輪椅使用者出行導航的研究[9]，未來將繼續增強導航安全性并加入公交導航，讓他們在出行方式的選擇上更加多元化，讓他們也能夠獨立出行與遠距離出行。憑借著更加便捷和更加人性化的輪椅使用者導航APP，進而提高他們的生活幸福感和存在感。隨著互聯網服務高速發展，輪椅使用者導航服務肯定有非常大的應用和發展空間。