一種汽車泊車時長計算的設計方案

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

（上汽通用五菱汽車股份有限公司廣西汽車新四化重點實驗室，廣西 柳州 545007）

引言

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

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

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

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

動態(tài)規(guī)劃解決問題的三個特點：

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

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

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

2 方案設計

2.1 難點介紹（見下頁圖2）

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

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

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

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

2.2 各項難點的解決

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

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

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

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

2.3 各節(jié)點聚合

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

3 結(jié)論

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

（編輯：趙婧）