利用Kmeans與蟻群算法的路徑尋優(yōu)方法

彭熙舜，陸安江，賈明俊，盧學敏

（貴州大學 大數(shù)據(jù)與信息工程學院，貴陽550025）

0 引 言

在當今時代，網(wǎng)購已經(jīng)成為了一種新的潮流，每年由電商舉辦的雙十一、六一八更是風靡盛行。隨著快遞數(shù)目的劇烈增長，物流的配送工作越來越重要。人們購買的物件也是花樣繁多，生鮮快遞必須滿足時效性，裝飾類物品需要避免發(fā)生碰撞。物流配送過程中常規(guī)應用GPS導航，而高效的物流管理取決于兩個關(guān)鍵因素，車輛問題（VRP）與資源配置問題，因此路徑規(guī)劃開始被廣泛應用于物流管理中。本文提出了利用Kmeans聚類將客戶購買物品按照特性進行分類，再利用蟻群算法進行路徑規(guī)劃。

1 研究背景與意義

路徑規(guī)劃是近代興起的新型技術(shù)，被廣泛應用于機器人避障，無人機避障，防空導彈系統(tǒng)中。人們的日常生活也開始利用這種技術(shù)，比如城市交通規(guī)劃，GPS智能導航，物流配送管理系統(tǒng)。通常情況下，按照周圍環(huán)境信息的布局規(guī)劃，可以將其分為全局和局部兩種路徑規(guī)劃［1］。前者需要在實踐之前掌握所有的環(huán)境數(shù)據(jù)，提前作出路徑規(guī)劃判斷；后者主要是采取傳感器實時得來的局部環(huán)境信息，及時的給出路徑規(guī)劃。本文主要研究解決車輛路徑問題（VPR），以物流中心為起點，派出車輛向不同位置的客戶進行物資配送，配送任務(wù)結(jié)束后返回起點，而其中的關(guān)鍵在于將配送效率最大化，車輛使用率最大化。

路徑規(guī)劃一般是由環(huán)境建模，路徑搜索，路徑平滑這3步所組成［2］。環(huán)境建模是起始環(huán)節(jié)，搭建一個方便計算機規(guī)劃具體路徑的模型，實質(zhì)上是將物理信息轉(zhuǎn)為數(shù)字信息，在空間上相互映射；……