基于軟時(shí)間窗的車(chē)間物料配送調(diào)度優(yōu)化研究

李加玲，錢(qián)吳永

（江南大學(xué) 商學(xué)院，江蘇 無(wú)錫 214122）

基于軟時(shí)間窗的車(chē)間物料配送調(diào)度優(yōu)化研究

李加玲，錢(qián)吳永

（江南大學(xué) 商學(xué)院，江蘇 無(wú)錫 214122）

實(shí)際生產(chǎn)中車(chē)間內(nèi)部工位物料需求存在一些不確定性問(wèn)題，基于軟時(shí)間窗的概念提出車(chē)間內(nèi)部物料配送調(diào)度優(yōu)化的方法。在已給定的假設(shè)基礎(chǔ)上，研究帶有時(shí)間窗的車(chē)間物料配送問(wèn)題，將配送總時(shí)間最短作為目標(biāo)函數(shù)，建立關(guān)于車(chē)間物料配送調(diào)度的數(shù)學(xué)模型，采用一種改進(jìn)的遺傳算法對(duì)模型求解，得到車(chē)間物料配送的最佳路徑。最后通過(guò)實(shí)例驗(yàn)證該模型的有效性。

物料配送；軟時(shí)間窗；遺傳算法；調(diào)度優(yōu)化

1 引言

近年來(lái)，企業(yè)生產(chǎn)智能化水平逐漸提高，制造企業(yè)間的競(jìng)爭(zhēng)日趨激烈。客戶的需求出現(xiàn)“多樣化、小眾化、個(gè)性化”的發(fā)展趨勢(shì)，為了適應(yīng)這種變化趨勢(shì)，多品種小批量的生產(chǎn)模式日趨引起關(guān)注和重視。這一變化增加了對(duì)產(chǎn)品制造柔性的要求，也對(duì)車(chē)間物料配送提出了新要求。一方面，多品種小批量生產(chǎn)產(chǎn)品種類(lèi)多，數(shù)量少，導(dǎo)致了物料的數(shù)量不易控制，引起了廣大學(xué)者對(duì)車(chē)間內(nèi)部物料流關(guān)注，尤其是物料配送方面的研究。李晉航建立模糊信息條件下的機(jī)會(huì)約束規(guī)劃模型，采用啟發(fā)式算法處理不確定因素，提高物料配送的可行性和高效性[1]。劉明周基于生產(chǎn)計(jì)劃、節(jié)拍、庫(kù)存等不確定因素，構(gòu)建RTMADS系統(tǒng)，闡述系統(tǒng)架構(gòu)，對(duì)物料配送各環(huán)節(jié)數(shù)據(jù)實(shí)時(shí)監(jiān)控[2]。凌琳考慮制造工位的生產(chǎn)能力與生產(chǎn)負(fù)荷間的關(guān)系，用兩者比值表征物料配送的迫切度，構(gòu)建改進(jìn)的時(shí)變的物料配送路徑模型，并考慮將物料拆分配送，提高配送效率[3]。

