閔政揚(yáng)，張 亮，韋通明，韋統(tǒng)邊，唐 瑩

（上汽通用五菱汽車股份有限公司廣西汽車新四化重點(diǎn)實(shí)驗(yàn)室，廣西 柳州 545007）

引言

如果說20世紀(jì)是一個(gè)石油為王的時(shí)代，21世紀(jì)就是一個(gè)數(shù)據(jù)為王的時(shí)代，21世紀(jì)數(shù)據(jù)的價(jià)值有可能等同于20世紀(jì)的石油[1]。不論是近十年來興起的互聯(lián)網(wǎng)企業(yè)，還是傳統(tǒng)的汽車制造企業(yè)，大數(shù)據(jù)既可以增強(qiáng)客戶體驗(yàn)，也可以提高運(yùn)營效率。對(duì)于近現(xiàn)代的汽車企業(yè)，數(shù)據(jù)意味客戶，掌握客戶生活習(xí)慣的數(shù)據(jù)即意味著把握住了未來汽車行業(yè)的走向，為企業(yè)贏得一步先機(jī)。泊車時(shí)長數(shù)據(jù)作為車企中不容忽視的存在具有極大的分析價(jià)值，收集到的數(shù)據(jù)中并非所有的數(shù)據(jù)都是有價(jià)值的，對(duì)于初步采集的數(shù)據(jù)我們往往要進(jìn)行一道或多道的加工才能提取到真正有效的數(shù)據(jù)，于是一種汽泊車時(shí)長的設(shè)計(jì)方案應(yīng)運(yùn)而生。

1 動(dòng)態(tài)規(guī)劃算法簡介

在現(xiàn)實(shí)生活中，有一類活動(dòng)的過程，由于它的特殊性，可將過程分成若干個(gè)互相聯(lián)系的階段，在它的每一階段都需要作出決策，從而使整個(gè)過程達(dá)到最好的活動(dòng)效果。因此各個(gè)階段決策的選取不能任意確定，它依賴于當(dāng)前面臨的狀態(tài)，又影響以后的發(fā)展。當(dāng)各個(gè)階段決策確定后，就組成一個(gè)決策序列，因而也就確定了整個(gè)過程的一條活動(dòng)路線。這種把一個(gè)問題看作是一個(gè)前后關(guān)聯(lián)具有鏈狀結(jié)構(gòu)的多階段過程就稱為多階段決策過程，這種問題稱為多階段決策問題。在多階段決策問題中，各個(gè)階段采取的決策，一般來說是與時(shí)間有關(guān)的，決策依賴于當(dāng)前狀態(tài)，又隨即引起狀態(tài)的轉(zhuǎn)移，一個(gè)決策序列就是在變化的狀態(tài)中產(chǎn)生出來的，故有“動(dòng)態(tài)”的含義，稱這種解決多階段決策最優(yōu)化的過程為動(dòng)態(tài)規(guī)劃方法[2]。

動(dòng)態(tài)規(guī)劃的概述圖如圖1所示（圓形為狀態(tài)節(jié)點(diǎn)）。

動(dòng)態(tài)規(guī)劃解決問題的三個(gè)特點(diǎn)：

1）最優(yōu)化原理：如果問題的最優(yōu)解所包含的子問題的解也是最優(yōu)的，就稱該問題具有最優(yōu)子結(jié)構(gòu)，即滿足最優(yōu)化原理。

2）無后效性：即某階段狀態(tài)一旦確定，就不受這個(gè)狀態(tài)以后決策的影響。也就是說，某狀態(tài)以后的過程不會(huì)影響以前的狀態(tài)，只與當(dāng)前狀態(tài)有關(guān)。

3）有重疊子問題：即子問題之間是不獨(dú)立的，一個(gè)子問題在下一階段決策中可能被多次使用到（該性質(zhì)并不是動(dòng)態(tài)規(guī)劃適用的必要條件，但是如果沒有這條性質(zhì)，動(dòng)態(tài)規(guī)劃算法同其他算法相比就不具備優(yōu)勢）。

