生產線物料配送的路徑優化研究

黨立偉 孫小明

(上海交通大學機械與動力工程學院，上海 200240)

0 引言

自車輛路徑問題被Dantzig[1]提出后，引起了國內外學者的重視。目前很多學者對帶時間窗的多目標車輛路徑問題[2－4]和帶軟時間窗的車輛路徑問題[5－7]進行了研究，而有關生產線物料配送的研究比較少。Boysen[8]等研究了混流裝配線的物料準時化配送。蔣麗[9]等提出以工位為中心的物料配送方案，即將物料按照工位的需求進行分類存儲，并給出了車輛的配送方案。曹振新[10]等對混流裝配生產線上的物料配送問題進行了研究，設計了總裝車間的物料ANDON系統，在系統中設定了線旁物料的Max/Min值，當達到這個值時系統會自動報警，同時給出了物料斷點的處理流程。本文研究了如何運用有限的配送車輛對生產線所需要的物料進行準時配送。

1 問題描述

設一條生產線由n個工位組成，每個工位的物料需求量為qi(i=1，2，…，n)。倉庫擁有K輛容量相同的車，每輛車的容量為Q。每個工位的物料需求量不大于每輛車的容量，即qi≤Q，n個工位物料需求量之和大于K輛車的總容量，每工位所需要的物料被一輛車配送一次完成。車輛從同一倉庫出發對各個工位所需要的物料進行配送，倉庫與工位的距離矩陣為dij，車輛的行駛時間為t1，物料的裝卸時間為t2。由于物料的總需求量大于車輛的總容量，因此車輛需要進行多次配送才能完成配送任務。配送目標是合理安排車輛服務的工位及行車路徑，使物料配送的時間最短。

2 解決方案

2.1 單車輛的物料配送問題

首先研究單車輛的情況。因為只有一輛車，所以車輛總的裝卸貨時間是常數，求解的目標可轉化為求車輛的最短行駛時間。一輛車要完成n個工位的物料配送，則最極端的情況是此輛車在工位和倉庫之間往返n次完成物料配送，因此假定車次數是n。基于上述分析建立了如下的數學模型。

式中:k=1，2，…，n;1≤i≠j≤n。

式(3)表示目標函數，即總的配送時間包括車輛的行駛時間和物料的裝卸時間;式(4)表示每個車次裝的物料數量不能超過車輛的容量;式(5)表示每個工位只被一個車次服務;式(6)和式(7)表示車輛行駛的連續性;式(8)表示消除支路，保證車輛從倉庫出發最后回到倉庫;式(9)表示輔助變量。

本文采用商業優化軟件Cplex對上述模型進行求解。

2.2 改進的遺傳算法

對于多車輛的物料配送問題，總的配送時間就是所有車輛中配送時間的最大值，求解目標是使車輛的最大配送時間最小化。對此，本文提出了改進的遺傳算法。首先將工位分配到車輛，分配的原則是每輛車運送的物料數量基本相同，則所需要的裝卸貨時間也就相同了，只需要對車輛的行駛時間進行優化即可，此問題就轉化為了單車輛的物料配送問題。

2.2.1 初始解的生成本文運用自然數進行編碼，具體的編碼過程如下。①根據每輛車配送物料數量基本相同的原則，將工位分配給車輛。

②將每輛車所服務的工位代入到單車輛的物料配送模型中，運用Cplex軟件進行求解，確定每輛車所要配送的次數、每次配送的工位次序和配送的時間。

例如有10個工位需要物料配送，由車輛A和B為其服務，每輛車的容量是10，具體配送信息如圖1所示。染色體編碼表示工位2、5、3、7、4、6 由車輛 A 服務，車輛A需要往返兩次，第一次配送工位2、5、3，配送的次序是2→5→3，第二次配送7、4、6，配送的次序是7→4→6;車輛B只需要配送一次，配送的工位次序是 8→1→9→10。

圖1 配送信息Fig.1 Delivery information

2.2.2 評價的目標函數

本文選取總的配送時間作為目標函數值，該目標函數值包括車輛的行駛時間和物料的裝卸時間。總的配送時間越短，染色體的適應度越好，染色體對應的解越優。每個染色體對應的總的配送時間就是所有車輛中配送完成時間的最大值。

本文采用輪盤賭策略選擇染色進行交叉和變異。假設種群的規模是psize，具體的選擇過程如下。

①計算種群的總的適應度函數值F，其表達式為:

式中:eval(Xh)為第Xh個染色體的適應度函數值，即配送的總時間。

②計算每個染色體Xh被選擇的概率Ph，其表達式為:

式中:h=1，2，…，psize。

③ 計算每個染色體Xh的累積概率密度

④ 生成一個隨機數r∈(0，1]。

⑤ 如果qh－1＜r≤qh，則選取染色體Xh進行遺傳操作。

2.2.3 交叉和變異

本文采用順序交叉法，兩個父代進行交叉產生兩個子代，保證種群規模的不發生變化。具體的交叉過程如圖2所示。

圖2 交叉機制Fig.2 Crossover mechanism

變異操作能夠擴大解的搜索空間，增強解的多樣性，避免解過早陷入局部最優。本文采用反轉變異，具體實施過程如圖3所示。

圖3 變異機制Fig.3 Mutation mechanism

2.3 三階段啟發式算法

本文設計的啟發式算法分3個階段，每個階段建立了相應的數學模型，運用Cplex軟件對模型進行求解。

①第一階段

