大规模单车场VRP问题中扫描法的改进-精选文档.docx
《大规模单车场VRP问题中扫描法的改进-精选文档.docx》由会员分享,可在线阅读,更多相关《大规模单车场VRP问题中扫描法的改进-精选文档.docx(12页珍藏版)》请在三一文库上搜索。
1、大规模单车场VRP问题中扫描法的改进摘要:为了降低问题规模,提高扫描法应用在单车场VRP问题中初始解的有效性,这里借鉴多车场VRP等问题中的分 区思想,以车场为中心,根据需求点覆盖区域的特点,对单车场VRP提出了新的环形分区思想,并给出了几种具体方法。在此基础上,对扫描法进行改进,分区分别扫描并且集中车辆使用率低的区域重新扫 描,合理地降低了大规模单车场VRP问题的复杂程度,为第二阶段的优化提供了有效的初始解。扫 算例表明运用该算法比传统描 法得到的路径更优且使用车辆数更少。Improvement of sweep algorithm to deal with large?scale SVRP
2、WANGShi?yao , WANGWen?fa, FU Wen?jun, LI Xiao?yingSchool of Mathematics and Computer Science , Yan, anUniversity , Yan,an 716000 , China ):To improve the effectiveness of sweep algorithm ' s initial solution in large?scale single?depot vehicle routing problem ( LSV R P) and reduce the scale of t
3、he problem , the partition thought of multiple?depot VRPMDVR)P is employed in this paper Centering on the yard , a new thought of an annular field partition is put forward according to the characteristics of the covered area at thedemand points , and several concrete methods is given.Based on this ,
4、 the sweep method was improved , that is partition scan and rescan for the areas with low vehicle?usage rate This method reduced the complexity of the LSVRP reasonably and provided the effective initial solution for the optimization in the second stage Experiments show that the algorithm is better t
5、han traditional sweep algorithm in path selection and uses less number of vehicles Keywords : VRP; sweeping algorithm; improved algorithm;single?depot VRP; LSVRP车辆路径问题(Vehicle Routing Problem , VRP随着物流业的发展越来越值得研究。Gillett和Miller于1 974年提出扫描法1,将其应用在求解VRP问题中简单易行,当节点规模较大时,运用传统扫描法得到的节点分组不利于第二阶段的路径优化 2?4 o
6、 本文借鉴多车场 VRP( Multiple depots VRP, MDVRP等问题中的分区方法的研究成果:5?11,提出一种针对大规模单车场VRP问题的 环形分区思想,在此基础上改进了扫描法。最后 运用Mat lab编程 并带入算 例,结果表明本文提出的环形扫描法比传统扫描法的路程和车辆使用情况更优。1单车场VRP的描述及模型1. 1问题的提出某采油厂下设一个车场,包含足够的车辆且型号相同,每个 井点都有 各自 的日产油量,井点、车场在平面图上的坐标和实际行驶距离已知,日常运作为车辆 从车场出发,沿规定去各个井点泵油,当车辆剩余载重量无法满足下一井点时返回 车场。要求每 个井点的产量一日内
7、仅由一辆车一次完成。安排怎样的车辆调度 方 案,可满足问题条件且总路程最小。此问题即带容量约束的单车场集货VRP问 题,总路程为目标函数。1. 2模型的建立N:井点个数;qi , i 1, 2, , N:井点日产油量;Q:车辆的额定容量;dij , i , j 1, 2, - N+1:井点间的实际行驶距离;xijm=l,车辆m从节点i行驶到节点jO ,否则,i , M , 2,N+1minZ=mMiN+ljN+lxijm,j 二 IN+Im 二 IMxijm 二 1 , i 1, 2,,N+1 (2)i=lN+lm=lMxijm=l , j 1, 2,,N+1(3)_i 二 IN+lqi j=
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 大规模 单车 VRP 问题 扫描 改进 精选 文档
链接地址:https://www.31doc.com/p-12578703.html