基于gis的烟草物流配送线路优化算法研究与应用

北京工业大学硕士学位论文基于GIS的烟草物流配送线路优化算法研究与应用姓名：王粲申请学位级别：硕士专业：软件工程指导教师：于学军;邹颖20090501基于GIS的烟草物流配送线路优化算法研究与应用作者：王粲学位授予单位：北京工业大学相似文献(10条)1.学位论文宋楠基于GIS的山东烟草物流配送线路优化系统设计与实现2009构建现代物流仓储、配送、营销体系是烟草行业建设现代化物流管理体系的核心内容。国家烟草专卖局学习国外经验结合国内行业实际情况，提出“电话订货、电子结算、网上配货、现代物流”的卷烟销售模式。一些省市烟草商业公司先后建立，对零售户实行卷烟“一库制”配送。但在卷烟配送中心，物流配送线路优化、车辆装载调度和监控等方面缺乏先进技术支持配送优化效果差、成本偏高，服务水平难以提高。作为一项先进的通用计算机技术，地理信息系统(GIS)技术将逐渐在我国烟草行业中推广使用。据了解，目前国内部分网建先进省市已经开始在物流配送线路优化、经济地理、BI分析等领域引进了GIS应用，并取得了初步的效果。由于GIS技术将为目前的“文字加数字”型零售户客户管理数据增加空间地理信息，从而形成更加完整的零售户客户管理数据，而零售户客户管理数据是专卖、营销、CRM、物流配送等烟草关键业务软件系统的最重要和最基础的数据。为了统一山东烟草GIS平台，避免今后各业务系统在引用零售户客户管理数据时出现混乱和不一致，山东烟草决定在2008年信息化工作中实现山东烟草物流配送线路优化系统的统一建设，并在此基础上完成全省GIS卷烟经营决策系统、省市两级基于GIS数字化地图的业务数据查询系统以及配送车辆GPS管理系统等GIS基本应用系统，在已经完成的“数字化仓储(WMS)”的基础上，向完善的“数字化物流”体系再迈进一大步。本文基于山东烟草GIS平台，以烟草现代物流配送环节中车辆配送优化问题为研究对象，对现有烟草车辆调度问题和实际配送中存在的问题作了深入的分析和讨论，提出烟草行业物流配送线路优化模型，并应用空间聚类方法和多维钻取技术的实现，利用智能算法求解模型解决山东烟草物流配送线路优化系统中的VRP难题，并实现了系统开发，为实际物流配送提供切实可行的线路优化手段，以达到降低物流成本，提高企业利润和客户满意度的目的，具体实施效果显著。对优化系统目前在烟草行业物流配送中的应用作了介绍。以山东烟草为例，由于配送线路的合理划分，配送时间得以保证，配送工作量趋于平衡，人员工作可考核性增强，企业的管理水平迈进了一大步，最重要的是企业通过挖潜增效使企业利润有了显著提高。2.会议论文费玉莲.苏永钢.王光明基于真实街道的规模配送车辆线路优化问题研究2005本文在对现有车辆线路优化问题(VRP)算法归类分析和对企业实际要求提炼的基础上，考虑城市街道中方向性等具体因素，将大规模VRP分解为线路(区域)划分和单车线路优化两个子问题，并分别进行求解，较好地解决了在大规模配送情况下求解VRP这类NP难问题可行时间与最优或较优解的矛盾。另外本文对单车线路优化做了重点阐述，采用最节约插值法与混合遗传算法相结合方法较好地解决了单车线路优化问题，实例数据测试表明该算法效果显著。3.学位论文李如姣ZS物流公司配送车辆线路优化的研究2008物流配送是物流活动中直接与消费者相连的环节。在物流的各项成本中，配送成本占了相当高的比例。配送线路安排的合理与否对配送速度、成本、效益影响很大，特别是多用户配送线路的确定更为复杂。采用科学、合理的方法来进行配送车辆线路优化，是物流配送中非常重要的一项活动。从配送中心把货物送到所需的各个用户，有很多种不同的路线选择方案。合理的选择配送路线，对企业和社会都具有很重要的意义。ZS物流公司广州分公司是一家典型的第三方物流公司，主要为广州浪奇、广州立白、广州太古可口可乐、广州宝洁等公司提供仓储、运输和配送服务，目前最大的客户是广州宝洁公司。本论文主要是围绕广州物流有限公司为“宝洁客户配送服务”这一项目来展开研究的。从研究中发现，随着合作的业务范围的扩大和增涨，项目部在配送的过程中，由于配送服务水平不高，配送车辆线路安排不合理，车辆空载率高，客户投诉不断增加，公司的配送成本也很难控制在一个合理的水平。因此要达到公司服务质量与服务成本的最佳结合，就必须寻求科学的方法和手段来满足这两种需求的最优配送车辆线路。作者在研究的过程中，首先利用实地考察和访谈的方法，收集、整理了“宝洁客户配送服务”项目部有关配送车辆线路的大量资料和数据，并对项目部的配送车辆线路的现状进行了全面的分析和诊断，把配送车辆线路优化的目标锁定在保证服务质量的同时使配送总成本达到最小。提出配送车辆线路优化的方法，并利用实用性较强的“节约法”的原理、思想和现有的模型对实际问题进行了配送车辆线路优化。从研究的整个过程来看，仅验证“宝洁客户配送服务”项目省内7家客户的一次配送，通过配送车辆线路优化，节约了里程226公里，节约了配送成本11163元，节约了车辆5台，这样无形中又减少了5个司机的人工费用和有效的解决了车辆的空载率。本文的研究结果表明：如何建立良好的配送车辆路线的方案，关键在于了解企业实际运作情况，才能做到对症下药。然后利用科学的方法和技术对公司的配送车辆线路进行优化，才能进行科学的决策。利用“节约法”进行车辆线路优化，可以节约罩程、车辆、成本和有效的降低空载率。4.会议论文李巍.赖明勇.许荻迪基于时间变量的奶制品物流配送优化研究2005随着社会对奶制品需求的不断增长，如何利用现代科学理论与实践来促进奶制品行业的发展已逐渐成为关注的热点，本文主要研究基于时间变量的奶制品物流配送线路优化问题。首先，介绍了奶制品物流配送技术的重要性和发展现状，然后建立以时间为决策变量的车辆调度模型，通过设计根据保鲜时间决定车次调度的线路优化算法，得到可有效缩短奶制品运输在途时间、提高车辆运营效率的线路优化方法。5.学位论文雷挺物流拼车配送中的线路优化2006作为“第三利润源”的现代物流业已经被全世界广泛关注，随着我国国民经济的高速发展，推进现代物流发展，推动物流管理、物流技术的进步已成为目前我国社会经济发展中的一项重要内容。随着“第三方物流”的发展成熟，配送作为一种特殊的、综合的物流活动形式正扮演者越来越重要的角色。如何制定配送计划并选择配送线路是配送业务中面临的最大难题，目前人们已经尝试了精确式算法和启发式算法，但这两种算法在实际应用中都存在着很大的不足，因此有效解决配送线路的选择和配送计划的制定就成为当前物流配送业务中的迫切要求。本文着眼于拼车配送线路的优化，以数学模型为工具来描述问题，以网络单纯形法、拉格朗日松弛算法以及试探法为主要研究方法，有效地得到该问题一个近似程度较高的可行解，从而很好的解决了货物的“配”与“送”，即配送计划的制定和配送线路的选择。本文首先对物流配送的现状做出概述，然后以配送中的最小运送成本为目标建立了一个混合整数规划模型，并分析最优解应该满足的条件。考虑到问题的复杂性，对最优解的求解既不实际也不实用，本文主要着眼于如何有效地得到其近似解。网络单纯形法是解决通常网络流问题的一类有效算法，而拉格朗日松弛是解决各类整数规划、组合优化、非线性规划的少数有效算法之一。本文中将拉格朗日松弛与网络单纯形法相结合有效地得到原问题的一个下界，并利用该下界结合试探法有效地得到该问题一个可行解作为上界，如此反复迭代逐步缩小上下界的区间范围并最终找到一个近似程度较高的可行解。本文在建立模型并给出算法的基础上又以一实例来验证所给算法的有效性，并以附表的形式给出其运算步骤。最后又对该模型的实际应用价值进行了描述，说明了本文所给出的算法能够很好地解决物流配送中配送线路的选择以及配送计划的制定。6.会议论文常春光.陈冬文.宋晓宇.刘亚臣面向大规模应急物流配送的线路优化模型2009大规模应急事件条件下，应急物资配送具有持续时间长、多供给地与多需求地间往复交错运输等主要特点。本文构建了区域范围内的多点应急物流配送的线路优化模型，给出了大规模应急物流配送模型构建的若干前提条件，研究了该多目标非线性规划模型的模型转换，设计了遗传算法加以求解。计算结果表明，运用该模型与算法求得的结果在满足线路长度、线路流量等约束的前提下，在线网重复系数、单次运输换乘次数、孤立点数、线路负载均衡度、线路弯曲度均值方面性能均获得满意的效果。应急物流配送的线路优化在大规模应急事件条件下，有助于提高应急物流配送效率与精确性。7.期刊论文韩冰源.肖生灵.HanBingyuan.XiaoShengling配送中心线路优化方法的探讨-森林工程2005,21(2)基于目前配送中心线路优化的各种方法,根据实际情况对上述算法进行分析和比较,并针对模拟退火法、遗传算法在配送线路优化问题中的具体应用,提出不同情形下的求解策略.8.学位论文袁正磊基于聚类的车辆线路优化算法研究2008本文针对大规模VRP问题的特点，提出了“先聚类，再分派，后排程”的三阶段求解算法。首先，利用改进的基于密度的聚类算法(DBSCAN，DensityBasedSpatialClusteringofApplicationswithNoise)对客户点进行分区聚类，生成一些虚拟客户，将大规模问题转化为小规模问题；然后，在第一阶段聚类的基础上，以生成的虚拟客户集合作为输入，采用Clark-Wright节约里程算法进行车辆分派；最后，将车辆服务的虚拟客户重新转化为实际客户，将问题变为若干个小规模的旅行商问题(TSP，TravelingSalesmanProblem)，采用蚁群算法或最邻近点算法对每辆车安排最优的客户访问次序。为验证算法的有效性，本文进行了大量的仿真试验。试验主要包括两部分：对标准试验库(benchmark)的测试和山西某市烟草配送中心实际线路优化问题的求解。一方面，在对标准试验库A集部分算例的试验中，探讨了算法相关参数值选择问题，而且试验获得的所有结果与最优解的偏差均在3％-7％之间，验证了算法的可行性；另一方面，本算法在27分钟内成功地解决了有4642个客户点的大规模车辆线路优化实际问题，在求解质量和运行时间方面都体现出本算法的高效性。最后，本文对基于聚类的车辆线路优化算法在解决大规模实际问题的应用前景进行了展望，并给出了进一步的研究方向。9.学位论文伊桂花配送网络拓扑构建研究及应用2007配送网络是合理安排配送路线的前提基础，对降低配送中心成本起着至关重要的作用。目前国内外对配送网络构建方面的研究还不够深入，本文利用图论和GIS技术对配送网络拓扑结构的构建方法进行研究，实现其自动化构建功能，建立物流配送系统所需韵空间属性数据库，并应用于一个基于GIS的面向大规模城市物流配送的线路优化系统。本文首先介绍了国内外网络拓扑构建和基于GIS物流配送系统的研究现状，提出现在GIS在配送线路优化应用中存在的问题，分析了物流配送系统所需的地理空间属性数据。然后，深入城市配送问题实践，针对城市物流配送和城市交通道路网的特点，研究道路网的矢量表达、网络拓扑结构的提取和构建、客户点与道路网的匹配等关键技术，提出一套将客户点添加进城市配送道路网络的规则，对地理信息和交通信息进行提取，构建了配送线路优化所需的包含客户资源信息和道路信息的拓扑网络。在此基础上，结合烟草配送中心的实际情况，介绍了实际应用背景和问题模型算法，分析网络拓扑构建在配送中心线路优化系统中的应用。在Maplnfo平台上实现算法与GIS的整合，对基于GIS的配送线路优化系统及网络拓扑构建模块的实现进行介绍。本文的研究结果，成功应用在济南市烟草物流配送线路优化中，构建了覆盖辖区内28000个客户点的配送网络，取得了一定的经济效益。同时，本文研究同样适用于其它领域大规模城市物流配送，具有重要的实用价值。10.期刊论文高鹏.徐瑞华.GAOPeng.XURui-hua物流配送线路优化的改进遗传算法研究-交通运输系统工程与信息2006,6(6)物流配送线路优化问题,即车辆路线问题(VRP,VehicleRoutingProblem)是组合优化领域中的著