2 方案設(shè)計(jì)

2.1 難點(diǎn)介紹（見下頁圖2）

1）企業(yè)中的數(shù)據(jù)大多都是存于數(shù)據(jù)庫中的，我們需要根據(jù)實(shí)際需求訪問數(shù)據(jù)庫獲取有分析價(jià)值的數(shù)據(jù)。

2）泊車時(shí)長的計(jì)算需要同一輛車前后兩條數(shù)據(jù)的連續(xù)性（第一次停車的時(shí)間，第二次啟動(dòng)的時(shí)間），然而直接從庫中取出的數(shù)據(jù)無法滿足這一特性。

3）對(duì)于每輛車每天的第一條數(shù)據(jù)，該如何獲取它的上一條數(shù)據(jù)以計(jì)算它上一次的泊車時(shí)長。

4）我們無法通過簡單的SQL語句獲取一輛車某天的泊車時(shí)長總和。

2.2 各項(xiàng)難點(diǎn)的解決

1）如何從企業(yè)數(shù)據(jù)庫中拉取數(shù)據(jù)。由于當(dāng)前企業(yè)項(xiàng)目絕大多數(shù)都是Spring項(xiàng)目，我們可以通過Spring框架集成MyBatis Plus（以下簡稱為MP），然后通過MP來實(shí)現(xiàn)單表的CRUD（Create、Retrieve、Update、Delete）操作，并且可以可以通過QueryWrapper對(duì)查詢條件進(jìn)行封裝，在一定程度上實(shí)現(xiàn)復(fù)雜SQL語句的查詢。MP查詢數(shù)據(jù)的原理見圖3數(shù)據(jù)獲取方法圖。

2）從數(shù)據(jù)庫中獲取到的時(shí)間并不具有單個(gè)車輛上的連續(xù)性。我們可以將獲取到的數(shù)據(jù)對(duì)每個(gè)車的唯一編碼（以下簡稱為VIN）以及車輛的啟動(dòng)時(shí)間進(jìn)行一個(gè)排序，最終獲取到的數(shù)據(jù)即為車輛編碼以及每輛車的每天的啟動(dòng)時(shí)間順序。通過排序操作的實(shí)現(xiàn)有兩種方式：通過SQL語句實(shí)現(xiàn)：SELECT X FROMTABLE YWHERE Z ORDER BY VIN,TIME，X為我們需要使用的字段，Y為數(shù)據(jù)表的名稱，Z為我們進(jìn)行數(shù)據(jù)篩選的條件；通過后端算法實(shí)現(xiàn)：使用快速排序的思想，當(dāng)VIN碼相同時(shí)根據(jù)時(shí)間的大小排序。我們可以通過重寫equals方法讓實(shí)體類的對(duì)象能夠被比較，并讓實(shí)體類實(shí)現(xiàn)Comparable接口，重寫compareTo方法，讓數(shù)據(jù)按照我們想要的規(guī)則進(jìn)行排序（附：我們也可以單獨(dú)為實(shí)體類寫一個(gè)比較器，將此比較器作為優(yōu)先隊(duì)列PriorityQueue或其他可以排序集合的參數(shù)對(duì)實(shí)現(xiàn)對(duì)實(shí)體類的排序功能，然而此方法于我們使用場景的適用性不高，故不作考慮）。對(duì)數(shù)據(jù)進(jìn)行排序算法的時(shí)間復(fù)雜度：Onlogn。數(shù)據(jù)連續(xù)性的實(shí)現(xiàn)原理圖見圖4。

