百源木业有限公司配送线路优化(5)

表4-4 节约里程顺序表 （单位：千米）

连接点 3-4 4-6 3-6 2-3 6-7 2-4 7-8 4-5 6-8 节约 里程 340.6 242.6 242.0 178.6 157.5 142.5 124.3 120.3 119.6 连接点 3-5 1-2 5-6 1-3 3-7 4-7 2-6 2-5 8-9 节约 里程 118.7 116.5 106.1 105.5 103.5 103.4 99.9 97.6 72.6 连接点 1-4 3-8 4-8 7-9 1-5 5-7 5-8 5-9 1-6 节约 里程 72.4 61.9 61.7 52.7 46.8 40.8 40.5 36.4 35.4 连接点 2-7 2-8 1-8 6-9 1-9 1-7 4-9 2-9 3-9 节约 里程 18.1 14.3 8.5 4.3 3.7 1.7 1.5 1.2 0.5 最后，按节约里程从大到小合并路径

（1）对于?c34?340.6km:r3?r4?120?60?180?500,

L3?L4??c34?186.7*2?170.3*2?340.6?373.4km?600km,B3?B4?0。 故合并3，4两点，则

I1??I3?I4??3,4?,r1??180,L?1?373.4km,B3?B4?1,I3?I4??。

（2）对于?c46?242.6km:r1??r6?180?220?400?500,

L?1?L6??c46?373.4?153.8*2?242.6?438.4km?600km,B4?1,B6?0。

故合并4，6两点，则

??I6??3,4,6?,r1??400,L?I2??I11?438.4km,B3?B6?1,B2?2,I3?I4?I6??

（3）对于?c36?242.0km:因为3与6处在同一回路中，故不满足合并条件。 （4）对于?c23?178.6km:r2??r2?400?120?520?500,故不满足合并条件。 （5）对于?c67?157.5km:r2??r7?400?70?470?500,

L?2?L7??c67?438.4?87*2?157.5?454.9km?600km,B6?1,B7?0。

14

故合并6，7两点，则

??I6??3,4,6,7?,r3??470,L?3?454.9km,B3?B7?1,B2?B6?2, I3??I1I3?I4?I6?I7??。

（6）余下各点的货运量均大于30，故回路0-3-4-6-7-0不能再与其他点合并。接下来的讨论将跳过与点3，4，6，7相关的?cij。 （7）对于?c12?116.5km:r1?r2?180?120?300?500,

L1?L2??c12?75.9*2?89.2*2?116.5?213.7km?600km,B1?B2?0。 故合并1，2两点，则

I4??I1?I2??1,2?,r4??3000,L?4?213.7km,B1?B2?1,I1?I2??。

（8）对于?c25?97.6km:r4??r5?300?80?380?500,

L?4?L5??c25?213.7?57*2?97.6km?230.1km?600km,B2?1,B5?0。

故合并2，5两点，则

??I5??1,2,5?,r1??380,L?I5??I41?230.1km,B1?B5?1,B2?2,I1?I2?I5??

（9）对于?c89?72.6km:r8?r9?90?200?290?300,

L8?L9??c89?81.5*2?82.5*2?72.6?255.4km?600km,B8?B9?0。 故合并8，9两点，则

I6??I8?I9??8,9?,r4??290,L?4?255.4km,B8?B9?1,I8?I9??。

（10）r4??r5??380?290?670?500，故线路0-1-2-5-0与线路0-8-9-0不能合并。

至此，合并结束。

最后得到的最优结果如表6所示，优化线路图如图4所示。

表4-5节约法优化结果

路线 0-3-4-6-7-0 0-1-2-5-0

运距 454.8km 230.1km 运货量 470 380 15

车型 11吨货车 11吨货车 司机 2 1

0-8-9-0 255.4km 290 7吨货车 1 由上表可知，公司每周需11吨货车2车次和7吨货车1车次配送，司机4人次，所需工资400元，运输总里程为940.3千米，消耗的柴油239.56升，所需燃油费1686.60元，一共花费2086.60元。

9 1 0 8 2 5 7 6

3 4 图4-1 节约算法求解线路结果

4.2.3 基于扫描算法的企业配送路线优化

对百源木业周边的9个县市采用扫描算法进行配送线路的优化。

首先建立极坐标系：以百源木业有限公司所在地婺源县作为原点，并以点1景德镇与原点的连线为零角度建立极坐标系，各点的货运量及极坐标的角坐标值如表7所示。坐标系如图5所示。

表4-6 运量和极坐标的角坐标值

客户 货运量（张/周） 角坐标 1景德镇 180 0 2乐平市 120 34 3鹰潭市 120 46 4贵溪市 60 52 16

5德兴市 80 61 6上饶市 220 103 7常山县 70 152 8开化县 90 169 9黄山市 200 238

9 1 0 8 2 5 7 6

3 4 图4-2 扫描算法的扫描过程

然后分组：从角度为零向逆时针方向进行扫描，如图所示。第一个被分组的是客户1，r1=180；继续转动，下个被分组的是客户2，r1=180+120=300；继续转动，下个被分组的是客户3，300+120=420；继续转动，下个被分组的是客户4，

r1=420+60=480；继续转动，下个被分组的是客户6，r1=480+80=560>500，由于超过了限制，按分组规则，需要一个新的组，这样在第一组里只有客户1，2，3，4，r1=480。

进行第二组扫描，最先扫描到的是客户5，r1=80；继续转动，下个被分组的是客户6，r1=80+220=300；继续转动，下个被分组的是客户7，r1=300+70=370；继续转动，下个被分组的是客户8，r1=370+90=460；继续转动，下个被分组的是客户9，r1=460+200=660>500，超过限制，所以需要一个新的组，这样在第二组中只有客户5，6，7，8，r1=460。

在第三组中只剩一个客户9，故顾客9单独在一组，r1=200。 这时，可以得到如图6所示的分组结果。

17

9 1 0 8 2 5 7 6 3 4 图4-3 扫描算法求解结果

最后对各子回路内的线路优化：对上面的3个组，都已经是一个单回路运输问题，对每个组进行线路优化。供应点0是任何一个组的TSP问题的起点和终点，用最近插入法分别对三个客户组进行求解。

对第一组进行求解。比较表4-2 中从0出发的所有路径大小，

min?c0i|i?N,1?i?4??c01?75.9km

这样，就有顾客点0，1构成一个子回路，T1??0,1,0?。 然后考虑剩下顾客点2，3，4到0和1中某一点的最小距离：

min?c0i,c1i|i?N,1?i?4,且i?1??c12?48.6km

由于对称性，无论将2插入到0和1之间往返路径中，结果都是一样的，这样，构成了一个新的子回路T1??0,1,2,0?。

接下来考虑剩下的顾客点3，4到0，1，2中某一点的最小距离

min?c0i,c1i,c2i|i?N,1?i?4,且i?1,2??c23?97.3km

顾客点3有3个位置可以插入，现在分析将点3加入到哪里合适。

（1） 插入到（0，1）之间，??c03?c31?c01?186.7?157.1?75.9?267.9km。 （2） 插入到（1，2）之间，??c13?c32?c12?157.1?97.3?48.6?205.8km。

18

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库百源木业有限公司配送线路优化(5)在线全文阅读。