李金良 王西彬 胡耀光 任維波

(1.北京理工大學(xué)機(jī)械與車輛學(xué)院, 北京 100081; 2.中北大學(xué)機(jī)械工程學(xué)院, 太原 030051)

0 引言

維護(hù)服務(wù)網(wǎng)絡(luò)是由制造商構(gòu)建為顧客提供及時(shí)、滿意的維修服務(wù)而形成的網(wǎng)絡(luò)[1]。服務(wù)網(wǎng)絡(luò)設(shè)計(jì)規(guī)劃的研究主要集中于救援、醫(yī)護(hù)、消防等多個(gè)領(lǐng)域。但是目前,裝備功能愈加復(fù)雜,作業(yè)任務(wù)更加繁重,這對(duì)裝備的可靠作業(yè)及運(yùn)維服務(wù)提出了更高要求[2]。尤其是在農(nóng)業(yè)領(lǐng)域,農(nóng)機(jī)裝備已成為提高農(nóng)業(yè)生產(chǎn)效率、降低農(nóng)民作業(yè)負(fù)擔(dān)的關(guān)鍵工具。受限于農(nóng)作物的地理位置與成熟時(shí)間,農(nóng)機(jī)裝備分布在廣泛的地理區(qū)域內(nèi)[3]。隨著農(nóng)作物由南到北依次成熟,農(nóng)機(jī)裝備作業(yè)過程隨之呈現(xiàn)由南向北的集群跨區(qū)作業(yè)趨勢[4]。尤其是“三夏”農(nóng)忙時(shí)節(jié),農(nóng)機(jī)跨區(qū)作業(yè)已經(jīng)成為了重要的農(nóng)業(yè)機(jī)械服務(wù)模式,可以更好地利用和配置農(nóng)機(jī)裝備,提高農(nóng)田作業(yè)效率[5]。

但是由于作業(yè)過程的高溫和復(fù)雜作業(yè)環(huán)境,農(nóng)機(jī)裝備很容易發(fā)生故障,而維修服務(wù)往往無法及時(shí)到達(dá),嚴(yán)重影響集群協(xié)同作業(yè)效率[6]。因此,農(nóng)機(jī)制造企業(yè)需要構(gòu)建動(dòng)態(tài)維護(hù)服務(wù)網(wǎng)絡(luò)來保障對(duì)農(nóng)機(jī)裝備維護(hù)服務(wù)的及時(shí)高效[7]。一方面,制造企業(yè)會(huì)建立靜態(tài)服務(wù)站,這些靜態(tài)服務(wù)站布局在固定的位置為其服務(wù)區(qū)域內(nèi)的故障農(nóng)機(jī)提供維修服務(wù);另一方面,為了應(yīng)對(duì)農(nóng)忙時(shí)節(jié)裝備移動(dòng)與故障激增的情況,制造企業(yè)會(huì)提供動(dòng)態(tài)服務(wù)車來彌補(bǔ)靜態(tài)服務(wù)站能力不足的情況。這些動(dòng)態(tài)服務(wù)車也會(huì)隨著農(nóng)機(jī)裝備集群的動(dòng)態(tài)移動(dòng)而進(jìn)行調(diào)整[8]。因此,本文以農(nóng)機(jī)集群的動(dòng)態(tài)維護(hù)服務(wù)網(wǎng)絡(luò)為研究對(duì)象,重點(diǎn)研究靜態(tài)服務(wù)站和動(dòng)態(tài)服務(wù)車的服務(wù)設(shè)施選址和服務(wù)區(qū)域劃分問題。

目前,服務(wù)網(wǎng)絡(luò)規(guī)劃已經(jīng)廣泛應(yīng)用于各個(gè)方面,例如消防和救援服務(wù)網(wǎng)絡(luò)系統(tǒng)、供應(yīng)鏈網(wǎng)絡(luò)系統(tǒng)、醫(yī)療保健服務(wù)網(wǎng)絡(luò)系統(tǒng)、農(nóng)機(jī)裝備服務(wù)網(wǎng)絡(luò)系統(tǒng)等[9-10]。在服務(wù)設(shè)施選址方面,服務(wù)網(wǎng)絡(luò)設(shè)施選址主要解決在給定的可選位置集合情況下確定相關(guān)服務(wù)設(shè)施的合理位置[11]。在服務(wù)設(shè)施選址過程中,部分服務(wù)設(shè)施總是處于固定的位置以滿足服務(wù)網(wǎng)絡(luò)客戶的需求,如保健醫(yī)院、物流中心、倉庫和維修服務(wù)站等[12]。但是,在大部分情況下,服務(wù)中心需要調(diào)整服務(wù)設(shè)施的位置以適應(yīng)用戶需求的動(dòng)態(tài)變化[13]。服務(wù)設(shè)施選址模型主要包括覆蓋模型、P-中值模型和P-中心模型[14-15]。服務(wù)區(qū)域劃分是指對(duì)每個(gè)服務(wù)設(shè)施劃分合適的服務(wù)區(qū)域,從而保證區(qū)域內(nèi)所有的服務(wù)需求及時(shí)交付。服務(wù)區(qū)域劃分方法主要包括:P-區(qū)域模型、隨機(jī)優(yōu)化模型、聚類方法和局部搜索方法等。在求解方法方面,研究人員目前已經(jīng)開發(fā)了許多方法,主要包括精確求解方法和啟發(fā)式算法等。其中,精確求解算法主要包括商業(yè)求解器CPLEX、分支定界算法、Benders分解算法等,啟發(fā)式算法主要包括禁忌搜索算法、模擬退火算法、粒子群優(yōu)化算法和遺傳算法等[16-18]。如ARABANI等[19]系統(tǒng)分析了動(dòng)態(tài)設(shè)施選址決策問題,從決策模型和方法、應(yīng)用領(lǐng)域和未來趨勢等方面對(duì)動(dòng)態(tài)設(shè)施選址問題進(jìn)行分類。REN等[1]針對(duì)維護(hù)服務(wù)網(wǎng)絡(luò)服務(wù)區(qū)域劃分問題,綜合考慮服務(wù)均衡和服務(wù)成本最小化,并以湖南省的服務(wù)網(wǎng)絡(luò)為例進(jìn)行了實(shí)例驗(yàn)證。