另一方面，工位物料需求時(shí)間的不固定，吸引了不少?lài)?guó)內(nèi)外的學(xué)者聚焦于車(chē)間內(nèi)部帶時(shí)間窗的物料配送工位需求的研究。車(chē)間內(nèi)部工位需求的問(wèn)題相當(dāng)于是縮小的車(chē)輛路徑問(wèn)題，將車(chē)輛路徑的研究范圍縮小到車(chē)間內(nèi)部。antzig和Ramser（1959）對(duì)帶時(shí)間窗的車(chē)輛路徑問(wèn)題（vehicle routing problems with time windows，VRPTW）進(jìn)行了研究。此后，許多研究人員對(duì)車(chē)輛路徑問(wèn)題展開(kāi)了較為系統(tǒng)的研究，構(gòu)建各種優(yōu)化模型，用優(yōu)化的智能算法對(duì)模型進(jìn)行求解應(yīng)用。Muller運(yùn)用兩階段啟發(fā)式算法，結(jié)合新型遺傳模擬退火算法，研究帶時(shí)間窗的車(chē)輛調(diào)度，并考慮違反時(shí)間窗的懲罰函數(shù)，控制總成本最小[4]。王旭坪等將時(shí)間窗的處理模糊化，用物料配送起始時(shí)間的模糊隸屬度函數(shù)將顧客服務(wù)的滿意度量化。建立模糊時(shí)間窗的車(chē)輛配送模型并通過(guò)實(shí)例驗(yàn)證模型在維持顧客服務(wù)水平、節(jié)省企業(yè)資源等方面的有效性[5]。BANOS等基于平行多目標(biāo)模擬退火遺傳算法來(lái)解決帶時(shí)間窗的車(chē)輛調(diào)度問(wèn)題，考慮了最大限度地減少車(chē)輛的行駛距離和線路的不合理多目標(biāo)約束并構(gòu)建模型，采用實(shí)證驗(yàn)證模型的有效性[6]。Kilic考慮帶有軟時(shí)間的車(chē)輛路徑問(wèn)題時(shí)，構(gòu)建一個(gè)模糊規(guī)劃處理顧客的偏好以及最新交貨時(shí)間公差，更易權(quán)衡分銷(xiāo)商的效率和反應(yīng)譜[7]。章勛宏等對(duì)考慮零件三維裝載約束帶時(shí)間窗的循環(huán)取貨路徑問(wèn)題展開(kāi)研究，建立多目標(biāo)數(shù)學(xué)模型，大幅提高可裝載性，減少不同車(chē)型車(chē)輛的投入[8]。也有研究人員將車(chē)輛路徑問(wèn)題引入到制造車(chē)間內(nèi)部物料配送方面，研究車(chē)間內(nèi)部物料配送，保持高效運(yùn)作，節(jié)約時(shí)間和成本，提高車(chē)間的生產(chǎn)率。如Androutsopoulos主要考慮危險(xiǎn)材料的路徑調(diào)度決策，假設(shè)成本和風(fēng)險(xiǎn)隨時(shí)間變化，提出路徑的調(diào)度問(wèn)題涉及測(cè)定非支配時(shí)變路徑和在規(guī)定的時(shí)間窗內(nèi)為客戶提供中間站服務(wù)，討論了解決這類(lèi)問(wèn)題的兩種算法[9]。Gao Gui-bing等構(gòu)造了混合制造系統(tǒng)中的物料配送路徑問(wèn)題的多目標(biāo)模型，采用混合多目標(biāo)進(jìn)化算法求解，通過(guò)實(shí)際案例研究表明，該模型可以減少總行駛距離，提高車(chē)輛的平均負(fù)載率[10]。嚴(yán)正峰等提出模糊軟時(shí)間窗的概念，在此概念基礎(chǔ)上研究車(chē)間物料流路徑優(yōu)化方法，主要以工位為中心安排物料配送，建立帶軟時(shí)間窗的物料配送路徑優(yōu)化模型，結(jié)合智能算法求解[11]。Simic等介紹了關(guān)于物流配送的車(chē)輛路徑問(wèn)題的建模與優(yōu)化，建立一種新的混合模型，運(yùn)用包括遺傳和螢火蟲(chóng)算法求解得到實(shí)驗(yàn)結(jié)果，并與真實(shí)數(shù)據(jù)比較，驗(yàn)證模型求解的結(jié)果更好[12]。

現(xiàn)有文獻(xiàn)中對(duì)物料配送的研究，主要包括物料的管理控制、配送路徑優(yōu)化等方面，而車(chē)輛路徑問(wèn)題的研究主要集中在較大型的物流運(yùn)輸方面，從成本、時(shí)間以及行駛路程等角度考慮，尋找最優(yōu)路徑。近年來(lái)，有學(xué)者開(kāi)始將宏觀的車(chē)輛路徑問(wèn)題的研究方法和思路應(yīng)用到制造業(yè)內(nèi)部物料流分析中，主要研究制造業(yè)內(nèi)部物料配送路徑問(wèn)題，求解制造業(yè)內(nèi)部物料配送的最優(yōu)路徑，縮短時(shí)間，提高生產(chǎn)效率。本文基于現(xiàn)有的研究，結(jié)合軟時(shí)間窗的概念，將車(chē)輛路徑問(wèn)題用到車(chē)間內(nèi)部物料配送上，以時(shí)間最小化為目標(biāo)，同時(shí)考慮到物料在時(shí)間窗之外到達(dá)時(shí)，構(gòu)建相應(yīng)的懲罰函數(shù)。本文將時(shí)間最短作為目標(biāo)函數(shù)，尋找最優(yōu)的車(chē)間物料配送路徑，是考慮到車(chē)間內(nèi)部的物料運(yùn)輸通常都是用叉車(chē)運(yùn)輸，且每條路徑行駛的路程較短、差距較小，所需成本差別也較小，可以忽略。所以選擇時(shí)間最小化為目標(biāo)是更加符合車(chē)間內(nèi)部物料運(yùn)輸?shù)膶?shí)際情況。

