◎阮潔 呂雯 朱夢(mèng)云

基于適應(yīng)動(dòng)態(tài)分布農(nóng)機(jī)裝備的維修服務(wù)背景下，簡(jiǎn)化問(wèn)題為多旅行商問(wèn)題。以江西省為例，預(yù)測(cè)每個(gè)空間區(qū)域的需求，再根據(jù)此需求進(jìn)行維修服務(wù)區(qū)域劃分。以維修成本最小的原則確定維修站，并采用蟻群算法對(duì)此路線進(jìn)行優(yōu)化，最終以實(shí)際數(shù)據(jù)檢驗(yàn)。

一、引言

隨著科學(xué)技術(shù)的不斷發(fā)展，農(nóng)業(yè)機(jī)械已經(jīng)成為農(nóng)業(yè)生產(chǎn)的重要組成部分，其保有量與使用量不斷增加，這就對(duì)農(nóng)業(yè)機(jī)械的結(jié)構(gòu)、工作質(zhì)量、可靠性以及服務(wù)便捷性都提出了更高的要求。然而，現(xiàn)階段的一個(gè)顯著問(wèn)題是在農(nóng)機(jī)市場(chǎng)快速擴(kuò)展的情況下，農(nóng)機(jī)維修工作的需求量也在不斷增長(zhǎng)，農(nóng)機(jī)維修能力的滯后與農(nóng)機(jī)維修任務(wù)量大成為了一對(duì)顯著的矛盾體。對(duì)于動(dòng)態(tài)移動(dòng)、集群式作業(yè)的農(nóng)機(jī)裝備而言，隨生產(chǎn)任務(wù)跨區(qū)域動(dòng)態(tài)變化的地理位置，短時(shí)間內(nèi)大量農(nóng)機(jī)同時(shí)高強(qiáng)度作業(yè)的工作模式，故障發(fā)生后必須快速響應(yīng)的維修服務(wù)要求，這些特點(diǎn)給服務(wù)管理和決策帶來(lái)了全新挑戰(zhàn)。因此，加強(qiáng)各級(jí)關(guān)聯(lián)的農(nóng)機(jī)維修網(wǎng)點(diǎn)建設(shè)是一件必須且長(zhǎng)久受益的工作。

本文以維修成本最小為目標(biāo)函數(shù)，建立農(nóng)機(jī)維修服務(wù)區(qū)域劃分的數(shù)學(xué)規(guī)劃模型，并提出高效求解算法，通過(guò)模型的求解確定維修服務(wù)區(qū)域、維修點(diǎn)的選址及路線方案，以確定維修車各自的服務(wù)區(qū)域。

二、維修區(qū)域劃分模型的建立

1.建模思路。

依據(jù)目前我國(guó)農(nóng)業(yè)生產(chǎn)的基本情況，很多農(nóng)村依靠土地流轉(zhuǎn)，"連地成片"進(jìn)行耕種，可以確定以一個(gè)省為大的區(qū)域，在這個(gè)省內(nèi)進(jìn)行服務(wù)區(qū)域劃分，可以劃分為若干個(gè)維修服務(wù)區(qū)域，每個(gè)維修服務(wù)區(qū)域由相近的幾個(gè)縣構(gòu)成，在每個(gè)維修服務(wù)區(qū)域設(shè)置一個(gè)維修點(diǎn)。

因此，本文建模思路是不完全按照縣的劃分條件下去劃分維修服務(wù)區(qū)域，而是為節(jié)省成本，擴(kuò)大每個(gè)維修服務(wù)區(qū)域，將若干個(gè)區(qū)縣劃分為一個(gè)服務(wù)責(zé)任區(qū)域，根據(jù)對(duì)該省的維修服務(wù)需求進(jìn)行預(yù)測(cè)，以及每個(gè)維修服務(wù)點(diǎn)所能承受的最大維修服務(wù)量來(lái)最終確認(rèn)劃分多少為多少區(qū)域，并盡量保證每個(gè)服務(wù)區(qū)域類的需求數(shù)量接近一致，再根據(jù)路線最優(yōu)化方案選擇出在該區(qū)域內(nèi)的維修站的最佳設(shè)計(jì)點(diǎn)，以及根據(jù)優(yōu)化得出最優(yōu)維修路線。

2.假設(shè)及變量意義。

①假定以縣區(qū)為一個(gè)空間單位（SU），每個(gè)維修區(qū)域單位（G）由若干個(gè)SU 構(gòu)成，每個(gè)G 中只有一個(gè)維修站，維修服務(wù)是通過(guò)該維修點(diǎn)派出維修車進(jìn)行的工作。

