按键盘上方向键 ← 或 → 可快速上下翻页，按键盘上的 Enter 键可回到本书目录页，按键盘上方向键 ↑ 可回到本页顶部！
————未阅读完？加入书签已便下次继续阅读！
0→6→5→7→3→0
0→4→8→2→1→0
相应的运输距离为：79。5
从上可见，遗传算法不失为VRP问题一个较优的满意解。而对上述算例的遗传算法过程
进行跟踪；发现每代最优个体的适应度变化如图5…31所示；说明所构造的遗传算法在较小的
种群规模下可以较快的速度进化，向最优解逼近。同时遗传算法也适用于规模较大的VRP问
题，对于具有如时间窗口、行驶里程限制等约束条件的VRP问题，通过实验证明，遗传算法
的求解性能也非常好，可以较快地找到问题的优化解或近似优化解。
0。015
0。0148
0。0146
0。0144
0。0142
0。014
0。0138
0。0136
0。0134
0。0132
0。013
图12…31GA寻优过程图
12…26
1 5 101520253035404550代数
适应度
本章小结
本章对产销运输问题、分配运输问题、最短路径问题、最小费用最大流问题、送货（集货）问题常见
运输问题进行了分析，建立了这些问题的数学模型，并就求解这些问题的基本方法如表上作业法、匈牙利
法、标号法、Dikstra法等进行了介绍，同时也就一些启发式算法、人工智能方法进行了分析和构造，如
扫描法、节约法、遗传算法、神经网络算法等等，这些对于掌握运输优化方法，提高运输管理水平具有重
要的意义。
思考题
1。下图为W仓库，A；B；C；D为4个需要配送的站点，图上每边上的数字为点对间的距离，请安
排从W出发，巡回配送每个站点的最短路线。
D
C
B
A
48
31
34
34
26
34
47
23
W
2。已知一个运输公司有两辆货车，一辆载重量为12吨，另一辆为10吨。该公司在
A；B；C；D；E；F6个城市装载货物，然后运回到货场o。货场和6城市间的距离以及
A；B；C；D；E；F6个城市需要装载的货物量均列在下表中，问如何安排车辆及运输线路比较合
理？
点对间距及载货需求表
间距 O A B C D E F
0 0 3 4 2 6 3 5
A 2 0 3 1 4 5 3
B 3 9 0 5 2 6 8
C 4 3 4 0 6 3 4
D 2 6 5 3 0 4 2
E 3 5 3 4 2 0 4
F 5 7 2 6 3 1 0
载货需求 6 5 8 5 6 7
3。设有某企业在a；b；c；d4个不同地区设有生产工厂生产同一种产品，每月产量分别为40，30，45和20（单位为吨），按计划调运到设在e；f；g的3个分配中心，分别为50，55和30（单位为吨）。已知各产地到各销地的单位产品运费（单位为元）如下表，请作出调运计
划，使调运费用最少。
单位运费表
产地
销地 e f g
12…27
a 17 16 14
b 11 14 13
c 15 11 14
d 12 11 10
4。请构造出带时间窗的VSP节约法算法，并进行说明。
12…28