尤其是在農(nóng)機(jī)維護(hù)服務(wù)網(wǎng)絡(luò)規(guī)劃領(lǐng)域,REN等[7]針對(duì)農(nóng)機(jī)維護(hù)服務(wù)網(wǎng)絡(luò)服務(wù)商選擇問題,綜合考慮服務(wù)商評(píng)價(jià)的單體評(píng)價(jià)和整體評(píng)價(jià)指標(biāo)選擇最合適的服務(wù)商。REN等[8]綜合考慮靜態(tài)服務(wù)商和動(dòng)態(tài)服務(wù)車選址問題,基于啟發(fā)式算法實(shí)現(xiàn)農(nóng)機(jī)故障動(dòng)態(tài)響應(yīng)。HAN等[20]針對(duì)動(dòng)態(tài)維修站的設(shè)施選址和資源分配問題,以最小化運(yùn)維服務(wù)成本為優(yōu)化目標(biāo),構(gòu)建了混合整數(shù)規(guī)劃模型,提出運(yùn)用Benders分解算法進(jìn)行動(dòng)態(tài)設(shè)施選址與優(yōu)化決策。

盡管目前研究服務(wù)網(wǎng)絡(luò)設(shè)施選址決策較多,但農(nóng)機(jī)集群動(dòng)態(tài)移動(dòng)對(duì)服務(wù)設(shè)施選址提出了更高的要求:①與傳統(tǒng)的離散點(diǎn)選址不同,農(nóng)機(jī)維護(hù)服務(wù)網(wǎng)絡(luò)選址過程中,農(nóng)機(jī)裝備集群通常分布在廣泛的作業(yè)區(qū)域內(nèi),傳統(tǒng)的離散選址難以解決農(nóng)機(jī)裝備集群維護(hù)服務(wù)網(wǎng)絡(luò)規(guī)劃問題。更進(jìn)一步,為了提高農(nóng)機(jī)裝備集群維護(hù)服務(wù)網(wǎng)絡(luò)規(guī)劃效率,本文將臨近區(qū)域的農(nóng)機(jī)裝備整合為一個(gè)單元區(qū)域進(jìn)行設(shè)施選址。②現(xiàn)有的研究忽略了服務(wù)網(wǎng)絡(luò)的服務(wù)區(qū)域劃分問題,尤其是在農(nóng)機(jī)維護(hù)服務(wù)網(wǎng)絡(luò)中,必須要考慮每個(gè)服務(wù)商的服務(wù)范圍,并且保障服務(wù)區(qū)域的連續(xù),即靜態(tài)服務(wù)站服務(wù)的所有單元區(qū)域在地理上是連續(xù)的,不允許進(jìn)行跨區(qū)服務(wù)。③現(xiàn)有的研究忽略了靜態(tài)服務(wù)設(shè)施與動(dòng)態(tài)服務(wù)設(shè)施的綜合選址,往往僅考慮靜態(tài)服務(wù)合適或者動(dòng)態(tài)服務(wù)設(shè)施的單種設(shè)施選址問題。因此,本文從決策優(yōu)化模型和求解算法兩方面提出面向農(nóng)機(jī)裝備集群維護(hù)服務(wù)網(wǎng)絡(luò)的服務(wù)設(shè)施選址和區(qū)域劃分方法。

1 問題描述

