基于貪心算法的常態(tài)化防疫交通路線(xiàn)智能推薦系統(tǒng)

孔欽，劉晨，顧永鑫

（1.南京信息職業(yè)技術(shù)學(xué)院 人工智能學(xué)院，江蘇 南京 210023；2.南京大學(xué) 軟件學(xué)院，江蘇 南京 210093；3.南京大學(xué)金陵學(xué)院信息科學(xué)與工程學(xué)院，江蘇 南京 210089）

0 引 言

自新冠疫情發(fā)生以來(lái)，“健康碼”“行程碼”“核酸報(bào)告”等通行物逐漸成為人們?nèi)粘３鲂斜貍?。這些隨社會(huì)發(fā)展所誕生的互聯(lián)網(wǎng)產(chǎn)品正在逐步地改變著人們的生活方式?！按髷?shù)據(jù)”“人工智能”等計(jì)算機(jī)技術(shù)在疫情防控中的成功應(yīng)用，是國(guó)家能夠控制疫情的重要原因之一。

每年春節(jié)期間，社會(huì)在應(yīng)對(duì)龐大人口的“春節(jié)效應(yīng)”的同時(shí)，地方政府也面對(duì)著數(shù)字化轉(zhuǎn)型所帶來(lái)巨大挑戰(zhàn)。在符合我國(guó)巨大“人口移動(dòng)”特點(diǎn)的春運(yùn)時(shí)期，我國(guó)的交通管控、疫情防控面臨著前所未有的壓力。隨著整體智能化汽車(chē)時(shí)代的到來(lái)，人們對(duì)于駕駛行程的安全性要求又提高到一個(gè)新的層次。目前行車(chē)搭載的“路線(xiàn)推薦”功能，雖然導(dǎo)航功能已經(jīng)相當(dāng)精確和完備，且提供較好的人機(jī)交互性體檢。但針對(duì)疫情環(huán)境下的“安全性”卻沒(méi)有得到很好的保障，甚至出現(xiàn)推薦路線(xiàn)中包含高風(fēng)險(xiǎn)地區(qū)經(jīng)過(guò)的現(xiàn)象，這對(duì)于沒(méi)有及時(shí)關(guān)注到疫情城市信息的司機(jī)來(lái)講，無(wú)疑會(huì)增加行車(chē)風(fēng)險(xiǎn)，政府管控疫情的難度也會(huì)大大增加。

在此前提下，一個(gè)基于實(shí)時(shí)城市疫情和基本路況信息的智能化路線(xiàn)推薦系統(tǒng)應(yīng)運(yùn)而生。該系統(tǒng)依靠國(guó)家城市發(fā)布的實(shí)時(shí)城市疫情信息作為數(shù)據(jù)源，借助大數(shù)據(jù)平臺(tái)收集實(shí)時(shí)數(shù)據(jù)，結(jié)合先進(jìn)的路線(xiàn)規(guī)劃算法，實(shí)現(xiàn)疫情期間人們的日常出行路線(xiàn)推薦。平臺(tái)實(shí)時(shí)提供最為安全的數(shù)據(jù)分析從而實(shí)現(xiàn)宏觀(guān)的交通管控，出行的人們可以根據(jù)系統(tǒng)推薦出的路線(xiàn)，選擇合適、安全、便捷的出行路線(xiàn)。

1 研究背景

為了滿(mǎn)足用戶(hù)的出行需求，用戶(hù)可以根據(jù)導(dǎo)航路線(xiàn)的指引，從出發(fā)地到達(dá)目的地。服務(wù)器獲取道路的相關(guān)情況（如：事故的發(fā)生地點(diǎn)，當(dāng)前的擁堵路段），根據(jù)道路的相關(guān)情況檢索導(dǎo)航路線(xiàn)，將最符合用戶(hù)需求的路線(xiàn)提供給用戶(hù)，使得用戶(hù)出行時(shí)，可以有效地避免擁堵。

