基于改進(jìn)A*算法的車(chē)間物料配送路徑規(guī)劃

摘要： 針對(duì)傳統(tǒng)避障搜索算法在車(chē)間物料配送中僅能解決單點(diǎn)配送且未充分考慮多點(diǎn)配送及往返取貨需求的問(wèn)題， 提出一種結(jié)合遺傳算法優(yōu)化的A*算法. 該方法利用A*算

法的成本計(jì)算方式完成有障礙物條件下各配送點(diǎn)之間的成本計(jì)算， 并融合遺傳算法的迭代尋優(yōu)特性， 實(shí)現(xiàn)了對(duì)多點(diǎn)配送及往返取貨需求的高效穩(wěn)定全局搜索. 通過(guò)某車(chē)間物料配送的實(shí)際算例驗(yàn)證， 該改進(jìn)算法能有效規(guī)劃障礙環(huán)境下的配送路徑， 顯著提升配送效率.

關(guān)鍵詞： 路徑規(guī)劃； 物料配送； 遺傳算法； A*算法; 柵格環(huán)境

中圖分類(lèi)號(hào)： TP29""文獻(xiàn)標(biāo)志碼： A""文章編號(hào)： 1671-5489（2024）06-1401-10

Workshop Material Distribution Path PlanningBased on Improved A* Algorithm

BAI Junfeng1， BAI Yichen2， XI Jialu1， ZHANG Jinyao3

（1. School of Mechanical and Electrical Engineering， Changchun University of Technology， Changchun 130012， China;2. School of Mechanical and Aerospace Engineering， Jilin University， Changchun 130025， China;3. School of Management， College of Humanities and Information

Changchun University of Technology， Changchun 130122， China）

Abstract： Aiming at the problem that "traditional obstacle avoidance search algorithms could only solve single-point distribution and inadequately considered

the needs for multi-point distribution and round-trip pickups in workshop material distribution， we proposed an A* algorithm that combined "a genetic algorithm optimization.

This method employed the cost calculation approach of the A* algorithm to complete cost calculation between various distribution points under obstacle conditions， and integrated

the iterative optimization characteristics of the genetic algorithm to achieve efficient and stable global search for multi-point distribution and round-trip pickup requirements.

Through the verification of a practical example of material distribution in a certain workshop， the improved algorithm can effectively plan distribution

paths in obstacle environments and "significantly improve distribution efficiency.

Keywords： path planning; material distribution; genetic algorithm; A* algorithm; grid environment

針對(duì)復(fù)雜障礙環(huán)境的路徑規(guī)劃， 利用A*算法進(jìn)行精確的鄰域搜索選取策略并引入障礙物占用柵格率量化地圖信息， 有助于提升避障及路徑規(guī)劃的能力^［1］. 傳統(tǒng)A*算法存在遍歷節(jié)點(diǎn)數(shù)多， 轉(zhuǎn)折角度大和搜索速度慢的問(wèn)題^［2］， 在路徑擴(kuò)展搜索時(shí)采用8個(gè)方向上自適應(yīng)調(diào)整搜索距離機(jī)制代替原有固定搜索距離， 可減少擴(kuò)展搜索節(jié)點(diǎn)數(shù)量， 達(dá)到減少搜索時(shí)間的目的^［3］. 遺傳算法具有很好的改進(jìn)路徑規(guī)劃算法的能力^［4］， 可使用遺傳算法解決靜態(tài)環(huán)境下具有可預(yù)測(cè)地形的移動(dòng)機(jī)器人路徑規(guī)劃問(wèn)題， 該方法可在靜態(tài)環(huán)境中處理不同類(lèi)型的任務(wù)^［5］. 在遺傳算子的設(shè)計(jì)中， 通過(guò)加入自適應(yīng)調(diào)整方法使算法更完善， 可解決進(jìn)化過(guò)程中因陷入局部極小值而不能到達(dá)目標(biāo)點(diǎn)的問(wèn)題^［6］， 利用包括神經(jīng)網(wǎng)絡(luò)在內(nèi)的算法輸出建立遺傳算法的適應(yīng)度函數(shù)， 并將其應(yīng)用于遺傳算法優(yōu)化路徑的規(guī)劃方法， 已被證明是有效的^［7］.為使算法在復(fù)雜環(huán)境下具有更強(qiáng)的搜索尋優(yōu)能力， 提升其搜索路徑的高效性和穩(wěn)定性， 本文通過(guò)分析A*算法和遺傳算法的性能和搜索原理， 提出一種利用柵格法對(duì)車(chē)間環(huán)境進(jìn)行離散化處理的方法， 以實(shí)現(xiàn)對(duì)存在障礙物的配送環(huán)境的有效模擬， 利用A*算法的成本計(jì)算方式完成有障礙物條件下各節(jié)點(diǎn)之間的配送成本計(jì)算， 并基于此融合遺傳算法迭代尋優(yōu)的搜索方式完成對(duì)最佳路徑的搜索， 以此進(jìn)行避障和路徑尋優(yōu)目標(biāo)的實(shí)現(xiàn)， 使改善后的算法具有高效穩(wěn)定的全局搜索能力， 能有效完成車(chē)間復(fù)雜配送環(huán)境下的路徑搜索規(guī)劃.

