吳 瑤,馬祖軍,鄭 斌

(1.西南交通大學 經濟管理學院,成都 610031; 2.湖北汽車工業(yè)學院 機械工程學院,湖北 十堰 442002;3.西南交通大學 交通運輸與物流學院,成都 610031)(*通信作者電子郵箱binzheng@swjtu.cn)

0 引言

隨著客戶需求日益多樣化以及市場競爭的加劇,越來越多的企業(yè)采用按訂單生產(Make-To-Order, MTO)模式來組織產品的生產和配送活動,以降低產品庫存,提高對市場的反應速度。對于易腐品供應企業(yè)來說,尤其如此。由于產品在生產加工完成后即開始變質,供應商通常需采用準時制(Just In Time, JIT)方式來安排產品的生產并立即組織配送,如鮮奶、鮮切果蔬、鮮焙面包等。通過協(xié)調易腐品的生產和配送,不但能夠提高供應鏈的效率,而且保障了產品交付時的新鮮度。因此,對生產和配送進行協(xié)同調度成為易腐品供應企業(yè)需要解決的關鍵問題。

目前,研究供應鏈中生產-配送協(xié)調優(yōu)化的文獻較多,但是大多數涉及戰(zhàn)略或戰(zhàn)術層面的決策問題,考慮了產品的庫存,需要優(yōu)化產品生產和配送的數量。如文獻[1-2]研究了多供應商、多客戶情形下的產品生產-分銷問題,文獻[3-4]研究了多周期的產品生產-庫存-路徑問題?？紤]到生產和配送的直接協(xié)調可以節(jié)約庫存成本,提高供應鏈的響應速度,近年來越來越多的學者對生產-配送集成中的生產調度問題進行了研究,但絕大多數假設配送過程為直達運輸模式[5-8]。

本文研究的生產-配送協(xié)同調度問題(Integrated Scheduling of Production and Distribution Problem, ISPDP),則需要協(xié)同優(yōu)化供應鏈中產品的生產調度和訂單配送路徑。由于問題的復雜性,目前該方面的研究文獻仍然較少。Ullrich[9]研究了并行機環(huán)境下帶時間窗約束的機器調度與車輛路徑集成優(yōu)化問題,采用兩個子問題分別編碼的遺傳算法(Genetic Algorithm, GA)進行求解。Chang等[10-11]分別對同型機和非等效并行機環(huán)境下的ISPDP設計了列生成算法和蟻群算法進行求解。Low等[12]針對批發(fā)商-零售商兩級供應鏈中的ISPDP,以車輛指派成本、運輸成本和違反時間窗懲罰成本總和最小為目標,建立了非線性規(guī)劃模型,設計了基于Johnson啟發(fā)式規(guī)則的自適應遺傳算法進行求解。Li等[13]以配送成本和客戶總等待時間為目標,建立了單機生產環(huán)境下ISPDP的多目標優(yōu)化模型,設計了嵌入批處理機制的帶精英策略的非支配排序GA(elitist Nodominated Sorting GA,NSGA-Ⅱ)進行求解。在國內,針對單機多車情形下的ISPDP,李凱等[14]設計了模擬退火算法最小化制造商信譽懲罰成本和配送成本之和,劉玲等[15]設計了遺傳算法最小化所有訂單的最長完工時間。

