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

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

中國(guó)輪椅使用者聯(lián)合會(huì)發(fā)布的數(shù)據(jù)顯示，目前我國(guó)輪椅使用者總數(shù)超過(guò)8500 萬(wàn)，其中肢體輪椅使用者數(shù)近2500萬(wàn)，未來(lái)輪椅使用者數(shù)量將繼續(xù)增長(zhǎng)[1]。在城市中，輪椅使用者等行動(dòng)不便人群日常出行遭遇“殘疾路”，面對(duì)的是復(fù)雜的路況以及樓梯臺(tái)階。目前社會(huì)對(duì)于輪椅使用者的出行主要停留在完善輪椅使用者出行設(shè)施方面，增加無(wú)障礙廁所、提供無(wú)障礙通道等。對(duì)于輪椅使用者出行導(dǎo)航方面，我國(guó)現(xiàn)有的導(dǎo)航APP主要針對(duì)的是能獨(dú)立出行的普通人士，且地圖導(dǎo)航APP 沒(méi)有針對(duì)輪椅使用者出行的優(yōu)化，更沒(méi)有開(kāi)發(fā)針對(duì)輪椅使用者出行的APP 或者小程序[2]。

對(duì)于輪椅出行者的出行問(wèn)題可以簡(jiǎn)化為點(diǎn)與點(diǎn)之間的連接，是一個(gè)自頂而下的選擇，符合貪心算法的特點(diǎn)。輪椅出行者的出行問(wèn)題的優(yōu)化測(cè)度需要進(jìn)行一定的改變，結(jié)合實(shí)際情況的分析，根據(jù)輪椅使用者出行的特點(diǎn)，對(duì)貪心算法啟發(fā)性規(guī)則進(jìn)行修改，最終得出一種基于貪心算法的改進(jìn)輪椅使用者出行的方法。輪椅使用者出行路線的優(yōu)化體現(xiàn)在，要結(jié)合使用者的出行需要、行程時(shí)間安排、體力狀況等，來(lái)生成一條最適合使用者的最佳出行線路。該算法把輪椅使用者的需求、身體狀況及其心理作為約束條件，最終找出一條滿足輪椅使用者需求的最佳出行路線。

1 基于貪心算法的路徑規(guī)劃

對(duì)于輪椅使用者出行問(wèn)題，Dijkstra 算法[3]是一種盲目的搜尋，雖然可以得出結(jié)果但是對(duì)于特定限制的問(wèn)題，得出的結(jié)論并不適用；對(duì)于A*算法[4]，雖然能根據(jù)啟發(fā)規(guī)則得到滿足要求的結(jié)論，但是無(wú)法滿足輪椅使用者出行的需求。

在介紹算法之前，先對(duì)一些相關(guān)名詞進(jìn)行解釋?zhuān)?/p>

補(bǔ)給點(diǎn)：每一個(gè)區(qū)域的控制點(diǎn)以及無(wú)障礙設(shè)施設(shè)置的地理位置；

友好度：對(duì)于每一個(gè)補(bǔ)給點(diǎn)，結(jié)合道路條件、無(wú)障礙設(shè)施的合理性和安全性等多方面因素評(píng)價(jià)得出的總體評(píng)分。

對(duì)于上述的問(wèn)題，基于貪心算法的路徑規(guī)劃采用貪心算法對(duì)單位距離范圍內(nèi)友好度收益最大的補(bǔ)給點(diǎn)進(jìn)行選取，作為無(wú)障礙出行的補(bǔ)給點(diǎn)集合，根據(jù)選取的補(bǔ)給點(diǎn)集合創(chuàng)造相對(duì)應(yīng)的鄰接矩陣；根據(jù)設(shè)置的限定條件，逐一搜索集合內(nèi)單位距離友好度收益最大且滿足要求的補(bǔ)給點(diǎn)，算法停止最終條件為下一補(bǔ)給點(diǎn)為最終目的地，則終止算法并輸出結(jié)果。

1.1 輪椅使用者的出行需求

輪椅使用者出行中需要兼顧時(shí)間和距離的平衡，也需要考慮輪椅使用者的身體狀況和出行存在的問(wèn)題，輪椅使用者的出行主要存在以下幾個(gè)問(wèn)題[5]：

（1）輪椅使用者的自身身體狀況不佳；

