龐劍飛，蔣俊成，馬 翠

基于交互式粒子群算法的部隊(duì)衛(wèi)生裝備巡修行程規(guī)劃設(shè)計(jì)

龐劍飛，蔣俊成，馬 翠

目的：建立基于交互式粒子群算法的部隊(duì)衛(wèi)生裝備巡修行程規(guī)劃模型，提高行程制訂的科學(xué)性、經(jīng)濟(jì)性。方法：首先將行程規(guī)劃問(wèn)題轉(zhuǎn)換為一類特殊的旅行商問(wèn)題，之后采用交互式粒子群算法進(jìn)行求解，并利用相對(duì)距離給定法與可量化屬性有效地緩解用戶在評(píng)價(jià)過(guò)程中的疲勞，最后通過(guò)對(duì)實(shí)際巡修任務(wù)進(jìn)行求解，驗(yàn)證模型的可行性、有效性。結(jié)果：該模型能夠根據(jù)實(shí)際巡修任務(wù)制訂出滿足任務(wù)需求與行車要求的行程，并在時(shí)間、費(fèi)用等方面盡可能令用戶滿意。結(jié)論：該模型可行性高、有效性強(qiáng)，其推廣應(yīng)用能夠有效提高部隊(duì)衛(wèi)生裝備巡修的效率與效益。

部隊(duì)衛(wèi)生裝備；巡修行程規(guī)劃；交互式粒子群算法

0 引言

衛(wèi)生裝備是部隊(duì)衛(wèi)生機(jī)構(gòu)遂行衛(wèi)勤保障任務(wù)的物質(zhì)基礎(chǔ)，加強(qiáng)衛(wèi)生裝備的維修保障，保持裝備完好率，對(duì)于維護(hù)官兵健康，提升部隊(duì)?wèi)?zhàn)斗力具有重要意義[1]。在全軍聯(lián)勤保障體系下，部隊(duì)衛(wèi)生裝備的維修主要依靠總部所—軍區(qū)所—區(qū)域性檢修站三級(jí)檢修機(jī)構(gòu)完成，各級(jí)衛(wèi)生機(jī)構(gòu)定期將需要維修的裝備上報(bào)，總部所將維修需求匯總，并按照保障范圍進(jìn)行任務(wù)分配，各檢修機(jī)構(gòu)根據(jù)分配的維修任務(wù)制訂巡修計(jì)劃，在規(guī)定的時(shí)間內(nèi)完成維修并上報(bào)維修情況[2-3]。維修機(jī)構(gòu)在巡修時(shí)，由于保障范圍廣，維修地點(diǎn)多，常常需要跨省市進(jìn)行，如何根據(jù)維修任務(wù)制訂最經(jīng)濟(jì)合理的巡修行程計(jì)劃是巡修人員面臨的難題[4]。鑒于此，本文首先將巡修行程規(guī)劃轉(zhuǎn)換為一類拓展的旅行商問(wèn)題（travelling salesman problem，TSP）問(wèn)題并利用交互式粒子群算法進(jìn)行求解，以期為巡修人員制訂一條在花費(fèi)、舒適度等方面均盡可能滿意的巡修計(jì)劃，并在提高衛(wèi)生裝備巡修效率的同時(shí)降低巡修成本。

1 行程規(guī)劃分析

巡修行程規(guī)劃與旅游行程規(guī)劃問(wèn)題類似，均屬于旅行商問(wèn)題的一個(gè)拓展[5]，巡修人員要在規(guī)定時(shí)間內(nèi)完成對(duì)多個(gè)維修需求點(diǎn)的維修保障，制訂一條最合理的巡修行程，從巡修機(jī)構(gòu)所在地出發(fā)，每個(gè)維修需求點(diǎn)訪問(wèn)一次，最后返回出發(fā)地點(diǎn)。行程的制訂不僅要求交通費(fèi)用、時(shí)間等可量化的指標(biāo)最優(yōu)，還要考慮舒適度、個(gè)人偏好、情感等主觀因素，屬于隱性目標(biāo)決策問(wèn)題，也是非決定性多項(xiàng)式完成（non-deterministic polynomial complete，NPC）問(wèn)題[6]。

1.1 基本概念定義

對(duì)某一檢修機(jī)構(gòu)，其保障范圍內(nèi)假設(shè)有n個(gè)維修需求點(diǎn)，需求點(diǎn)集合表示為DP={vi｜i=1，2，…，n}。

（1）行程段。維修需求點(diǎn)vi與vj組成的序偶，可表示為（vi，vj），其中i≠j，表示vi到vj的行程，包括時(shí)間、路程等。