2 模型構(gòu)建

2.1 問(wèn)題的描述

關(guān)于車(chē)間內(nèi)部物料流的車(chē)輛路徑問(wèn)題的描述：車(chē)間內(nèi)部各工位所需要的物料都儲(chǔ)存在統(tǒng)一的倉(cāng)庫(kù)，這里稱(chēng)之為物料超市，工位所需物料都由物料超市負(fù)責(zé)運(yùn)輸配送，由k個(gè)承載量為q的車(chē)輛負(fù)責(zé)將物料配送到需要的各工位，車(chē)間內(nèi)有N個(gè)工位，各工位上所需的物料要在時(shí)間窗之間被送到。考慮到物料有可能會(huì)在時(shí)間窗之外被送達(dá)，本文基于軟時(shí)間窗的車(chē)間物料配送調(diào)度進(jìn)行研究，如果物料不在規(guī)定的時(shí)間窗之內(nèi)送達(dá)，建立相應(yīng)的懲罰函數(shù)。考慮到車(chē)間內(nèi)部物料的配送都是以叉車(chē)為主，且車(chē)間內(nèi)部的行駛距離較短，因此，車(chē)輛的油耗差距小，當(dāng)叉車(chē)的速度一定時(shí)，若配送時(shí)間短，則車(chē)子的行駛距離就短，且人力的消耗最小，因此，可以將車(chē)間內(nèi)部物料配送路徑優(yōu)化問(wèn)題轉(zhuǎn)化為求車(chē)間內(nèi)物料配送時(shí)間最短的車(chē)輛行駛路徑。

2.2 工位物料配送模型假設(shè)與約束條件

2.2.1 假設(shè)條件。為了使研究問(wèn)題更加明確，現(xiàn)對(duì)模型做如下假設(shè)：

物料超市所提供的物料種類(lèi)、數(shù)量等信息已知，各工位所需要的物料品種、數(shù)量也已知。且配送到各工位的物料都是由一個(gè)物料超市負(fù)責(zé)提供。

各工位所需的物料量之和不超過(guò)物料超市的儲(chǔ)存量。

物料超市到每個(gè)工位的距離、各工位之間的距離均已知。

假定車(chē)輛的行駛速度已知且勻速行駛，因此派出取物料的車(chē)輛在各工位節(jié)點(diǎn)之間以及物料超市到各工位的行駛時(shí)間可以直接求出。

2.2.2 約束條件。（1）物料配送時(shí)，車(chē)輛從物料超市出發(fā)到各工位進(jìn)行物料配送，當(dāng)車(chē)輛重新回到物料超市表示一個(gè)物料配送路徑結(jié)束。

（2）根據(jù)物料需求將工位分為多個(gè)工位組，一輛車(chē)對(duì)一個(gè)工位組所需要的物料進(jìn)行一次或多次配送。

（3）一個(gè)工位組需要的所有物料都儲(chǔ)存在一個(gè)物料超市里，而一個(gè)物料超市可以?xún)?chǔ)存多個(gè)工位組需要的物料。

（4）一個(gè)工位組所需要的物料由一輛車(chē)負(fù)責(zé)配送。

（5）一個(gè)工位組一次所需要的物料量不能超過(guò)一個(gè)物料超市的最大儲(chǔ)存量。

（6）每輛車(chē)的行駛距離須在其規(guī)定的最大行駛距離之內(nèi)。

2.3 參數(shù)符號(hào)

（1）已知量