基于實(shí)際案例,本文考慮一個(gè)包括靜態(tài)服務(wù)站和動(dòng)態(tài)服務(wù)車的動(dòng)態(tài)服務(wù)網(wǎng)絡(luò)。為了提高計(jì)算效率,臨近的多個(gè)需求點(diǎn)將整合為一個(gè)單元區(qū)域。因此動(dòng)態(tài)分布式裝備集群維護(hù)服務(wù)網(wǎng)絡(luò)的服務(wù)設(shè)施選址問題考慮在單元區(qū)域服務(wù)需求動(dòng)態(tài)變化的情況下,以最小化運(yùn)維服務(wù)網(wǎng)絡(luò)成本為目標(biāo),在單元區(qū)域集合中選擇合適的單元區(qū)域建立靜態(tài)服務(wù)站或動(dòng)態(tài)服務(wù)車。靜態(tài)服務(wù)站的位置固定不變,而動(dòng)態(tài)服務(wù)車的位置則將根據(jù)單元區(qū)域的需求變化而動(dòng)態(tài)調(diào)整,同時(shí)根據(jù)選定的靜態(tài)服務(wù)站確定其服務(wù)的單元區(qū)域。

如圖1所示,整個(gè)區(qū)域由20個(gè)單元區(qū)域組成。假設(shè)靜態(tài)服務(wù)站和動(dòng)態(tài)服務(wù)車的位置以及動(dòng)態(tài)服務(wù)車的轉(zhuǎn)移路徑如圖1所示,整個(gè)區(qū)域共劃分為4個(gè)服務(wù)區(qū)域,并且每個(gè)服務(wù)區(qū)域設(shè)置一個(gè)靜態(tài)服務(wù)站。如靜態(tài)服務(wù)站8為單元區(qū)域1、2、6、7、8提供運(yùn)維服務(wù)。同時(shí),整個(gè)運(yùn)維服務(wù)過程劃分為3個(gè)階段,通過增加動(dòng)態(tài)服務(wù)車以彌補(bǔ)靜態(tài)服務(wù)站服務(wù)能力不足的情況。如在T1階段,動(dòng)態(tài)服務(wù)車位于單元區(qū)域16,協(xié)助靜態(tài)服務(wù)站17為單元區(qū)域16提供運(yùn)維服務(wù)。而在T2階段,動(dòng)態(tài)服務(wù)車移動(dòng)至單元區(qū)域7,此時(shí)動(dòng)態(tài)服務(wù)車協(xié)助靜態(tài)服務(wù)站8為單元區(qū)域7提供運(yùn)維服務(wù)。以此類推在T3階段,動(dòng)態(tài)服務(wù)車轉(zhuǎn)移至單元區(qū)域1,協(xié)助靜態(tài)服務(wù)站8為單元區(qū)域1提供運(yùn)維服務(wù)。

圖1 動(dòng)態(tài)運(yùn)維服務(wù)網(wǎng)絡(luò)示意圖Fig.1 Description of dynamic maintenance service network

假設(shè)條件:①單元區(qū)域的位置是固定已知的,并且單元區(qū)域的需求會(huì)進(jìn)行周期變化。②靜態(tài)服務(wù)站的服務(wù)范圍有限。③每個(gè)單元區(qū)域可以同時(shí)被靜態(tài)服務(wù)站和動(dòng)態(tài)服務(wù)車服務(wù),但同時(shí)只能被一個(gè)靜態(tài)服務(wù)站服務(wù)。④靜態(tài)服務(wù)站在完成維修維護(hù)服務(wù)后,會(huì)回到起點(diǎn)。⑤動(dòng)態(tài)服務(wù)車主要是彌補(bǔ)靜態(tài)服務(wù)站的服務(wù)能力,只能為動(dòng)態(tài)服務(wù)車所在的單元區(qū)域提供運(yùn)維服務(wù)。⑥由于動(dòng)態(tài)服務(wù)車使用成本高,并且由農(nóng)機(jī)制造商直接分配,因此單元區(qū)域的服務(wù)需求優(yōu)先被動(dòng)態(tài)服務(wù)車服務(wù)。⑦多輛動(dòng)態(tài)服務(wù)車可以選擇同一個(gè)單元區(qū)域。⑧靜態(tài)服務(wù)站服務(wù)的單元區(qū)域是連續(xù)的。⑨由于靜態(tài)服務(wù)站的建站成本固定不變,所以本文不考慮靜態(tài)服務(wù)站的建站成本。

2 數(shù)學(xué)模型

農(nóng)機(jī)裝備集群維護(hù)服務(wù)網(wǎng)絡(luò)的服務(wù)設(shè)施選址和區(qū)域劃分以運(yùn)維服務(wù)網(wǎng)絡(luò)成本最小化為目標(biāo),以確定靜態(tài)服務(wù)站的位置和服務(wù)區(qū)域以及動(dòng)態(tài)服務(wù)車的數(shù)量和位置。

2.1 參數(shù)與變量設(shè)置

(1)集合

I為單元區(qū)域集合,J為候選靜態(tài)服務(wù)站位置集合,K為候選動(dòng)態(tài)服務(wù)車位置集合,T為運(yùn)維服務(wù)階段集合,A為相鄰單元區(qū)域?qū)Α?/p>

(2)下標(biāo)

