面向跨區農機集群的動態維護服務網絡規劃方法

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

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

0 引言

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

但是由于作業過程的高溫和復雜作業環境,農機裝備很容易發生故障,而維修服務往往無法及時到達,嚴重影響集群協同作業效率[6]。因此,農機制造企業需要構建動態維護服務網絡來保障對農機裝備維護服務的及時高效[7]。一方面,制造企業會建立靜態服務站,這些靜態服務站布局在固定的位置為其服務區域內的故障農機提供維修服務;另一方面,為了應對農忙時節裝備移動與故障激增的情況,制造企業會提供動態服務車來彌補靜態服務站能力不足的情況。這些動態服務車也會隨著農機裝備集群的動態移動而進行調整[8]。因此,本文以農機集群的動態維護服務網絡為研究對象,重點研究靜態服務站和動態服務車的服務設施選址和服務區域劃分問題。

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

尤其是在農機維護服務網絡規劃領域,REN等[7]針對農機維護服務網絡服務商選擇問題,綜合考慮服務商評價的單體評價和整體評價指標選擇最合適的服務商。REN等[8]綜合考慮靜態服務商和動態服務車選址問題,基于啟發式算法實現農機故障動態響應。HAN等[20]針對動態維修站的設施選址和資源分配問題,以最小化運維服務成本為優化目標,構建了混合整數規劃模型,提出運用Benders分解算法進行動態設施選址與優化決策。

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

1 問題描述

基于實際案例,本文考慮一個包括靜態服務站和動態服務車的動態服務網絡。為了提高計算效率,臨近的多個需求點將整合為一個單元區域。因此動態分布式裝備集群維護服務網絡的服務設施選址問題考慮在單元區域服務需求動態變化的情況下,以最小化運維服務網絡成本為目標,在單元區域集合中選擇合適的單元區域建立靜態服務站或動態服務車。靜態服務站的位置固定不變,而動態服務車的位置則將根據單元區域的需求變化而動態調整,同時根據選定的靜態服務站確定其服務的單元區域。

如圖1所示,整個區域由20個單元區域組成。假設靜態服務站和動態服務車的位置以及動態服務車的轉移路徑如圖1所示,整個區域共劃分為4個服務區域,并且每個服務區域設置一個靜態服務站。如靜態服務站8為單元區域1、2、6、7、8提供運維服務。同時,整個運維服務過程劃分為3個階段,通過增加動態服務車以彌補靜態服務站服務能力不足的情況。如在T1階段,動態服務車位于單元區域16,協助靜態服務站17為單元區域16提供運維服務。而在T2階段,動態服務車移動至單元區域7,此時動態服務車協助靜態服務站8為單元區域7提供運維服務。以此類推在T3階段,動態服務車轉移至單元區域1,協助靜態服務站8為單元區域1提供運維服務。

圖1 動態運維服務網絡示意圖Fig.1 Description of dynamic maintenance service network

假設條件:①單元區域的位置是固定已知的,并且單元區域的需求會進行周期變化。②靜態服務站的服務范圍有限。③每個單元區域可以同時被靜態服務站和動態服務車服務,但同時只能被一個靜態服務站服務。④靜態服務站在完成維修維護服務后,會回到起點。⑤動態服務車主要是彌補靜態服務站的服務能力,只能為動態服務車所在的單元區域提供運維服務。⑥由于動態服務車使用成本高,并且由農機制造商直接分配,因此單元區域的服務需求優先被動態服務車服務。⑦多輛動態服務車可以選擇同一個單元區域。⑧靜態服務站服務的單元區域是連續的。⑨由于靜態服務站的建站成本固定不變,所以本文不考慮靜態服務站的建站成本。

2 數學模型

農機裝備集群維護服務網絡的服務設施選址和區域劃分以運維服務網絡成本最小化為目標,以確定靜態服務站的位置和服務區域以及動態服務車的數量和位置。

2.1 參數與變量設置

(1)集合

I為單元區域集合,J為候選靜態服務站位置集合,K為候選動態服務車位置集合,T為運維服務階段集合,A為相鄰單元區域對。

(2)下標

i、i′為單元區域索引,i,i′∈I;j為候選靜態服務站位置的索引,j∈J,J?I;k、k′為候選動態服務車位置的索引,k,k′∈K,K?I;t為運維服務階段的索引,t∈T。

(3)參數

(4)決策變量

2.2 決策優化模型

以運維服務網絡成本最小化為目標,構建決策模型P0,表達式為

minf=f1+f2+f3

(1)

(2)

(3)

(4)

其中,式(1)表示動態服務網絡總成本,主要包括兩方面:式(2)、(3)表示的動態服務車的轉移成本和使用成本;式(4)表示的靜態服務站服務里程成本。