（2）輪椅使用者的出行不只是一個(gè)簡(jiǎn)單的點(diǎn)對(duì)點(diǎn)的三維移動(dòng)，而是一種對(duì)著空間有更加苛刻要求和諸多限制的移動(dòng)；

（3）輪椅使用者的出行心理與正常人存在差異，當(dāng)出行需求受阻，他會(huì)產(chǎn)生自卑心理；

（4）輪椅使用者對(duì)出行的安全更加看重。

通過(guò)對(duì)上述問(wèn)題的分析，可以得出輪椅使用者的需求：身體狀況不同、出行距離和時(shí)間盡量短、安全因素的考慮等。

1.2 數(shù)學(xué)模型的建立

根據(jù)輪椅使用者的出行需求，將身體狀況、心理因素、出行距離和安全性作為約束條件[6]，對(duì)模型作出以下假設(shè)：

（1）起終點(diǎn)之間距離在一定范圍之內(nèi)；

（2）輪椅使用者在進(jìn)行垂直空間變換時(shí)須借助無(wú)障礙設(shè)施；

（3）每個(gè)補(bǔ)給點(diǎn)最多被使用一次；

（4）各補(bǔ)給點(diǎn)間的位置距離可獲??；

（5）每個(gè)補(bǔ)給點(diǎn)根據(jù)道路及設(shè)施有一個(gè)等級(jí)評(píng)分。

根據(jù)上述假設(shè)建立如下的函數(shù)模型：

在上述的數(shù)學(xué)模型中，包涵了目標(biāo)函數(shù)和約束條件，每個(gè)參數(shù)的代表含義如下：

1.3 路徑算法的描述

對(duì)于貪心算法最主要的是找出最優(yōu)的量度標(biāo)準(zhǔn)，對(duì)于大眾一般的出行量度標(biāo)準(zhǔn)是距離和時(shí)間，但是對(duì)于輪椅使用者出行的量度標(biāo)準(zhǔn)不僅僅是時(shí)間和距離，還有更多其他的因素需要考慮，對(duì)一般的出行量度標(biāo)準(zhǔn)做了一定的修改，使其更加符合輪椅使用者出行。

對(duì)算法的介紹如下：

（1）初始化備選庫(kù)、已選庫(kù)和收益庫(kù)。其中備選庫(kù)用來(lái)存放待考察的補(bǔ)給點(diǎn)，已選庫(kù)存放符合要求的補(bǔ)給點(diǎn)，收益庫(kù)用來(lái)存放各個(gè)補(bǔ)給點(diǎn)的友好度收益。

（2）把補(bǔ)給點(diǎn)0 加入已選庫(kù)，并將補(bǔ)給點(diǎn)0 的鄰接點(diǎn)加入備選庫(kù)。

（3）判斷加入的補(bǔ)給點(diǎn)是否為目標(biāo)點(diǎn)，如果是則直接輸出已選庫(kù)；否則向下執(zhí)行。

（4）計(jì)算各個(gè)補(bǔ)給點(diǎn)的收益。

計(jì)算每個(gè)補(bǔ)給點(diǎn)的友好度，具體公式如下：

每個(gè)補(bǔ)給點(diǎn)的友好度收益計(jì)算公式為：

（5）比較備選庫(kù)里面每個(gè)補(bǔ)給點(diǎn)的友好度收益，將友好度收益最大的補(bǔ)給點(diǎn)加入已選庫(kù),并初始化備選庫(kù)和收益庫(kù)。

（6）重復(fù)步驟（3），繼續(xù)計(jì)算直到補(bǔ)給點(diǎn)到達(dá)目標(biāo)點(diǎn)才結(jié)束。最后輸出已選庫(kù)的結(jié)果。

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

2 程序界面介紹

該程序的搭建接入高德地圖API，使用部分高德地圖的原始數(shù)據(jù)進(jìn)行程序框架的搭建，在此基礎(chǔ)上對(duì)頁(yè)面進(jìn)行調(diào)整[7]。加入Weather 天氣查詢(xún)服務(wù)，根據(jù)城市名稱(chēng)或區(qū)域編碼返回城市4 天的天氣預(yù)報(bào)信息。搜索服務(wù)采用Autocomplete 插件，根據(jù)輸入關(guān)鍵字提示匹配信息，可將Poi 類(lèi)型和城市作為輸入提示的限制條件，并增設(shè)無(wú)障礙導(dǎo)航按鈕。反饋報(bào)警界面采用InfoWindow 類(lèi)信息窗體，在網(wǎng)頁(yè)上彈出提醒窗體和一個(gè)信息展示窗體。通過(guò)增設(shè)三個(gè)功能，分別為天氣播報(bào)界面、無(wú)障礙路線查詢(xún)界面和反饋報(bào)警界面，使其具備輪椅使用者出行導(dǎo)航程序的使用特色。