i,j∈N：表示需要被服務(wù)的工位的編號(hào)；

k：表示負(fù)責(zé)配送的車(chē)輛的編號(hào)；

ti：車(chē)輛到達(dá)服務(wù)的工位的時(shí)間；

te：物料配送到達(dá)工位的時(shí)間窗的開(kāi)始時(shí)間；

tl：物料配送到達(dá)工位的時(shí)間窗的結(jié)束時(shí)間；

wi：為服務(wù)工位i所需要的等待時(shí)間；

si：在工位i裝卸貨的服務(wù)時(shí)間；

dij：工位i到工位j之間的距離；

v：車(chē)輛的平均行駛速度；

Q：車(chē)輛的最大載重量；

L：車(chē)輛行駛的最大距離；

M,N：工位組的編碼；

qik：車(chē)輛需k要向工位i配送的物料量。

（2）決策變量。為了方便物料配送模型建立與求解，根據(jù)車(chē)間內(nèi)部物料配送的實(shí)際情況對(duì)模型做了一些簡(jiǎn)化處理，如下：

2.4 模型建立

多品種小批量制造車(chē)間的物料配送調(diào)度主要研究的是物料配送效率的提高，主要反映在如何優(yōu)化求解可以使得一次物料配送的總時(shí)間最短。若車(chē)輛在提前或滯后到達(dá)工位，建立懲罰函數(shù)如下：

其中α，β是車(chē)輛在時(shí)間窗之前和在時(shí)間窗之后到達(dá)的懲罰因子是指車(chē)輛在時(shí)間窗之前和時(shí)間窗之后到達(dá)工位的不滿意度。

根據(jù)以上分析構(gòu)建的從物料超市到工位物料配送時(shí)間最短的目標(biāo)函數(shù)如下：

其中：

在上述表達(dá)式中，公式（2）為所構(gòu)模型的目標(biāo)函數(shù)，完成物料配送的總的服務(wù)時(shí)間最短為目標(biāo)函數(shù)。主要由四部分組成是車(chē)輛行駛時(shí)間（從物料超市到各工位）是求在物料超市排貨、揀貨、裝卸貨的等待時(shí)間是在工位站點(diǎn)裝卸貨物的服務(wù)時(shí)間；pi(ti)是車(chē)輛在超出工位規(guī)定的時(shí)間窗達(dá)到工位的一個(gè)懲罰函數(shù)，如果車(chē)輛在工位設(shè)定的時(shí)間窗之內(nèi)到達(dá)，懲罰函數(shù)pi(ti)為0，到達(dá)時(shí)間在工位設(shè)定的時(shí)間窗之外時(shí)則考慮懲罰函數(shù)。其中α，β是車(chē)輛在時(shí)間窗之前和在時(shí)間窗之后到達(dá)的懲罰因子。如果車(chē)輛在工位設(shè)定的時(shí)間窗之前到達(dá)，其懲罰函數(shù)為如果車(chē)輛在工位設(shè)定的時(shí)間窗之后到達(dá)，其懲罰函數(shù)為

約束（4）保證每個(gè)工位上到達(dá)的車(chē)輛和離開(kāi)的車(chē)輛的數(shù)量相等。約束（5）表示的是工位時(shí)間窗的限制，即工位可接受的物料到達(dá)的時(shí)間范圍。約束（6）約束的是所有物料的配送需要在一定的時(shí)間內(nèi)完成。約束（7）是車(chē)輛從工位i到工位j的過(guò)程中，對(duì)其服務(wù)時(shí)間前后的約束。約束（8）保證車(chē)輛的裝載量在其最大載荷之內(nèi)。約束（9）是限制車(chē)輛的行駛距離須在其規(guī)定的最大行駛距離之內(nèi)。