上述對ISPDP的研究,針對的都是一般產品。對于易腐品而言,其易腐特性是導致產品采取ISPDP的關鍵。因此,研究易腐品的ISPDP尤為重要。Farahani等[16]將快餐ISPDP分解為生產調度和車輛路徑優(yōu)化兩個子問題,采用循環(huán)迭代方式進行求解,在各次迭代計算中,兩個子問題分別采用CPLEX軟件和大規(guī)模鄰域搜索算法進行優(yōu)化。Chen等[17]研究了易腐食品ISPDP,考慮了需求的隨機性和產品的常數變質率,以供應商的收益最大為目標,建立了非線性規(guī)劃模型,設計了以單純形算法和插入算法為基礎的迭代求解算法,優(yōu)化客戶訂單的生產時間、生產量和配送車輛的行駛路徑。Amorim等[18]對易腐食品ISPDP進行了較系統(tǒng)的研究,比較了組批和批量兩種生產模式下的ISPDP,通過CPLEX計算算例驗證了批量生產模式的ISPDP能夠產生較大的經濟效益。Belo-Filho等[19]研究了具有保鮮期限的易腐品在批量生產模式下的ISPDP,設計了自適應大規(guī)模鄰域搜素算法協(xié)調各個子問題的優(yōu)化,包括批量生產調度問題,配送路徑問題以及小規(guī)模的ISPDP,對各子問題均采用CPLEX進行計算。Viergutz等[20]在單機、單車和多客戶情形下,研究了有限保質期的易腐品ISPDP,使客戶需求的滿足率最大化,設計了分支定界算法對問題求解。Devapriya等[21]在車輛可進行多回程配送情況下,研究了有限計劃期內有確定保質期的易腐品ISPDP,以指派車輛的固定成本和產品運輸成本總和最小為目標,建立了混合整數規(guī)劃模型,設計了基于進化算法的啟發(fā)式方法對問題求解。吳瑤等[22]對時變路網環(huán)境下帶時間窗的易腐食品ISPDP進行了研究,以車輛指派成本、配送成本和產品價值損失總和最小為目標,建立了混合整數規(guī)劃模型并設計了混合遺傳算法進行求解,分析了路網時變性和產品變質系數對生產-配送方案的影響。馬雪麗等[23]綜合考慮了配送的軟時窗約束以及需求和運輸時間的隨機性,以供應鏈整體利潤最大化為目標,建立了生產商-零售商二級供應鏈模式下易腐食品ISPDP的數學模型,設計了改進遺傳算法和隨機模擬技術相結合的混合智能算法求解模型。

以上關于ISPDP的文獻,大多均考慮的是單個目標,或者將多個目標通過加和轉讓為單目標進行處理。僅有文獻[13]從產品交付時間和配送成本兩個方面對ISPDP進行多目標優(yōu)化,但是針對的是一般產品。而對于易腐品,客戶的滿意度主要體現為產品按時交付時的新鮮度水平,如文獻[24],把產品交付新鮮度和配送成本作為易腐品配送的兩個目標,但是該文并未考慮產品的生產調度與配送路徑的協(xié)調優(yōu)化。因此,本文借鑒文獻[13]的研究成果,把文獻[24]的易腐品配送問題擴展到供應鏈環(huán)境下,在更全面考慮配送成本和交付產品新鮮度的基礎上,建立具有最低新鮮度限制的易腐品生產-配送協(xié)同調度多目標優(yōu)化問題(Multi-Objective ISPDP, MOISPDP)的模型并設計求解算法。首先從需求時間窗和產品變質率兩方面對產品需求特征進行分析,在考慮客戶產品最低新鮮度約束下,以總配送成本最小和交付產品總新鮮度最大為兩個目標,建立了混合整數規(guī)劃模型并設計了雙子串編碼的NSGA-Ⅱ進行求解,最后通過算例計算和不同算法的結果對比驗證了模型和算法的有效性,對產品最低新鮮度限制的敏感性進行了分析。

1 問題建模

1.1 問題描述

本文考慮一個供應商(加工中心)向多個客戶供應多種易腐品的情形,如加工廠向超市或個人供應鮮奶、鮮肉等。假設供應商有一條生產線,可混流生產多種產品,任意時刻只能生產一種產品,不同產品的生產效率具有差異性。為保證產品生產操作的便利性和交付客戶的及時性,生產過程按配送路徑來進行組織,同一路徑上客戶所需的產品作為一個生產批次,各產品的生產量為路徑上該產品的總需求量。對同一批次生產的多種產品,為了減小產品生產完成后等待配送過程中的變質損失,提高產品交付的新鮮度水平,優(yōu)先生產變質速度慢的產品,即生命周期長的產品。當一條路徑配送的所有產品生產完成后立即進行裝車配送。在滿足所有客戶需求量和交付時間窗的情況下,為了使總配送成本最小和交付產品總的新鮮度最大,需要決策生產線上產品的生產批量、生產起始時間以及各配送路徑上客戶的服務先后順序。

以鮮切果蔬生產/配送為例,現實中客戶對產品的需求時間比較趨同,一定時間范圍內訂單較為集中,因此通常采用交付期限來描述客戶需求的急迫性,體現客戶對產品需求時間的差異。

而對于任意一種易腐品p,由于產品的堆積和微生物的發(fā)酵,其新鮮度在生產完成后即開始衰減,隨著時間的推移,呈加速遞減趨勢。本文采用文獻[25]定義的單調連續(xù)減函數θp(t)來描述產品p新鮮度隨時間的變化。若產品生產完成時間為0時刻,在ti時刻產品交付客戶i時,其新鮮度可表示為式(1):

θp(ti)=1-(ti/Tp)2;0≤ti≤Tp

(1)

其中:Tp為產品的有效生命周期。

