黨立偉 孫小明

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

0 引言

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

1 問題描述

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

2 解決方案

2.1 單車輛的物料配送問題

首先研究單車輛的情況。因?yàn)橹挥幸惠v車，所以車輛總的裝卸貨時(shí)間是常數(shù)，求解的目標(biāo)可轉(zhuǎn)化為求車輛的最短行駛時(shí)間。一輛車要完成n個(gè)工位的物料配送，則最極端的情況是此輛車在工位和倉庫之間往返n次完成物料配送，因此假定車次數(shù)是n。基于上述分析建立了如下的數(shù)學(xué)模型。

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

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

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

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

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

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

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

例如有10個(gè)工位需要物料配送，由車輛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 評(píng)價(jià)的目標(biāo)函數(shù)

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

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

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

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

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

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

③ 計(jì)算每個(gè)染色體Xh的累積概率密度

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

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

2.2.3 交叉和變異

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

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

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

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

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

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

①第一階段

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

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

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

②第二階段

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

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

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

③第三階段

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

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

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

3 算例分析

現(xiàn)有一條生產(chǎn)線由15個(gè)工位組成，工位和倉庫的信息如表1所示。倉庫中有3輛相同的車輛為這些工位進(jìn)行配送物料，車輛的最大容量是18，行駛速度是0.75 m/s，每單位物料的裝卸貨時(shí)間是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#編程實(shí)現(xiàn)，計(jì)算機(jī)共需要運(yùn)行296 s，計(jì)算結(jié)果如表2所示。車輛1需要完成兩個(gè)車次的配送，需要的配送時(shí)間是3 004 s;車輛2需要完成3個(gè)車次的配送，需要的配送時(shí)間是2 880 s;車輛3需要完成兩個(gè)車次的配送，需要的配送時(shí)間是2 916 s;完成所有工位的物料的配送取3輛車的最大值3 004 s。

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

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

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

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

3.3 兩種方法的比較

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

4 結(jié)束語

通過上述算例的計(jì)算，證明了算法能夠有效地解決生產(chǎn)線中物料的配送問題，提高物料配送的效率，防止生產(chǎn)線因?yàn)槲锪瞎?yīng)不及時(shí)而停頓，有效保證了流水線的連續(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)，孫小明.帶軟時(shí)間窗的集貨與送貨多車輛路徑問題節(jié)約算法[J].交通運(yùn)輸工程學(xué)報(bào)，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ì)算機(jī)集成制造系統(tǒng)，2009，15(11):2154 －2159.

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