1"遺傳算法及A*算法

1.1"遺傳算法

遺傳算法提供了一種求解復(fù)雜系統(tǒng)優(yōu)化問(wèn)題的通用框架， 具有較強(qiáng)的魯棒性， 在解決問(wèn)題時(shí)并不依賴(lài)問(wèn)題的領(lǐng)域， 在解決路徑規(guī)劃這類(lèi)問(wèn)題上遺傳算法應(yīng)用廣泛. 該算法常被應(yīng)用在函數(shù)優(yōu)化等領(lǐng)域， 函數(shù)優(yōu)化也是對(duì)遺傳算法進(jìn)行性能評(píng)價(jià)的常用算例.

在遺傳算法中， 將n維決策向量V=（v1，v2，…，vn）用若干個(gè)記號(hào)Vn（n為正整數(shù)）所組成的符號(hào)串n表示. 把每個(gè)Vn視為一個(gè)遺傳基因， 它的所有可能取值稱(chēng)為等位基因， 從而V即可視為由n個(gè)遺傳基因v所組成的一個(gè)染色體. 遺傳算法通過(guò)對(duì)染色體V的搜索完成對(duì)最優(yōu)解的搜索， 因而所有染色體V即組成了問(wèn)題的搜索空間. 遺傳算法最優(yōu)解的搜索是通過(guò)模擬自然界中生物進(jìn)化過(guò)程中染色體的基因變異以及染色體之間的交叉等過(guò)程實(shí)現(xiàn)的， 所以算法搜索尋優(yōu)過(guò)程是一個(gè)進(jìn)行反復(fù)迭代的過(guò)程. 在進(jìn)行具體操作時(shí)， 遺傳算法從第t代群體P（t）， 經(jīng)過(guò)一代遺傳和進(jìn)化后， 得到第（t+1）代群體P（t+1）. 這個(gè)群體不斷地經(jīng)過(guò)遺傳和進(jìn)化操作， 并按問(wèn)題求解的需求對(duì)遺傳算法產(chǎn)生的群體進(jìn)行篩選， 最終在該群體中得到一個(gè)最優(yōu)解^［8］.

1.2"A*算法

1.2.1"A*算法原理

A*算法搜索的核心是估價(jià)函數(shù)f（n）， 該核心函數(shù)主要由從初始狀態(tài)到當(dāng)前狀態(tài)的實(shí)際代價(jià)g（n）和從當(dāng)前狀態(tài)到目標(biāo)狀態(tài)的估計(jì)值， 即估計(jì)需經(jīng)過(guò)多少步才能到達(dá)目標(biāo)點(diǎn)h（n）構(gòu)成. 其中f（n）=g（n）+h（n）， 擴(kuò)展節(jié)點(diǎn)時(shí)， 先將所有節(jié)點(diǎn)的值從小到大排序， 然后對(duì)值較小的節(jié)點(diǎn)進(jìn)行擴(kuò)展.

在A*算法運(yùn)算過(guò)程中， 一般實(shí)際代價(jià)g（n）的數(shù)值是一定的， 因此A*算法評(píng)估函數(shù)的重點(diǎn)是對(duì)估計(jì)值h（n）的設(shè)計(jì). A*算法的運(yùn)算性能和搜索結(jié)果的產(chǎn)生極大程度受估計(jì)值h（n）的影響， 通過(guò)對(duì)估計(jì)值h（n）的有效設(shè)計(jì)可達(dá)到提升A*算法性能的目的. 本文采用節(jié)點(diǎn)a到目標(biāo)點(diǎn)b的歐氏直線距離定義h（n）可完全滿足上述估價(jià)函數(shù)值達(dá)到最小值的要求， 保證尋找到的路徑為最短路徑^［9］.

1.2.2"環(huán)境柵格化

配送物料車(chē)間的可通行區(qū)域?yàn)檫B續(xù)區(qū)域且存在各種類(lèi)型的障礙物， 障礙物的幾何形狀也各不相同. 為簡(jiǎn)化計(jì)算并提升尋徑效率， 配送物料車(chē)間可將連續(xù)可通行區(qū)域通過(guò)單元分解劃

分為單元， 既減少尋徑計(jì)算強(qiáng)度， 又確保尋徑結(jié)果的準(zhǔn)確性， 同時(shí)考慮障礙物的多樣性. 針對(duì)車(chē)間布局圖， 可構(gòu)建具有分辨精度的柵格網(wǎng)格模型， 將柵格劃分為可通行和不可通行狀態(tài)［10］. 當(dāng)存在障礙及障礙邊界空間時(shí)， 柵格的被占用率為100%， 用黑色表示； 當(dāng)不存在障礙及障礙邊界空間時(shí)， 柵格的被占用率為0， 用白色表示. 圖1為環(huán)境柵格化示意圖.

1.2.3"柵格環(huán)境下A*算法的搜索方式