導(dǎo)航一般分為兩類(lèi)：（1）基于數(shù)字地圖的導(dǎo)航；（2）基于軌跡數(shù)據(jù)的導(dǎo)航?；跀?shù)字地圖的導(dǎo)航是最為傳統(tǒng)的導(dǎo)航方式，其原理是基于最短路徑或者最優(yōu)路徑的目標(biāo)，應(yīng)用動(dòng)態(tài)規(guī)劃原理計(jì)算路徑，其中最常使用到的是以Dijkstra 算法為代表的貪心算法。這種算法的缺點(diǎn)是當(dāng)路網(wǎng)比較大、路線(xiàn)圖分支比較多時(shí)，使用該算法會(huì)大大浪費(fèi)時(shí)間。因此貪心算法適合圖網(wǎng)不是特別復(fù)雜的情況。另一種基于軌跡數(shù)據(jù)的導(dǎo)航大多把注意力放在軌跡挖掘上，更多的是利用機(jī)器學(xué)習(xí)的方法，對(duì)人們的出行數(shù)據(jù)進(jìn)行挖掘、分析，再綜合天氣、路況等其他外界因素，形成一個(gè)最終的結(jié)果，找到與用戶(hù)行駛更加匹配、合適的出行路線(xiàn)。

但是，上述兩種方法中提供的導(dǎo)航路線(xiàn)只單純考慮了道路的相關(guān)情況，沒(méi)有結(jié)合近幾年不斷波動(dòng)、實(shí)時(shí)變化的疫情發(fā)展情況。本系統(tǒng)在對(duì)比以上兩種方法的基礎(chǔ)上，依據(jù)目前省市之間的交通通行節(jié)點(diǎn)，參考“高德地圖”數(shù)據(jù)庫(kù)里的基礎(chǔ)數(shù)據(jù)，利用貪心算法，將實(shí)時(shí)疫情信息納入重要參數(shù)序列，形成一套適合都市圈城間交通的智能化路線(xiàn)推薦系統(tǒng)。

2 技術(shù)框架

2.1 高德地圖開(kāi)放平臺(tái)API

高德地圖是市面上優(yōu)秀、專(zhuān)業(yè)的手機(jī)地圖APP，它擁有國(guó)內(nèi)全面的地圖數(shù)據(jù)和精確的定位能力，為民眾的出行提供了優(yōu)秀的解決方案。它同時(shí)還提供開(kāi)放平臺(tái)API 服務(wù)，開(kāi)發(fā)者可以通過(guò)調(diào)用API 快速構(gòu)建處理地理信息的服務(wù)，如路線(xiàn)規(guī)劃、導(dǎo)航、實(shí)時(shí)地圖數(shù)據(jù)更新、獲取精確坐標(biāo)等。本項(xiàng)目運(yùn)用其提供的數(shù)據(jù)，加上特定算法，以實(shí)現(xiàn)路線(xiàn)推薦。由于該API 由大型專(zhuān)業(yè)公司提供，因此穩(wěn)定性、準(zhǔn)確性有充分保障。

2.2 Python-Flask 框架

Flask 是使用Python 語(yǔ)言編寫(xiě)的開(kāi)源Web 框架，相較于Python 下其他流行的Web 框架如Django，F(xiàn)lask 一個(gè)很大的特點(diǎn)就是“輕量”。它本身相當(dāng)于一個(gè)“內(nèi)核”，開(kāi)發(fā)者可以基于這個(gè)“內(nèi)核”開(kāi)發(fā)程序擴(kuò)展、中間件等，市面上有許多成熟的基于Flask 的程序增強(qiáng)擴(kuò)展，它們可以大幅提升開(kāi)發(fā)效率和程序穩(wěn)定性。擴(kuò)展插件在Flask 中“即插即用”，因此Flask 在保持輕量、快速開(kāi)發(fā)的同時(shí)，也具備了極強(qiáng)的擴(kuò)展與兼容性。綜上所述，不論是開(kāi)發(fā)還是維護(hù)，F(xiàn)lask 框架都能為開(kāi)發(fā)者提供便利。

2.3 以貪心思想為核心的Dijkstra 算法

貪心算法又名為貪婪算法，它是一種抽象的算法思想，代表了一系列具體算法的集合。這類(lèi)算法通常對(duì)問(wèn)題進(jìn)行分解，并在迭代過(guò)程中每次搜索局部最優(yōu)解，并期望得到最終的最優(yōu)解。貪心算法的優(yōu)點(diǎn)是簡(jiǎn)單且高效，省去了不必要的枚舉操作。