傳統(tǒng)的路徑優(yōu)化模型一般都是在大型的物流運(yùn)輸中的，構(gòu)建目標(biāo)函數(shù)時(shí)都是以成本最小化為目標(biāo)，也有以成本、時(shí)間為目標(biāo)構(gòu)建多目標(biāo)函數(shù)的。本文所構(gòu)建的模型是針對(duì)車(chē)間內(nèi)部物料流的，車(chē)間內(nèi)部物料運(yùn)輸都是叉車(chē)運(yùn)輸，其各路徑的行駛路程較短且接近，人力成本、能源消耗相差都較小，所以以成本最小化為目標(biāo)函數(shù)不太符合實(shí)際情況。本文在構(gòu)建模型時(shí)之所以選擇時(shí)間最小化作為目標(biāo)函數(shù)，是因?yàn)闀r(shí)間對(duì)于車(chē)間內(nèi)部物料配送而言較重要，物料到達(dá)工位的時(shí)間對(duì)生產(chǎn)會(huì)有很大的影響，提前和延后都會(huì)對(duì)生產(chǎn)線產(chǎn)生影響，只有在規(guī)定的時(shí)間窗之內(nèi)到達(dá)才是最佳的。因此，對(duì)在時(shí)間窗之外達(dá)到的物料構(gòu)建了相應(yīng)的時(shí)間懲罰函數(shù)，更加符合車(chē)間內(nèi)部物料配送的實(shí)際情況。

3 模型求解

本文的研究主要是制造業(yè)內(nèi)部物料流的物料配送調(diào)度問(wèn)題，該問(wèn)題的關(guān)鍵是確定從物料超市到工位組的路線安排，考慮帶有軟時(shí)間窗的車(chē)間內(nèi)部物料的配送，在物料儲(chǔ)存確定的基礎(chǔ)上，將物料配送調(diào)度問(wèn)題轉(zhuǎn)化為一個(gè)時(shí)間最短問(wèn)題，尋找最優(yōu)的車(chē)間內(nèi)部物料配送路徑。解決這類(lèi)問(wèn)題最常用的方法就是建立相應(yīng)的目標(biāo)函數(shù)，用遺傳算法等智能算法對(duì)目標(biāo)函數(shù)求解，得到最優(yōu)的物料配送路徑。

遺傳算法求解帶時(shí)間窗約束的車(chē)間內(nèi)部物料配送路徑的步驟如下：

STEP1：構(gòu)造滿足上述模型中約束條件的路徑染色體。由于解空間中的解遺傳算法不能直接處理，要通過(guò)編碼用適當(dāng)?shù)娜旧w將解表示出來(lái)。對(duì)于實(shí)際問(wèn)題，染色體的編碼方式多種多樣，在選取染色體的編碼方式時(shí)應(yīng)選取符合約束條件的，否則會(huì)影響計(jì)算。

本文求解的是帶時(shí)間窗的VRP問(wèn)題，采用實(shí)數(shù)編碼是求解時(shí)的最直接、最容易實(shí)現(xiàn)的方式。可以用每個(gè)基因表示每個(gè)需要服務(wù)的工位，一組基因代表一條配送路線，各路線之間用0隔開(kāi)，0表示物料配送超市。例如：012305768490這樣的染色體編碼，表示共有9個(gè)工位有物料配送的需求，分為3條配送路線。這3條配送路線的安排如下：

路徑1：物料超市→工位1→工位2→工位3→物料超市；

路徑2：物料超市→工位5→工位7→物料超市；

路徑3：物料超市→工位6→工位8→工位4→工位9→物料超市。

在該染色體編碼中各路徑內(nèi)是有順序的，如路徑1中工位1和工位2之間位置互換的話，會(huì)導(dǎo)致最后目標(biāo)函數(shù)的值發(fā)生改變；而編碼的各子路徑之間是無(wú)序的，如上述的路徑1和路徑3的位置互換，是不會(huì)對(duì)最終目標(biāo)函數(shù)的值產(chǎn)生影響的。即0123057068490和0570123068490是沒(méi)有區(qū)別的。

STEP2：產(chǎn)生隨機(jī)初始群體。搜索開(kāi)始的一組染色體為初始種群，其數(shù)量也就是種群規(guī)模需要適當(dāng)進(jìn)行選擇；

考慮到帶時(shí)間窗的車(chē)輛路徑問(wèn)題較特殊，按照傳統(tǒng)的隨機(jī)排列方式所生成的染色體，會(huì)導(dǎo)致大部分都不滿足時(shí)間窗的約束。因此，本文為了更方便地求出可行解，采用一種賭輪啟發(fā)式算法尋找可行的物料配送路徑。具體步驟如下：

