以編輯距離相似度及分群方式進行軌跡模式探勘－以都市地區宅配車輛為例

Trajectory Pattern Mining Using Edit Distance Similarity and Clustering－A Case Study of Urban Home Delivery Vehicle

傅嘉修(Chia-Hsiu Fu)

指導教授 ： 黃奎隆

國立臺灣大學/工學院/工業工程學研究所/碩士(2020年)

https://doi.org/10.6342/NTU202003043

摘要

隨著網際網路的普及，人們的消費模式也正在逐漸改變，電子商務供應鏈的發展促使線上零售的管道取代部分的傳統實體零售店面，而宅配在此供應鏈中負責最後一哩運送，佔有不可或缺的地位。近年隨著電商的蓬勃發展，宅配的需求也隨之增長，並衍生出龐大的宅配物流商機。而宅配貨件的配送工作因為貨件量大、工時長、路線規劃所要考慮的因素複雜，造成宅配人員的工作壓力居高不下。若能從大量累積的軌跡資料中將無形的過往經驗轉化為可判讀的知識，針對配送區內的紀錄歸納出較為頻繁的運送模式做為參考，應能有效幫助配送人員縮短作業時間，也降低各項成本的耗損。
本研究針對都市區域內的貨運車輛軌跡進行觀察，將軌跡資料中的資料點轉換為網格化表示以及路段表示，同時使用加權編輯距離（Weighted Edit Distance）以及最長共同子序列（Longest Common Subsequence）兩種方式定義樣本相似度的計算方式，並針對編輯距離在軌跡序列長度不同時，編輯距離會隨著長度膨脹的問題做出了修正，並且利用元素之間的距離關係定義作為依據，提出新的編輯操作成本定義方式。從分群結果來看，該資料集雖然不存在明顯的群集，但其中仍然有部分樣本具有非常相似的特徵，表明在該觀察區域內，駕駛車輛的人員確實具有習慣的行為模式。

關鍵字

GPS軌跡 ； 軌跡模式探勘 ； 軌跡分群 ； 軌跡相似度 ； 加權編輯距離 ； 最長共同子序列 ； 網格化表示 ； 路段表示

並列摘要

Due to the popularity of the internet, people's consumption patterns are gradually changing. Online retail websites are gradually replacing traditional retail stores because of the rapid development of e-commerce. In supply chains of E-commerce, home delivery is responsible for the last mile delivery and takes an important role in the distribution of goods. In recent years, with the vigorous development of online shopping, the demand for commodity distribution has also increased and created a lot of business opportunities for home delivery. Due to the large quantity of goods, long working hours, and complex factors to be considered in route planning of delivery, the couriers are working under great stress. The purpose of this study is to provide couriers with some experience-based route planning advice through finding the frequent trajectory patterns from the GPS records of home delivery fright trucks in urban areas.
In this study, we applied a framework of trajectory pattern mining to observe the GPS records of home delivery fright trucks in urban areas and proposed a new concept to define the operation costs of edit distance based on the geographical relations between elements, and we also normalized the pairwise distance using the length of trajectory sequences. The data we used is recorded by the in-vehicle GPS devices equipped on the freight trucks and presented as sequences of timestamped coordinates on a daily basis. The raw GPS trajectory data is transformed into grid-based representation and road segment representation, and the pairwise similarities are calculated using weighted edit distance and longest common subsequence method. A hierarchical method is applied for clustering and the result shows that some frequent patterns ae exists in the original data.

並列關鍵字

GPS Trajectory ； Trajectory Pattern Mining ； Trajectory Clustering ； Trajectory Similarity ； Weighted Edit Distance ； Longest Common Subsequence ； LCSS ； Grid-Based Representation ； Road Segment Representation

參考文獻

Huang, H. Gartner, G. (2014). Using trajectories for collaborative filtering-based POI recommendation, Int. J. Data Mining, Modelling and Management, Vol. 6, No. 4, pp.333–346.

Cui, G., Luo, J., Wang, X. (2017). Personalized travel route recommendation using collaborative filtering based on GPS trajectories. International Journal of Digital Earth, 11(3), 284–307.

Zheng, Y. (2015). Trajectory Data Mining: An Overview. ACM Transactions on Intelligent Systems and Technology. 6. 1-41.

Yoon, H., Zheng, Y., Xie, X., Woo, W. (2010). Smart itinerary recommendation based on user-generated gps trajectories. In: Ubiquitous intelligence and computing. Springer, pp.19–34

Zhang, F., Yuan, N. J., Wilkie, D., Zheng, Y. Xing, X. (2015). Sensing the Pulse of Urban Refueling Behavior: A Perspective from Taxi Mobility. ACM Transactions on Intelligent Systems and Technology. 6. 1-23.