基于軟時間窗的車間物料配送調度優化研究

李加玲，錢吳永

（江南大學 商學院，江蘇 無錫 214122）

基于軟時間窗的車間物料配送調度優化研究

李加玲，錢吳永

（江南大學 商學院，江蘇 無錫 214122）

實際生產中車間內部工位物料需求存在一些不確定性問題，基于軟時間窗的概念提出車間內部物料配送調度優化的方法。在已給定的假設基礎上，研究帶有時間窗的車間物料配送問題，將配送總時間最短作為目標函數，建立關于車間物料配送調度的數學模型，采用一種改進的遺傳算法對模型求解，得到車間物料配送的最佳路徑。最后通過實例驗證該模型的有效性。

物料配送；軟時間窗；遺傳算法；調度優化

1 引言

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

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

現有文獻中對物料配送的研究，主要包括物料的管理控制、配送路徑優化等方面，而車輛路徑問題的研究主要集中在較大型的物流運輸方面，從成本、時間以及行駛路程等角度考慮，尋找最優路徑。近年來，有學者開始將宏觀的車輛路徑問題的研究方法和思路應用到制造業內部物料流分析中，主要研究制造業內部物料配送路徑問題，求解制造業內部物料配送的最優路徑，縮短時間，提高生產效率。本文基于現有的研究，結合軟時間窗的概念，將車輛路徑問題用到車間內部物料配送上，以時間最小化為目標，同時考慮到物料在時間窗之外到達時，構建相應的懲罰函數。本文將時間最短作為目標函數，尋找最優的車間物料配送路徑，是考慮到車間內部的物料運輸通常都是用叉車運輸，且每條路徑行駛的路程較短、差距較小，所需成本差別也較小，可以忽略。所以選擇時間最小化為目標是更加符合車間內部物料運輸的實際情況。

2 模型構建

2.1 問題的描述

關于車間內部物料流的車輛路徑問題的描述：車間內部各工位所需要的物料都儲存在統一的倉庫，這里稱之為物料超市，工位所需物料都由物料超市負責運輸配送，由k個承載量為q的車輛負責將物料配送到需要的各工位，車間內有N個工位，各工位上所需的物料要在時間窗之間被送到。考慮到物料有可能會在時間窗之外被送達，本文基于軟時間窗的車間物料配送調度進行研究，如果物料不在規定的時間窗之內送達，建立相應的懲罰函數。考慮到車間內部物料的配送都是以叉車為主，且車間內部的行駛距離較短，因此，車輛的油耗差距小，當叉車的速度一定時，若配送時間短，則車子的行駛距離就短，且人力的消耗最小，因此，可以將車間內部物料配送路徑優化問題轉化為求車間內物料配送時間最短的車輛行駛路徑。

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

2.2.1 假設條件。為了使研究問題更加明確，現對模型做如下假設：

物料超市所提供的物料種類、數量等信息已知，各工位所需要的物料品種、數量也已知。且配送到各工位的物料都是由一個物料超市負責提供。

各工位所需的物料量之和不超過物料超市的儲存量。

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

假定車輛的行駛速度已知且勻速行駛，因此派出取物料的車輛在各工位節點之間以及物料超市到各工位的行駛時間可以直接求出。

2.2.2 約束條件。（1）物料配送時，車輛從物料超市出發到各工位進行物料配送，當車輛重新回到物料超市表示一個物料配送路徑結束。

（2）根據物料需求將工位分為多個工位組，一輛車對一個工位組所需要的物料進行一次或多次配送。

（3）一個工位組需要的所有物料都儲存在一個物料超市里，而一個物料超市可以儲存多個工位組需要的物料。

（4）一個工位組所需要的物料由一輛車負責配送。

（5）一個工位組一次所需要的物料量不能超過一個物料超市的最大儲存量。

（6）每輛車的行駛距離須在其規定的最大行駛距離之內。

2.3 參數符號

（1）已知量

i,j∈N：表示需要被服務的工位的編號；

k：表示負責配送的車輛的編號；

ti：車輛到達服務的工位的時間；

te：物料配送到達工位的時間窗的開始時間；

tl：物料配送到達工位的時間窗的結束時間；

wi：為服務工位i所需要的等待時間；

si：在工位i裝卸貨的服務時間；

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

v：車輛的平均行駛速度；

Q：車輛的最大載重量；

L：車輛行駛的最大距離；

M,N：工位組的編碼；

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

（2）決策變量。為了方便物料配送模型建立與求解，根據車間內部物料配送的實際情況對模型做了一些簡化處理，如下：

2.4 模型建立

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

其中α，β是車輛在時間窗之前和在時間窗之后到達的懲罰因子是指車輛在時間窗之前和時間窗之后到達工位的不滿意度。

根據以上分析構建的從物料超市到工位物料配送時間最短的目標函數如下：

其中：

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

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

傳統的路徑優化模型一般都是在大型的物流運輸中的，構建目標函數時都是以成本最小化為目標，也有以成本、時間為目標構建多目標函數的。本文所構建的模型是針對車間內部物料流的，車間內部物料運輸都是叉車運輸，其各路徑的行駛路程較短且接近，人力成本、能源消耗相差都較小，所以以成本最小化為目標函數不太符合實際情況。本文在構建模型時之所以選擇時間最小化作為目標函數，是因為時間對于車間內部物料配送而言較重要，物料到達工位的時間對生產會有很大的影響，提前和延后都會對生產線產生影響，只有在規定的時間窗之內到達才是最佳的。因此，對在時間窗之外達到的物料構建了相應的時間懲罰函數，更加符合車間內部物料配送的實際情況。