本項(xiàng)目應(yīng)用Dijkstra 算法的核心在于實(shí)時(shí)獲取地點(diǎn)位置信息之后，將其與疫情城市信息庫(kù)數(shù)據(jù)進(jìn)行對(duì)比，如果經(jīng)過(guò)風(fēng)險(xiǎn)地區(qū)，路徑置為一個(gè)最大閾值，這樣在進(jìn)行最短路徑（或者其他需求路徑比如紅綠燈最少等）會(huì)將其放置末尾（因?yàn)槲覀冎缹?duì)于最長(zhǎng)路徑極小概率成為人們的日常行程出行選擇）。所以最終返回一個(gè)安全通暢的路徑，并對(duì)于原本經(jīng)過(guò)高風(fēng)險(xiǎn)地區(qū)的路徑給出安全警示消息提示，具體算法流程圖如圖1所示。

圖1 改進(jìn)貪心算法流程圖

3 系統(tǒng)架構(gòu)

在知曉國(guó)家對(duì)于疫情的防控監(jiān)管程度以及人們?nèi)粘３鲂新肪€(xiàn)的需求時(shí)間節(jié)點(diǎn)范圍后，再根據(jù)如今的一些地圖導(dǎo)航功能和數(shù)據(jù)等綜合情況，最后通過(guò)算法計(jì)算出系統(tǒng)的最終需求。

系統(tǒng)的整體目標(biāo)為：（1）實(shí)現(xiàn)一個(gè)基于疫情城市數(shù)據(jù)的城市交通路線(xiàn)推薦系統(tǒng)；（2）用戶(hù)可以根據(jù)實(shí)時(shí)疫情情況選擇合適安全的路線(xiàn)；（3）政府機(jī)構(gòu)可以通過(guò)系統(tǒng)實(shí)時(shí)了解人們的出行情況、給予出行者安全的建議，并實(shí)現(xiàn)系統(tǒng)端的宏觀(guān)管控。應(yīng)用系統(tǒng)架構(gòu)圖如圖2所示。

圖2 應(yīng)用系統(tǒng)架構(gòu)圖

主要功能模塊包括：（1）注冊(cè)登錄模塊。用戶(hù)可以注冊(cè)登錄系統(tǒng)，編輯個(gè)人信息；（2）引入健康碼、行程碼、核酸檢查報(bào)告等同步信息庫(kù)收錄、查看功能；（3）自動(dòng)同步個(gè)人位置信息功能；（4）實(shí)時(shí)重點(diǎn)疫情城市播報(bào)、顯示、錄入疫情城市數(shù)據(jù)庫(kù)功能；（5）所有路線(xiàn)查看功能，其中由兩部分組成，第一部分是根據(jù)傳統(tǒng)算法計(jì)算出的推薦路線(xiàn)，第二部分是排除風(fēng)險(xiǎn)地區(qū)的推薦路線(xiàn)。軟件功能模塊圖如圖3所示。

圖3 軟件功能模塊圖

4 推薦路線(xiàn)具體詳細(xì)設(shè)計(jì)

根據(jù)用戶(hù)當(dāng)前定位所在的城市，結(jié)合數(shù)據(jù)庫(kù)里不斷更新的實(shí)時(shí)城市疫情信息，推薦模塊靈活設(shè)置途徑城市的權(quán)重值，服務(wù)器利用貪心算法計(jì)算出優(yōu)先級(jí)較高的幾條路線(xiàn)，給予用戶(hù)相應(yīng)的出行建議，并將推薦信息同步至數(shù)據(jù)庫(kù)中保存。如圖4、圖5、圖6所示。

圖4 路線(xiàn)推薦模塊流程圖

圖5 用戶(hù)行程上傳界面圖

圖6 行程推薦展示圖

城市道路信息由高德地圖開(kāi)放平臺(tái)提供，服務(wù)器通過(guò)調(diào)用開(kāi)放平臺(tái)提供的API 獲取地圖信息。其地圖數(shù)據(jù)約五分鐘更新一次，保證數(shù)據(jù)的實(shí)時(shí)性、可靠性。為獲取調(diào)用權(quán)限，需要申請(qǐng)高德開(kāi)放平臺(tái)的APP KEY 并下載官網(wǎng)提供的地圖開(kāi)發(fā)包，同時(shí)，根據(jù)開(kāi)發(fā)環(huán)境的不同，需要使用不同的SHA1。調(diào)用流程如圖7所示。

圖7 服務(wù)器調(diào)用API 流程

