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

周泳江 羅睿 易磊 楊詩霞

摘 要 隨著社會老齡化，以殘障人士為典型的無障礙出行愈發(fā)受到關(guān)注。創(chuàng)建無障礙出行環(huán)境，既是社會文明進(jìn)步的重要標(biāo)志，也是城市功能和城市品質(zhì)提升的必然要求，同時也是我國進(jìn)入老齡化社會發(fā)展的現(xiàn)實(shí)需要。為了順應(yīng)時代潮流，應(yīng)在現(xiàn)有的地圖導(dǎo)航上做出改進(jìn)，在原有高德地圖的路線規(guī)劃算法上增添了對出行友好度的定義，讓出行路線對輪椅使用者而言更加輕松。

關(guān)鍵詞 輪椅使用者 出行導(dǎo)航 無障礙 公共交通

中圖分類號：TN96 文獻(xiàn)標(biāo)識碼：A 文章編號：1007-0745（2020）02-0001-03

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

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

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

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

在介紹算法之前，先對一些相關(guān)名詞進(jìn)行解釋：

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

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

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

1.1 輪椅使用者的出行需求

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1.3 路徑算法的描述

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

對算法的介紹如下：

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

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

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

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

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

是設(shè)施服務(wù)的友好度，包括道路平整度、設(shè)施合理性和道路剩余價值三部分組成。

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

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

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

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

2 程序界面介紹

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

3 案例對比分析

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

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

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

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

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

4 結(jié)論

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

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

參考文獻(xiàn)：

[1] 呂世明.我國無障礙環(huán)境建設(shè)現(xiàn)狀及發(fā)展思考[J].殘疾人研究.2013（02）：3-8.

[2] 洪澤.助老助殘輪椅室外自主導(dǎo)航行為設(shè)計與融合方法研究[D].揚(yáng)州大學(xué)，2018.

[3] 劉建美，馬壽峰，馬帥奇.基于改進(jìn)的Dijkstra算法的動態(tài)最短路計算方法[J].系統(tǒng)工程理論與實(shí)踐，2011，31（06）：1153-1157.

[4] Abdulrasool D，Sabra S.Mobile-embedded smart guide for the blind[C].Dijon，F(xiàn)rance： Sprinr? Verbg， 2011：571-578.

[5] 秦海春.智能輪椅自主導(dǎo)航行進(jìn)控制技術(shù)研究[D].合肥工業(yè)大學(xué)，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] 倪琴，周國祥.基于無障礙設(shè)計的Android手機(jī)導(dǎo)航方法[J].合肥工業(yè)大學(xué)學(xué)報（自然科學(xué)版），2015，38（04）：490-494.

[8] 郝帥. 面向輪椅人士的基于可達(dá)性的出行規(guī)劃系統(tǒng)[D].電子科技大學(xué)，2016.

[9] 聶雷剛，李詠梅，余元輝.基于聚類分析算法的智能旅游規(guī)劃[J].電腦開發(fā)與應(yīng)用，2012，25（02）：28-30.

西華大學(xué) 汽車與交通學(xué)院，四川 成都