在按訂單生產過程中,客戶對交付產品的新鮮度有較高的期望。當產品送達時,若質量明顯下降,通常將直接被拒絕接收,而不是以折扣價進行銷售。尤其在流行網購的當下,這種狀況更為普遍,產品價格支付后,客戶對產品滿意與否取決于交付產品的質量。因此,易腐品的配送就必須使交付產品滿足客戶的最低新鮮度gp的要求,即θp(ti)≥gp。產品新鮮度變化和接受條件如圖1所示。

圖1 產品新鮮度變化和接受條件

1.2 模型假設

為了方便模型的建立,作以下假設:

1)同一配送路徑的客戶訂單產品作為一個生產批次,同一批次優(yōu)先生產生命周期較長的產品,不考慮產品間的生產轉化成本和時間[17,22-23]。

2)車輛在一條路徑上可配送多個客戶的訂單,各客戶的需求只能由一輛車進行配送。所有受指派的車輛從加工中心出發(fā),服務完路徑上的客戶后返回加工中心。

3)交付客戶的產品必須滿足最低新鮮度要求。

1.3 符號說明

為方便模型的建立,用G=(N,A)表示由加工中心和客戶構成的配送網絡,其中N=C∪{0}, 0表示加工中心,C={1,2,…,n}表示客戶點集合;A={(i,j)|i,j∈N,i≠j}為路段集合。加工中心的生產時間窗為[0,l0],可生產的產品類型集合為P,各產品的保質期限為T1≥T2≥…≥T|P|,單位產品p(p∈H)的生產時間為bp?？蛻鬷訂購產品p的數量為qip,考慮到產品交付的及時性,其訂單最遲交付期限表示為li,對應的時間窗為[0,li]。供應商可指派的車輛集合為K,車輛容量為Q。此外,定義如下參數和變量:

g表示配送車輛啟用的固定成本;

k表示產品生產批次的編號,與配送批次一致,k∈K;

ti表示客戶i訂單交付的時間;

si表示客戶i訂單交付過程的服務時間;

gp表示產品p的最低新鮮度要求;

cij表示從客戶點i到客戶點j的路段行駛成本;

τij表示從客戶點i到客戶點j的路段行駛時間;

θp(ti)表示產品p交付客戶時的新鮮度水平;

Tp表示產品p生產完成后的有效生命周期;

M表示很大的正數;

1.4 模型建立

建立有最低新鮮度限制的易腐品MOISPDP模型如下:

(2)

(3)

s.t.

(4)

(5)

(6)

(7)

(8)

(9)

(10)

(11)

(12)

(13)

(14)

(15)

(16)

(17)

(18)

xijk,yik∈{0,1};?i,j∈N,k∈K

(19)

目標函數式(2)表示最小化總配送成本,包括車輛指派成本和運輸成本。

目標函數式(3)表示最大化交付產品總的新鮮度，與文獻[24]不同的是,在此定義的客戶產品新鮮度為平均新鮮度水平,同時考慮了產品的數量和剩余保質期限。

約束式(4)～(9)為訂單生產過程約束。其中：式(4)表示同一生產批次中的任一產品連續(xù)生產所需的時間;式(5)表示同一生產批次中的不同產品無生產轉換等待時間;式(6)和(7)分別表示初始批次的生產開始時間和最末批次的生產完成時間不得違反加工中心的生產時間窗約束;式(8)表示執(zhí)行某批次配送任務的車輛只有在該批次所有訂單產品生產完工后才能開始配送;式(9)表示連續(xù)批次的生產開始時間約束。

約束式(10)～(18)為訂單配送過程約束。其中：式(10)表示所有客戶的需求均得到滿足;式(11)表示到達客戶的車輛完成訂單交付后必須離開;式(12)表示車輛僅對分配給它的批次訂單進行配送;式(13)表示每輛車配送的產品數量不超過車輛容量;式(14)表示配送過程中使用的車輛數量不超過車輛總數;式(15)表示配送車輛到達客戶的時刻與客戶的服務順序一致;式(16)表示客戶的服務開始時刻不遲于產品最遲交付期限,不早于批次產品的生產完成時間;式(17)為產品新鮮度與時間的關系函數[25],其中,Tp為產品的有效生命周期,0≤ti≤Tp；式(18)表示客戶接收產品的新鮮度滿足其最低新鮮度約束；式(19)為模型中定義的0-1變量和連續(xù)變量。

1.5 模型分析

目標函數式(2)和(3)分別求最小值和最大值,為便于目標函數的統(tǒng)一處理,把式(3)轉化為交付產品新鮮度下降總和的最小值,即為式(20):

(20)