（1）所有的需要進(jìn)行物料配送的工位都安排完畢，結(jié)束（1），否則轉(zhuǎn)（2）；

（2）選中已選擇的點(diǎn)，若之前未有選定，那么即為物料超市。將所有還沒(méi)有被安排的工位與該點(diǎn)連接，將符合約束條件的路徑（約束包括時(shí)間窗約束，車(chē)輛最大載重約束）保留，用路徑的長(zhǎng)短表示評(píng)價(jià)保留的路徑值。如果沒(méi)有一條符合條件，這條線安排完畢，選擇下一輛服務(wù)的車(chē)，起始點(diǎn)還是物料超市，轉(zhuǎn)（2）；所有車(chē)輛安排完畢，轉(zhuǎn)（3）；

（3）采用輪盤(pán)賭的方式對(duì)保留的路徑進(jìn)行高低排列、區(qū)域劃分，路徑值越高，其所占有的區(qū)域值就越大；

（4）旋轉(zhuǎn)一次賭輪，選出一條符合條件的路徑，其它路徑都刪除，而選中的點(diǎn)為下一個(gè)起始點(diǎn)，返回（1）。

每執(zhí)行一次，可以得到一個(gè)車(chē)輛路徑計(jì)劃方案，將該方案當(dāng)做一個(gè)可行染色體，然后重復(fù)執(zhí)行，得到多個(gè)不同的可行染色體。進(jìn)而得到初始種群。

STEP3：計(jì)算每個(gè)染色體的適應(yīng)度eval(xi)。尋找適應(yīng)度最大的染色體；

構(gòu)造的適應(yīng)度函數(shù)與目標(biāo)函數(shù)呈線性相關(guān)，一般單目標(biāo)問(wèn)題，其適應(yīng)度函數(shù)可以直接用目標(biāo)函數(shù)f(xi)代替。對(duì)于超出時(shí)間窗約束之外和超出車(chē)輛最大載重量的染色體，可以用懲罰函數(shù)P(xi)降低適應(yīng)性。本文中要求車(chē)輛的承載量必須在一定的范圍之內(nèi)，所以只考慮超出時(shí)間窗之外的染色體。本文的目標(biāo)函數(shù)時(shí)間最小化，其適應(yīng)度可以表示為eval(xi)=-w1f(xi)+w2P(xi)。其中，w1+w2=1。

STEP4：按由個(gè)體適應(yīng)度值所決定的某個(gè)規(guī)則，選取將進(jìn)入下一代的個(gè)體，體現(xiàn)優(yōu)勝劣汰的自然規(guī)律；

STEP5：按概率Pc進(jìn)行交叉，交叉體現(xiàn)有性繁殖的思想；

TEPS6：按概率Pm進(jìn)行變異，變異體現(xiàn)進(jìn)化過(guò)程中的基因突變的思想；

STEP7：若不滿足停止條件，轉(zhuǎn)STEP3，否則轉(zhuǎn)下一步。

STEP8：得到種群中適應(yīng)度值最佳的染色體。此最優(yōu)染色體即所求車(chē)輛路徑問(wèn)題的最優(yōu)解。

若完成了預(yù)先給定的進(jìn)化代數(shù)，程序停止；若連續(xù)若干代后，種群中的最優(yōu)個(gè)體沒(méi)有任何改進(jìn)，或者連續(xù)若干代后，平均適應(yīng)度代沒(méi)有改進(jìn)，程序停止。這是兩種最簡(jiǎn)單的程序停止的情況。

4 實(shí)例驗(yàn)證