（2）行程T。維修需求點(diǎn)的排列，表示對(duì)維修需求點(diǎn)的巡修順序。T=（0，vi1，vi2，…，vin，0），其中，0表示出發(fā)點(diǎn)，是集合的一個(gè)排列。

（3）單元屬性。維修需求點(diǎn)的信息，如維修點(diǎn)的維修任務(wù)耗時(shí)、到達(dá)時(shí)間、離開時(shí)間等。

（4）雙元屬性。行程段上的信息，如兩維修需求點(diǎn)之間的時(shí)間花費(fèi)、距離等。

（5）行程屬性。巡修行程的具體路線所展示的信息，如總的費(fèi)用、時(shí)間花費(fèi)等。

1.2 行程規(guī)劃模型建立

在某一檢修機(jī)構(gòu)的保障范圍內(nèi)，巡修人員需要制訂一條經(jīng)濟(jì)合理的行程來(lái)完成對(duì)維修需求點(diǎn)的裝備維修任務(wù)，即制訂一條在費(fèi)用、時(shí)間、舒適度等方面使巡修人員最滿意的行程。

式中：T∈NM，NM為所有可能的行程集合；S為行程的滿意度；G為行程需滿足的限制條件。

滿意度不僅包括可量化的指標(biāo)，如行程的距離、時(shí)間花費(fèi)、費(fèi)用花費(fèi)等，還包括不能或難以量化的值，如巡修人員對(duì)到達(dá)需求點(diǎn)時(shí)間偏好等，因此滿意度函數(shù)φ不能完全表示，無(wú)法通過(guò)解析方法得到最優(yōu)行程。對(duì)于此類問(wèn)題，常采用交互式智能算法（IEC）求解，即借助人的智能信息處理能力給出解方案的適應(yīng)度，使算法進(jìn)一步搜索更好的解。采用交互式智能算法，讓巡修人員人工地對(duì)行程進(jìn)行評(píng)價(jià)，促使問(wèn)題向巡修人員滿意的方向收斂，通過(guò)智能體的進(jìn)化，實(shí)現(xiàn)主觀情感空間向客觀特征空間的映射，最終得到滿意的行程。其中，巡修人員的評(píng)價(jià)值即為問(wèn)題的適應(yīng)度F（fitness），可表示為

式中：A（attribute）為行程T的屬性集；λ為巡修人員的心理偏好評(píng)價(jià)函數(shù)，是根據(jù)個(gè)人的知識(shí)、經(jīng)驗(yàn)和偏好等對(duì)行程的主觀評(píng)價(jià)。

2 算法設(shè)計(jì)與實(shí)現(xiàn)

2.1 標(biāo)準(zhǔn)粒子群算法

粒子群算法（particle swarm optimization，PSO）是一種智能進(jìn)化算法，從隨機(jī)解出發(fā)，采用“群體”與“進(jìn)化”的概念，通過(guò)迭代尋找最優(yōu)解并使用個(gè)體的適應(yīng)值評(píng)價(jià)解的優(yōu)劣[7]。該算法將每個(gè)鳥兒看作是D維搜索空間中一個(gè)沒有質(zhì)量和體積的粒子，在空間中只有一塊食物，每只鳥兒（粒子）按一定速度在空間中移動(dòng)，尋找這塊食物，這塊食物的位置即為最優(yōu)解，每個(gè)粒子飛行時(shí)根據(jù)周圍粒子和自身的位置調(diào)整速度的方向和大小直至尋找到最優(yōu)解。設(shè)粒子的種群規(guī)模為m；粒子i的位置為zi=（zi1，zi2，…，ziD），根據(jù)要解決的問(wèn)題設(shè)定適應(yīng)度函數(shù)并計(jì)算zi當(dāng)前的適應(yīng)值；vi=（vi1，vi2，…，viD）為粒子的飛行速度；pi=（pi1，pi2，…，piD）為粒子i目前搜索到的最優(yōu)位置；pg=（pg1，pg2，…，pgD）為整個(gè)粒子群目前搜索到的最優(yōu)位置，粒子的位置和速度更新公式為

式中：i=1，2，…，m；d=1，2，…，D；k為迭代次數(shù)；r1和r2為[0，1]之間的隨機(jī)數(shù)；c1為粒子跟蹤自己歷史最優(yōu)值的權(quán)重系數(shù)，表示粒子自身的認(rèn)識(shí)，稱為“認(rèn)知”，通常設(shè)置為2；c2為粒子跟蹤群體最優(yōu)值的權(quán)重系數(shù)，表示粒子對(duì)整個(gè)群體知識(shí)的認(rèn)識(shí)，稱為“社會(huì)知識(shí)”，一般設(shè)置為2；ω為慣性權(quán)重，衡量粒子的全局搜索能力與局部搜索能力。