對于任意可行路徑,不僅需要滿足路徑上客戶的時間窗和產品最低新鮮度約束,而且路徑的總配送量不能超過車輛容量。對于交付產品的最低新鮮度約束,可從MOISPDP模型中的約束式(17)～(18)推導出產品交付客戶的最遲時間,即存在如下定理1。

(21)

由定理1可知,利用產品的保鮮期可以檢驗交付產品的新鮮度約束式(18)是否得到滿足。

2 算法設計

在傳統(tǒng)車輛路徑問題(Vehicle Routing Problem, VRP)基礎上,MOISPDP模型考慮的約束條件更加復雜,因此問題求解更加困難。而VRP為NP-hard,故MOISPDP也為NP-hard。對于此類問題,通常采用智能算法進行求解,以求在有限的計算時間內獲得滿意解。遺傳算法(GA)作為典型的群智能算法,具有操作簡單、對問題適應性強和對初始解敏感度低等優(yōu)點。NSGA-Ⅱ繼承了GA的思想,是迄今最優(yōu)秀的進化類多目標算法之一[26],在求解多目標問題上具有突出特點:1)采用快速非支配排序,提高了算法的速度;2)通過同一非劣等級中個體擁擠密度比較,保持種群的多樣性,同時避免個體適應度計算中參數選擇困難的問題;3)引入精英保留策略防止最佳個體的丟失,提高了算法的運算速度和魯棒性。NSGA-Ⅱ目前已廣泛應用于車間調度、VRP和ISPDP等多目標問題的求解上[13],表現出良好的性能。本文基于模型特點,設計了具有雙子串編碼的染色體和帶有懲罰策略的目標評價方法,采用NSGA-Ⅱ的非劣分層、擁擠度計算方法和種群進化框架來求解MOISPDP的Pareto解集,使決策者根據實際需要及偏好選擇合適的優(yōu)化方案。算法流程如圖2所示。

圖2 NSGA-Ⅱ流程

2.1 染色體編碼和種群初始化

為了方便染色體的交叉和變異操作,采用兩個長度均為|C|的子串對染色體進行編碼。子串1為1～|C|的不重復自然數,表示客戶的隨機序列。子串2為生產批次編號序列,設基因位的取值為1～|K|的任意自然數,對應表示子串1相同基因位的客戶所在的生產批次。子串1中同一生產批次的客戶在序列中出現的次序,表示該批次客戶配送的先后順序。例如,加工中心有5個待服務的客戶,配送車輛數為3,故最多可有3個生產批次。若生成染色體為

由于子串2的1和4位均為1,子串1對應位置為5和4,表示客戶訂單5和4在第1批次生產,配送過程的順序為5-4;同理,客戶訂單3、1和2在第3批次生產,配送過程的順序為3-1-2。由于在子串2中未有2編號,意味著第2生產批次為空,在實際生產過程中第3批次順位遞補為第2批次。

設種群規(guī)模為popsize,按照上述方式隨機產生1條染色體,檢驗各批次配送路徑上的客戶總需求量是否滿足車輛容量約束,若滿足,則將其加入種群;否則,重新生成1條染色體,直到生成的染色體數達到種群規(guī)模為止。

2.2 染色體適應值

在MOISPDP模型中含有車輛容量約束式(13),客戶時間窗約束式(16)和產品最低新鮮度約束式(17),為了提高解的質量,采用對不可行解進行懲罰的方式來擴大鄰域搜索范圍。由于約束式(13)和(16)影響著路徑客戶點的訪問可行性,與目標函數式(2)密切相關,故可將約束式(13)和(16)的違反量分別轉化為懲罰項Z1和Z2,加入目標函數式(2),即

其最大取值為1,故目標函數式(20)可轉化為:

其中：sgn(·)為符號函數。δi由式(21)進行判斷,當式(21)成立時,δ=0;否則,δ=1。

2.3 解的快速非支配排序

對于多目標優(yōu)化問題,通常目標值之間存在此消彼長的沖突,因此很難使各個目標函數值同時達到最優(yōu),即絕對最優(yōu)解,通常只能獲得在目標值不相互妥協(xié)下的相對最優(yōu)解,即Pareto解。以本文轉化后的最小化問題為例,首先通過定義1說明任意兩個可行解Xa和Xb的優(yōu)劣。

與單目標計算過程不同,多目標遺傳算法根據每一代計算的非支配解集進行染色體重組,在若干次迭代后,使Pareto前沿面逼近最優(yōu)解集,因此非支配解集的構造過程是影響多目標遺傳算法計算效率的關鍵。依據定義1給出的支配關系的判斷,種群中個體的非支配排序計算過程如下:

