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

閔政揚，張 亮，韋通明，韋統邊，唐 瑩

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

引言

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

1 動態規劃算法簡介

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

動態規劃的概述圖如圖1所示（圓形為狀態節點）。

動態規劃解決問題的三個特點：

1）最優化原理：如果問題的最優解所包含的子問題的解也是最優的，就稱該問題具有最優子結構，即滿足最優化原理。

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

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

2 方案設計

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

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

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

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

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

2.2 各項難點的解決

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

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

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

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

2.3 各節點聚合

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

3 結論

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

（編輯：趙婧）