葛能鵬，陳金蘭，吳利清

（湖南工業(yè)職業(yè)技術學院機械工程學院，湖南 長沙 410082）

0 引言

隨著柔性制造企業(yè)的不斷發(fā)展，生產(chǎn)模式也朝著多品種和小批量生產(chǎn)模式演變，這勢必會增加生產(chǎn)組織的難度，生產(chǎn)物料配送環(huán)節(jié)是車間制造過程的重要組成部分，如何快速地把生產(chǎn)物料通過AGV 小車配送至生產(chǎn)線邊對生產(chǎn)效率的提升有著重要的意義[1]。對于解決這類帶時間窗約束的車間物流路徑優(yōu)化問題，本文建立以配送成本為優(yōu)化目標的數(shù)學模型，提出一種改進的蟻群算法求解該問題，并與基本蟻群算法、遺傳算法等進行實驗對比，最終實驗結果表明本文提出的改進后的蟻群算法可以更好地解決帶時間窗的車間AGV 小車物流路徑優(yōu)化問題，以達到降低車間運輸?shù)奈锪鞒杀?、提高物流效率等目的[2]。

1 帶時間窗車間物流路徑優(yōu)化的數(shù)學模型

1.1 問題描述

帶時間窗車間AGV 小車物流路徑優(yōu)化問題可以描述為：存在M個貨物供應點，負責給N個生產(chǎn)崗位需求點配送貨物，每輛AGV 小車最大的運量為Q，每個貨物供應點最多可派遣的AGV 小車數(shù)量為Km（m= 1，2，…，M），每個客戶對貨物的需求都有時間窗要求[ETi，LTi]（i= 1，2，…，N），貨物必須要在生產(chǎn)崗位要求的時間內(nèi)送達，每個生產(chǎn)崗位的貨物需求量為Gi（i= 1，2，…，N），且每個生產(chǎn)崗位的需求量應小于單輛AGV 小車的運量，每個生產(chǎn)崗位都可以由任何一個貨物供應點供貨，要求設計一套合理的車間AGV 小車配送方案，在滿足各個客戶的前提下，使車間AGV 小車物流運輸成本最低或者運輸距離最短[3]。并且，存在以下多項約束條件：

（1）單個生產(chǎn)崗位的貨物需求量必須由同一輛AGV 小車完成配送，即不可多輛AGV 小車同時經(jīng)過一個需求點。

（2）車間由貨物供應點作為配送開始位置，經(jīng)過各個生產(chǎn)崗位后最后返回原來的貨物供應點。

（3）單個生產(chǎn)崗位的需求量不能超過AGV 小車的最大運量。

1.2 數(shù)學模型的建立

為了簡化模型的復雜度，設生產(chǎn)崗位的需求點的編碼為（1，2，…，N），貨物供應點的編碼為（N+ 1，N+2，…，N + M），定義變量表示供應點m的AGV 小車k是否從貨物需求點i行駛至貨物需求點j，若不行駛的值為0，否則的值為1[4]。

總行駛距離：

式中，Z為AGV 小車行駛的總路程。

目標函數(shù)：

式中，目標函數(shù)C是最小化成本，P為AGV 小車路徑單價成本。

約束條件為：

約束條件（4）～（9）中，式（4）表示車間AGV 小車行駛的開始位置和終點位置必須為所屬貨物供應點；式（5）和式（6）表示每個生產(chǎn)崗位需求點有且只能通過一個AGV 小車進行貨物配送；式（7）表示車間途徑各客戶的總需求量必須小于等于AGV 小車的最大運量；式（8）表示車間不能從貨物供應點直接行駛到供應點；式（9）表示車間到達生產(chǎn)崗位需求點時需在時間窗內(nèi)。

2 基于蟻群算法優(yōu)化配送路徑

2.1 傳統(tǒng)蟻群算法的求解模型

蟻群算法是由Marco Dorigo 提出，是一種模擬螞蟻覓食尋找最優(yōu)路徑的仿生算法，螞蟻在覓食的過程中會根據(jù)概率選擇一條路徑留下信息素，當某一路徑或者節(jié)點留下的信息素濃度越大，被選擇的概率就越大，因此螞蟻會根據(jù)信息素濃度最大的地方找到一條最佳的覓食路徑[5]。

2.2 蟻群算法的改進

2.2.1 種群個體編碼和解碼方案設計

（1）個體編碼方案：編碼是應用群體智能算法時要解決的首要問題，也是設計群體智能算法時的一個關鍵步驟。多中心物流配送路徑優(yōu)化問題是將已知的點通過不同的順序進行連接，以保證AGV 小車行駛路徑距離最短。以一個具有N個生產(chǎn)崗位需求點，M個貨物供應點，每個貨物供應點最多可派遣K輛AGV 小車的問題為例。將N個需求點分別標記為1，2，3，…，N-1，N；對于任意供應點的K輛AGV 小車標記為相同的編號，M個供應點的車間編號分別為N+1，N+2，N+3，…，N+M；故一個個體所具有的基因個數(shù)為N+M*K，其中編號小于等于N的基因代表需求點，大于N的基因代表不同供應點派遣的車間，如圖1 所示。將這些基因置亂即可得到不同的個體。

圖1 個體編碼方案