i、i′為單元區(qū)域索引,i,i′∈I;j為候選靜態(tài)服務(wù)站位置的索引,j∈J,J?I;k、k′為候選動(dòng)態(tài)服務(wù)車位置的索引,k,k′∈K,K?I;t為運(yùn)維服務(wù)階段的索引,t∈T。

(3)參數(shù)

(4)決策變量

2.2 決策優(yōu)化模型

以運(yùn)維服務(wù)網(wǎng)絡(luò)成本最小化為目標(biāo),構(gòu)建決策模型P0,表達(dá)式為

minf=f1+f2+f3

(1)

(2)

(3)

(4)

其中,式(1)表示動(dòng)態(tài)服務(wù)網(wǎng)絡(luò)總成本,主要包括兩方面:式(2)、(3)表示的動(dòng)態(tài)服務(wù)車的轉(zhuǎn)移成本和使用成本;式(4)表示的靜態(tài)服務(wù)站服務(wù)里程成本。

約束條件為

(5)

(6)

(7)

(8)

(9)

(10)

(11)

(12)

(13)

(14)

(15)

M=imax

(16)

(17)

其中,式(5)表示在候選靜態(tài)服務(wù)站單元區(qū)域選擇設(shè)置m個(gè)靜態(tài)服務(wù)站。式(6)表示每個(gè)單元區(qū)域只能被一個(gè)靜態(tài)服務(wù)站服務(wù)。式(7)表示每個(gè)服務(wù)區(qū)域內(nèi)只有一個(gè)靜態(tài)服務(wù)站。式(8)表示所有的單元區(qū)域被服務(wù)。式(9)表示每個(gè)候選動(dòng)態(tài)服務(wù)車單元區(qū)域在階段t設(shè)置的動(dòng)態(tài)服務(wù)車數(shù)量與階段t+1轉(zhuǎn)移的動(dòng)態(tài)服務(wù)車數(shù)量相同。式(10)約束靜態(tài)服務(wù)站的最大服務(wù)距離。式(11)～(13)參考文獻(xiàn)[1,16],并擴(kuò)展到本文的農(nóng)機(jī)裝備運(yùn)維服務(wù)網(wǎng)絡(luò),保證了分配給靜態(tài)服務(wù)站的單元區(qū)域的連續(xù)性,其中式(11)保障了單元區(qū)域i與服務(wù)區(qū)域的連續(xù)性,式(12)、(13)表示每個(gè)服務(wù)區(qū)域內(nèi)只有一個(gè)假想流槽,保障了服務(wù)區(qū)域內(nèi)的連續(xù)。式(14)～(17)用來限制各個(gè)變量的取值。

3 求解算法

3.1 模型線性化

minf=f1+f2+f3

(18)

(19)

(20)

(21)

約束條件除式(5)～(17),還包括

(22)

(23)

(24)

(25)

(26)

(27)

minf=f1+f2+f3

(28)

(29)

(30)

(31)

約束條件除式(5)～(17)、式(22)～(27)外,還包括

(32)

(33)

(34)

(35)

3.2 Benders分解算法

模型P2包括多個(gè)決策變量,其中變量x用來決定靜態(tài)服務(wù)站的選址,變量y用來表示服務(wù)單元分配結(jié)果,變量z決定動(dòng)態(tài)服務(wù)車輛在各個(gè)階段的轉(zhuǎn)移,變量w用來判斷分配之后的服務(wù)單元是否連續(xù)。由于模型中存在多個(gè)變量,因此本文采用Benders分解方法將原問題分解為兩個(gè)子問題:主問題(Master problem)基于變量x、y和z來判斷靜態(tài)服務(wù)站的選址和服務(wù)分配以及動(dòng)態(tài)服務(wù)車在各個(gè)階段的轉(zhuǎn)移;子問題(Subproblem)基于變量w用來判斷劃分之后的服務(wù)單元是否連續(xù)。

主問題 min{f:x,y,z}

約束條件為式(5)～(10)、式(14)～(16)、式(22)～(27)和式(32)～(35)。

子問題 min{0:w}

約束條件為式(11)～(13)和式(17)。

(36)

將生成的組合Benders切割公式(36)添加到主問題。這樣迭代重復(fù)求解主問題和子問題,直到求得原問題的最優(yōu)解。

4 案例

以河南省農(nóng)機(jī)裝備集群的運(yùn)維服務(wù)網(wǎng)絡(luò)規(guī)劃為例,確定靜態(tài)服務(wù)站和動(dòng)態(tài)服務(wù)車的位置以及服務(wù)區(qū)域劃分結(jié)果。

4.1 案例描述