為清晰地描述A*算法在柵格環(huán)境下搜索路徑的過(guò)程， 本文描述的A*算法搜索模型如圖2所示. 在柵格地圖中黑色表示障礙物， 藍(lán)色方格表示起始節(jié)點(diǎn)， 紅色方格表示終止節(jié)點(diǎn).

首先將起點(diǎn)放入開(kāi)放列表， 將可通行的相鄰節(jié)點(diǎn)加入開(kāi)放列表， 障礙物則放入關(guān)閉列表. 柵格單元包含實(shí)際路徑成本（左下）、 預(yù)計(jì)消耗成本（右下）和總路徑代價(jià)（左上）， 采用歐氏距離描述路徑. 在柵格環(huán)境下， A*算法通過(guò)計(jì)算相鄰節(jié)點(diǎn)， 選擇移動(dòng)代價(jià)最低的點(diǎn)為下一個(gè)節(jié)點(diǎn)， 并考慮轉(zhuǎn)角碰撞， 規(guī)劃繞障路徑. 路徑代價(jià)相同時(shí)， 算法隨機(jī)選擇路徑.

2"改進(jìn)A*算法

A*算法是一種應(yīng)用于連通圖的經(jīng)典搜索算法， 能在短時(shí)間內(nèi)完成靜態(tài)環(huán)境的路徑規(guī)劃. 但傳統(tǒng)的A*算法僅適用于障礙環(huán)境下從一個(gè)節(jié)點(diǎn)到另一個(gè)節(jié)點(diǎn)的路徑規(guī)劃， 而遺傳算法則能有效完成多點(diǎn)之間的路徑規(guī)劃. 如果能融合A*算法的避障尋徑能力和遺傳算法的多點(diǎn)路徑規(guī)劃能力， 則可能解決多目標(biāo)點(diǎn)車(chē)輛路徑規(guī)劃問(wèn)題. 改進(jìn)的A*算法吸取了這兩種算法的優(yōu)

點(diǎn)， 既考慮了現(xiàn)實(shí)避障的需求， 也保持了搜索的全面性和高效性.

2.1"融合遺傳算法的改進(jìn)A*算法

利用遺傳算法良好的全局搜索能力對(duì)A*算法進(jìn)行改進(jìn)， 設(shè)計(jì)一種遺傳A*算法， 在保障全局搜索穩(wěn)定的同時(shí)， 又能使算法適應(yīng)車(chē)間復(fù)雜的配送環(huán)境， 可以更好地完成路徑規(guī)劃.

改進(jìn)A*算法的流程如圖3所示.

由遺傳算法改進(jìn)的A*算法流程如下.

模塊1： 利用A*算法計(jì)算有障礙條件下各目標(biāo)點(diǎn)兩兩之間的距離.

步驟1） 對(duì)環(huán)境進(jìn)行柵格化處理， 記錄行進(jìn)路徑的目標(biāo)點(diǎn)V1，V2，…，Vn；

步驟2） 判斷各節(jié)點(diǎn)間距離是否完成， 若未完成則執(zhí)行步驟3）， 若完成則執(zhí)行步驟15）；

步驟3） 隨機(jī)挑選兩個(gè)節(jié)點(diǎn)， 記為起始節(jié)點(diǎn)和終止節(jié)點(diǎn)；

步驟4） 將起始節(jié)點(diǎn)放入開(kāi)放列表中（其中開(kāi)放列表是存放待檢查節(jié)點(diǎn)的表格）， 并計(jì)算評(píng)估函數(shù)f（n）、 起始點(diǎn)到節(jié)點(diǎn)實(shí)際代價(jià)g（n）以及從節(jié)點(diǎn)到目標(biāo)點(diǎn)最優(yōu)路徑的估計(jì)代價(jià)h（n）；

步驟5） 從開(kāi)放列表中選出并計(jì)算評(píng)估函數(shù)f（n）值最小的節(jié)點(diǎn)， 記為M點(diǎn)；

步驟6） 判斷當(dāng)前選取的節(jié)點(diǎn)是否為終止節(jié)點(diǎn)， 如果當(dāng)前節(jié)點(diǎn)是終止節(jié)點(diǎn)則記錄實(shí)際移動(dòng)的距離， 返回步驟2）進(jìn)行判斷；

步驟7） 如果當(dāng)前節(jié)點(diǎn)不是終止節(jié)點(diǎn)， 則將當(dāng)前節(jié)點(diǎn)移出開(kāi)放列表， 放入關(guān)閉列表中（關(guān)閉列表存放不需要被檢查的節(jié)點(diǎn)）， 并檢查臨近節(jié)點(diǎn)；

步驟8） 計(jì)算起始點(diǎn)到當(dāng)前節(jié)點(diǎn)的實(shí)際代價(jià)g（n）與當(dāng)前節(jié)點(diǎn)到臨近節(jié)點(diǎn)距離之和gt；

步驟9） 如果相鄰節(jié)點(diǎn)在關(guān)閉列表中且gt大于等于相鄰節(jié)點(diǎn)的實(shí)際代價(jià)g（n）， 則忽略該節(jié)點(diǎn)并重新尋找相鄰節(jié)點(diǎn)；

