李 彬，曾喜云，劉俊鑫

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

1 問題提出

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

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

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

2 問題求解

2.1 巡檢工人數(shù)量

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

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

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

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

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

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

2.3 各組巡檢線路與工作量

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

表3 各分組巡檢線路耗時 min

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

3 結(jié)語

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