A企業(yè)是一家以客戶定制為主的生產(chǎn)制造企業(yè)，客戶定制的特征決定了其加工車(chē)間的生產(chǎn)模式為多品種小批量的生產(chǎn)模式。該企業(yè)規(guī)模較小，生產(chǎn)所需的物料都儲(chǔ)存在一個(gè)倉(cāng)庫(kù)中心，共有8個(gè)工位負(fù)責(zé)生產(chǎn)，將上述建立的以配送時(shí)間最短為目標(biāo)函數(shù)的模型應(yīng)用到該企業(yè)的生產(chǎn)制造車(chē)間，以下是該企業(yè)的一組數(shù)據(jù)，表格1是該企業(yè)物料儲(chǔ)存?zhèn)}庫(kù)到各個(gè)工位以及各個(gè)工位之間的距離，表格2是各工位的物料需求清單，還包括車(chē)輛在物料配送過(guò)程中在各工位的服務(wù)時(shí)間、等待裝卸物料的時(shí)間和每個(gè)工位的時(shí)間窗限制。將表中的數(shù)據(jù)作為輸入，規(guī)定負(fù)責(zé)物料配送車(chē)輛的最大載重量為70，速度最大不超過(guò)50，用Matlab7進(jìn)行編程，求解上述模型，結(jié)果見(jiàn)表3。

表1 工位之間及工位與物料超市之間的距離

表2 工位物料需求清單

表3 模型求解結(jié)果統(tǒng)計(jì)

通過(guò)以上的賭輪啟發(fā)式算法用Matab7求解，設(shè)置種群的大小為100，運(yùn)行200代之后算法終止，經(jīng)過(guò)計(jì)算，算法在運(yùn)行10次實(shí)驗(yàn)中，平均157代之后表現(xiàn)為收斂，平均運(yùn)行時(shí)間為4.3s，行駛總距離為795。統(tǒng)計(jì)實(shí)驗(yàn)10次的平均的結(jié)果為：

車(chē)輛一的物料配送路線是：0—3—5—1—0，滿載率為72.9%，完成一次配送的總時(shí)間為9.6min；

車(chē)輛二的物料配送路線是：0—8—7—2—0，滿載率為78.6%，完成一次配送的總時(shí)間為11.2min；

車(chē)輛三的物料配送路線是：0—6—4—0，滿載率為78.6%，完成一次配送的總時(shí)間為9.3min。

根據(jù)模型求解的結(jié)果，畫(huà)出簡(jiǎn)易的工位需求的物料配送情況如圖1所示。

以上求解的結(jié)果可以看出：與企業(yè)原始路徑相比，優(yōu)化路徑的行駛距離更短，且每條路徑的行駛距離都比原來(lái)的短；完成一次配送的總時(shí)間優(yōu)化路徑最大為11.2，原始的為12.8，兩者相比優(yōu)化路徑的時(shí)間更短；優(yōu)化路徑中的車(chē)輛滿載率平均在75%以上，且每輛車(chē)都超過(guò)70%，原始路徑雖然車(chē)輛1和車(chē)輛2的滿載率較高，但車(chē)輛3的滿載率卻偏低，利用率低。因此，與原始路徑相比，在使用同樣的人力物力的條件下，優(yōu)化路徑所行駛的距離更短，車(chē)輛資源消耗更少，花費(fèi)的時(shí)間也更短，更有利于提高企業(yè)的生產(chǎn)效率。

圖1 工位需求物料配送情況

5 結(jié)論

本文結(jié)合多品種小批量生產(chǎn)的特征，在企業(yè)制造車(chē)間內(nèi)部工位物料需求時(shí)間不確定的基礎(chǔ)上，借鑒物流行業(yè)現(xiàn)有的車(chē)輛路徑問(wèn)題研究，將其應(yīng)用到車(chē)間內(nèi)部物料配送上，對(duì)帶有時(shí)間窗的車(chē)間內(nèi)部物料配送調(diào)度的優(yōu)化路徑展開(kāi)研究，建立帶有時(shí)間窗的物料配送路徑的數(shù)學(xué)模型，對(duì)于物料到達(dá)較時(shí)間窗提前或滯后的情況，建立相應(yīng)的懲罰函數(shù)，采用改進(jìn)的遺傳算法求解模型，并將模型應(yīng)用到一家多品種小批量生產(chǎn)模式的企業(yè)案例中，求解出具體的物料配送的路徑。將本文提出的模型求解的結(jié)果與企業(yè)原有的配送路徑對(duì)比，結(jié)果表明本文的模型所用的時(shí)間更短，更有助于企業(yè)節(jié)約時(shí)間成本，提高生產(chǎn)效率。車(chē)輛滿載率雖然不是很高，但平均利用率較高。

