物流配送中多車多點路徑規(guī)劃算法研究

李淑飛 駱劍鋒

摘? 要： 物流配送中常用的Dijkstra、Floyd、A*等最短路徑算法只能計算兩點之間的最短路徑，沒有帶約束條件和回程規(guī)劃。多車多點路徑規(guī)劃算法利用神經(jīng)網(wǎng)絡(luò)對收送貨地點進行分區(qū)，用百度地圖API計算各點之間的最短路徑，通過繞行遍歷思想計算繞行貢獻值，利用貪婪思想在車輛限載重、限路程的情況下組合回程，從而形成最優(yōu)路徑方案。該算法已用在物流企業(yè)的多車多點路徑規(guī)劃云平臺上，大大提高了物流配送效率。

關(guān)鍵詞： 多車多點;最短路徑;繞行貢獻值;規(guī)劃算法;物流配送

【Abstract】： The Shortest path algorithms such as Dijkstra， Floyd， and A* commonly used in logistics distribution can only calculate the shortest path between two points， without constraints and backhaul planning. The multi-vehicle multi-point path planning algorithm uses neural network to partition the receiving and delivering places， and uses Baidu Map API to calculate the shortest path between the points，and the detour contribution is calculated by detour traversal idea， and the greedy idea is used to combine the backhaul under the condition of Limited vehicle load and distance， thus forming the optimal path scheme. This algorithm has been used in multi-vehicle multi-point path planning cloud platform of logistics enterprises， which greatly improves the efficiency of logistics distribution.

【Key words】： Multi-vehicle multi-point; Shortest path; Detour contribution value; Planning algorithm; Logistics distribution

0? 引言

在物流配送活動中，物流配送路徑的最優(yōu)化問題，是物流配送系統(tǒng)優(yōu)化中關(guān)鍵的一環(huán)。隨著配送路網(wǎng)的日趨復(fù)雜，配送成本日益增大[1]，在物流配送中規(guī)劃合理的配送路線，避免迂回運輸與重復(fù)運輸，有利于節(jié)省配送費用，降低物流成本，提高物流配送的效率和經(jīng)濟效益。

物流配送問題是典型的組合尋優(yōu)問題[2]，常用的路徑最優(yōu)算法有Dijkstra[3]、Floyd、A*等算法[4]。Dijkstra算法是經(jīng)典的廣度優(yōu)先算法，該算法的主要特點是以起始點為中心搜索所有與其連接的點，從中心向外層延展，直到延展到終點為止，因此能夠有效解決單源最短路徑問題[5]。Floyd算法是經(jīng)典的深度優(yōu)先算法，該算法利用動態(tài)規(guī)劃思想，尋找給定的加權(quán)圖中多源點之間最短路徑，因此能夠有效解決任意兩點之間最短距離[6]。A*算法是基于啟發(fā)式的最短路徑算法，是一種靜態(tài)路網(wǎng)中求解最短路徑最有效的直接搜索方法，通過計算函數(shù)的慢相對最優(yōu)解來篩選出發(fā)點周圍的后繼點[7]?！?br>