生產(chǎn)線物料配送的路徑優(yōu)化研究

黨立偉 孫小明

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

0 引言

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

1 問題描述

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

2 解決方案

2.1 單車輛的物料配送問題

首先研究單車輛的情況。因為只有一輛車，所以車輛總的裝卸貨時間是常數(shù)，求解的目標(biāo)可轉(zhuǎn)化為求車輛的最短行駛時間。一輛車要完成n個工位的物料配送，則最極端的情況是此輛車在工位和倉庫之間往返n次完成物料配送，因此假定車次數(shù)是n?；谏鲜龇治鼋⒘巳缦碌臄?shù)學(xué)模型。

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

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

本文采用商業(yè)優(yōu)化軟件Cplex對上述模型進(jìn)行求解。

2.2 改進(jìn)的遺傳算法

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

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

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

例如有10個工位需要物料配送，由車輛A和B為其服務(wù)，每輛車的容量是10，具體配送信息如圖1所示。染色體編碼表示工位2、5、3、7、4、6 由車輛 A 服務(wù)，車輛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 評價的目標(biāo)函數(shù)

本文選取總的配送時間作為目標(biāo)函數(shù)值，該目標(biāo)函數(shù)值包括車輛的行駛時間和物料的裝卸時間?？偟呐渌蜁r間越短，染色體的適應(yīng)度越好，染色體對應(yīng)的解越優(yōu)。每個染色體對應(yīng)的總的配送時間就是所有車輛中配送完成時間的最大值。

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

①計算種群的總的適應(yīng)度函數(shù)值F，其表達(dá)式為:

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

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

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

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

④ 生成一個隨機(jī)數(shù)r∈(0，1]。

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

2.2.3 交叉和變異

本文采用順序交叉法，兩個父代進(jìn)行交叉產(chǎn)生兩個子代，保證種群規(guī)模的不發(fā)生變化。具體的交叉過程如圖2所示。

圖2 交叉機(jī)制Fig.2 Crossover mechanism

變異操作能夠擴(kuò)大解的搜索空間，增強(qiáng)解的多樣性，避免解過早陷入局部最優(yōu)。本文采用反轉(zhuǎn)變異，具體實施過程如圖3所示。

圖3 變異機(jī)制Fig.3 Mutation mechanism

2.3 三階段啟發(fā)式算法

本文設(shè)計的啟發(fā)式算法分3個階段，每個階段建立了相應(yīng)的數(shù)學(xué)模型，運(yùn)用Cplex軟件對模型進(jìn)行求解。

①第一階段

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

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

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

②第二階段

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

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

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

③第三階段

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

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

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

3 算例分析

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

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

3.1 遺傳算法求解

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

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

3.2 三階段啟發(fā)式方法求解

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

表3 啟發(fā)式方法的計算結(jié)果Tab.3 Calculation result of heuristic method

3.3 兩種方法的比較

從以上計算可以看出，改進(jìn)的遺傳算法得到的目標(biāo)函數(shù)值是3 004 s，而三階段啟發(fā)式算法得到的目標(biāo)函數(shù)值是3 083 s，改進(jìn)的遺傳算法要優(yōu)于三階段啟發(fā)式算法;且三階段啟發(fā)式算法的計算速度優(yōu)于改進(jìn)的算法。

4 結(jié)束語

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

[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] 祁文祥，陸志強(qiáng)，孫小明.帶軟時間窗的集貨與送貨多車輛路徑問題節(jié)約算法[J].交通運(yùn)輸工程學(xué)報，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] 蔣麗，丁斌，臧曉寧.以工位為中心的生產(chǎn)物流配送優(yōu)化[J].計算機(jī)集成制造系統(tǒng)，2009，15(11):2154 －2159.

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