約束條件為

(5)

(6)

(7)

(8)

(9)

(10)

(11)

(12)

(13)

(14)

(15)

M=imax

(16)

(17)

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

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包括多個決策變量,其中變量x用來決定靜態服務站的選址,變量y用來表示服務單元分配結果,變量z決定動態服務車輛在各個階段的轉移,變量w用來判斷分配之后的服務單元是否連續。由于模型中存在多個變量,因此本文采用Benders分解方法將原問題分解為兩個子問題:主問題(Master problem)基于變量x、y和z來判斷靜態服務站的選址和服務分配以及動態服務車在各個階段的轉移;子問題(Subproblem)基于變量w用來判斷劃分之后的服務單元是否連續。

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

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

子問題 min{0:w}

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

(36)

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

4 案例

以河南省農機裝備集群的運維服務網絡規劃為例,確定靜態服務站和動態服務車的位置以及服務區域劃分結果。

4.1 案例描述

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

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

圖3 不同時間段單元區域的故障數量Fig.3 Maintenance demands in different units at each stage

本文中每個單元區域都可以設置為靜態服務站和動態服務車。同時,為了在農忙時節為故障農機提供及時的維修服務,整個維修服務網絡共建立12個靜態服務站。由于制造商要求靜態服務站必須在2 h內達到故障農機的位置,因此靜態服務站最大覆蓋距離為120 km。運維服務過程中靜態服務站每單位里程費用為3元/km,動態服務車轉移成本為5元/km,動態服務車每階段的使用成本為 8 000元,動態服務車在每一階段可以為40個故障需求提供服務。

基于上述數據,本文所有的求解都是在個人計算機上進行,計算機的基本配置為AMD 4.00 GHz和16 GB RAM。

4.2 案例計算

首先,直接采用求解器GUROBI對動態維護服務網絡設施選址與區域劃分問題進行求解,最優解無法在24 h內獲得。因此,本文采用線性化方法和Benders分解算法對問題進行求解,共經歷3次迭代,共計用時1 601 s。運維服務網絡維修總成本為2.103×106元。靜態服務站選址和區域劃分結果如圖4所示,動態服務車在各個階段的位置如圖5(圖中橢圓表示動態服務車位置)所示。

圖4 靜態服務站選址和區域劃分結果Fig.4 Location of static service stations and service region districting results

圖5 動態服務車位置Fig.5 Location of dynamic service vehicles

如圖4所示,選擇單元區域3、11、17、33、60、70、74、87、96、110、113、117作為靜態服務站的位置。計算結果表明,靜態服務站一般會選擇在服務需求較多的單元區域,如單元區域11、74、87、110、113等。每個服務站服務的單元區域用不同的顏色來區分,可以發現基于選擇的靜態服務站,單元區域一般會劃分給距離最近的靜態服務站。例如,位于單元區域11的靜態服務站對單元區域8、9、10、11、12、42、44、45、62、63、106的故障農機提供維修維護服務。而位于單元區域110的靜態服務站對單元區域88、107、108、109、110的農機提供服務。

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

4.3 與兩階段決策對比

在實際生活中,農機企業通常采用兩階段求解的方法來解決動態維護服務網絡設施選址與區域劃分問題。所謂的兩階段求解方法是指首先解決靜態服務站的選址和區域劃分問題,然后再根據靜態服務站的位置去決策動態服務車在不同階段的位置。因此,本節將兩階段求解方法與本文提出的聯合求解方法進行對比。

兩階段求解結果如圖6所示,總成本為2.300×106元,與聯合決策結果相比增加9.37%,這也證明了本文提出模型的有效性。此外,基于聯合優化方法和兩階段方法的動態服務車的移動成本和靜態服務站的服務里程成本如表1所示。在兩階段決策結果中,28輛動態服務車參與農機裝備維護服務,因此,動態服務車的使用和轉移成本高于聯合決策中的動態服務車使用和轉移成本。而因為多輛動態服務車的參與,靜態服務站的服務里程成本則低于聯合優化決策的服務里程成本。

表1 優化結果對比Tab.1 Comparison between two methods 元

圖6 兩階段靜態服務站選址與區域劃分結果Fig.6 Service region districting and service stations location in two-stage method

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

因此,與兩階段決策相比,聯合調度決策綜合考慮各單元區域的總維護需求與各個階段的單元區域的故障維護需求,通過綜合決策靜態服務站和動態服務車的位置,進而獲得更小的維護服務成本。

4.4 參數敏感性

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

表2 不同數量靜態服務站的成本Tab.2 Total costs for different value of m 元