步驟10） 如果相鄰節(jié)點(diǎn)不滿足步驟9）的條件， 則判斷臨近節(jié)點(diǎn)是否在開(kāi)放列表或gt小于相鄰節(jié)點(diǎn)的實(shí)際代價(jià)g（n）， 若不滿足則忽略該節(jié)點(diǎn)并重新尋找相鄰節(jié)點(diǎn)；

步驟11） 如果滿足步驟10）的條件則置該節(jié)點(diǎn)為新的當(dāng)前節(jié)點(diǎn)M， 相鄰節(jié)點(diǎn)的g（n）=gt， 并計(jì)算評(píng)估函數(shù)f（n）和從節(jié)點(diǎn)到目標(biāo)點(diǎn)的最佳路徑的估計(jì)代價(jià)h（n）；

步驟12） 如果新的當(dāng)前節(jié)點(diǎn)不在開(kāi)放列表中， 則將其加入， 并返回步驟5）繼續(xù)操作， 通過(guò)步驟6）進(jìn)行判斷；

步驟13） 如果操作通過(guò)步驟6）的判斷， 則記錄實(shí)際移動(dòng)距離并通過(guò)步驟2）判斷上述各目標(biāo)點(diǎn)兩兩之間距離是否計(jì)算完畢， 如果完成計(jì)算， 則重復(fù)步驟3）的操作.

模塊2： 根據(jù)模塊1計(jì)算出的距離， 利用遺傳算法完成對(duì)最優(yōu)路徑的搜索.

步驟14） 如果滿足步驟13）， 則獲得D（Vi，Vj）， D（Vi，Vj）表示在有障礙條件下從地點(diǎn)i到地點(diǎn)j的距離， 繼續(xù)執(zhí)行如下步驟；

步驟15） 確定各項(xiàng)參數(shù)， 將種群初始化， 產(chǎn)生一個(gè)初始的路徑規(guī)劃編碼， 然后確定初始化種群的規(guī)模， 初始化種群的個(gè)體編碼為V1，V2，…，Vn；

步驟16） 計(jì)算適應(yīng)度函數(shù)， 根據(jù)步驟15）的種群順序依次移動(dòng)， 根據(jù)載具返回配送中心補(bǔ)

貨的情況對(duì)每個(gè)個(gè)體生成獨(dú)立的路徑軌跡編碼v1，v2，…，vn， 其中v1表示配送中心， 最終可表示為K1，K2，…，Kn；

步驟17） 選擇操作， 通過(guò)一個(gè)與適應(yīng)度值相關(guān)的概率（適應(yīng)度值越大則對(duì)應(yīng)的概率越大）選擇個(gè)體到新的種群；

步驟18） 交叉操作， 采用部分映射雜交；

步驟19） 變異操作；

步驟20） 進(jìn)化逆轉(zhuǎn)操作；

步驟21） 判斷， 如果不滿足迭代次數(shù)則執(zhí)行步驟16）， 如果滿足迭代次數(shù)則進(jìn)行解碼， 生成新種群擇優(yōu)選擇找出最佳個(gè)體對(duì)應(yīng)的路徑各點(diǎn)v的排序.

模塊3： 根據(jù)最優(yōu)路徑規(guī)劃方案， 完成有障礙條件下完整的路徑生成及計(jì)算.

步驟22） 根據(jù)最優(yōu)排序依次對(duì)各點(diǎn)排序， 按順序依次挑選兩點(diǎn)；

步驟23） 將起始節(jié)點(diǎn)放入開(kāi)放列表中（其中開(kāi)放列表是存放待檢查節(jié)點(diǎn)的表格）， 并計(jì)算評(píng)估函數(shù)f（n）、 起始點(diǎn)到節(jié)點(diǎn)的實(shí)際代價(jià)g（n）以及從節(jié)點(diǎn)到目標(biāo)點(diǎn)最優(yōu)路徑的估計(jì)代價(jià)h（n）；

步驟24） 從開(kāi)放列表中選出并計(jì)算評(píng)估函數(shù)f（n）值最小的節(jié)點(diǎn)M；

步驟25） 判斷當(dāng)前選取的節(jié)點(diǎn)是否為終止節(jié)點(diǎn)， 如果當(dāng)前節(jié)點(diǎn)是終止節(jié)點(diǎn)則回溯路徑， 記錄實(shí)際移動(dòng)的距離；

步驟26） 如果當(dāng)前節(jié)點(diǎn)不是終止節(jié)點(diǎn)， 則將當(dāng)前節(jié)點(diǎn)移出開(kāi)放列表， 放入關(guān)閉列表中（關(guān)閉列表存放不需要被檢查的節(jié)點(diǎn)）， 并檢查臨近節(jié)點(diǎn)， 如果是終止節(jié)點(diǎn)則轉(zhuǎn)步驟32）；

步驟27） 計(jì)算起始點(diǎn)到當(dāng)前節(jié)點(diǎn)的實(shí)際代價(jià)g（n）與當(dāng)前節(jié)點(diǎn)到臨近節(jié)點(diǎn)距離的和gt；

