基于聚類的城市速遞車輛路徑問題研究

[摘 要]本文分析了城市速遞車輛路徑問題相對于經典的車輛路徑問題存在的一些不同點，指出城市速遞服務中客戶位置更趨向于聚簇型分布，基于此，將客戶點進行聚集，將整個聚集塊作為一個整體的服務單元，采用了公用的Sololon100數據集來進行車輛路徑問題的求解。

[關鍵詞]聚類；城市速遞；服務單元；車輛路徑問題

[中圖分類號]U4 [文獻標識碼]A [文章編號]1005-6432（2014）44-0145-02

1 引 言

隨著電子商務的發展，速遞業務量急劇增大，如何針對速遞貨運問題建立高效的車輛路徑規劃模型，成為了當前的一個研究熱點[1-2]。傳統的車輛路徑問題建模直接針對客戶地理位置進行車輛路徑的優化，更多的是考慮了各種優化算法的性能，而沒有考慮到速遞業客戶服務的本地化、社區化在速遞運送中的作用^[3]。

通過分析可以發現，現代城市速遞車輛路徑的規劃和傳統的車輛路徑規劃面臨的環境有所不同。在城市速遞服務中，由于區域規劃、定位的不同，客戶在整個區域內并不呈現隨機均勻分布，而是呈現出聚簇狀分布的特征，例如學校、居民社區、寫字樓等均是潛在的客戶密集分布區域，如圖1所示。因此，在城市社區速遞路徑優化時，我們可以通過對密集客戶區域進行聚類以構建服務單元，基于服務單元進行城市速遞路徑的優化與投遞服務。

Zhong^[4]等指出，構建速遞投送的局部性、本地性，即保持速遞員投遞路線的相對固定性，使速遞員多次進入同一服務單元，有助于提高服務效率；Sungur^[5]在進行車輛路徑優化時，將局部路徑的相似性作為限制條件。

城市速遞服務必須綜合考慮車輛路徑的最優化原則和速遞配送的相似性原則。實際上，速遞員對地域的熟悉程度有助于速遞服務效率的提升，因此，需要在速遞服務路徑規劃中考慮到社區或地理位置相似性原則，即盡量讓地理位置相似的客戶由同一速遞員進行服務。

2 城市車輛路徑問題客戶點聚類

基于上述對城市速遞車輛路徑問題的分析，我們提出采用聚類的方法首先對密集客戶區域進行聚類，以形成服務單元。實際上，現實生活中經常見到的基于行政單元劃分將速遞配送區域進行劃分的方式，可以認為是基于聚類的城市速遞車輛路徑問題的特例，采用這種方式具有簡單快捷的優勢，但這種方法沒有充分的挖掘客戶間的地理位置相關性；Christofides^[6]將配送區域按照笛卡爾坐標系劃分為標準的方形網格；Charikar^[7]等采用k-median的方式進行配送區域的劃分；在本文中，我們從理論的角度，采用了k均值聚類的方式進行區域客戶的聚類。

本文在采用k均值算法進行客戶點的聚類時，添加了兩個額外的限制條件，類內距離R1和類間距離R2，在聚類過程中，可根據限制條件增加或減少聚類中心。類內距離定義為在一個聚類區域（服務單元）內，不同客戶距離聚類中心的距離；類間距離定義為不同聚類中心之間的距離。在進行客戶聚類時，類內距離不應過大，若在一個聚類中，存在客戶與聚類中心之間的距離大于給定閾值，可將該客戶獨立的組成新的聚類中心，然后更新數據點所屬聚類和聚類中心；同樣的，當存在兩個類間距離（聚類中心之間的距離）小于給定閾值的情形時，可將兩個聚類區域進行合并，隨后更新聚類區域和聚類中心。

于是，本文的聚類算法在進行完常規的k均值聚類算法后，需要依據上述的兩個額外限制條件對產生的聚類中心進行分割和合并，導致聚類中心數目并不固定為k個。類內距離R1和類間距離R2將直接影響到最終聚類的結果，需要在實驗中進行合理的設置。

3 基于服務單元的車輛路徑問題求解

基于上述的分析，對于城市速遞車輛路徑問題，我們首先將客戶點進行聚集，將整個聚集塊作為一個整體的服務單元進行考慮。隨后，將服務單元作為虛擬客戶點進行車輛路徑問題的求解。

考慮到城市速遞車輛路徑問題的特點，采用了公用的Sololom100數據集來進行車輛路徑問題的分析。

首先，我們采用了本文算法對客戶點進行了聚類，圖2給出了Solomon100數據集客戶點、中心點、聚簇中心在二維坐標系空間的直觀展示。

其次，我們以上述基于聚類分析得到的服務單元作為虛擬的客戶點，進行車輛路徑的規劃，根據客戶點位置和上述的車輛配送路徑，圖3將其在平面坐標系進行了直觀展示。基于上述的路徑規劃，總的行駛路徑為：59.62+95.89+50.80+97.23+64.81+101.88+59.40+127.30+76.07+95.94=828.94。

參考文獻：

[1]段宗訓.中國快遞業發展現狀及發展趨勢分析[J].企業導報，2012，1（3）： 94-95.

[2]張如云.中國快遞行業發展環境和并購趨勢分析[J].物流技術（裝備版），2013，32（1）： 77-79.

[3]熊浩，鄢慧麗，周和平.多階段動態車輛路徑問題實時優化策略[J].上海交通大學學報，2013，47（3）： 450-453.

[4]H.Zhong，M.Dessouky，D.J.Epstein.Territory planning and vehicle dispatching with driver learning[J].Transportation Science，2007，41（1）： 74-89.

[5]I.Sungur，Y.Ren，F.Ordóòez，et al.A Model and Algorithm for the Courier Delivery Problem with Uncertainty[J].Transportation Science，2010，44（2）： 193-205.

[6]Christofides N.Fixed routes and areas for delivery operations[J].International Journal of Physical Distribution Logistics Management，1971，1（2）： 87-92.

[7]Charikar M，Guha S，Tardos ，et al.A constant-factor approximation algorithm for the k-median problem[J].Journal of Computer and System Sciences，2002，65（1）： 129-149.