（2）個體解碼方案：如果需求點數(shù)N= 30，供應點數(shù)M= 2，每個供應點最多可派遣AGV 小車數(shù)K=5，每個個體的基因數(shù)為30 + 2 × 5 = 40，將該40 個基因位隨機置亂得到一個個體，如圖2 所示。1～30 的基因代表30 個“需求點基因”，31～32 的基因分別有5 個代表不同供應點派遣的“AGV 小車基因”。

圖2 隨機個體

以一個“AGV 小車基因”為起點，下一個“AGV 小車基因”的前一個基因為終點，即代表了一輛AGV 小車派遣路徑。以圖2 個體為例，從左往右，從上至下掃描各個基因位。一個“AGV 小車基因”為31，下一個“AGV 小車基因”為32，故第一輛AGV 小車的派遣路徑為{31}，因為沒有經(jīng)過需求點故舍棄；同理第二輛AGV 小車和第三輛AGV 小車的派遣路徑為{32}，舍棄；第四條{31}，舍棄；第五條{31-1-30-6-27-9-20-23-22-19}，保留，由于AGV 小車的派遣必須從起點出發(fā)最終回到原供應點，故完整的AGV 小車路線應為{31-1-30-6-27-9-20-23-22-19-31}，其中31 代表了1 號供應點。以此類推，最終可保留3 輛AGV 小車，其中供應點31 派遣1 輛AGV 小車，供應點22 派遣2 輛AGV 小車。

2.2.2 變異算子改進

本文在傳統(tǒng)蟻群算法的基礎上，對變異算子進行改進，加入擾動算法，該擾動算法輸入當前個體individual，輸出新個體newIndividual。此種擾動策略主要針對TSP 類的路徑優(yōu)化問題，TSP 問題的個體是Hamilton 回路，是一個需求點序列，而個體中的每一個基因表現(xiàn)為序列中相鄰的兩個需求點，通過兩個需求點組成的序列，就可以求得目標值。傳統(tǒng)鄰域擾動算子是隨機選擇兩個基因位r0，r1，然后進行調(diào)換位置，這會改變4 處的距離，分別是r0 位左右距離和r1位左右距離。而新策略的擾動只會改變2 處的距離，分別是r0 位左距離和r1 位右距離。采用此種策略的好處是，可以盡量降低一次的擾動程度，有利于局部搜索。如圖3 所示。

圖3 改進變異操作

2.2.3 交叉算子改進

本文在傳統(tǒng)蟻群算法的基礎上，對交叉算子進行改進，該算法與傳統(tǒng)的交叉操作不同，這里提出一種改進交叉操作。具體步驟是設定一個變異概率p，如圖4 所示，先在染色體中隨機選擇一個點G1，如G1=34。產(chǎn)生一個隨機小數(shù)，若小于p，則第二個點G2 來自同一個個體的另外一個任意點，如G2=54，然后點G1 和G2 之間的部分被倒置；若隨機小數(shù)大于p，則從種群中任意再選擇一個個體，找出G1=34 在該個體中，上一個位置的點，如下一個點G3=3，則回到原來的個體，點34 到3 之間被倒置。這種遺傳的思路在于，它能盡量利用種群中獲得的信息，來指引個體的變異或者導致操作，最后使得交叉算子比較高效。

圖4 改進遺傳操作

3 實例計算與仿真

將某柔性制造車間的AGV 小車物流配送作為測試背景條件，經(jīng)調(diào)查，該車間AGV 小車物料配送中心有2 個配送中心，20 個生產(chǎn)崗位需求點，每輛AGV小車的最大載荷量為800 kg，每個需求點的具體坐標、需求量及時間要求見表3。

表3 客戶點信息

使用遺傳算法、傳統(tǒng)蟻群算法和本文改進后的遺傳算法對該實例進行計算得到的最佳路徑及種群進化曲線如圖5、圖6、圖7 所示。

圖5 遺傳算法最佳路徑

圖6 傳統(tǒng)蟻群算法最佳路徑

圖7 改進蟻群算法最佳路徑

具體路徑情況見表4。

表4 最優(yōu)路徑對比表

三種算法的種群進化曲線對比如圖8 所示。從上述實驗的結果來看，相比于傳統(tǒng)的遺傳算法和蟻群算法，得到的AGV 小車最優(yōu)路徑總路程為373.47 km，優(yōu)于遺傳算法的392.91 km 和傳統(tǒng)蟻群算法的446.66 km，所以本文提出的改進后蟻群算法應用在帶有時間窗約束的AGV 小車物流路徑優(yōu)化問題上，可以得到不錯的使用效果。

圖8 三種算法的種群進化曲線對比

4 結語

針對帶時間窗約束的AGV 小車物流路徑優(yōu)化問題，本文建立以配送成本為優(yōu)化目標的數(shù)學模型，通過對傳統(tǒng)蟻群算法進行變異算子改進和交叉算子改進，提出一種改進的蟻群算法求解該問題。通過實例進行驗證，改進后的蟻群算法相比于傳統(tǒng)的遺傳算法和蟻群算法，可以更好地解決帶時間窗的柔性制造車間AGV 小車物流路徑優(yōu)化的問題，以達到降低物流成本、提高物流效率等目的。