3 案例對(duì)比分析

基于高德地圖JS API 搭建web 前端，將本算法加入到該前端，使其作為程序運(yùn)行，在假設(shè)條件下將本算法程序與高德地圖進(jìn)行對(duì)比。假設(shè)現(xiàn)有一個(gè)輪椅使用者初次到四川大學(xué)華西醫(yī)院治療，準(zhǔn)備從四川大學(xué)華西醫(yī)院（東門(mén)）到華西壩（地鐵站）乘坐地鐵回家，但不熟悉周邊路徑情況。

根據(jù)實(shí)際情況觀測(cè)，國(guó)學(xué)巷、小天竺街視界良好但路面不平，校西路路面平整且道路寬廣，華西壩地鐵站A 出入口配有一個(gè)行人通道和一個(gè)方向向上的自動(dòng)扶梯，華西壩地鐵站B 出入口配有一個(gè)行人通道和一個(gè)無(wú)障礙電梯。高德地圖導(dǎo)航選擇的國(guó)學(xué)巷、小天竺街以及華西壩地鐵站A 出入口作為規(guī)劃路線，此路線不但道路條件不良，而且沒(méi)有充分利用無(wú)障礙設(shè)施，對(duì)于輪椅使用者十分不方便且需要他人幫助才能順利到達(dá)終點(diǎn)。本算法程序則充分考慮輪椅使用者的各個(gè)方面，選擇校西路、華西壩地鐵站B 出入口作為補(bǔ)給點(diǎn)，將道路條件良好、無(wú)障礙設(shè)施齊全的道路選作規(guī)劃路線。

通過(guò)兩種導(dǎo)航路線對(duì)比，發(fā)現(xiàn)本算法基于友好度的規(guī)劃導(dǎo)航路線更適合輪椅使用者。相較于其他導(dǎo)航算法有以下兩個(gè)優(yōu)點(diǎn)：

（1）本算法不同于其它步行導(dǎo)航算法，不再以時(shí)間最短或者費(fèi)用最低為目標(biāo)，而是綜合考慮輪椅使用者的各方面情況：身體狀況、安全需求、無(wú)障礙設(shè)施、出行舒適度、出行便捷性等等，將考慮因素作為部分約束條件，合理利用無(wú)障礙設(shè)施，選擇一條適合輪椅使用者出行的最優(yōu)路線。

（2）本算法將友好度作為導(dǎo)航路線選擇標(biāo)準(zhǔn)之一，能夠讓輪椅使用者獨(dú)立出行程度達(dá)到最優(yōu)化，增強(qiáng)輪椅使用者獨(dú)立出行的能力，使他們更加積極地面對(duì)社會(huì)，讓他們不再認(rèn)為自己肢體的缺陷是一種累贅或者負(fù)擔(dān)，積極改變他們內(nèi)心深處的負(fù)面想法。

圖1 :路徑算法流程圖

4 結(jié)論

對(duì)輪椅使用者而言，無(wú)障礙設(shè)施是參與社會(huì)生活的重要保證，使其更加便利地使用設(shè)施就是錦上添花。此算法的應(yīng)用勢(shì)必會(huì)使得輪椅使用者出行越來(lái)越便利化。對(duì)輪椅使用者的重視，是一座城市的現(xiàn)代化水平和文明程度的具體體現(xiàn)[8]。

對(duì)于輪椅使用者出行導(dǎo)航的研究[9]，未來(lái)將繼續(xù)增強(qiáng)導(dǎo)航安全性并加入公交導(dǎo)航，讓他們?cè)诔鲂蟹绞降倪x擇上更加多元化，讓他們也能夠獨(dú)立出行與遠(yuǎn)距離出行。憑借著更加便捷和更加人性化的輪椅使用者導(dǎo)航APP，進(jìn)而提高他們的生活幸福感和存在感。隨著互聯(lián)網(wǎng)服務(wù)高速發(fā)展，輪椅使用者導(dǎo)航服務(wù)肯定有非常大的應(yīng)用和發(fā)展空間。