以某農(nóng)機(jī)制造企業(yè)在河南省運(yùn)維服務(wù)為例,數(shù)據(jù)來自于河南省2019年5月16日至6月14日121個(gè)縣(單元區(qū)域)約7.5×104km2的糧食作物面積。這些單元區(qū)域如圖2所示。隨著農(nóng)作物由南向北依次成熟,整個(gè)收獲季節(jié)可以分為6個(gè)階段,每個(gè)階段5 d左右。每個(gè)單元區(qū)域的收獲作業(yè)任務(wù)一般持續(xù)1～2個(gè)階段。不同時(shí)間段內(nèi)各空間單元的農(nóng)機(jī)故障信息如圖3所示。不同時(shí)間段內(nèi)的各空間單元的農(nóng)機(jī)故障信息依據(jù)歷史故障數(shù)據(jù)、農(nóng)機(jī)保有量和農(nóng)田作業(yè)面積等[21],通過分析歷史故障數(shù)據(jù)中農(nóng)機(jī)故障數(shù)據(jù)與農(nóng)機(jī)保有量和農(nóng)田作業(yè)面積等關(guān)系,分析每個(gè)空間單元各個(gè)時(shí)間階段的農(nóng)機(jī)故障數(shù)量。

圖2 河南省單元區(qū)域Fig.2 Service units in Henan Province

圖3 不同時(shí)間段單元區(qū)域的故障數(shù)量Fig.3 Maintenance demands in different units at each stage

本文中每個(gè)單元區(qū)域都可以設(shè)置為靜態(tài)服務(wù)站和動(dòng)態(tài)服務(wù)車。同時(shí),為了在農(nóng)忙時(shí)節(jié)為故障農(nóng)機(jī)提供及時(shí)的維修服務(wù),整個(gè)維修服務(wù)網(wǎng)絡(luò)共建立12個(gè)靜態(tài)服務(wù)站。由于制造商要求靜態(tài)服務(wù)站必須在2 h內(nèi)達(dá)到故障農(nóng)機(jī)的位置,因此靜態(tài)服務(wù)站最大覆蓋距離為120 km。運(yùn)維服務(wù)過程中靜態(tài)服務(wù)站每單位里程費(fèi)用為3元/km,動(dòng)態(tài)服務(wù)車轉(zhuǎn)移成本為5元/km,動(dòng)態(tài)服務(wù)車每階段的使用成本為 8 000元,動(dòng)態(tài)服務(wù)車在每一階段可以為40個(gè)故障需求提供服務(wù)。

基于上述數(shù)據(jù),本文所有的求解都是在個(gè)人計(jì)算機(jī)上進(jìn)行,計(jì)算機(jī)的基本配置為AMD 4.00 GHz和16 GB RAM。

4.2 案例計(jì)算

首先,直接采用求解器GUROBI對(duì)動(dòng)態(tài)維護(hù)服務(wù)網(wǎng)絡(luò)設(shè)施選址與區(qū)域劃分問題進(jìn)行求解,最優(yōu)解無法在24 h內(nèi)獲得。因此,本文采用線性化方法和Benders分解算法對(duì)問題進(jìn)行求解,共經(jīng)歷3次迭代,共計(jì)用時(shí)1 601 s。運(yùn)維服務(wù)網(wǎng)絡(luò)維修總成本為2.103×106元。靜態(tài)服務(wù)站選址和區(qū)域劃分結(jié)果如圖4所示,動(dòng)態(tài)服務(wù)車在各個(gè)階段的位置如圖5(圖中橢圓表示動(dòng)態(tài)服務(wù)車位置)所示。

圖4 靜態(tài)服務(wù)站選址和區(qū)域劃分結(jié)果Fig.4 Location of static service stations and service region districting results

圖5 動(dòng)態(tài)服務(wù)車位置Fig.5 Location of dynamic service vehicles

如圖4所示,選擇單元區(qū)域3、11、17、33、60、70、74、87、96、110、113、117作為靜態(tài)服務(wù)站的位置。計(jì)算結(jié)果表明,靜態(tài)服務(wù)站一般會(huì)選擇在服務(wù)需求較多的單元區(qū)域,如單元區(qū)域11、74、87、110、113等。每個(gè)服務(wù)站服務(wù)的單元區(qū)域用不同的顏色來區(qū)分,可以發(fā)現(xiàn)基于選擇的靜態(tài)服務(wù)站,單元區(qū)域一般會(huì)劃分給距離最近的靜態(tài)服務(wù)站。例如,位于單元區(qū)域11的靜態(tài)服務(wù)站對(duì)單元區(qū)域8、9、10、11、12、42、44、45、62、63、106的故障農(nóng)機(jī)提供維修維護(hù)服務(wù)。而位于單元區(qū)域110的靜態(tài)服務(wù)站對(duì)單元區(qū)域88、107、108、109、110的農(nóng)機(jī)提供服務(wù)。