3）對(duì)于每輛車的第一條數(shù)據(jù)，如何獲取它的上一條數(shù)據(jù)。我們可以通過對(duì)車的VIN碼和時(shí)間參數(shù)A為限制，查詢該車在A時(shí)間前的最后一條數(shù)據(jù)（max（time）as time2 where time＜A），然后做表之間的自連接，連接的關(guān)鍵字段依舊為VIN碼以及時(shí)間參數(shù)，不過所需的連接條件變化為VIN1=VIN2 AND TIME1=TIME2（TIME2為上述的max time的別名）。值得注意的是：直接對(duì)滿足時(shí)間小于A的VIN碼進(jìn)行分組然后取最大的一條數(shù)據(jù)的寫法是錯(cuò)誤的—通過此種方式我們能夠輕易的獲取到VIN碼以及小于某時(shí)間節(jié)點(diǎn)的最大值，但我們需要的其他信息，例如停車位置的獲取是不正確的，這一點(diǎn)我們可以通過查看MYSQL SQL語句group by的使用方法得以驗(yàn)證。獲取車輛某一天第一條數(shù)據(jù)的上一條數(shù)據(jù)實(shí)現(xiàn)方法圖見圖5。

4）如何獲取每天每輛車的泊車時(shí)長總和?；蛟S我們不清楚如何一次性獲取某一天車輛的泊車時(shí)長總和，但我們卻了解一天中的總泊車時(shí)長是每次停車時(shí)長做加法運(yùn)算所產(chǎn)生的結(jié)果，而每次泊車時(shí)長的獲取即為此次啟動(dòng)的時(shí)間點(diǎn)減去上一次停車的時(shí)間點(diǎn)。但是麻煩又來了，當(dāng)我們得到一條泊車數(shù)據(jù)時(shí)，我們該如何獲取此車輛的下次啟動(dòng)時(shí)間呢？不用擔(dān)心，這點(diǎn)恰恰可以通過數(shù)據(jù)在車輛的VIN碼和時(shí)間上連續(xù)性得以保證。值得注意的是，某一天車輛的第一天數(shù)據(jù)需要判斷該車輛在這一天前是否有過泊車記錄，如果有，需要找出最后停車的那個(gè)時(shí)間點(diǎn)（這個(gè)時(shí)間點(diǎn)不一定是昨天的最后一條數(shù)據(jù)——因?yàn)榇嬖谲囕v停放超過一天的場景）。具體獲取方法見圖6泊車時(shí)長總和獲取實(shí)現(xiàn)圖。

2.3 各節(jié)點(diǎn)聚合

通過2.2節(jié)對(duì)于停車時(shí)長計(jì)算難點(diǎn)的分析，現(xiàn)在我們可以很容易的理清思路并得到如圖7所示的泊車時(shí)長計(jì)算方案實(shí)現(xiàn)圖。通過SQL語句的編寫獲取車輛某一天最近的停車時(shí)間；對(duì)數(shù)據(jù)庫數(shù)據(jù)的排序使得數(shù)據(jù)在某些方面呈現(xiàn)一種連續(xù)性；通過動(dòng)態(tài)規(guī)劃的思想，分別從兩個(gè)數(shù)據(jù)源獲取數(shù)據(jù)對(duì)目標(biāo)數(shù)據(jù)集合進(jìn)行填充，最終得到目標(biāo)集合，至此一種汽車泊車時(shí)長的設(shè)計(jì)方案已浮現(xiàn)于我們的眼前。

3 結(jié)論

文本提出了一種汽車泊車時(shí)長的設(shè)計(jì)方案，用于解決在大數(shù)據(jù)時(shí)代車企泊車時(shí)長大數(shù)據(jù)獲取提純難度大的問題，將方法的時(shí)間復(fù)雜度由On2降低至Onlogn，極大地縮減了數(shù)據(jù)處理的時(shí)間，為大數(shù)據(jù)時(shí)代下的車企節(jié)省了寶貴的數(shù)據(jù)運(yùn)算時(shí)間，增強(qiáng)了用戶的使用體驗(yàn)。

（編輯：趙婧）