相同路径规划

起讫点相同的路径规划方法为了解决此类问题，人们已经提出不少方法，经典的通常有以下两种：扫描法（TheSweepMethod）节约法（TheSavingMethod）此外，还有一种使用模糊聚类分析加上动态规划的方法，得出的解决方案往往会比以上两种方法更加优化。1、扫描法是是开始将所有的停留点位置画在地图上选择最大的车辆装载这个停留点的货物然后顺时针或逆时针方向转动直尺，直到直尺交到一个停留点。通过仓库位置放置一直尺，直尺指向任何方向均可是否超过车辆容积或体积的限度是否扫描完所有停留点安排下一辆车装载货物，得到一条运行线路结束继续转动直尺，扫描到下一个停留点，分配该车辆装载货物优化每条运行路线的停留点顺序，以求运行距离最小化否否3图7-14客户位置及扫描法求出的结果4［例］某公司从其所属仓库用货车到各客户点提货，然后将客户的货物运回仓库，以便集成大批量进行远程运输，全天的提货量见下图（A)，我们给出了所有提货点和仓库。送件货货车每次可以运送10000件货物。完成一次运行路线一般要一天时间。请确定：需要多少条路线；每条路线上有哪几个客户点；送货车辆服务有关客户点的顺序。5汽车站100040002000300020002000200010002000200030003000停留点提货量数据汽车站100040002000300020002000200010002000200030003000扫描法解决方案62、节约里程法在车辆路线设计方案中，“节约法”是最广为人知的方法，它也形成了人工和计算机载荷计划系统的基础。图2-14

路线图ＡＢO从仓库O要运送货物给客户A和B第一条路线是从O到A，再返回，然后再从O到B，再返回O，总距离为a＋a＋b＋b＝2a＋2b外一种路线，从O到A到B，再到O。总距离为：a＋b＋x。将客户结合考虑，在第二种方案下走行路线的节约里程数是：（2a＋2b）－（a＋b＋x）即：a＋b－x7例题已知配送中心PO向5个用户Pj配送货物，其配送路线网络、配送中心与用户的距离以及用户之间的距离如下图与表所示：图中括号内的数字表示客户的需求量（单位：吨），线路上的数字表示两结点之间的距离，配送中心有3台2t卡车和2台4t两种车辆可供使用，1、试利用节约里程法制定最优的配送方案？2、设卡车行驶的速度平均为40公里/小时，试比较优化后的方案比单独向各用户分送可节约多少时间？8（1.4）P0P2P3P4P5P1（2.4）（0.9）（1.7）（1.5）1012751241368121689第（1）步：作运输里程表，列出配送中心到用户及用户间的最短距离。需要量P01.58P11.7812P20.96134P31.471595P42.41016181612P510第（2）步：由运输里程表、按节约里程公式，求得相应的节约里程数，如上表（）内。需要量P01.58P11.78（4）12P20.96（1）13（10）4P31.47（0）15（6）9（8）5P42.410（2）16（0）18（0）16（5）12P511第（3）步：将节约里程进行分类，按从大到小顺序排列序号路线节约里程序号路线节约里程1P2P3106P1P522P3P487P1P313P2P468P2P504P4P559P3P505P1P2410P1P4012第（4）步：确定单独送货的配送线路（1.4）P0P2P3P4P5P1（2.4）（0.9）（1.7）（1.5）107688得初始方案配送距离=39×2=78KM13第（5）步：根据载重量约束与节约里程大小，将各客户结点连接起来，形成二个配送路线。即A、B两配送方案。（1.4）P0P2P3P4P5P1（2.4）（0.9）（1.7）（1.5）107548168A：（24KM，4T）B：（34KM，3.9T）14①配送线路A：P0-P2-P3-P4-P0运量qA=q2+q3+q4=1.7+0.9+1.4=4t用一辆4t车运送节约距离SA=10+8=18km②配送线路B:P0-P5-P1-P0运量qB=q5+q1=2.4+1.5=3.9t<4t车用一辆4t车运