為方便數(shù)據(jù)的傳遞和存儲(chǔ)，開(kāi)放平臺(tái)提供的地圖數(shù)據(jù)為JSON 或XML 格式。當(dāng)用戶(hù)確定始發(fā)地、目的地、交通方式時(shí)，系統(tǒng)將結(jié)合數(shù)據(jù)庫(kù)存儲(chǔ)的全國(guó)各地疫情信息，推薦安全系數(shù)較高的路線(xiàn)。推薦處理服務(wù)器首先會(huì)調(diào)用開(kāi)放平臺(tái)的路線(xiàn)規(guī)劃接口，獲取可能的出行路線(xiàn)（不包含疫情分析）。接著將所有路線(xiàn)進(jìn)行以城市為單位的拆分（市內(nèi)出行則以區(qū)/鎮(zhèn)/街道為單位），得到可能途徑的所有城市的非重復(fù)集合。再將其與數(shù)據(jù)庫(kù)中的疫情信息進(jìn)行比對(duì)，對(duì)有疫情/交通管制的城市按其風(fēng)險(xiǎn)程度進(jìn)行加權(quán)，風(fēng)險(xiǎn)程度的評(píng)估包括該城市風(fēng)險(xiǎn)地區(qū)數(shù)量、城市交通管制措施、歷史疫情數(shù)據(jù)等。

加權(quán)處理后形成由城市到城市的加權(quán)圖，最后利用Dijkstra 算法找出總權(quán)重最小路徑，此路徑即為較安全的出行路線(xiàn)。除了安全層面的分析與加權(quán)計(jì)算，距離、時(shí)間、出行費(fèi)用等常規(guī)策略選擇也可以包含在推薦結(jié)果的算法當(dāng)中。當(dāng)用戶(hù)選擇其中一種策略時(shí)，路線(xiàn)推薦模塊將按照加權(quán)圖，以路徑的安全程度進(jìn)行分類(lèi)，再對(duì)不同安全程度的路徑進(jìn)行策略加權(quán)，策略權(quán)重的大小與距離、時(shí)間、費(fèi)用成正比。加權(quán)后形成以安全、策略為主的加權(quán)圖，最后同樣使用Dijkstra 算法找出總權(quán)重最小路徑。

循環(huán)往復(fù)上述步驟得到路徑集合后，其數(shù)據(jù)保存在一個(gè)整體的表中，接著該模塊使用部分排序算法對(duì)所有路徑按照安全/策略權(quán)重的高低進(jìn)行升序排序。例如，從上述步驟的結(jié)果得到蘇州到南京路徑集合：A（中風(fēng)險(xiǎn)，10 千米）、B（低風(fēng)險(xiǎn)，5 千米）、C（中風(fēng)險(xiǎn)、5 千米）、D（低風(fēng)險(xiǎn)、10 千米），用戶(hù)選擇最短距離，則路線(xiàn)推薦模塊首先依據(jù)安全程度將B、D（均為低風(fēng)險(xiǎn)）為一組，A、C（均為中風(fēng)險(xiǎn)）分為一組，再按照策略對(duì)其部分排序（路程升序），其推薦結(jié)果為B、D、C、A。

推薦結(jié)果內(nèi)容包括系統(tǒng)推薦的始末地路徑圖、推薦路徑上各個(gè)城市的詳細(xì)疫情數(shù)據(jù)、交通情況、出行距離、出行費(fèi)用、通行時(shí)間。其中，由于詳細(xì)疫情數(shù)據(jù)為可選展示，因此路徑圖與詳細(xì)疫情數(shù)據(jù)為不同的JSON 字符串。并且對(duì)于詳細(xì)疫情數(shù)據(jù)進(jìn)行懶加載處理，如用戶(hù)不點(diǎn)擊查看詳細(xì)城市數(shù)據(jù)，則不會(huì)包含在推薦頁(yè)面中。這樣既能精簡(jiǎn)頁(yè)面的信息量，提升用戶(hù)的閱覽、判斷速度，也能減少大用戶(hù)量情況下系統(tǒng)卡頓、崩潰的風(fēng)險(xiǎn)。上述處理流程如圖8所示。

圖8 推薦路線(xiàn)處理流程

5 獲取疫情城市數(shù)據(jù)具體詳細(xì)設(shè)計(jì)

