李 彬，曾喜云，劉俊鑫

（湖南工學(xué)院數(shù)理科學(xué)與能源工程，湖南衡陽(yáng)421002）

1 問(wèn)題提出

某工廠(chǎng)為了安全生產(chǎn)的需要，將對(duì)26個(gè)點(diǎn)進(jìn)行巡檢，各點(diǎn)的位置如圖1所示，兩巡檢點(diǎn)之間連線(xiàn)上的數(shù)字表示兩點(diǎn)間行走耗時(shí)，每個(gè)點(diǎn)的巡檢耗時(shí)與巡檢周期如表1所示。每個(gè)點(diǎn)的巡檢需要一名工人，求至少需要安排幾名工人才能滿(mǎn)足巡檢要求？巡檢點(diǎn)該如何分配，才能使所有點(diǎn)按要求完成巡檢，并且每個(gè)工人的工作量比較均衡。

圖1 巡檢點(diǎn)連通關(guān)系

表1 巡檢點(diǎn)耗時(shí)與周期 min

2 問(wèn)題求解

2.1 巡檢工人數(shù)量

設(shè)tij為第i點(diǎn)到第j點(diǎn)的最短行走耗時(shí)，根據(jù)圖1各點(diǎn)的位置關(guān)系，利用FLOYD算法求出任意兩點(diǎn)之間行走最短耗時(shí)矩陣t=｛tij｝26×26。現(xiàn)假設(shè)只有一名工人在巡檢所有的點(diǎn)，他從某個(gè)點(diǎn)出發(fā)，把所有巡檢點(diǎn)都巡檢一遍再回到起點(diǎn)。他的總時(shí)間由兩部分構(gòu)成，其一是總的行走時(shí)間，這是一個(gè)26個(gè)點(diǎn)的TSP問(wèn)題[1]，采用Lingo編程得到最短時(shí)間為68 min；其二是每個(gè)點(diǎn)都巡檢一次的時(shí)間為67 min，總時(shí)間為135 min[2]。由于大多數(shù)巡檢點(diǎn)的巡檢周期為35 min，且，所以需要4名工人。

2.2 巡檢任務(wù)的分配

把26個(gè)點(diǎn)分成4組，每組安排一名工人。通過(guò)聚類(lèi)的方法把26個(gè)點(diǎn)按距離關(guān)系分成4組，建立規(guī)劃模型，優(yōu)化目標(biāo)為分在同一組內(nèi)的任意兩點(diǎn)間的行走耗時(shí)之和趨向于較小。設(shè)tij為第i點(diǎn)到第j點(diǎn)最短行走耗時(shí)，引入如下決策變量

其中，i=1，2，3，…，26，j=1，2，3，4，建立如下規(guī)劃模型

利用Lingo求得局部最優(yōu)解，如表2所示。

表2 巡檢點(diǎn)分組

2.3 各組巡檢線(xiàn)路與工作量

每組分配一名工人，一個(gè)周期總耗時(shí)為巡檢耗時(shí)與行走耗時(shí)之和。每組的行走耗時(shí)可看成TSP問(wèn)題進(jìn)行求解；巡檢耗時(shí)為各巡檢點(diǎn)巡檢耗時(shí)之和，求得結(jié)果如表3所示。

表3 各分組巡檢線(xiàn)路耗時(shí) min

從結(jié)果來(lái)看，只有第2組耗時(shí)38 min，略微超過(guò)了巡檢周期35 min，但第10個(gè)巡檢點(diǎn)巡檢周期為120 min，可安排每3個(gè)周期巡檢一次，總體上還可減少耗時(shí)。

3 結(jié)語(yǔ)

本文利用聚類(lèi)的方法對(duì)巡檢點(diǎn)進(jìn)行了任務(wù)分配，得出的結(jié)果較為滿(mǎn)意，只有個(gè)別組工作量略高，但可以在聚類(lèi)分組的基礎(chǔ)上進(jìn)行人工干預(yù)，對(duì)分組進(jìn)行微調(diào)，較易實(shí)現(xiàn)工作量的均衡分配。