步驟28） 如果相鄰節(jié)點(diǎn)在關(guān)閉列表中， 且gt大于等于相鄰節(jié)點(diǎn)的實(shí)際代價(jià)g（n）， 則忽略該節(jié)點(diǎn)并重新尋找相鄰節(jié)點(diǎn)；

步驟29） 如果相鄰節(jié)點(diǎn)不滿足步驟28）的條件， 則判斷臨近節(jié)點(diǎn)是否在開(kāi)放列表中或gt小于相鄰節(jié)點(diǎn)的實(shí)際代價(jià)g（n）， 如果不滿足則忽略該節(jié)點(diǎn)并且重新尋找相鄰節(jié)點(diǎn)；

步驟30） 如果滿足步驟29）的條件則置該節(jié)點(diǎn)為新的當(dāng)前節(jié)點(diǎn)M， 相鄰節(jié)點(diǎn)的g（n）=gt， 并計(jì)算評(píng)估函數(shù)f（n）及從節(jié)點(diǎn)到目標(biāo)點(diǎn)最優(yōu)路徑的估計(jì)代價(jià)h（n）；

步驟31） 如果新的當(dāng)前節(jié)點(diǎn)不在開(kāi)放列表中， 則將其加入， 并返回步驟24）繼續(xù)操作， 通過(guò)步驟25）進(jìn)行判斷；

步驟32） 如果操作通過(guò)步驟25）的判斷， 則記錄回溯路徑并將實(shí)際的移動(dòng)距離相加， 判斷是否按步驟22）給出的順序完成訪問(wèn)所有的配送節(jié)點(diǎn)， 如果未完成則返回步驟22）， 按順序繼續(xù)依次選擇節(jié)點(diǎn)， 進(jìn)行操作， 如果訪問(wèn)完成配送節(jié)點(diǎn)則輸出規(guī)劃路徑， 計(jì)算路徑總長(zhǎng)度完成算法的路徑規(guī)劃.

2.2"柵格環(huán)境下A*算法搜索節(jié)點(diǎn)拓展原則

A*算法在搜索過(guò)程中需拓展搜索節(jié)點(diǎn)， 即節(jié)點(diǎn)拓展機(jī)制. 不同節(jié)點(diǎn)拓展機(jī)制會(huì)影響算法搜索的結(jié)果， 其中四鄰域搜索的每個(gè)搜索方向之間夾角都為90°， 易導(dǎo)致路徑轉(zhuǎn)折點(diǎn)過(guò)多， 搜索路徑的移動(dòng)成本偏高. 八鄰域搜索在四鄰域搜索的基礎(chǔ)上又增加了4個(gè)鄰域， 使搜索方向之間的夾角變?yōu)?5°， 優(yōu)化了搜索角度， 擴(kuò)大了搜索節(jié)點(diǎn)的范圍^［11］. 八鄰域的搜索方式在較復(fù)雜的地圖環(huán)境中易不精確， 忽略障礙物的存在. 節(jié)點(diǎn)的拓展方法如圖4所示.

四鄰域與八鄰域搜索各有局限， 本文結(jié)合實(shí)際需求， 采用混合策略： 遠(yuǎn)離障礙物時(shí)用八鄰域提升精度， 靠近障礙物時(shí)用四鄰域確保避障安全^［12］. 圖5為當(dāng)在障礙物附近和不在障礙物附近時(shí)， A*算法分別采取四鄰域搜索和八鄰域搜索的最終結(jié)果^［13］.

3"問(wèn)題建模

3.1"車(chē)間物料配送問(wèn)題描述

為驗(yàn)證本文算法有效性， 選擇某車(chē)間的配送問(wèn)題作為研究對(duì)象. 當(dāng)前該車(chē)間僅有一個(gè)物料配送中心， 物料配送中心有足夠的能力保障各物料需求點(diǎn)的物料需求； 車(chē)間內(nèi)物料需求點(diǎn)

的位置已知且固定， 各物料需求點(diǎn)單次物料需求量小于運(yùn)輸載具的最大載荷. 每個(gè)物料需求點(diǎn)僅需一輛配送載具進(jìn)行配送； 配送載具從配送中心出發(fā)， 完成本次配送任務(wù)后返回配送中心， 并接受下一次調(diào)度； 車(chē)間內(nèi)每條物料配送路徑上的載具能滿足該條配送路徑上的物料需求之和. 本文研究中， 在滿足各需求點(diǎn)物料供應(yīng)的前提下， 配送載具的總配送距離越短即認(rèn)為配送成本越低. 該車(chē)間柵格化后的情況如圖6所示.

3.2"車(chē)間物料配送規(guī)劃問(wèn)題模型

根據(jù)該車(chē)間具體問(wèn)題的描述， 本文的物料配送路徑規(guī)劃問(wèn)題模型如下：

目標(biāo)函數(shù)為

Z=min ∑Ni=0∑Nj=0∑Nk=1dijxijk，（1）

