上传者: 26712065
|
上传时间: 2021-08-20 16:02:29
|
文件大小: 12.77MB
|
文件类型: PDF
8.4.3 多邮递员问题
邮局有k(k≥2)位投递员同时投递信件,全城街道都要投递,完成任务后
返回邮局,如何分配投递路线,使得完成投递任务的时间最早?我们把这一
问题记成KPP。
KPP的数学模型如下:
G(V,E)是连通图,v0∈V(G),求G的回路C1,…,Ck,使得
(1)v0∈V(Ci),i=1,2,…,k;
(2)max
1≤i≤ke∈E(Ci)
w(e)=min;
(3)∪
k
i=1
E(Ci)=E(G)。
·751·