步驟1 初始化。令Sa表示種群中受染色體a支配的個體集合，na表示支配染色體a的個體數目，Fm表示第m前沿面的個體集合。初始化Sa=?,Fm=?,na=0。

步驟2 計算個體的支配解集和被支配數量。從種群中的第1條染色體開始計算,若個體a支配個體b(b>a),則Sa=Sa∪;而當個體b支配個體a,則na=na+1;直到種群中的所有個體已全部比較。

步驟3 計算第一前沿面的解集。遍歷種群中的所有個體,若na=0,則表示個體a不受其他任何支配,屬于第1前沿面Ranka=1,更新集合F1=F1∪{a}。初始化i=0。

步驟4i=i+1,當Fi≠?時,對于每個個體a∈Fi,每個個體b∈Sa,令nb=nb-1;若nb=0,則Rankb=i+1,Fi+1=Fi+1∪。

步驟5 若Fi+1=?,則終止；否則轉步驟4。

2.4 非劣面的擁擠密度排序

為了確保遺傳算法收斂到一個均勻分布的Pareto前沿面,在進化過程中可通過染色體重組來控制目標空間中解的分布,以提高解的均勻性與多樣性,使區(qū)域個體密度不至于過于擁擠。在此采用基于小生境尺寸的擁擠密度排序法,計算同一非劣等級內各條染色體j的擁擠度Dj,使遺傳算法選擇過程中,擁擠密度較小的個體擁有較大的概率進入下一代。設目標函數的數量為h,在本文中h=2。擁擠密度計算的具體步驟如下：

步驟2 循環(huán)執(zhí)行步驟1,至到前沿面Fi中的所有個體在h個目標函數下的表現距離計算完畢。

2.5 遺傳算子

遺傳算子主要包括選擇、交叉、變異和重組過程,各算子的執(zhí)行方式直接影響著遺傳算法的計算效率。本文改進的NSGA-Ⅱ在兼顧計算時間和效率的情況下,各算子的操作方式設計如下。

選擇操作 通過2次錦標選擇,選出兩條染色體作為父代進行交叉操作。在每次錦標選擇過程中,若取出的兩條染色體屬于同一非劣等級,則保留擁擠密度大的個體;否則,保留非劣等級低的個體。

交叉操作 依概率Pc,對子串1采用順序交叉和部分匹配交叉操作,子串2采用均勻交叉操作。

變異操作 依概率Pm,對交叉后的個體進行變異操作,子串1執(zhí)行位置互換和次序逆轉變異,子串2選擇任意基因位進行隨機變異,取值為車輛數量范圍內的任意值。

2.6 終止條件

當遺傳算法進化代數達到最大迭代數Gen時,算法終止并輸出最優(yōu)解方案。

3 算例分析

3.1 算例構造

為驗證算法的正確性和有效性,模擬每天上午6:00—12:00加工中心為客戶提供生產/配送服務的情形來構造如下算例。下面為了表述方便,把6:00記為0時刻,12:00記為6時刻,其他時間類推。加工中心和30個客戶的坐標及需求信息如表1所示,節(jié)點坐標和訂單交付期限的單位均為km,產品需求單位為kg。加工配送中心可提供A、B和C三種產品,其有效生命周期分別設置為10 h、8 h和6 h,對應單位數量產品的生產時間分別為0.001 2 h、0.002 5 h和0.001 8 h。任意客戶對產品的需求種類數為1～3種。各路段的長度為節(jié)點間歐氏距離的1.3倍,車輛在路段上的平均行駛速度為30 km/h。配送中心可提供容量均為300單位的車輛共10輛,車輛啟用的固定成本均為100元,單位距離行駛成本為1元/公里。

圖4 不同算法參數設置下的Pareto前沿面的解分布

