新年全國大學(xué)生數(shù)學(xué)建模競賽題

步分組,并用近似算法求每一組的近似最佳推銷員回路,再根據(jù)均衡度進(jìn)行微調(diào),

算法,得出總路程較短且各組盡可能均衡的路線,各組的巡視

公里,191.1

公里,總路程

組時各組的較優(yōu)巡視路線,各組的巡視時

小時,22.59

小時,22.54

3,求出完成巡小時,并用較為合理的分組的準(zhǔn)則,分成

研究了在不影響分組的均衡條件下,

組方案和路線.將每個鄉(xiāng)（鎮(zhèn)）或村看作一個圖的頂點(diǎn)，各鄉(xiāng)鎮(zhèn)、村之間的公路

i

……..各點(diǎn)的停留時間，即點(diǎn)權(quán)。i

……..各點(diǎn)的停留時間，即點(diǎn)權(quán)。本題是旅行售貨員問題的延伸－多旅行售貨員問題.本題所求的分組巡視的

使用近似算法來求得近似最優(yōu)解.(i,

j)……..任意兩點(diǎn)i

j

e

d

ij

i

j

dij

wi,

j

,E

,

E

,

,

用對角線完全算法（見[23]）產(chǎn)生一個初始

2、3、4

,

,......

,

,......

,

,......

i

i=1，2，3……n

i

wC

C

的權(quán)，i，j=1，2，3……n此問題是多個推銷員的最佳推銷員回路問題.即在加權(quán)圖

n

ii

i,

j

wCi

wi,

ji iiii i

w

j,ii

i

Ci

C

j

C

ii

說明分組的均衡性越好.取定一個

足條件（3）的分組是一個均衡分組.條件（4）表示總巡視路線最短。

個，我們只能去尋求一種較合理的劃分準(zhǔn)則，對圖１1－9

點(diǎn)到該點(diǎn)的最短路.故用圖

點(diǎn)出發(fā)的樹枝稱為干枝，見圖１１－１0，從圖中可以看出，從

準(zhǔn)則三：盡量將長的干枝與短的干枝分在同一組.

C

C

C

ii

O—P—28—27—26—N—24—23—22—17— 16—I—15—I—18—K—21—20—25—M—O O—2—5—6—7—E—8—E—9—F—10—F— —H—14—13—G—11—J—19—L—6—5 O—R—29—Q—30—32—31—33—35—34— A—1—B—C—3—D—4—D—3—2—O

ii

為分的組數(shù)).得

組，同時計算各組的停留時間,然后用成巡視的近似最佳時間.用算法一計算時，初始圈的輸入與分三組時同樣處理。

O—2—5—6—7—E—8—E—11 —G—12—H—12—F—10—F—9 —E—7—6—5—2—OO—R

—29—Q—30—Q—28—27 —26—N—24—23—22—17—16 —17

—22

—23

—N

—26

—P—M—25—20—21—K—18—I —15

—14

—13

—J

—19

—L

O—R—A—33—31—32—35—34 —B—1—C—3—D—4—D—3—

小時，t=1

公里/小時。若巡視人員足夠多，完成巡

12、10、15、22）開

點(diǎn)到每一個點(diǎn)的最短距離;

t

iV

i

第五步：若不能則依次判斷次遠(yuǎn)點(diǎn)、第三遠(yuǎn)點(diǎn)……,滿足總巡視時間不超過

T

T

X

i

, i

,

T，t

就得要求每組完成巡視時間盡量均衡,

對最佳巡視路線的影響。顯然在分組不變的情況下,

如何改變,

T，t

壞原來分組均衡的條件下，T，t

i

i

i

,

,

;

i,

j

K

,i j i j i j

T，t

（一）不影響分組的均衡時，T，t

i i i

i

Ki

K

,

i j

i

i

,

j

,n

i j iiK

,

,

ii

,n

(

)

(

i j i j

i

j

i

j

j

j

i

i

時，要保持原均衡分組不變，T

i j

ji j i ji

j i j i

j i j

時，要保持原均衡分組不變，t

i jj

j

i

ii j i jij i j ij i j

時，由（2）式得i j

j

i

i j i j

(

)

(

)

時，有i j i j

j

i

j

i

jii

j

j

i

j

i

j

i

ji i i i j

i j

i j

i j i j

i j

j i ji

j i j

i

i

i

i

,

i,

j

表6

不變時，t

不變時，V

（2）當(dāng)實(shí)際均衡度

不變時，t

小時；t

不變時，V

,即取

i,

j

i j i j

j i ji j現(xiàn)討論對停留時間相等的均衡分組,T,t,V

i

i,j

ji

j

i

j

i

i

i

i

ji,j

j

不變時,即

不變時,即

,i j i j i j 式知道，要保持平衡分組,V

i

i

j

i j

i j i j

ji

j

i

j

i,

j的含義同*

i

j

i

j

,

,

時,對圖進(jìn)行停留時間相等的均衡分組后,設(shè)

1、本文