2.2 改進(jìn)的粒子群算法

行程規(guī)劃問(wèn)題的解空間為離散空間，用PSO求解需對(duì)標(biāo)準(zhǔn)粒子群算法中粒子的位置、速度以及操作進(jìn)行重新定義[8]。

2.2.1 粒子的位置

行程規(guī)劃問(wèn)題的結(jié)果是得到具有最優(yōu)大用戶滿意度的哈密爾頓圈，其狀態(tài)空間即為所有行程的集合。粒子的位置可定義為一個(gè)包括所有維修需求點(diǎn)與出發(fā)點(diǎn)的哈密爾頓圈，即序列x=（n0，n1，…，nN，n0），其中ni∈E，E為狀態(tài)空間，設(shè)所有ni與ni+1之間的路徑存在。

2.2.2 粒子的速度

速度定義為粒子位置的置換序列集，表示一組置換序列的有序列表，可表示為v={（ik，jk）｜（ik，jk）∈{1，2，…，N}，k∈{1，2，…，}}，即先交換粒子中ik、jk的位置，然后交換ik+1、jk+1的位置，依此類推；表示該速度所含交換的數(shù)目。

2.2.3 粒子位置、速度、實(shí)數(shù)間的操作

粒子位置與速度的加法操作表示將一組置換序列依次作用于某個(gè)粒子位置，從而得到一個(gè)新位置，即新的行程排列。例如：位置為{l，5，2，4，3，l}+ {（2，4）}={1，5，4，2，3，1}。

粒子位置與位置相減后結(jié)果為一組置換序列，即速度。粒子速度與速度的加法操作為2個(gè)置換序列的合并，結(jié)果為一個(gè)新的置換序列，即一個(gè)新的速度。

實(shí)數(shù)c為[0，1]的任意實(shí)數(shù)，設(shè)速度v為k個(gè)置換序列，則乘法操作為對(duì)速度的置換序列進(jìn)行截取，使得新的速度的置換序列長(zhǎng)度為｜c(diǎn)×k｜（c×k取整）。

2.2.4 公式更新

粒子的速度、位置及其各種操作重新定義后，離散粒子群算法的速度更新公式表示如下：

式中，c1、c2、r1、r2與標(biāo)準(zhǔn)PSO算法中定義相同；⊕為兩交換序列的合并算子，表示速度與速度的加法操作；“－”表示粒子位置與位置的減法操作；“＋”表示粒子位置與速度的加法操作。

2.3 算法描述及策略

2.3.1 算法流程

圖1給出了交互式粒子群算法的流程，其計(jì)算過(guò)程如下：

（1）設(shè)定算法有關(guān)參數(shù)，包括種群數(shù)量、最大迭代次數(shù)、慣性權(quán)重等；

（2）隨機(jī)生成指定數(shù)量的粒子作為初始種群；

（3）巡修人員標(biāo)記當(dāng)代最優(yōu)粒子，并據(jù)此產(chǎn)生適應(yīng)度；

（4）滿意度判斷，若巡修人員對(duì)當(dāng)代最優(yōu)行程滿意，則結(jié)束，否則，進(jìn)行下一步；

（5）終止條件判斷，若已到達(dá)最大迭代次數(shù)，則結(jié)束，否則，轉(zhuǎn)（6）；

（6）粒子群更新，根據(jù)速度與位置更新公式產(chǎn)生種群新的位置，轉(zhuǎn)（3）。

圖1 交互式粒子群算法流程

2.3.2 適應(yīng)度策略

將行程T的屬性A分為可量化與不可量化2個(gè)部分，其中可量化部分包括總距離、總花費(fèi)（油耗、住宿等）、總時(shí)間；不可量化評(píng)價(jià)部分包括到達(dá)時(shí)間、離開時(shí)間等。雖然算法中粒子種群規(guī)模較小，但對(duì)每代個(gè)體進(jìn)行評(píng)價(jià)易導(dǎo)致用戶疲勞，若進(jìn)一步減少種群規(guī)模的話，則會(huì)影響算法的收斂速度，為此，采用相對(duì)距離給定法[9]與可量化行程屬性來(lái)計(jì)算適應(yīng)度。首先用戶在每代種群中選出一個(gè)最滿意的行程個(gè)體作為最優(yōu)個(gè)體，并給予固定的適應(yīng)度值F，則其他粒子的適應(yīng)度FE按下式計(jì)算：