其次,分析動態服務車數量對總服務成本的影響。通過改變動態服務車數量來評估動態服務車數量對計算結果的影響,計算結果如表3所示。

表3 不同動態服務車數量的成本Tab.3 Total costs for different number of vehicles 元

如表3所示,當動態服務車數量為26時,總服務成本最小。因此在本案例中,最優的動態服務車數量為26。此外,當動態服務車數量大于26時,總服務成本隨著動態服務車數量的增加而增加,并且增加幅度變大。

因此,在實際案例中,決策者需要綜合考慮動態服務車數量和靜態服務站數量,以便獲得更小的服務成本,更高的服務效率。

4.5 區域連續性

區域連續性主要通過式(11)～(13)和式(17)進行約束。因此,采用線性化方法和Benders分解算法對去掉約束式(11)～(13)和式(17)的動態服務網絡選址和區域劃分問題進行求解,靜態服務站選址和區域劃分結果如圖7所示。忽略區域連續性約束的總服務成本為2.034×106元,總服務成本降低3.28%。

圖7 不考慮區域連續性的服務網絡規劃結果Fig.7 Location and districting results without contiguity

如圖7所示,靜態服務站103、104服務的單元區域107、119不連續,因此在對其進行維修服務時,必須進行跨區服務。這種跨區服務方案在農業生產過程中通常是不可行的,這會導致服務延長和服務資源浪費。決策者更愿意將單元區域104分配給其最近的靜態服務站107,從而保障靜態服務站107服務的單元區域是連續的。

通過改變m,對不同參數下的區域連續性約束進行分析,計算結果如表4所示。

表4 不同靜態服務站數量的區域連續性分析Tab.4 Analysis of contiguity constraints with different value of m

如表4所示,在不考慮區域連續性約束時,總服務成本均會降低。并且總服務成本的變化與靜態服務站的數量之間沒有關系。例如,當m為 10時,總服務成本降低0.93%,而當m為16時,總服務成本降低0.85%。

綜上所述,在維修服務過程中應考慮區域連續性約束,以保障分配給靜態服務站的單元區域是連續的,以避免生成不可行的解決方案。

4.6 算法性能

對于動態服務網絡選址和區域劃分問題,求解器GUROBI均不能在24 h內獲得最優解。對于線性化方法,部分案例可以在3 h內求得最優解,而其他案例的求解時間則大于6 h,甚至超過12 h。但是使用線性化方法結合Benders分解算法,所有案例的計算時間均在1 h內。

此外,通過分析不同案例,本文所提出的線性化方法結合Benders分解算法的計算時間如表5所示。對于不同案例,Benders分解算法結合線性化方法始終是計算時間最短的一種方法。此外,對于求解器GUROBI,當單元區域數量n小于100時,最優方案可以在24 h獲得,當單元區域數量大于100時,求解器GUROBI無法在24 h求得最優解。對于線性化方法,當單元區域數量大于200時,計算時間大于12 h。對于線性化結合Benders分解方法,則所有的案例都可以在最短的時間內求解,尤其是當單元數量大于等于200時,最優解可以在3 h內獲得,遠小于其他兩種方法的時間。

表5 不同案例的計算時間Tab.5 Calculation time for cases with different sizes

總之,本文提出的Benders分解結合線性化方法對于求解動態服務網絡選址和服務區域劃分問題表現出了良好的計算性能。

5 結論

(1)研究了面向農機裝備的動態維護服務網絡設施選址和區域劃分問題,以確定靜態服務站的位置和服務區域以及動態服務車的動態位置變化為目標,構建了以最小化服務成本為目標的決策模型。同時,結合線性化方法和Benders分解算法進行求解,并通過在河南省的實際案例證明了模型與算法的有效性和高效性。

(2)計算結果表明,靜態服務站一般會選擇在故障數量較多的單元區域,而隨著農作物成熟,動態服務車會移動到其他故障數量較多的單元區域。更具體地,靜態服務站負責為服務區域內的多個單元區域提供維護服務。但在農忙季節,隨著作物成熟,一些單元區域的維修需求急劇增加,動態服務車會向這些單元區域移動,以彌補靜態服務站服務能力的不足。而這些動態服務車可以在維修服務后轉移到其他單元區域。

(3)進行了相關參數敏感性分析。分析結果表明,在不考慮靜態服務站建站成本時,總服務成本會隨著靜態服務站數量的增加而下降。當考慮靜態服務站建站成本時,總服務成本隨著靜態服務站數量的增加先降低而后增加。并對算法的性能進行分析,本文所提出的線性化方法結合Benders分解算法優于現有的求解器 GUROBI 和線性化方法。