GIS技术在多点配送路线规划中的应用初探

,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,Company name,#,单击此处编辑母版标题样式,GIS,技术在多点配送路线,规划中的应用初探,报告人：郭伟祥,主要内容,基本思路,：为了考虑配送点之间的实际运送成本，结合,GIS Network Analyst,技术建立一种配送车辆路线规划方法。这种方法能够考虑实际路网情况，将路线规划结果呈现在地里信息系统的路网图上，以准确的道路路线图示方式表示规划的结果。,主要内容,1.VRP,问题的概念,2.VRP,问题求解算法,3.GIS,技术与,VRP,问题的结合,4.OD Cost Matrix,的输出操作,1.VRP,问题的概念,车辆路线问题（,VRP,）最早是由,Dantzig,和,Ramser,于,1959,年首次提出，它是指一定数量的客户，各自有不同数量的货物需求，配送中心向客户提供货物，由一个车队负责分送货物，组织适当的行车路线，目标是使得客户的需求得到满足，并能在一定的约束下，达到诸如路程最短、成本最小、耗费时间最少等目的。,2.,VRP,问题求解算法,求解算法,4.,智能,算法,3.,启发式算法,2.,近似,算法,1.,精确,算法,分支定界法割平面法,网络流算法动态规划,法,先路线后聚类,先聚类后路线,遗传算法,模拟,退火算法,禁忌搜索算法,节约算法,插入算法,拉格朗日松弛法,先聚类再规划路线,2024/10/7,2,4,6,5,7,1,3,8,0,先规划路线再聚类,2,4,6,5,7,1,3,8,0,节约,法,2,1,3,0,5,5,6,6,4,4,4,5+6-4=7,8,6+4-8=2,5+4-10=-1,10,3.GIS,技术与,VRP,问题的结合,传统,VRP,研究时存在的问题：,各配送点间的距离是以直线距离作为计算依据。,没有将道路质量、通过能力等地理信息因素考虑进去。,研究的点对较少。,前两个问题可以通过地理信息缺失及实际路线与计算路线脱离的问题可通过在传统,VRP,问题中引入,GIS,使用,GIS,辅助设计功能来解决。,第三,个问题主要靠算法的改进来提高搜索速率。,基于,GIS,的,VRP,问题,地理,信息约束条件的构建流程,3.GIS,技术与,VRP,问题的结合,i j,1,2,3,4,5,6,7,8,1,8,5,9,12,13,12,17,2,8,8,5,17,7,11,14,3,5,8,7,9,10,7,12,4,9,15,7,3,17,11,16,5,12,17,9,3,18,11,15,6,13,7,10,17,18,8,8,7,12,11,7,11,11,8,5,8,17,14,12,16,15,8,5,各,点之间的最短路,r,3.GIS,技术与,VRP,问题的结合,数学,建模,节点两两之间,最短路数据,OD Cost Matrix,客户点需求量,客户点服务时间窗,选择合适的求解算法,.,单行道情况,道路等级,道路,中有隔离带,.,3.GIS,技术与,VRP,问题的结合,4.OD Cost Matrix,的输出操作,The OD cost matrix can also be used as an input in logistics routing models,that use origin destination matrices to allocate goods and services.,谢谢,!,