此外,在動(dòng)態(tài)服務(wù)網(wǎng)絡(luò)中,26輛動(dòng)態(tài)服務(wù)車參與農(nóng)機(jī)裝備維修服務(wù),動(dòng)態(tài)服務(wù)車在每個(gè)階段的位置如圖5所示。計(jì)算結(jié)果表明,動(dòng)態(tài)服務(wù)車一般會(huì)選擇每個(gè)階段除靜態(tài)服務(wù)站所在單元區(qū)域外故障需求數(shù)量較多的單元區(qū)域。在階段1,26輛動(dòng)態(tài)服務(wù)車主要位于單元區(qū)域93、94、95、97、98、99、101、118,主要位于河南省的最南端。在階段2,動(dòng)態(tài)服務(wù)車主要移動(dòng)至單元區(qū)域75、84、109、111、112、118、120。之后動(dòng)態(tài)服務(wù)車逐步向北移動(dòng),最后在階段6,動(dòng)態(tài)服務(wù)車移動(dòng)至單元區(qū)域31、32、34、40、53、54、55、56。收獲期間動(dòng)態(tài)服務(wù)車從南到北移動(dòng),這與農(nóng)作物從南到北成熟的趨勢也基本相同,這證明了本文模型和算法的有效性。

4.3 與兩階段決策對(duì)比

在實(shí)際生活中,農(nóng)機(jī)企業(yè)通常采用兩階段求解的方法來解決動(dòng)態(tài)維護(hù)服務(wù)網(wǎng)絡(luò)設(shè)施選址與區(qū)域劃分問題。所謂的兩階段求解方法是指首先解決靜態(tài)服務(wù)站的選址和區(qū)域劃分問題,然后再根據(jù)靜態(tài)服務(wù)站的位置去決策動(dòng)態(tài)服務(wù)車在不同階段的位置。因此,本節(jié)將兩階段求解方法與本文提出的聯(lián)合求解方法進(jìn)行對(duì)比。

兩階段求解結(jié)果如圖6所示,總成本為2.300×106元,與聯(lián)合決策結(jié)果相比增加9.37%,這也證明了本文提出模型的有效性。此外,基于聯(lián)合優(yōu)化方法和兩階段方法的動(dòng)態(tài)服務(wù)車的移動(dòng)成本和靜態(tài)服務(wù)站的服務(wù)里程成本如表1所示。在兩階段決策結(jié)果中,28輛動(dòng)態(tài)服務(wù)車參與農(nóng)機(jī)裝備維護(hù)服務(wù),因此,動(dòng)態(tài)服務(wù)車的使用和轉(zhuǎn)移成本高于聯(lián)合決策中的動(dòng)態(tài)服務(wù)車使用和轉(zhuǎn)移成本。而因?yàn)槎噍v動(dòng)態(tài)服務(wù)車的參與,靜態(tài)服務(wù)站的服務(wù)里程成本則低于聯(lián)合優(yōu)化決策的服務(wù)里程成本。

表1 優(yōu)化結(jié)果對(duì)比Tab.1 Comparison between two methods 元

圖6 兩階段靜態(tài)服務(wù)站選址與區(qū)域劃分結(jié)果Fig.6 Service region districting and service stations location in two-stage method

更進(jìn)一步,基于兩階段獨(dú)立決策,在進(jìn)行靜態(tài)服務(wù)站選址和服務(wù)區(qū)域劃分過程中,靜態(tài)服務(wù)站通常會(huì)選擇單元區(qū)域故障數(shù)量較多的單元區(qū)域,如33、87、113、60、74等單元區(qū)域。其他單元區(qū)域則基于連續(xù)性約束分配給距離最近的靜態(tài)服務(wù)站,以此獲得較低的靜態(tài)服務(wù)站服務(wù)里程成本。而在動(dòng)態(tài)服務(wù)車動(dòng)態(tài)選址決策中,動(dòng)態(tài)服務(wù)車則選擇在故障數(shù)量較多的單元區(qū)域。而在聯(lián)合決策中,靜態(tài)服務(wù)站的選址不僅考慮總故障數(shù)量最多的單元區(qū)域,同樣考慮在各個(gè)階段故障數(shù)量最多的單元區(qū)域。在這種情況下,靜態(tài)服務(wù)站則會(huì)選擇單元區(qū)域96、3、70、12等。如在圖4中位于單元區(qū)域96的靜態(tài)服務(wù)站,其服務(wù)區(qū)域包括94、95、96、97、98、99、100、101等單元區(qū)域。在階段1,動(dòng)態(tài)服務(wù)車主要位于靜態(tài)服務(wù)站的服務(wù)區(qū)域內(nèi)。在這種情況下,這些單元區(qū)域的故障維護(hù)主要由動(dòng)態(tài)服務(wù)車服務(wù),以保障總服務(wù)成本最小。而在階段2～階段6,單元區(qū)域96的維護(hù)需求大于單元區(qū)域95的維護(hù)需求,因此在這種情況下,靜態(tài)服務(wù)站選擇在單元區(qū)域96,可以獲得更小的服務(wù)成本。

因此,與兩階段決策相比,聯(lián)合調(diào)度決策綜合考慮各單元區(qū)域的總維護(hù)需求與各個(gè)階段的單元區(qū)域的故障維護(hù)需求,通過綜合決策靜態(tài)服務(wù)站和動(dòng)態(tài)服務(wù)車的位置,進(jìn)而獲得更小的維護(hù)服務(wù)成本。

4.4 參數(shù)敏感性