3 模型求解

本文的研究主要是制造業內部物料流的物料配送調度問題，該問題的關鍵是確定從物料超市到工位組的路線安排，考慮帶有軟時間窗的車間內部物料的配送，在物料儲存確定的基礎上，將物料配送調度問題轉化為一個時間最短問題，尋找最優的車間內部物料配送路徑。解決這類問題最常用的方法就是建立相應的目標函數，用遺傳算法等智能算法對目標函數求解，得到最優的物料配送路徑。

遺傳算法求解帶時間窗約束的車間內部物料配送路徑的步驟如下：

STEP1：構造滿足上述模型中約束條件的路徑染色體。由于解空間中的解遺傳算法不能直接處理，要通過編碼用適當的染色體將解表示出來。對于實際問題，染色體的編碼方式多種多樣，在選取染色體的編碼方式時應選取符合約束條件的，否則會影響計算。

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

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

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

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

在該染色體編碼中各路徑內是有順序的，如路徑1中工位1和工位2之間位置互換的話，會導致最后目標函數的值發生改變；而編碼的各子路徑之間是無序的，如上述的路徑1和路徑3的位置互換，是不會對最終目標函數的值產生影響的。即0123057068490和0570123068490是沒有區別的。

STEP2：產生隨機初始群體。搜索開始的一組染色體為初始種群，其數量也就是種群規模需要適當進行選擇；

考慮到帶時間窗的車輛路徑問題較特殊，按照傳統的隨機排列方式所生成的染色體，會導致大部分都不滿足時間窗的約束。因此，本文為了更方便地求出可行解，采用一種賭輪啟發式算法尋找可行的物料配送路徑。具體步驟如下：

（1）所有的需要進行物料配送的工位都安排完畢，結束（1），否則轉（2）；

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

（3）采用輪盤賭的方式對保留的路徑進行高低排列、區域劃分，路徑值越高，其所占有的區域值就越大；

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

每執行一次，可以得到一個車輛路徑計劃方案，將該方案當做一個可行染色體，然后重復執行，得到多個不同的可行染色體。進而得到初始種群。

STEP3：計算每個染色體的適應度eval(xi)。尋找適應度最大的染色體；

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

STEP4：按由個體適應度值所決定的某個規則，選取將進入下一代的個體，體現優勝劣汰的自然規律；

STEP5：按概率Pc進行交叉，交叉體現有性繁殖的思想；

TEPS6：按概率Pm進行變異，變異體現進化過程中的基因突變的思想；

STEP7：若不滿足停止條件，轉STEP3，否則轉下一步。

STEP8：得到種群中適應度值最佳的染色體。此最優染色體即所求車輛路徑問題的最優解。

若完成了預先給定的進化代數，程序停止；若連續若干代后，種群中的最優個體沒有任何改進，或者連續若干代后，平均適應度代沒有改進，程序停止。這是兩種最簡單的程序停止的情況。

4 實例驗證

A企業是一家以客戶定制為主的生產制造企業，客戶定制的特征決定了其加工車間的生產模式為多品種小批量的生產模式。該企業規模較小，生產所需的物料都儲存在一個倉庫中心，共有8個工位負責生產，將上述建立的以配送時間最短為目標函數的模型應用到該企業的生產制造車間，以下是該企業的一組數據，表格1是該企業物料儲存倉庫到各個工位以及各個工位之間的距離，表格2是各工位的物料需求清單，還包括車輛在物料配送過程中在各工位的服務時間、等待裝卸物料的時間和每個工位的時間窗限制。將表中的數據作為輸入，規定負責物料配送車輛的最大載重量為70，速度最大不超過50，用Matlab7進行編程，求解上述模型，結果見表3。

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

表2 工位物料需求清單

表3 模型求解結果統計

通過以上的賭輪啟發式算法用Matab7求解，設置種群的大小為100，運行200代之后算法終止，經過計算，算法在運行10次實驗中，平均157代之后表現為收斂，平均運行時間為4.3s，行駛總距離為795。統計實驗10次的平均的結果為：

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

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

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

根據模型求解的結果，畫出簡易的工位需求的物料配送情況如圖1所示。

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

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

5 結論

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

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

[2]劉明周,王小巧,張銘鑫,等.不確定環境下混流裝配線動態準時制物料配送系統[J].計算機集成制造系統,2014,12(20):3 020-3 031.

[3]凌琳,劉明周,葛茂根,等.計及漂移瓶頸的時變物料配送路徑優化[J].機械工程學報,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]王旭坪,張凱,胡祥培.基于模糊時間窗的車輛調度問題研究[J].管理工程學報,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]章勛宏,賈國柱,孔繼利.考慮零件三維裝載約束帶時間窗的循環取貨路徑問題研究[J].管理工程學報,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]嚴正峰,梅發東,等.基于模糊軟時間窗的車間物料流路徑優化方法[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

國家自然科學基金項目(71503103)；江蘇自然科學基金項目（BK20150157）；江蘇省社會科學基金項目（14GLC008）;中央高校基本科研業務費專項資金資助（JUSRP11583;2015JDZD04）

李加玲（1992-），女，江蘇南通人，研究生，研究方向：供應鏈管理；錢吳永（1979-），男，江蘇連云港人，副教授，研究生導師，博士，研究方向：系統建模與數量經濟。