式中：RD為粒子與最優(yōu)粒子之間路徑的相對(duì)距離；AT為粒子的可量化屬性。

對(duì)于行程T1與T2，其路徑相對(duì)距離計(jì)算如下：

式中：L為個(gè)體的程度即維修需求點(diǎn)的數(shù)量；Ls為T1、T2最長(zhǎng)相同子路徑的程度；S為最長(zhǎng)相同子路徑的位移；C為歸一化后行程的總花費(fèi)；WT為總時(shí)間；α、β∈R，表示權(quán)重。

式中：（ai，ai+1，…，ai+m）和（ai+k，ai+k+1，…，ai+k+m）是T1、T2最長(zhǎng)相同子路徑，其相對(duì)位移為

2.4 仿真實(shí)驗(yàn)及分析

以某三級(jí)維修站某年度維修任務(wù)為研究實(shí)例，在保障區(qū)域內(nèi)有A1～A15共計(jì)15個(gè)維修需求點(diǎn)，具體位置見表1。在巡修之前需對(duì)各點(diǎn)維修時(shí)間進(jìn)行預(yù)判（見表2）。假設(shè)汽車行駛的平均速度為70 km/h，人員住宿標(biāo)準(zhǔn)為100元/（人·d），燃油消耗為15 L/100 km，汽油價(jià)格為7.6元/L，巡修人員每天的工作時(shí)間為10 h，巡修行程是從維修站所在地出發(fā)，依次完成全部維修需求點(diǎn)的維修任務(wù)之后返回駐地，兩地間的距離采用公路距離。

表1 維修需求點(diǎn)位置分布

表2 各維修需求點(diǎn)維修時(shí)間估計(jì) h

具體行程安排時(shí)需滿足以下原則：（1）人員的工作時(shí)間為8：00—18：00，可適當(dāng)加班，但不超過(guò)1 h；（2）行車時(shí)間為8：00—22：00。

將粒子群算法中種群規(guī)模設(shè)置為20，初始慣性權(quán)重為0.96并隨迭代次數(shù)增加而遞減，最大迭代次數(shù)設(shè)為200，則權(quán)重分別為0.5、0.6；個(gè)體行程顯示總路程、總花費(fèi)、總時(shí)間及各點(diǎn)到達(dá)、離開時(shí)間等項(xiàng)目;算法結(jié)束方式為達(dá)到最大迭代次數(shù)或用戶手動(dòng)結(jié)束2種。利用Matlab對(duì)算法進(jìn)行實(shí)現(xiàn)，邀請(qǐng)巡修人員進(jìn)行評(píng)價(jià)，最終計(jì)算得到最滿意巡修行程如圖2所示，具體安排見表3。

圖2 巡修行程示意圖

表3 巡修行程具體安排 h

最滿意行程總路程為2 099 km，總的巡修時(shí)間為12 d，總的花費(fèi)（油耗、住宿、過(guò)路費(fèi)）為4 852元。通過(guò)修改指標(biāo)權(quán)重及行程要求還可制訂不同偏好、不同要求的行程方案，如時(shí)間較短、花費(fèi)較少、加班較少等。

3 討論

本文利用交互式粒子群算法對(duì)部隊(duì)衛(wèi)生裝備巡修行程規(guī)劃問(wèn)題進(jìn)行了建模與求解，幫助巡修人員制訂花費(fèi)少、效率高同時(shí)兼顧舒適度的巡修路線與安排。模型采用交互式粒子群算法對(duì)行程進(jìn)行尋優(yōu)，引入用戶評(píng)價(jià)機(jī)制，在迭代過(guò)程中，讓用戶對(duì)個(gè)體的適應(yīng)度（滿意度）進(jìn)行評(píng)價(jià)，標(biāo)記出用戶對(duì)行程個(gè)體滿意度，從而引導(dǎo)粒子群向用戶最滿意的位置移動(dòng)。采用相對(duì)距離給定法使用戶僅需在對(duì)少量行程個(gè)體進(jìn)行評(píng)價(jià)的情況下完成適應(yīng)度計(jì)算，減輕用戶疲勞。與人工制訂行程相比，本文提出的方法工作量小、操作簡(jiǎn)單，能夠?qū)傂谐虝r(shí)間、費(fèi)用花費(fèi)進(jìn)行有效控制。本文討論的衛(wèi)生裝備巡修行程規(guī)劃是在巡修前通過(guò)對(duì)行程時(shí)間、維修時(shí)間等因素的預(yù)測(cè)進(jìn)行的，實(shí)際巡修時(shí)可能會(huì)出現(xiàn)突發(fā)狀況，如維修時(shí)間增加或提前、擾亂既定的行程、對(duì)后續(xù)的行程不能按計(jì)劃進(jìn)行等情況，可通過(guò)對(duì)剩余巡修任務(wù)的分析重新制訂用戶滿意的行程。算法可進(jìn)一步推廣至其他行程規(guī)劃問(wèn)題，如旅行規(guī)劃、部隊(duì)巡診等。