②現(xiàn)在已知每個(gè)SU 的預(yù)測(cè)需求量和每個(gè)G 內(nèi)的最大服務(wù)量（N），現(xiàn)規(guī)定每個(gè)服務(wù)區(qū)域內(nèi)的需求量要超過(guò)服務(wù)量的90%但不能超過(guò)最大服務(wù)量。

③同一個(gè)維修服務(wù)區(qū)域內(nèi)SU 同時(shí)需要維修服務(wù)。

參數(shù)及變量意義：

①uiG：每個(gè)維修區(qū)域G 內(nèi)的需求總和②xi：表示是否有維修站，xi∈{0，1}

③m，A 分別表示維修車總數(shù)和每輛維修車所能達(dá)到的最大服務(wù)要求。

④以點(diǎn)0 表示維修車的出發(fā)城市，稱為原點(diǎn)，點(diǎn)1，2，……l 表示m 個(gè)維修車需要維修的SU，（l 表示每個(gè)G 內(nèi)的SU 個(gè)數(shù)）因此定義以下變量：

否則

否則）

3.模型建立。

目標(biāo)函數(shù)Z 表示維修路線總的成本，

其中，

cij表示維修車經(jīng)過(guò)對(duì)應(yīng)弧段（i，j）距離，K=1，2……m

約束條件

其中j=0，1……l；k=1，2……m

在該模型中，式（1）表示m 個(gè)維修車維修過(guò)程中路程最大的那個(gè)最小化；式（2）表示各個(gè)維修車的路程；式（3）表示從維修站出發(fā)，所有的維修點(diǎn)都只停留一次；式（4）表示任一條弧的終點(diǎn)僅有一個(gè)起點(diǎn)與之相連；式（5）表示任一條弧的起點(diǎn)僅有一個(gè)終點(diǎn)與之相連。

三、維修區(qū)域劃分模型的求解以及優(yōu)化

1.維修區(qū)域劃分。

維修區(qū)域的劃分對(duì)最終的農(nóng)機(jī)裝備派送有很大的影響。合理的區(qū)域劃分能夠在較短的時(shí)間，以較低的成本完成農(nóng)機(jī)派送維修服務(wù)。因而選擇合理的區(qū)域劃分方法十分重要。

基于實(shí)際應(yīng)用場(chǎng)景的情況，我們采用聚類算法中的K-means 算法。K-means 聚類算法主要是對(duì)于給定的樣本集，按照樣本之間的距離大小，將樣本集劃分為k 個(gè)簇。讓簇內(nèi)的點(diǎn)盡量緊密的連在一起，而讓簇間的距離盡量的大。假設(shè)簇劃分為（C1，C2，…，Ck），目標(biāo)函數(shù)是Z。

運(yùn)用注意點(diǎn)：第一，k 的選擇以區(qū)域總需求/維修車數(shù)量的值上下浮動(dòng)10%左右。第二，每個(gè)區(qū)域內(nèi)需求大體相似，這樣有利于資源的充分利用。

傳統(tǒng)的k-means 聚類方法，隨機(jī)產(chǎn)生初始中心點(diǎn)，運(yùn)行時(shí)間長(zhǎng)，具有較大的隨意性，收斂效果差?；诖耍捎妹芏确ㄐЧ^好。

初始中心點(diǎn)以密度來(lái)定義，運(yùn)用兩點(diǎn)間歐氏距離的方法，求解所有對(duì)象間的相互距離，并求平均數(shù)mean（D）表示，確定領(lǐng)域半徑是對(duì)象數(shù)目，coefR 是半徑調(diào)節(jié)系數(shù)，0＜coefR＜1，經(jīng)驗(yàn)表明，coefR=0.13 效果最好。

2.基于蟻群算法的維修路線優(yōu)化。

將MTSP 定義為帶權(quán)無(wú)向圖G（V，E）。各個(gè)縣由圖上的頂點(diǎn)Vj表示，各個(gè)縣的路徑有圖上的邊ei表示，邊ei上的成本用w（ei）表示。MTSP 中，圖G（V，E）上需要定義m 個(gè)閉合回路C1，C2，…，Cm（i=1，2，…，m）。V0為倉(cāng)庫(kù)節(jié)點(diǎn)，V0∈Ci，w（Ci）為回路i 成本。MTSP 問(wèn)題可定義為如下模型：

蟻群算法室友意大利學(xué)者M(jìn).Dorigo等人在20 世紀(jì)90 年代初提出的一種智能算法，其真實(shí)地模擬了自然界螞蟻群體的覓食行為。M.Dorigo 等人將其用在解決旅行商問(wèn)題TSP，并取得了較好的結(jié)果。