客戶坐標(X, Y)/km交付期限/h產品需求(A, B, C)客戶坐標(X, Y)/km交付期限/h產品需求(A, B, C)0(17.5, 18)——16(31.5, 11.2)5.4(0, 0, 13)1(5.8, 12.2)2.5(11, 0, 0)17(34.9, 13.8)4.8(24, 13, 17)2(18.5, 21.2)3.2(11, 0, 24)18(21.4, 2.5)2.8(0, 29, 0)3(7.9, 14.2)3.2(15, 0, 0)19(23.9, 27.8)3.6(11, 0, 24)4(26.5, 14.4)4.7(29, 11, 0)20(34.9, 26.2)2.9(29, 15, 0)5(28.8, 4.5)3.7(18, 0, 0)21(19.2, 29.6)3.0(16, 15, 0)6(28.3, 12.1)2.8(0, 21, 26)22(26.4, 24.1)3.3(14, 14, 0)7(7.1, 8)4.2(0, 0, 11)23(33.2, 11.1)6.0(0, 0, 29)8(15.7, 31.3)5.6(0, 10, 23)24(19.2, 14.2)2.8(0, 0, 17)9(15.1, 29.5)4.4(21, 18, 27)25(25, 18.6)4.5(21, 17, 21)10(5.4, 18.3)4.0(20, 0, 0)26(14.7, 3.7)2.7(0, 0, 16)11(27.5, 22.3)4.9(24, 17, 11)27(33.9, 15.2)4.6(23, 14, 0)12(26.5, 7.8)4.3(0, 0, 27)28(19.6, 25.1)2.7(0, 0, 10)13(15, 8.9)3.1(12, 0, 0)29(31.6, 15.2)5.0(22, 20, 29)14(20.5, 18.6)4.4(0, 19, 25)30(7.8, 27.1)4.8(0, 16, 25)15(24, 20.2)3.4(0, 27, 0)

3.2 算例求解

對MOISPDP模型的約束懲罰系數分別設置為α1=60,α2=60。NSGA-Ⅱ參數設置為:種群規(guī)模popsize=150,進化代數Gen=800,交叉概率Pc=0.9,變異概率Pm=0.08。采用MatlabR2014a對NSGA-Ⅱ進行編碼實現,在Intel Core i3, 2.13 GHz CPU、4 GB內存和Windows 7操作系統(tǒng)的PC上運行。在三種產品的最低新鮮度均設置為0.75的情況下,計算耗時449.3 s,算法終止,所有解收斂到Pareto前沿面上,總共得到106個不同的Pareto解。圖3為Pareto前沿面上的解分布。表2中給出了3種生產-配送方案,即Pareto前沿面上3個典型的解,在第3列“生產-配送時間”中,括號內的時間序列表示批次生產開始時間和生產結束時間,括號外的時間序列為路徑上客戶點的訪問時間。

從表2可以看出,隨著配送過程中使用的車輛數從6輛增加到9輛,總配送成本持續(xù)增大,同時交付產品的新鮮度下降總和也進一步降低?？偱渌统杀九c交付產品新鮮度下降總和之間的悖反現象也可以從圖3看出,隨著使用的車輛數量由6輛增加到10輛,Pareto前沿面存在間斷不連續(xù),但整體比較光滑,兩目標此消彼長現象明顯。

圖3 Pareto前沿面的解分布

3.3 算法性能分析

為測試算法性能,將本文算法與基于Pareto的模擬退火(Pareto based Simulated Annealing, PSA)算法[27]的求解結果進行對比,PSA采用文獻[24]的編碼方式。實驗共分為三種情形,NSGA-Ⅱ在情形1～3的種群規(guī)模popsize分別設為500、800和800,進化代數Gen分別設為100、100和150。PSA在對應情形下產生的鄰域解數量與NSGA-Ⅱ產生的解數量相同。圖4為兩種算法在上述三種情形下產生的Pareto前沿面的解分布,表3對比了兩種算法的性能指標和算例的前沿面結果。

從圖4和表3中可以發(fā)現:1)兩種算法在三種情形下都可以得到有效的Pareto前沿解集;2)隨著迭代過程中產生的鄰域解的數量增大,兩種算法獲得的Pareto解的數量均明顯增多,計算時間均明顯增長,但是NSGA-Ⅱ的計算時間稍短,且獲得的Pareto解分布更加均勻,分散空間更廣;3)相對于PSA,NSGA-Ⅱ在三種情形下的Pareto前沿面更接近最優(yōu)前沿面,這得益于NSGA-Ⅱ的精英保留策略和非劣層級的擁擠密度排序,使優(yōu)秀個體得到加強并逐漸向最優(yōu)前沿面逼近。因此,可以看出本文提出的改進NSGA-Ⅱ對于求解MOISPDP更加有效。

表2 典型的Pareto解

表3 NSGA-Ⅱ和PSA算法性能指標的對比

圖5 不同新鮮度水平限制下的Pareto前沿面

3.4 最低新鮮度分析

