吳 瑤,馬祖軍,鄭 斌

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

0 引言

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

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

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

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

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

1 問題建模

1.1 問題描述

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

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

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

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

(1)

其中:Tp為產(chǎn)品的有效生命周期。

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

圖1 產(chǎn)品新鮮度變化和接受條件

1.2 模型假設(shè)

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

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

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

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

1.3 符號(hào)說明

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

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

k表示產(chǎn)品生產(chǎn)批次的編號(hào),與配送批次一致,k∈K;

ti表示客戶i訂單交付的時(shí)間;

si表示客戶i訂單交付過程的服務(wù)時(shí)間;

gp表示產(chǎn)品p的最低新鮮度要求;

cij表示從客戶點(diǎn)i到客戶點(diǎn)j的路段行駛成本;

τij表示從客戶點(diǎn)i到客戶點(diǎn)j的路段行駛時(shí)間;

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

Tp表示產(chǎn)品p生產(chǎn)完成后的有效生命周期;

M表示很大的正數(shù);

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)

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

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

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

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

1.5 模型分析

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

(20)

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

(21)

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

2 算法設(shè)計(jì)

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

圖2 NSGA-Ⅱ流程

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

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

由于子串2的1和4位均為1,子串1對(duì)應(yīng)位置為5和4,表示客戶訂單5和4在第1批次生產(chǎn),配送過程的順序?yàn)?-4;同理,客戶訂單3、1和2在第3批次生產(chǎn),配送過程的順序?yàn)?-1-2。由于在子串2中未有2編號(hào),意味著第2生產(chǎn)批次為空,在實(shí)際生產(chǎn)過程中第3批次順位遞補(bǔ)為第2批次。

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

2.2 染色體適應(yīng)值

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

其最大取值為1,故目標(biāo)函數(shù)式(20)可轉(zhuǎn)化為:

其中：sgn(·)為符號(hào)函數(shù)。δi由式(21)進(jìn)行判斷,當(dāng)式(21)成立時(shí),δ=0;否則,δ=1。

2.3 解的快速非支配排序

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

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

步驟1 初始化。令Sa表示種群中受染色體a支配的個(gè)體集合，na表示支配染色體a的個(gè)體數(shù)目，F(xiàn)m表示第m前沿面的個(gè)體集合。初始化Sa=?,Fm=?,na=0。

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

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

步驟4i=i+1,當(dāng)Fi≠?時(shí),對(duì)于每個(gè)個(gè)體a∈Fi,每個(gè)個(gè)體b∈Sa,令nb=nb-1;若nb=0,則Rankb=i+1,Fi+1=Fi+1∪。

步驟5 若Fi+1=?,則終止；否則轉(zhuǎn)步驟4。

2.4 非劣面的擁擠密度排序

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

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

2.5 遺傳算子

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

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

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

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

2.6 終止條件

當(dāng)遺傳算法進(jìn)化代數(shù)達(dá)到最大迭代數(shù)Gen時(shí),算法終止并輸出最優(yōu)解方案。

3 算例分析

3.1 算例構(gòu)造

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

圖4 不同算法參數(shù)設(shè)置下的Pareto前沿面的解分布

客戶坐標(biāo)(X, Y)/km交付期限/h產(chǎn)品需求(A, B, C)客戶坐標(biāo)(X, Y)/km交付期限/h產(chǎn)品需求(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 算例求解

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

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

圖3 Pareto前沿面的解分布

3.3 算法性能分析

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

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

表2 典型的Pareto解

表3 NSGA-Ⅱ和PSA算法性能指標(biāo)的對(duì)比

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

3.4 最低新鮮度分析

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

因此,企業(yè)在實(shí)際生產(chǎn)/配送過程中,通過準(zhǔn)確評(píng)估客戶對(duì)產(chǎn)品的新鮮度要求,在一定程度可以降低配送過程中的成本開支。而當(dāng)客戶產(chǎn)品交付的新鮮度為優(yōu)先考慮目標(biāo)時(shí),企業(yè)可根據(jù)財(cái)力和效益多投入車輛運(yùn)營(yíng),以提高客戶的滿意度。

4 結(jié)語

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

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

參考文獻(xiàn)(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松弛分解的多產(chǎn)品生產(chǎn)-分銷系統(tǒng)的聯(lián)合決策[J]. 機(jī)械工程學(xué)報(bào), 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] 柏孟卓, 唐國(guó)春. 與交貨期有關(guān)的供應(yīng)鏈排序問題[J]. 運(yùn)籌學(xué)學(xué)報(bào), 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] 蔣大奎, 李波. 基于混合禁忌搜索算法的供應(yīng)鏈排序問題[J]. 機(jī)械工程學(xué)報(bào), 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] 李凱, 王明星, 楊平,等. 單機(jī)多車情形生產(chǎn)與配送協(xié)同調(diào)度算法[J]. 計(jì)算機(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] 劉玲, 李昆鵬, 劉志學(xué). 生產(chǎn)和運(yùn)輸協(xié)同調(diào)度問題的模型和算法[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] 吳瑤, 馬祖軍. 時(shí)變路網(wǎng)下帶時(shí)間窗的易腐食品生產(chǎn)-配送問題[J]. 系統(tǒng)工程理論與實(shí)踐, 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] 馬雪麗, 王淑云, 劉曉冰, 等. 易腐食品二級(jí)供應(yīng)鏈生產(chǎn)調(diào)度與配送路線的協(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] 吳忠和, 陳宏, 趙千, 等. 時(shí)間約束下鮮活農(nóng)產(chǎn)品供應(yīng)鏈應(yīng)急協(xié)調(diào)契約[J]. 系統(tǒng)管理學(xué)報(bào), 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] 公茂果, 焦李成, 楊咚咚, 等. 進(jìn)化多目標(biāo)優(yōu)化算法研究[J]. 軟件學(xué)報(bào), 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).