爬蟲(chóng)模塊會(huì)從國(guó)家衛(wèi)建委官方網(wǎng)站請(qǐng)求疫情數(shù)據(jù)，通過(guò)上次保存的數(shù)據(jù)日期與當(dāng)前獲取的數(shù)據(jù)日期進(jìn)行對(duì)比，篩選出最新的數(shù)據(jù)。為了防止頻繁的調(diào)用爬蟲(chóng)模塊而導(dǎo)致網(wǎng)站的崩潰，本項(xiàng)目使用每天定時(shí)獲取數(shù)據(jù)的方式。這樣既能減輕網(wǎng)站、數(shù)據(jù)處理服務(wù)器的負(fù)荷，也基本符合官方疫情數(shù)據(jù)的發(fā)布規(guī)律如圖9所示。根據(jù)官方發(fā)布的數(shù)據(jù)類(lèi)型，本項(xiàng)目將關(guān)鍵信息概括為：城市名稱(chēng)、該城市最新數(shù)據(jù)日期、該城市確診病例統(tǒng)計(jì)、該城市無(wú)癥狀感染病例統(tǒng)計(jì)、該城市死亡病例統(tǒng)計(jì)、高風(fēng)險(xiǎn)地區(qū)統(tǒng)計(jì)及具體地區(qū)、中風(fēng)險(xiǎn)地區(qū)統(tǒng)計(jì)及具體地區(qū)、低風(fēng)險(xiǎn)地區(qū)統(tǒng)計(jì)及具體地區(qū)如圖10所示。爬蟲(chóng)將從國(guó)家衛(wèi)建委官網(wǎng)獲取HTML 網(wǎng)頁(yè)文件，在經(jīng)過(guò)爬蟲(chóng)框架的預(yù)處理后得到具體的發(fā)布信息，此時(shí)將數(shù)據(jù)提交給數(shù)據(jù)處理模塊。

圖9 獲取城市疫情數(shù)據(jù)模塊圖

圖10 處理爬蟲(chóng)獲取文件信息的模塊圖

數(shù)據(jù)處理模塊將對(duì)爬蟲(chóng)模塊提交的數(shù)據(jù)進(jìn)一步提煉。該模塊首先比對(duì)數(shù)據(jù)庫(kù)中的各個(gè)城市的信息更新時(shí)間進(jìn)而篩出過(guò)期的數(shù)據(jù)，然后將新發(fā)布的數(shù)據(jù)累加到原有的舊數(shù)據(jù)上形成最新數(shù)據(jù)，再根據(jù)城市名稱(chēng)，將最新數(shù)據(jù)分類(lèi)，形成數(shù)據(jù)列表，最后提交給數(shù)據(jù)庫(kù)將其持久化。處理爬蟲(chóng)數(shù)據(jù)的流程如圖11所示。

圖11 數(shù)據(jù)庫(kù)表設(shè)計(jì)圖

6 結(jié) 論

常態(tài)化防疫交通路線(xiàn)智能推薦系統(tǒng)，前端采用移動(dòng)端比較流行的微信小程序以及方便辦公人員操作Web 網(wǎng)頁(yè)呈現(xiàn)，并且結(jié)合較為流行的前端開(kāi)發(fā)流行框架，快速實(shí)現(xiàn)一個(gè)高響應(yīng)的行程推薦系統(tǒng)。后端主要采用輕量級(jí)的Web 開(kāi)發(fā)框架Flask，接收前端發(fā)送的數(shù)據(jù)，并配合擅長(zhǎng)數(shù)據(jù)處理的Python語(yǔ)言，返回統(tǒng)一的響應(yīng)格式數(shù)據(jù)給予前端相對(duì)應(yīng)的響應(yīng)，有效地實(shí)現(xiàn)推薦算法。服務(wù)器采用較為穩(wěn)定的阿里云服務(wù)器，在能夠保障安全性的同時(shí)給予整個(gè)項(xiàng)目最穩(wěn)定、高效的運(yùn)行模式。該系統(tǒng)的創(chuàng)新點(diǎn)在于能夠?qū)崟r(shí)根據(jù)疫情城市信息更新城市數(shù)據(jù)庫(kù)、路線(xiàn)推薦方案，利用貪心算法，賦予不同城市權(quán)重值，從而給予用戶(hù)最安全的行程路線(xiàn)和使用體驗(yàn)。