為了分析產品交付最低新鮮度約束對求解結果的影響,把各種產品最低新鮮度分別設置為0.65和0.85,求得其Pareto前沿面的解分布如圖5所示。從圖5可以看出,在產品新鮮度限制水平為0.65時,約束式(18)較寬松,可以通過減少車輛使用數量,產生更多配送成本較低的解,如圖5左上角的解分布所示;此外,在車輛使用數量較少時,產品新鮮度限制水平為0.65時產生的少量Pareto解支配新鮮度限制水平為0.85時所產生的Pareto解,如圖5虛線框中的解所示;而在車輛使用數量較多時,算法在兩種產品新鮮度限制水平下產生的解幾乎完全重合,如圖5右下角的解分布所示。

因此,企業(yè)在實際生產/配送過程中,通過準確評估客戶對產品的新鮮度要求,在一定程度可以降低配送過程中的成本開支。而當客戶產品交付的新鮮度為優(yōu)先考慮目標時,企業(yè)可根據財力和效益多投入車輛運營,以提高客戶的滿意度。

4 結語

針對快速易腐品生產和配送環(huán)節(jié)緊密聯(lián)系的情況,基于客戶需求特征和產品易腐性,以總配送成本最小和交付產品總的新鮮度最大為目標,建立了具有最低新鮮度限制的易腐品生產-配送協(xié)同調度雙目標優(yōu)化模型?；谀Ｐ偷奶匦?對目標函數和約束條件進行了轉化,設計了雙子串編碼的帶精英策略的非支配排序遺傳算法。結合問題背景構造了算例,計算結果和算法對比分析表明本文算法能夠有效獲得Pareto前沿;對新鮮度限制進行敏感性分析,結果顯示在車輛數量較少時,總配送成本和產品交付總的新鮮度受到顯著的影響,供應商在決策時可根據實際需要在Pareto前沿面上選擇合適的方案。

進一步研究可以將易腐品生產-配送協(xié)同調度問題擴展到動態(tài)環(huán)境下,研究訂單的動態(tài)到達情形,或者考慮生產環(huán)節(jié)的復雜流程和產品轉換時間等情況。

參考文獻(References)

[1] PALEKAR U S, KARWAN M H, ZIONTS S. A branch-and-bound method for the fixed charge transportation problem[J]. Management Science, 1990, 36(9): 1092-105.

[2] 唐加福, YUNG Kai-leung. 基于Lagranege松弛分解的多產品生產-分銷系統(tǒng)的聯(lián)合決策[J]. 機械工程學報, 2005, 41(8): 153-158.(TANG J F, YUNG K-L. Lagrange relaxation decomposition based joint decisions for production and distribution system with multiple products[J]. Chinese Journal of Mechanical Engineering, 2005, 41(8): 153-158.)

[3] FUMERO F, VERCELLIS C. Synchronized development of production, inventory, and distribution schedules[J]. Transportation Science, 1999, 33(3): 330-340.

[4] BARDA J F, NANANUKUL N. A branch-and-price algorithm for an integrated production and inventory routing problem[J]. Computers & Operations Research, 2010, 37(12): 2202-2217.

[5] PUNDOOR G, CHEN Z L. Scheduling a production-distribution system to optimize the tradeoff between delivery tardiness and total distribution cost[J]. Naval Research Logistics, 2005, 52(6): 571-589.

[6] CHEN, Z L, PUNDOOR G. Order assignment and scheduling in a supply chain[J]. Operations Research, 2006, 54(3): 555-572.

[7] 柏孟卓, 唐國春. 與交貨期有關的供應鏈排序問題[J]. 運籌學學報, 2009, 13(1): 113-119.(BAI M Z, TANG G C. Integrated production and distribution scheduling in supply chain management[J]. OR Transactions, 2009, 13(1): 113-119.)

[8] 蔣大奎, 李波. 基于混合禁忌搜索算法的供應鏈排序問題[J]. 機械工程學報, 2011, 47(20): 53-59.(JANG D K, LI B. Supply chain scheduling based on hybrid taboo search algorithm[J]. Journal of Mechanical Engineering, 2011, 47(20): 53-59.)

[9] ULLRICH C A. Integrated machine scheduling and vehicle routing with time windows[J]. European Journal of Operational Research, 2013, 227(1): 152-165.

[10] CHANG Y C, CHANG K H, CHANG T K. Applied column generation-based approach to solve supply chain scheduling problems[J]. International Journal of Production Research, 2013, 51(13): 4070-4086.

[11] CHANG Y, LI V C, CHIANG C J. An ant colony optimization heuristic for an integrated production and distribution scheduling problem[J]. Engineering Optimization, 2014, 46(4): 503-520.

[12] LOW C, CHANG C M, LI R K, et al. Coordination of production scheduling and delivery problems with heterogeneous fleet[J]. International Journal of Production Economics, 2014, 153(7): 139-148.