約束條件為

∑Ni=1miyik≤Q，"k=1，2，…，K，（2）∑Kk=1yik=1，"i=2，3，…，N，（3）

∑Kk=1y0k=K，（4）∑Kk=1∑Ni=1xi0k=K，（5）

其中： K為配送中心載具數(shù)量; Q為配送中心載具最大載荷; N為車(chē)間內(nèi)物料需求點(diǎn)數(shù); mi為第i個(gè)物料需求點(diǎn)的物料需求量; dij為載具從車(chē)間內(nèi)地點(diǎn)i到地點(diǎn)j的移動(dòng)距離; 若第k輛載具從地點(diǎn)i到地點(diǎn)j， 則xijk=1， 否則xijk=0; 若第k輛載具完成地點(diǎn)i的配送， 則yik=1， 否則yik=0. 上述公式表示了配送路徑問(wèn)題的限制， 其中式（2）表示每輛載具的配送路線上各需求點(diǎn)物料需求量之和不應(yīng)超過(guò)載具最大荷載量； 式（3）表示每個(gè)物料需求點(diǎn)只能由一輛載具完成配送， 配送服務(wù)僅一次完成； 式（4）表示所有載具僅從同一配送中心出發(fā)； 式（5）表示載具完成配送后返回同一配送中心.

在進(jìn)行實(shí)際搜索計(jì)算時(shí)， 為簡(jiǎn)化計(jì)算結(jié)構(gòu)， 載具的運(yùn)輸姿態(tài)不應(yīng)過(guò)度考慮在內(nèi)^［14］， 理想狀態(tài)下將載具視為一個(gè)質(zhì)點(diǎn)更方便計(jì)算， 但由于現(xiàn)實(shí)條件下存在運(yùn)輸載具的幾何尺寸限制，

在進(jìn)行區(qū)域劃分時(shí)應(yīng)注意運(yùn)輸單元的劃分大于載具的幾何尺寸， 避免實(shí)際應(yīng)用時(shí)載具無(wú)法通過(guò)構(gòu)建的可通行單元或發(fā)生碰撞^［15］. 可通行單元的尺寸a應(yīng)大于載具的最大尺寸l， 即

a≥max l.（6）

4"改進(jìn)A*算法應(yīng)用及性能分析

4.1"改進(jìn)A*算法應(yīng)用

根據(jù)圖6車(chē)間布局的特性， 對(duì)車(chē)間內(nèi)連續(xù)空間進(jìn)行劃分， 構(gòu)建一個(gè)52×52的模擬配送環(huán)境柵格圖， 對(duì)劃分好的柵格進(jìn)行編碼， 每個(gè)柵格通過(guò)向上取整進(jìn)行坐標(biāo)表達(dá)， 小柵格為白色表示可通過(guò)區(qū)域， 黑色表示不可通過(guò)區(qū)域， 圓點(diǎn)表示包括配送中心在內(nèi)的各配送節(jié)點(diǎn)^［16］. 建立車(chē)間布局圖的柵格模型如圖7所示.

根據(jù)建立的柵格模擬環(huán)境的特性及各配送點(diǎn)的物料需求量建立配送點(diǎn)的信息列于表1.

在算法開(kāi)始搜索前， 仍需對(duì)改進(jìn)A*算法的參數(shù)進(jìn)行設(shè)置， 改進(jìn)A*算法的重點(diǎn)參數(shù)設(shè)置如下： 柵格坐標(biāo)尺寸為52×52， 載具配送能力為1， 柵格尺寸比例為

1∶1， 交叉概率為0.9， 變異概率為0.05， 代溝參數(shù)為0.9， 種群規(guī)模為50×N（N為需求點(diǎn)數(shù)量）， 迭代次數(shù)為100×N（N為需求點(diǎn)數(shù)量）^［17］.

參數(shù)設(shè)立完成后， 利用改進(jìn)A*算法對(duì)車(chē)間內(nèi)配送路徑的搜索結(jié)果如圖8所示.

4.2"算法穩(wěn)定性驗(yàn)證

為驗(yàn)證算法的穩(wěn)定性， 本文對(duì)改進(jìn)A*算法進(jìn)行重復(fù)搜索運(yùn)算， 算法的各項(xiàng)主要指標(biāo)列于表2. 由于本文將車(chē)間內(nèi)物料配送路徑規(guī)劃任務(wù)轉(zhuǎn)換為利用算法對(duì)配送載具的最終移動(dòng)軌跡進(jìn)行規(guī)劃， 啟發(fā)式算法在搜索過(guò)程中會(huì)根據(jù)適應(yīng)度函數(shù)以一定的概率選擇搜索節(jié)點(diǎn)， 所以算法在搜素路徑時(shí)， 對(duì)總運(yùn)輸任務(wù)下的子任務(wù)（各小循環(huán)）的出發(fā)順序或出發(fā)方向（順時(shí)針或逆時(shí)針）會(huì)略有不同， 規(guī)劃路線經(jīng)過(guò)各點(diǎn)的順序也不相同， 但從配送任務(wù)的全局規(guī)劃角度， 若配送載具的最終移動(dòng)軌跡和經(jīng)過(guò)的軌跡長(zhǎng)度未發(fā)生變化， 則可認(rèn)為規(guī)劃結(jié)果相同， 表2中不同運(yùn)行次數(shù)給出的經(jīng)過(guò)各點(diǎn)順序不同， 但最終得到的路徑規(guī)劃結(jié)果卻始終一致， 算法的搜索結(jié)果均為211.15， 規(guī)劃路徑給出的路線軌跡相同， 說(shuō)明本文算法穩(wěn)定性較好.