首先通過進(jìn)行參數(shù)敏感性分析來判斷靜態(tài)服務(wù)站數(shù)量m變化對(duì)總成本的影響,進(jìn)而選擇構(gòu)建最佳數(shù)量的靜態(tài)服務(wù)站。通過改變靜態(tài)服務(wù)站數(shù)量m來評(píng)估靜態(tài)服務(wù)站數(shù)量對(duì)計(jì)算結(jié)果的影響。首先通過減小m來獲得m的下限。結(jié)果表明當(dāng)m小于10時(shí),無法獲得最優(yōu)解。因此將m從10開始逐漸增加,假設(shè)單個(gè)靜態(tài)服務(wù)站的建站成本為1.0×105元,考慮靜態(tài)服務(wù)站建站成本的總成本和不考慮靜態(tài)服務(wù)站建站成本的總成本如表2所示。在不考慮靜態(tài)服務(wù)站建站成本時(shí),總成本隨著靜態(tài)服務(wù)站數(shù)量的增加而降低,但隨著靜態(tài)服務(wù)站數(shù)量的增加,總成本的變化逐漸變小。例如,靜態(tài)服務(wù)站的數(shù)量從10增加到11,總成本降低2.10×105元,而靜態(tài)服務(wù)站的數(shù)量從16增加到17,總成本只降低5.60×104元。在考慮靜態(tài)服務(wù)站建站成本時(shí),當(dāng)靜態(tài)服務(wù)站數(shù)量小于12時(shí),總成本隨著靜態(tài)服務(wù)站數(shù)量的增加而降低,而當(dāng)靜態(tài)服務(wù)站數(shù)量大于12時(shí),總成本隨著靜態(tài)服務(wù)站數(shù)量的增加而增加。因此,在本案例中,當(dāng)靜態(tài)服務(wù)站的數(shù)量設(shè)置為12時(shí),總服務(wù)成本最低。

表2 不同數(shù)量靜態(tài)服務(wù)站的成本Tab.2 Total costs for different value of m 元

其次,分析動(dòng)態(tài)服務(wù)車數(shù)量對(duì)總服務(wù)成本的影響。通過改變動(dòng)態(tài)服務(wù)車數(shù)量來評(píng)估動(dòng)態(tài)服務(wù)車數(shù)量對(duì)計(jì)算結(jié)果的影響,計(jì)算結(jié)果如表3所示。

表3 不同動(dòng)態(tài)服務(wù)車數(shù)量的成本Tab.3 Total costs for different number of vehicles 元

如表3所示,當(dāng)動(dòng)態(tài)服務(wù)車數(shù)量為26時(shí),總服務(wù)成本最小。因此在本案例中,最優(yōu)的動(dòng)態(tài)服務(wù)車數(shù)量為26。此外,當(dāng)動(dòng)態(tài)服務(wù)車數(shù)量大于26時(shí),總服務(wù)成本隨著動(dòng)態(tài)服務(wù)車數(shù)量的增加而增加,并且增加幅度變大。

因此,在實(shí)際案例中,決策者需要綜合考慮動(dòng)態(tài)服務(wù)車數(shù)量和靜態(tài)服務(wù)站數(shù)量,以便獲得更小的服務(wù)成本,更高的服務(wù)效率。

4.5 區(qū)域連續(xù)性

區(qū)域連續(xù)性主要通過式(11)～(13)和式(17)進(jìn)行約束。因此,采用線性化方法和Benders分解算法對(duì)去掉約束式(11)～(13)和式(17)的動(dòng)態(tài)服務(wù)網(wǎng)絡(luò)選址和區(qū)域劃分問題進(jìn)行求解,靜態(tài)服務(wù)站選址和區(qū)域劃分結(jié)果如圖7所示。忽略區(qū)域連續(xù)性約束的總服務(wù)成本為2.034×106元,總服務(wù)成本降低3.28%。

圖7 不考慮區(qū)域連續(xù)性的服務(wù)網(wǎng)絡(luò)規(guī)劃結(jié)果Fig.7 Location and districting results without contiguity

如圖7所示,靜態(tài)服務(wù)站103、104服務(wù)的單元區(qū)域107、119不連續(xù),因此在對(duì)其進(jìn)行維修服務(wù)時(shí),必須進(jìn)行跨區(qū)服務(wù)。這種跨區(qū)服務(wù)方案在農(nóng)業(yè)生產(chǎn)過程中通常是不可行的,這會(huì)導(dǎo)致服務(wù)延長和服務(wù)資源浪費(fèi)。決策者更愿意將單元區(qū)域104分配給其最近的靜態(tài)服務(wù)站107,從而保障靜態(tài)服務(wù)站107服務(wù)的單元區(qū)域是連續(xù)的。

通過改變m,對(duì)不同參數(shù)下的區(qū)域連續(xù)性約束進(jìn)行分析,計(jì)算結(jié)果如表4所示。

表4 不同靜態(tài)服務(wù)站數(shù)量的區(qū)域連續(xù)性分析Tab.4 Analysis of contiguity constraints with different value of m