根據工位的需求信息和車輛的容量，計算出車次的分配方案。此階段的目標函數是最小化車次數，給出每個車次配送的具體工位，將此配送方案作為第二階段輸入，數學模型如下。

式中:qi為工位的物料需求;i=1，2，…，n;Q為車輛的容量限制。

式(12)表示從倉庫派出的車次數最少;式(13)表示每個工位需要一個車次為其提供物料;式(14)表示每個車次配送的物料數量不能超過車輛的容量限制。

②第二階段

對第一階段車次的分配方案進行優化，優化的目標是使每個車次的行駛時間最短，求出每個車次對所服務的工位進行配送的先后次序;并將此車次的行駛時間和裝卸貨時間進行合并，求出此車次的配送完成時間作為第三階段的輸入。

式中:i=0，1，…，l;j=0，1，…，l;R?{1，2，…，l}。

式(15)表示目標函數求車次的行駛時間最短;式(16)和式(17)表示每個工位只需要一個車次為其服務;式(18)表示消除支路;式(19)表示決策變量的取值。

③第三階段

對車次進行合并，用有限的車輛完成所有車次的配送，要求車輛中最大的配送時間最小。設R={R1，R2，…，Rm}，表示 m 個車次的集合;K={K1，K2，…，Kk}表示k(k≥2)輛車的車輛集合;車次Ri的配送完成時間為 Ti(i=1，2，…，m)。Ci(i=1，2，…，k)表示第i輛車的配送完成時間，表示總的配送完成時間，表示最優方案的總的配送完成時間。

式中:i=1，2，…，m;j=1，2，…，k。

式(20)表示目標函數，要求總的配送完成時間最短;式(21)表示每個車次只需一輛車完成配送;式(22)表示每輛車配送完成時間;式(23)表示決策變量。

3 算例分析

現有一條生產線由15個工位組成，工位和倉庫的信息如表1所示。倉庫中有3輛相同的車輛為這些工位進行配送物料，車輛的最大容量是18，行駛速度是0.75 m/s，每單位物料的裝卸貨時間是60 s。

表1 工位和倉庫的信息Tab.1 Information of work positions and inventories

3.1 遺傳算法求解

設遺傳算法求解的參數為:psize=30，MAXGEN=100，PXOVER=0.8，PMUTATION=0.1。采用 Visual C#編程實現，計算機共需要運行296 s，計算結果如表2所示。車輛1需要完成兩個車次的配送，需要的配送時間是3 004 s;車輛2需要完成3個車次的配送，需要的配送時間是2 880 s;車輛3需要完成兩個車次的配送，需要的配送時間是2 916 s;完成所有工位的物料的配送取3輛車的最大值3 004 s。

表2 遺傳算法計算結果Tab.2 Calculation result of genetic algorithm

3.2 三階段啟發式方法求解

采用三階段啟發式方法在Cplex平臺上對此算例進行求解，計算機共需要運行28 s。第一階段計算得到完成配送至少需要6個車次;第二階段計算得到每個車次的最小的配送時間及每個車次的配送工位的次序;第三個階段對車次進行了合并，每輛車需要完成兩個車次的配送，車輛完成所有的物料配送所需要的最短配送時間是3 083 s。三階段的計算結果如表3所示。

表3 啟發式方法的計算結果Tab.3 Calculation result of heuristic method

3.3 兩種方法的比較

從以上計算可以看出，改進的遺傳算法得到的目標函數值是3 004 s，而三階段啟發式算法得到的目標函數值是3 083 s，改進的遺傳算法要優于三階段啟發式算法;且三階段啟發式算法的計算速度優于改進的算法。

4 結束語

通過上述算例的計算，證明了算法能夠有效地解決生產線中物料的配送問題，提高物料配送的效率，防止生產線因為物料供應不及時而停頓，有效保證了流水線的連續性生產。

[1] Dantzig G B，Ramser J H.The truck dispatching problem[J].Management Science，1959(6):80 －91.

[2] Ghoseiri K，Ghannadpour S F.Multi-objective vehicle routing problem with time windows using goal programming and genetic algorithm[J].Applied Soft Computing，2010，10(4):1096 －1107.

[3] Donati A V，Roberto M，Norman C，et al.Time dependent vehicle routing problem with a multi ant colony system[J].European Journal of Operational Research，2008，185(3):1174 －1191.

[4] Anbuudayasankar S，Ganesh K，Lenny K S C，et al.Modified savings heuristics and genetic algorithm for bi-objective vehicle routing problem with forced backhauls[J].Expert Systems with Applications，2012，39(3):2296－2305.

[5] Qureshi A G，Taniguchi E，Yamada T.Exact solution for the vehicle routing problem with semi soft time windows and its application[J].Procedia-Social and Behavioral，2010，2(3):5931 －5943.

[6] Müller J.Approximative solutions to the bicriterion Vehicle routing problem with time windows[J].European Journal of Operational Research，2010，202(1):223 －231.

[7] 祁文祥，陸志強，孫小明.帶軟時間窗的集貨與送貨多車輛路徑問題節約算法[J].交通運輸工程學報，2010，10(4):99 －103.

[8] Boysen N，Bock S.Scheduling just-in-time part supply for mixedmodel assembly lines Original Research[J].European Journal of Operational Research，2011，211(1):15 －25.

[9] 蔣麗，丁斌，臧曉寧.以工位為中心的生產物流配送優化[J].計算機集成制造系統，2009，15(11):2154 －2159.

[10] 曹振新，朱云龍.混流轎車總裝配線上物料配送的研究與實踐[J].計算機集成制成造系統，2006，12(2):285－291.