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

GISGIS技术在多点配送路线技术在多点配送路线规划中的应用初探规划中的应用初探报告人：郭伟祥主要内容主要内容基基本本思思路路：为了了考考虑配配送送点点之之间的的实际运运送送成成本本，结合合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.精确算法分支定界法分支定界法割平面法割平面法网网络流算法流算法动态规划划法法先路先路线后聚后聚类先聚先聚类后路后路线遗传算法算法模模拟退火算法退火算法禁忌搜索算法禁忌搜索算法 节约算法算法插入算法插入算法拉格朗日松弛法拉格朗日松弛法先聚类再规划路线先聚类再规划路线2022/10/282022/10/28246571380先规划路线再聚类先规划路线再聚类246571380节约节约法法213055664445+6-4=786+4-8=25+4-10=-1103.GIS技术与技术与VRP问题的结合问题的结合传统传统VRP研究时存在的问题：研究时存在的问题：各配送点间的距离是以直线距离作为计算依据。各配送点间的距离是以直线距离作为计算依据。没有将道路质量、通过能力等地理信息因素考虑进去。没有将道路质量、通过能力等地理信息因素考虑进去。研究的点对较少。研究的点对较少。前两个问题可以通过地理信息缺失及实际路线与计算路线脱离的问题前两个问题可以通过地理信息缺失及实际路线与计算路线脱离的问题可通过在传统可通过在传统VRP问题中引入问题中引入GIS,使用使用GIS辅助设计功能来解决。辅助设计功能来解决。第三第三个问题主要靠算法的改进来提高搜索速率。个问题主要靠算法的改进来提高搜索速率。基于基于GIS的的VRP问题问题地理地理信息约束条件的构建流程信息约束条件的构建流程3.GIS技术与技术与VRP问题的结合问题的结合 i j1234567818591213121728851771114358791071249157317111651217931811156137101718887121171111858171412161585各各点之间的最短路点之间的最短路r3.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.