[1]李晉航,黃剛,賈艷.多模糊信息條件下的物料配送路徑規(guī)劃問(wèn)題研究[J].機(jī)械工程學(xué)報(bào),2011,1(47).

[2]劉明周,王小巧,張銘鑫,等.不確定環(huán)境下混流裝配線動(dòng)態(tài)準(zhǔn)時(shí)制物料配送系統(tǒng)[J].計(jì)算機(jī)集成制造系統(tǒng),2014,12(20):3 020-3 031.

[3]凌琳,劉明周,葛茂根,等.計(jì)及漂移瓶頸的時(shí)變物料配送路徑優(yōu)化[J].機(jī)械工程學(xué)報(bào),2015,51(23):133-143.

[4]Muller J.Approximative solutions to the bicriterion vehicle routing problem with time windows[J].European Journal of Operational Research,2010,202(1):223-231.

[5]王旭坪,張凱,胡祥培.基于模糊時(shí)間窗的車(chē)輛調(diào)度問(wèn)題研究[J].管理工程學(xué)報(bào),2011,(3):148-154.

[6]Banos ttega J,Gll C,et al.A simulated annealing based parallel multi-objective approach to vehicle routing problems with time windows[J].Expert Systems with Application,2013,40(5): 1 696-1 707.

[7]Kilic Sezgin,Kaplan Sezgin.An Efficient Fuzzy Programming Approach for the Vehicle Routing Problem withSoft Time Windows[J].Joutnal of multiple-valued logic and soft computing,2014,4(22):443-457.

[8]章勛宏,賈國(guó)柱,孔繼利.考慮零件三維裝載約束帶時(shí)間窗的循環(huán)取貨路徑問(wèn)題研究[J].管理工程學(xué)報(bào),2014,(4):207-218.

[9]AndroutsopoulosKonstantinosN,ZografosKonstantinosG. Solving the bicriterion routing and scheduling problem for hazardous materialsdistribution[J].Transportation research part c:emerging technologies,2010,18(5):713-726.

[10]Gao Guibing,Zhang Guojun,Huang Gang.Solving material distribution routing problem in mixed manufacturing systems with a hybrid multi-objective evolutionary algorithm[J]. Journal of central south university,2012,19(2):433-422.

[11]嚴(yán)正峰,梅發(fā)東,等.基于模糊軟時(shí)間窗的車(chē)間物料流路徑優(yōu)化方法[J].計(jì)算機(jī)集成與制造,2015,(10):2 761-2 767.

[12]Simic Dragan,Kovacevic Ilija,Svircevic Vasa.Hybrid Firefly Model in Routing Heterogeneous Fleet of Vehicles in LogisticsDistribution[J].Logic journal of the igpl,2015,23(3):521-532.

Optimization of Workshop Material Dispatching with Soft Time Window

Li Jialing,Qian Wuyong
(School of Business,Jiangnan University,Wuxi 214122,China)

In this paper,based on the concept of the soft time window,we proposed the method for the optimization of the internal dispatching of workshop materials,then upon the given hypotheses,studied the workshop material distribution problem with time window, which aimed at minimizing the total distribution time and established the relevant mathematical model.Next,we solved it using the improved genetic algorithm to obtain the optimal route for the distribution of the workshop materials.At the end,we demonstrated the validity of the model through an empirical study.

material distribution;soft time window;genetic algorithm;dispatching optimization

F252.14;F253

A

1005-152X(2016)12-0135-06

10.3969/j.issn.1005-152X.2016.12.032

2016-10-24

國(guó)家自然科學(xué)基金項(xiàng)目(71503103)；江蘇自然科學(xué)基金項(xiàng)目（BK20150157）；江蘇省社會(huì)科學(xué)基金項(xiàng)目（14GLC008）;中央高校基本科研業(yè)務(wù)費(fèi)專(zhuān)項(xiàng)資金資助（JUSRP11583;2015JDZD04）

李加玲（1992-），女，江蘇南通人，研究生，研究方向：供應(yīng)鏈管理；錢(qián)吳永（1979-），男，江蘇連云港人，副教授，研究生導(dǎo)師，博士，研究方向：系統(tǒng)建模與數(shù)量經(jīng)濟(jì)。