蟻群算法的基本思路是：螞蟻在覓食過(guò)程中，會(huì)在所經(jīng)過(guò)的路徑上釋放一種具有揮發(fā)性的物資——信息素，不同螞蟻個(gè)體通過(guò)感知信息素的存在及其強(qiáng)度指導(dǎo)自己的移動(dòng)方向。最終，整個(gè)蟻群能夠搜索出巢穴與食物源之間的最優(yōu)路徑。

（1）狀態(tài)轉(zhuǎn)移概率準(zhǔn)則。

每臺(tái)維修車選擇下一個(gè)維修區(qū)縣時(shí)按照如下偽隨機(jī)概率選擇規(guī)則進(jìn)行：

其中τik（t）為t 時(shí)刻區(qū)縣i 到區(qū)縣j間的信息素軌跡值；ηij為相對(duì)于區(qū)縣i 區(qū)縣j 的能見(jiàn)度；α 是能見(jiàn)度在概率選擇因素中的相對(duì)重要性系數(shù)；S 為未訪問(wèn)區(qū)縣的集合；q 為滿足均勻分布的隨機(jī)數(shù)，參數(shù)qo值越低進(jìn)行隨機(jī)選擇的概率越高；I 為隨機(jī)變量，其選擇根據(jù)如下分布：

根據(jù)該規(guī)則，當(dāng)鄰域中沒(méi)有被訪問(wèn)的城市時(shí)，算法以概率q0選擇最佳的下一城市，以概率（1-q0）按照式（9）的概率分布隨機(jī)選擇下一城市。這一過(guò)程直到所有城市被訪問(wèn)。

（2）信息素軌跡更新。

信息素軌跡更新遵循最大最小蟻群算法框架：算法開(kāi)始每條路徑上的信息素軌跡初始化為τmax，迭代過(guò)程中信息素軌跡限制在區(qū)間[τmin，τmax]。τmin和τmax定義如下：

其中ρ 為信息素軌跡保持系數(shù)（1-ρ即為揮發(fā)系數(shù)）；f（sgb）是全局最優(yōu)解（sgb）的路徑長(zhǎng)度；n 是所有城市的數(shù)目。

解的構(gòu)造過(guò)程之后，信息素軌跡以全局最優(yōu)解為基礎(chǔ)更新，更新規(guī)則如下

其中

式（12）表示只有屬于全局最優(yōu)解的那些邊才會(huì)加強(qiáng)。

四、模型應(yīng)用

文章中建立的維修區(qū)域劃分模型以及路徑優(yōu)化模型將應(yīng)用于江西省農(nóng)機(jī)裝備維修服務(wù)區(qū)域中，以縣為空間單位SU，劃分成不同的維修區(qū)域單位G。并基于此計(jì)算出最優(yōu)的維修車的數(shù)量及其維修路徑。

1.確定空間單位。

江西省共100 個(gè)空間單位。包括市轄區(qū)25 個(gè)、縣級(jí)市11 個(gè)、縣64 個(gè)（11 個(gè)市區(qū)不列入數(shù)據(jù)內(nèi)）。

2.劃分維修區(qū)域。

利用K-means 算法，對(duì)于給定的100個(gè)空間單位樣本集，按照樣本之間的距離大小，將樣本集劃分為k 簇。讓簇內(nèi)的點(diǎn)盡量緊密的連在一起，而讓簇間的距離盡量的大，使其具有"高內(nèi)聚，低耦合"的特點(diǎn)，目的是減少維修路徑，節(jié)省維修成本，提高維修效率。

3.利用蟻群算法確定維修站的所在地和路徑優(yōu)化。

每個(gè)維修區(qū)域有且僅有一個(gè)維修站，維修站派出維修車，基于維修車優(yōu)化后的路徑進(jìn)行維修。

五、結(jié)語(yǔ)

本文針對(duì)農(nóng)業(yè)生產(chǎn)的時(shí)間和地域差異性和維修地點(diǎn)不固定的問(wèn)題，利用K-means 方法建立維修服務(wù)區(qū)域劃分，并利用蟻群算法優(yōu)化模型，提出相應(yīng)求解算法，并以江西省農(nóng)機(jī)維修為實(shí)例作仿真應(yīng)用，打破了地理的限制，解決了跨區(qū)域維修的難題。

服務(wù)區(qū)域的合理劃分和優(yōu)化可進(jìn)一步優(yōu)化服務(wù)站配置決策及大幅度節(jié)約路徑成本，在服務(wù)系統(tǒng)應(yīng)用中具有重大意義的，特別是對(duì)于流動(dòng)性強(qiáng)，區(qū)域范圍大，樣本多的服務(wù)系統(tǒng)，更加值得重視。