由表2可見(jiàn)， 改進(jìn)A*算法的搜索時(shí)間穩(wěn)定且均未超過(guò)19 s， 算法的最大收斂代數(shù)為211次， 最小收斂代數(shù)為15次， 均未超過(guò)300次. 實(shí)驗(yàn)結(jié)果表明， 本文改進(jìn)的A*算法在

解決規(guī)劃配送路徑問(wèn)題上具有高效性. 相比于傳統(tǒng)A*算法， 利用遺傳算法改進(jìn)的A*算法可保持良好的全局搜索能力， 且實(shí)用效果較好， 因此改進(jìn)后的A*算法具有解決車(chē)間物料配送路徑規(guī)劃的能力.

綜上所述， 本文通過(guò)引入遺傳算法改進(jìn)傳統(tǒng)A*算法的路徑規(guī)劃方式， 解決了存在障礙物情況下的車(chē)間物料配送問(wèn)題. 在實(shí)際生產(chǎn)過(guò)程中， 充分考慮了車(chē)間內(nèi)部復(fù)雜的障礙環(huán)境， 采用柵格法對(duì)具有障礙限制條件的車(chē)間物料配送環(huán)境進(jìn)行離散化建模. 該方法不僅合理描述了環(huán)境， 還確保了算法能對(duì)車(chē)間環(huán)境進(jìn)行高效的路徑搜索. 同時(shí)， 利用遺傳算法的選擇、 交叉、 變異等操作， 增強(qiáng)了傳統(tǒng)A*算法的全局搜索能力， 使算法能精確且高效地完成有障礙環(huán)境下的路徑搜索及規(guī)劃任務(wù).

參考文獻(xiàn)

［1］"賈明超， 馮斌， 吳鵬， 等. 一種融合改進(jìn)A*算法與改進(jìn)動(dòng)態(tài)窗口法的文旅服務(wù)機(jī)器人路徑規(guī)劃 ［J］. 圖學(xué)學(xué)報(bào)， 2024， 45（3）： 505-515. （JIA M C， FENG B， WU P， et al. Path Planning for Cultural Tourism Service Robots Integrating Improved A* Algorithm and Enhanced Dynamic Window Approach ［J］. Journal of Graphics， 2024， 45（3）： 505-515.）

［2］"張涌， 成海飛， 趙奉奎. 基于自適應(yīng)A*算法的自動(dòng)駕駛車(chē)輛路徑規(guī)劃方法研究 ［J］. 重慶交通大學(xué)學(xué)報(bào)（自然科學(xué)版）， 2024， 43（2）： 115-121. （ZHANG Y， CHENG H F，

ZHAO F K. Research on Path Planning Method for Autonomous Vehicles Based on Adaptive A* Algorithm ［J］. Journal of Chongqing Jiaotong University （Natural Science Edition）， 2024， 43（2）： 115-121.）

［3］"王殿君. 基于改進(jìn)A*算法的室內(nèi)移動(dòng)機(jī)器人路徑規(guī)劃 ［J］. 清華大學(xué)學(xué)報(bào)（自然科學(xué)版），

2012， 52（8）： 1085-1089. （WANG D J. Path Planning for Indoor Mobile Robots B

ased on an Improved A* Algorithm ［J］. Journal of Tsinghua University （Science and Technology）， 2012， 52（8）： 1085-1089.）

［4］"SAMADI M， OTHMAN M F. Global Path Planning for Autonomous Mobile Robot Using Genetic Algorithm ［C］//International Conference on Signal-Image Technology amp; Internet-Based Systems. Piscataway， NJ： IEEE， 2014： 726-730.

［5］"TAHARWA A L. A Mobile Robot Path Planning Using Genetic Algorithm in Static Environment ［J］. Journal of Computerence， 2008， 4（4）： 341-344.

［6］"郝博， 秦麗娟， 姜明洋. 基于改進(jìn)遺傳算法的移動(dòng)機(jī)器人路徑規(guī)劃方法研究 ［J］. 計(jì)算機(jī)工程與科學(xué)， 2010， 32（7）： 104-107. （HAO B， QIN L J， JIANG M Y. Research on Path Planning Method for Mobile Robots Based on Improved Genetic Algorithm ［J］. Computer Engineering and Science， 2010， 32（7）： 104-107.）

