四川灾区巡视最优化路线的设计

第一组线路：成都——眉山——乐山——雅安——成都——都江堰——汶川——茂县——理县——茂县——北川——平武——青川——北川——绵竹——什邡——彭州——成都，所需的巡视时间为：

T8?0.89+0.74+1.73+0.66+1.86+1.56+1.17+0.79+1.87+1.55+1.17+1.16+0.38+0.53+0.51+1.58+2.28+0.81+7?2.5+1.5?6 =47.74 (小时) 第二组路线：成都——自贡——泸州——内江——资阳——遂宁——广安——南充——巴中——广元——安县——江油——安县——成都，所需巡视时间为：

T9?1.8+1.2+0.96+2.43+2.12+0.86+3.35+2.7+1.84+1.14+1.78+3.9+10?2.5+1.5

=50.58（小时） 此两组的均衡度

A4为：(50.58?47.74)?50.58?5.61%

（四）模型的评价与改进

１．本模型运用图论中最佳推销员路径问题的相关结论，建立了关于该类问题的严格的优化模型，但是可以说求得这类问题的精确最优解是十分困难的。因此本模型为了解决这类问题采用了近似的算法，得到的结果比较理想。

2 . 模型主观性相对较强，求出的均衡度比较符合要求。而且由于信息不够完善，本文在建模中考虑的因素不多，比如在巡视过程中的阻抗问题未加以考虑。本文中的模型适用范围相

对较窄，对市县较多等情况下的通用模型解决力度不够，耗时较多。对此可以采用更先进的算法或原理，比如遗传算法，神经网络算法，对问题加以解决。 3.

附录：

#include #include

#define TFACTR 0.9 #define MAX 10000.0

#define MBIG 1000000000 #define MSEED 161803398 #define MZ 0

#define FAC (1.0/MBIG) float weight[12][12]; int iorder[11]; void anneal(int ncity) {

int irbit(unsigned long *iseed); int metrop(float de,float t); float ran(long *idum);

float reverse_len(int ncity,int n[]); void reverse(int ncity,int n[]); float transe_len(int ncity,int n[]); void transe(int ncity,int n[]); int ans,nover,nlimit,i1,i2; int i,j,nsucc,nn,idec; unsigned long k; static int n[7]; long idum;

unsigned long iseed; float path,de,t,T;

nlimit=100*ncity;/*max succ try numbers path =0.0;

for(i=1;i

{ /* primitive path length */ i1=iorder[i]; i2=iorder[i+1];

path+=weight[i1][i2]; }

*/ i1=iorder[ncity]; i2=iorder[1];

path+=weight[i1][i2]; idum=-1; iseed=111; T=2.8;

for(j=1;j<=30;j++) {

nsucc=0;

for(k=1;k<=20000;k++) {

do {

n[1]=1+(int)(ncity*ran(&idum)); n[2]=1+(int)((ncity-1)*ran(&idum)); if(n[2]>=n[1]) ++n[2];

nn=1+((n[1]-n[2]+ncity-1)%ncity); }while(nn<3); idec=irbit(&iseed);

if(idec==0) {

n[3]=n[2]+(int)(abs(nn-2)*ran(&idum))+1; n[3]=1+((n[3]-1)%ncity); de=transe_len(ncity,n); ans=metrop(de,T); if(ans) {

++nsucc; path+=de; transe(ncity,n); } } else {

de=reverse_len(ncity,n); ans=metrop(de,T); if(ans) {

++nsucc; path+=de;

reverse(ncity,n); }

}

if(nsucc>=nlimit) break; }

printf(\ %s .6f %s .6f j=%d\ len=\

printf(\ moves: m\\n\ for(i=1;i<=11;i++)

printf(\ T*=TFACTR; if(nsucc==0) return; } }

float reverse_len(int ncity,int n[]) {

float de;

int xx[5],yy[5]; int j,ii;

n[3]=1+((n[1]+ncity-2)%ncity); n[4]=1+(n[2]%ncity); for(j=1;j<=4;j++) {

xx[j]=iorder[n[j]]; }

de=-weight[xx[1]][xx[3]]; de-=weight[xx[2]][xx[4]]; de+=weight[xx[1]][xx[4]]; de+=weight[xx[2]][xx[3]]; return de; }

void reverse (int ncity,int n[]) {

int nn,j,k,l,itmp;

nn=(1+((n[2]-n[1]+ncity)%ncity))/2; for(j=1;j<=nn;j++) {

k=1+((n[1]+j-2)%ncity); l=1+((n[2]-j+ncity)%ncity); itmp=iorder[k]; iorder[k]=iorder[l]; iorder[l]=itmp;