77书库

手机浏览器扫描二维码访问

第47部分（第9页）

条线路）→起点（另一条线路）的顺序。第二列表示考察的两点的位置，若不满足位置条

件，显然不能连接，不再考察其它各项，在第四列划×，转其他点对。第三列表示连接后

线路的总货运量，若大于车辆容量，则在第四列中划×。

当一个点i不在线路上时，认为点i与中心仓库单独构成线路0→i→0。

由表12…18，得到最终送货线路分别为：

4吨货车：　0→4→6→5→0，其送货里程=20＋1＋6＋24=51公里

2。5吨货车：　0→1→2→3→0，其送货里程=9＋9＋10＋12=40公里

这样，完成上述送货任务需安排4吨和2。5吨货车各一辆，总送货里程为91公里。

12。4。4　遗传算法求解

遗传算法（Geic　Algorithm；GA）是由J。H。Holland等于70年代发展起来的。它是一

种以自然选择和遗传理论为基础，将生物进化过程中适者生存规则与同一群染色体的随机

信息变换机制相结合的搜索算法。其通过给解向量编码、形成初始种群，然后用变异、交

叉重组、自然选择等算子，进行并行迭代，求得优化解。由于它采用随机运算，对搜索空

间无特殊要求，无需求导，具有运算简单、收敛速度快等优点，因此近年来有很快的发

展，并在组合优化、自适应控制、机器学习等许多领域获得应用，有着广泛的应用前景。

应用遗传算法可方便地对式（12…16）到式（12…21）所表示的VSP模型进行求解。

从上述模型可知，求解的关键是合理确定车辆与各分仓库的关系；在满足车辆载重量和

分仓库需求约束条件的情况下使得总里程最小；因此可以构造遗传算法如下：

1。　构造染色体；产生初始种群

用矢量（S1　；S2　；。。。；Sl　）表示染色体G，其中元素（基因）S　j　为＇1；Kl＇之间的一个互不

重复的自然数，它表示了第j个确定第　m

=

（sj

。＇sj

。1　＇。　l）　个分库与路径　k=＇sj　。1　＇＋1的关系

（。。表示取整数；　下同。），即确定分库m是否由车辆（l）　k配送及确定分库　m在路径（l）　k中的顺序的

次序为j。随机产生一组染色体G　h　（h=1；2；。。。；n）（其中n为一代种群中的个体数），G　h　各

不相同，此为第一代种群。

2。　可行化过程

将染色体的编码向量映射为满足全部约束条件的可行解称为可行化，其过程如下：

a。　令分库需求条件满足的标志变量dz　m=0　（m=1；2；　…；l）。

b。　令路径k中的分库数目n　k=0　（k=1；2；。。。；K），令　bk

　=

bk

；Rk=φ　（k=1；2；。。。；K），路径

k中除去中心仓库后第i个位置的分库号为r　ki=0　（i=1；2；…；l）；即此时所有路径皆未形成。

j

c。　j=1。

d。　第j次确定分库m与路径k间的关系，其中；m

=

美国厚黑学-人生必胜之道  著名女性演说精粹  黑天鹅(军旅)  苍狼与白鹿  红色风暴  杀手的任务穿越  长沙王传  你为什么是穷人  痞子将军:战争之王  宇宙第一军  泣画  唤起心中的巨人  瓦岗英雄  二战大兵  心理操纵术  狼性法则  真本事来自好观念  不忍放开你的手  蛟郎  企业员工哲学:终极期望