［7］"劉玲， 王耀南， 況菲， 等. 基于神經(jīng)網(wǎng)絡(luò)和遺傳算法的移動(dòng)機(jī)器人路徑規(guī)劃 ［J］. 計(jì)算機(jī)應(yīng)用研究， 2007， 24（2）： 264-265. （LIU L， WANG Y N， KUANG F， et al. Path Planning for Mobile Robots Based on Neural Network and Genetic Algorithm ［J］. Application Research of Computers， 2007， 24（2）： 264-265.）

［8］"史峰， 王輝， 郁磊， 等. MATLAB智能優(yōu)化算法30個(gè)案例分析 ［M］. 北京： 北京航空航天大學(xué)出版社， 2012： 38-39. （SHI F， WANG H， YU L，

et al. 30 Case Studies of Intelligent Optimization Algorithms in MATLAB ［M］. Beijing： Beihang University Press， 2012： 38-39.）

［9］"黃琦. 履帶式無(wú)人車(chē)輛的路徑規(guī)劃方法研究 ［D］. 武漢： 武漢大學(xué)， 2018. （HUANG Q. Research on Path Planning Methods for Crawler-Type Unmanned Vehicles ［D］. Wuhan： Wuhan University， 2018.）

［10］"葉小艷， 鐘華鈞， 鄧可兒. 一種基于改進(jìn)A*算法的室內(nèi)導(dǎo)航路徑規(guī)劃方法 ［J］. 計(jì)算機(jī)技術(shù)與發(fā)展， 2022， 32（2）： 202-206. （YE X Y， ZHONG H J， DENG K E. An Indoor Navigation Path Planning Method Based on Improved A* Algorithm ［J］. Computer Technology and Development， 2022， 32（2）： 202-206.）

［11］"王淼弛. 基于A*算法的移動(dòng)機(jī)器人路徑規(guī)劃 ［D］. 沈陽(yáng)： 沈陽(yáng)工業(yè)大學(xué)， 2017

. （WANG M C. Path Planning for Mobile Robots Based on A* Algorithm ［D］. Shenyang： Shenyang University of Technology， 2017.）

［12］"張世清. 自動(dòng)化工廠的多AGV系統(tǒng)路徑規(guī)劃及調(diào)度機(jī)制研究 ［D］. 西安： 西京學(xué)

院， 2021. （ZHANG S Q. Research on Path Planning and Scheduling Mechanism of Multi-AGV System in Automated Factories ［D］. Xi’an： Xijing University， 2021.）

［13］"孫齊， 卞強(qiáng)， 童余德. 基于地磁匹配輔助導(dǎo)航的改進(jìn)A*算法路徑規(guī)劃［J］. 江蘇大學(xué)學(xué)報(bào)（自然科學(xué)版）， 2023， 44（6）： 696-703. （SUN Q， BIAN Q， TONG Y D. Path Planning of Improved A* "Algorithm Based on Geomagnetic Matching Aided Navigation［J］. Journal of Jiangsu University （Natural Science Edition）， 2023，44（6）： 696-703.）

［14］"李宇昊， 趙又群. 基于雙層控制策略的四輪獨(dú)立轉(zhuǎn)向無(wú)人駕駛汽車(chē)路徑跟蹤［J］. 江蘇大學(xué)學(xué)報(bào)（自然科學(xué)版）， 2022， 43（4）： 386-393.

（LI Y H， ZHAO Y Q. Path Tracking of 4WIS Autonomous Vehicle Based on Double-Layer Control Strategy［J］. Journal of Jiangsu University （Natural Science Edition），

2022， 43（4）： 386-393.）

［15］"李玉堂， 趙競(jìng)爭(zhēng)， 王民水， 等. 基于位置分配模型的避震疏散最優(yōu)路徑規(guī)劃［J］. 吉林大學(xué)學(xué)報(bào)（地球科學(xué)版）， 2023， 53（6）： 2018-2028. （LI Y T， ZHAO J Z， WANG M S， et al. Optimal Path Planning for Earthquake Evacuation Based on Location Assignment Model［J］. Journal of Jilin University （Earth Science Edition）， 2023， 53（6）： 2018-2028.）

［16］"劉仁云， 張美娜， 姚亦飛， 等. 一種新的全局排序高維多目標(biāo)優(yōu)化算法［J］. 吉林大學(xué)學(xué)報(bào)（理學(xué)版）， 2022， 60（3）： 664-670.

（LIU R Y， ZHANG M N， YAO Y F， et al. A Novel High-Dimensional Multi-objective Optimization Algorithm for Global Sorting［J］.

Journal of Jilin University （Science Edition）， 2022， 60（3）： 664-670.）

［17］"秦劍， 張飛凱， 張映輝， 等. 基于地理信息數(shù)據(jù)的貨運(yùn)索道選址及路徑規(guī)劃方法［J］. 吉林大學(xué)學(xué)報(bào)（地球科學(xué)版）， 2022， 52（6）： 2081-2088.

（QIN J， ZHANG F K， ZHANG Y H， et al. Location and Path Planning Method of Freight Ropeway Based on Geographic Information Data［J］.

Journal of Jilin University （Earth Science Edition）， 2022， 52（6）： 2081-2088.）

（責(zé)任編輯： 韓"嘯）