[13] LI K, ZHOU C, LEUNG J Y T, et al. Integrated production and delivery with single machine and multiple vehicles[J]. Expert Systems with Applications, 2016, 57: 12-20.

[14] 李凱, 王明星, 楊平,等. 單機多車情形生產與配送協(xié)同調度算法[J]. 計算機集成制造系統(tǒng), 2014, 20(12): 3011-3019.(LI K, WANG M X, YANG P, et al. Coordinated scheduling algorithm of production and distribution in the case of single machine and multi-vehicle[J]. Computer Integrated Manufacturing Systems, 2014, 20(12): 3011-3019.)

[15] 劉玲, 李昆鵬, 劉志學. 生產和運輸協(xié)同調度問題的模型和算法[J]. 工業(yè)工程與管理, 2016, 21(2): 86-91.(LIU L, LI K P, LIU Z X. Model and algorithms for the integrated production and transportation scheduling[J]. Industrial Engineering and Management, 2016, 21(2): 86-91.)

[16] FARAHANI P, GRUNOW M, GüNTHER H O. Integrated production and distribution planning for perishable food products[J]. Flexible Services and Manufacturing Journal, 2012, 24(1): 28-51.

[17] CHEN H K, HSUEH C F, CHANG M S. Production scheduling and vehicle routing with time windows for perishable food products[J]. Computers & Operations Research, 2009, 36(7): 2311-2319.

[18] AMORIM P, BELO-FILHO M A F, TOLEDO F M B, et al. Lot sizing versus batching in the production and distribution planning of perishable goods[J]. International Journal of Production Economics, 2013, 146(1): 208-218.

[19] BELO-FILHO M A F, AMORIM P, ALMADA-LOBO B. An adaptive large neighborhood search for the operational integrated production and distribution problem of perishable products[J]. International Journal of Production Research, 2015, 53(20): 1-19.

[20] VIERGUTZ C, KNUST S. Integrated production and distribution scheduling with lifespan constraints[J]. Annals of Operations Research, 2014, 213(1): 293-318.

[21] DEVAPRIYA P, FERRELL W, GEISMAR N. Integrated production and distribution scheduling with a perishable product[J]. European Journal of Operational Research, 2017, 259(3): 906-916.

[22] 吳瑤, 馬祖軍. 時變路網下帶時間窗的易腐食品生產-配送問題[J]. 系統(tǒng)工程理論與實踐, 2017, 37(1): 172-181.(WU Y, MA Z J. Time-dependent production-delivery problem with time windows for perishable foods[J]. Systems Engineering — Theory & Practice, 2017, 37(1): 172-181.)

[23] 馬雪麗, 王淑云, 劉曉冰, 等. 易腐食品二級供應鏈生產調度與配送路線的協(xié)同優(yōu)化[J]. 工業(yè)工程與管理, 2017, 22(2): 46-52.(MA X L, WANG S Y, LIU X B, et al. Integrated optimization of production scheduling and distribution for perishable food products in two-echelon supply chain[J]. Industrial Engineering & Management, 2017, 22(2): 46-59.)

[24] AMORIM P, ALMADA-LOBO B. The impact of food perishability issues in the vehicle routing problem[J]. Computers & Industrial Engineering, 2014, 67(1): 223-233.

[25] 吳忠和, 陳宏, 趙千, 等. 時間約束下鮮活農產品供應鏈應急協(xié)調契約[J]. 系統(tǒng)管理學報, 2014, 23(1): 49-61.(WU Z H, CHEN H, ZHAO Q, et al. Supply chain disruptions coordination for fresh agricultural products under time constraints[J]. Journal of Systems & Management, 2014, 23(1): 49-61.)

[26] 公茂果, 焦李成, 楊咚咚, 等. 進化多目標優(yōu)化算法研究[J]. 軟件學報, 2009, 20(2): 271-289.(GONG M G, JIAO L C, YANG D D, et al. Research on evolutionary multi-objective optimization algorithm[J]. Journal of Software, 2009, 20(2): 271-289.)

[27] CZYZAK P, JASZKIEWICZ A. Pareto simulated annealing — a metaheuristic technique for multiple objective combinatorial optimization[J]. Journal of Multi-Criteria Decision Analysis, 1998, 7(1): 34-47.

This work is partially supported by the National Natural Science Foundation of China (71672154, 71502146), the Fundamental Research Funds for the Central Universities (2682014CX009EM), the Science and Technology Research Project of Hubei Provincial Department of Education (B2015119), the Foundation for High-level Talents of Southwest Jiaotong University-Emei Campus (10501X0096014).