如表4所示,在不考慮區(qū)域連續(xù)性約束時(shí),總服務(wù)成本均會(huì)降低。并且總服務(wù)成本的變化與靜態(tài)服務(wù)站的數(shù)量之間沒有關(guān)系。例如,當(dāng)m為 10時(shí),總服務(wù)成本降低0.93%,而當(dāng)m為16時(shí),總服務(wù)成本降低0.85%。

綜上所述,在維修服務(wù)過程中應(yīng)考慮區(qū)域連續(xù)性約束,以保障分配給靜態(tài)服務(wù)站的單元區(qū)域是連續(xù)的,以避免生成不可行的解決方案。

4.6 算法性能

對(duì)于動(dòng)態(tài)服務(wù)網(wǎng)絡(luò)選址和區(qū)域劃分問題,求解器GUROBI均不能在24 h內(nèi)獲得最優(yōu)解。對(duì)于線性化方法,部分案例可以在3 h內(nèi)求得最優(yōu)解,而其他案例的求解時(shí)間則大于6 h,甚至超過12 h。但是使用線性化方法結(jié)合Benders分解算法,所有案例的計(jì)算時(shí)間均在1 h內(nèi)。

此外,通過分析不同案例,本文所提出的線性化方法結(jié)合Benders分解算法的計(jì)算時(shí)間如表5所示。對(duì)于不同案例,Benders分解算法結(jié)合線性化方法始終是計(jì)算時(shí)間最短的一種方法。此外,對(duì)于求解器GUROBI,當(dāng)單元區(qū)域數(shù)量n小于100時(shí),最優(yōu)方案可以在24 h獲得,當(dāng)單元區(qū)域數(shù)量大于100時(shí),求解器GUROBI無法在24 h求得最優(yōu)解。對(duì)于線性化方法,當(dāng)單元區(qū)域數(shù)量大于200時(shí),計(jì)算時(shí)間大于12 h。對(duì)于線性化結(jié)合Benders分解方法,則所有的案例都可以在最短的時(shí)間內(nèi)求解,尤其是當(dāng)單元數(shù)量大于等于200時(shí),最優(yōu)解可以在3 h內(nèi)獲得,遠(yuǎn)小于其他兩種方法的時(shí)間。

表5 不同案例的計(jì)算時(shí)間Tab.5 Calculation time for cases with different sizes

總之,本文提出的Benders分解結(jié)合線性化方法對(duì)于求解動(dòng)態(tài)服務(wù)網(wǎng)絡(luò)選址和服務(wù)區(qū)域劃分問題表現(xiàn)出了良好的計(jì)算性能。

5 結(jié)論

(1)研究了面向農(nóng)機(jī)裝備的動(dòng)態(tài)維護(hù)服務(wù)網(wǎng)絡(luò)設(shè)施選址和區(qū)域劃分問題,以確定靜態(tài)服務(wù)站的位置和服務(wù)區(qū)域以及動(dòng)態(tài)服務(wù)車的動(dòng)態(tài)位置變化為目標(biāo),構(gòu)建了以最小化服務(wù)成本為目標(biāo)的決策模型。同時(shí),結(jié)合線性化方法和Benders分解算法進(jìn)行求解,并通過在河南省的實(shí)際案例證明了模型與算法的有效性和高效性。

(2)計(jì)算結(jié)果表明,靜態(tài)服務(wù)站一般會(huì)選擇在故障數(shù)量較多的單元區(qū)域,而隨著農(nóng)作物成熟,動(dòng)態(tài)服務(wù)車會(huì)移動(dòng)到其他故障數(shù)量較多的單元區(qū)域。更具體地,靜態(tài)服務(wù)站負(fù)責(zé)為服務(wù)區(qū)域內(nèi)的多個(gè)單元區(qū)域提供維護(hù)服務(wù)。但在農(nóng)忙季節(jié),隨著作物成熟,一些單元區(qū)域的維修需求急劇增加,動(dòng)態(tài)服務(wù)車會(huì)向這些單元區(qū)域移動(dòng),以彌補(bǔ)靜態(tài)服務(wù)站服務(wù)能力的不足。而這些動(dòng)態(tài)服務(wù)車可以在維修服務(wù)后轉(zhuǎn)移到其他單元區(qū)域。

(3)進(jìn)行了相關(guān)參數(shù)敏感性分析。分析結(jié)果表明,在不考慮靜態(tài)服務(wù)站建站成本時(shí),總服務(wù)成本會(huì)隨著靜態(tài)服務(wù)站數(shù)量的增加而下降。當(dāng)考慮靜態(tài)服務(wù)站建站成本時(shí),總服務(wù)成本隨著靜態(tài)服務(wù)站數(shù)量的增加先降低而后增加。并對(duì)算法的性能進(jìn)行分析,本文所提出的線性化方法結(jié)合Benders分解算法優(yōu)于現(xiàn)有的求解器 GUROBI 和線性化方法。