[1]羅自力，何湘，荀魯川.部隊(duì)衛(wèi)生裝備維修保障工作形勢(shì)與對(duì)策[J].西南國(guó)防醫(yī)藥，2012，22（2）：209-211.

[2]方鐵，胡紅波.衛(wèi)生裝備管理服務(wù)網(wǎng)的設(shè)計(jì)與實(shí)現(xiàn)[J].醫(yī)療衛(wèi)生裝備，2013，34（8）：37-39.

[3]蔣忠偉，方梅華.醫(yī)院醫(yī)療設(shè)備維修管理方案的設(shè)計(jì)[J].醫(yī)療衛(wèi)生裝備，2013，34（8）：40-42.

[4]湯獻(xiàn)國(guó)，胡瑩.衛(wèi)生裝備巡檢巡修工作實(shí)踐與探索[J].醫(yī)療衛(wèi)生裝備，2014，35（8）：134-136.

[5]陸青，粱昌勇，黃永青，等.面向旅游行程規(guī)劃的交互式多智能體遺傳算法木[J].計(jì)算機(jī)應(yīng)用研究，2008，25（11）：3 311-3 313.

[6]陸青.基于IEC的隱性目標(biāo)智能決策方法研究[D].合肥：合肥工業(yè)大學(xué)，2009：20-24.

[7]曾建潮，介婧，崔志華.微粒群算法[M].北京：科學(xué)出版社，2004：12-18.

[8]Onwubolu，Godfrey C，Babu B V.New Optimization Techniques in Engineering[M].Berlin：SpringerBerlinHeidelberg，2004：219-239.

[9]許芳誠(chéng)．智能型多準(zhǔn)則決策支持研究：以交談式遺傳算法為基礎(chǔ)的模型[D].臺(tái)灣：國(guó)立中央大學(xué)，2000．

（收稿：2014-08-12 修回：2014-12-20）

Military medical equipment maintenance itinerary planning based on interactive particle swarm algorithm

PANG Jian-fei1,2,JIANG Jun-cheng1,MA Cui3
（1.Department of Medical Engineering,the 117th Hospital of the PLA,Hangzhou 310013,China;2.No.73232 Unit of the PLA,Zhoushan 316217,Zhejiang Province,China;3.Teaching and Research Section of Mathematics and Biomathematics, School of Biomedical Engineering of the Third Military Medical University,Chongqing 400038,China）

ObjectiveTo realize military medical equipment repair itinerary planning based on interactive particle swarm algorithm.MethodsItinerary planning was transformed into some traveling salesman problem,and then interactive particle swarm algorithm was utilized to solve the problem.The users′fatigue was alleviated efficiently during the evaluation process by methods of relative distance and quantifiable attributes.A solution was made based on practical maintenance to prove the feasibility and availability of the model.ResultsThe route planning model could make work schedule and traffic plan based on practical maintenance tasks and requests,which could also satisfy users with time cost,expenses, etc.ConclusionIt proves that the route planning model is of feasibility and availability by solution towards practical issues,thus can greatly improve efficiency and benefit of military medical equipment maintenance.[Chinese Medical E-quipment Journal，2015，36（3）：17-20]

military medical equipment;maintenance itinerary planning;interactive particle swarm algorithm

R318；TP18

A

1003-8868（2015）03-0017-04

10.7687/J.ISSN1003-8868.2015.03.017

重慶市自然科學(xué)基金項(xiàng)目（CSTC2013jcyjA10041）

龐劍飛（1989—），男，助理工程師，主要從事醫(yī)學(xué)圖像處理、醫(yī)療儀器維修與管理方面的研究工作，E-mail：jian11fei.happy@163.com。

310013杭州，解放軍117醫(yī)院醫(yī)學(xué)工程科（龐劍飛，蔣俊成）；316217浙江舟山，解放軍73232部隊(duì)（龐劍飛）；400038重慶，第三軍醫(yī)大學(xué)生物醫(yī)學(xué)工程學(xué)院數(shù)學(xué)與生物數(shù)學(xué)教研室（馬 翠）

馬 翠，E-mail：macui4956@163.com