基本信息
- 项目名称：
- 网购物流快速配送研究--基于最小生成树的动态规划最优路径选择
- 来源：
- 第十二届“挑战杯”省赛作品
- 小类：
- 数理
- 大类：
- 自然科学类学术论文
- 简介：
- 本文研究了货运配送中的最优路线选择问题，为了综合考虑到配送中航行路程、停留时间等影响因素，利用动态规划建立算法选择最优配送路线。其中我们制定的路线选择指数和以最小生成树的叶子结点划分阶段的基本思路是本文的创新之处，同时编写出上述模型的c语言程序，进一步对实际货运配送问题提供可推广的基础。本文所研究的货运配送路线的算法思路有一定的可推广性，在解决货运配送这一热点问题有切实、可行的研究价值。
- 详细介绍：
- 货物配送路径优化问题是一个NP-hard问题，随着送货地点增加，可选的配送路径数量将急剧增长。为了提高货物运送效率，本文在最小生成树的研究基础上，用动态规划的方法，在运输路径尽可能短的情况下，综合考虑停靠和重复停靠时间对结果的影响，研究耗时最短的送货路径。 本文通过编程求解最优路径，脱离人工的手动优化，提高了解决问题的严谨性和科学性。另外，为了综合考虑运输工具的路程消耗和停留消耗，本文制定了路径选择指数α，通过比较α的大小即可选择出最优路线。本文以全国20个省市的运输为实例，在具体问题中探讨该方法的可行性。实验结果表明，本文研究的方法对于解决货物配送路径优化问题是有效的，具有较大的应用价值。 最后，根据实际情况，对方法思路进行拓展，解决了在各地区需求量不同时的路线优化问题。
作品专业信息
撰写目的和基本思路
- 撰写目的：网上购物成为了现代购物的一种重要形式，快递公司合理的、快速的选择出最优运输路线，提高物流配送的效率是一个亟需解决的重要问题。本文提出了快速配送路线选择算法，并加以推广。 基本思路：在最小生成树的基础上，建立最优路径选择的算法，并编制了可推广应用的C语言程序，实现货物配送路线的优化、提高配送效率。
科学性、先进性及独特之处
- 论文在最小生成树的基础上选择运输路线，删除在动态规划选择路径时可能重复经过或造成环路的路径，结合制定的指数选择路线，减少运输所需时间的消耗。本文独特之处是建立了路线选择指数，分析其科学性与合理性，使用C程序求解方便快捷，论文力求从运输所需时间最少的角度选择最优运输方案，以满足公司和消费者的需求。并论证了对从经济角度也为很好方案。
应用价值和现实意义
- 动态规划是解决最优问题的一种普遍性方法，具有较强的推广性。本作品结合最小生成树和路线选择指数的创新性运用，可以广泛应用于物流快递、旅游路径选择等实际问题中。 作品利用最小生成树特性为切入点，建立的相关数学模型，可用于快递公司高效、合理地选择最优运输路径，有效地缩短快递运输时间，极大地推动科学化设计最优路径技术的发展，具有重要的学术价值，可以产生重大社会效益和经济效益。
学术论文摘要
- 随着经济社会发展，人们的消费观念、购物方式发生了很大改变。相比于传统的商店实体销售方式，近年来刚刚兴起并迅速占领市场的网购具有货物齐全、物美价廉等诸多优势。现今，网购的人越来越多、商品需求量日益增加，消费者对货物运送效率的要求也随之提高。物流公司要在市场竞争中脱颖而出，合理选择、优化配送路线方案、提高配送效率就显得至关重要。 货物配送路径优化问题是一个NP-hard问题，随着送货地点增加，可选的配送路径数量将急剧增长。为了提高货物运送效率，本文在最小生成树的研究基础上，有选择地减少了参与考虑的可行路线方案，用动态规划的方法研究耗时最短的送货路径。 本文通过编程求解最优路径，脱离人工的手动优化，提高了解决问题的严谨性和科学性。另外，为了综合考虑运输工具的路程消耗和停留消耗，本文制定了路径选择指数α，通过比较α的大小即可选择出最优路线。本文以全国20个省市的运输为实例，在具体问题中探讨该方法的可行性。实验结果表明，本文研究的方法对于解决货物配送路径优化问题是有效的，具有较大的应用价值。 最后，根据实际情况，对方法思路进行拓展，解决了在各地区需求量不同时的路线优化问题。
获奖情况
- 无
鉴定结果
- 动态规划解决最优路径选择问题已见诸多篇文献报道，但结合最小生成树特性及综合考虑路线消耗和停留消耗而制定路线选择指数来解决路径选择问题的方法未见有。
参考文献
- [1] 陈思勇，供应商选择与货物配送路径规划研究及其应用[D]， 2009 - 北京交通大学：计算机科学与技术 [2] 范恩海.用于配送调度的节约法德又一种模型[J].太原理工大学学报,1999,3 [3] 李嘉，王梦光，唐立新等．一类特殊车辆路径问题(VRP)[J]．东北大学学报(自然科学版)，2001，6 [4] 程世东,刘小明,王兆赓. 物流配送车辆调度研究的回顾与展望 [J]交通运输工程与信息学报 , 2004,(03) . [5] 田青，缪立新，郑力. 基于运输规划和组合GA的基本物流网络设计.[J] 《清华大学学报（自然科学版）》
同类课题研究水平概述
- 随着互联网在中国的进一步普及应用，网上购物逐渐融入人们的消费生活，网购的物流配送问题也在持续地改进和优化。物流公司要在市场竞争中脱颖而出，合理组织货物配送、优化配送路线方案、提高配送效率就显得至关重要。 国外将优化配送问题归结为VSP问题，最早由Dantzig和Ramser在1959年提出。 VSP是一个NP-hard问题，随着顾客数量的增加，可选的配送路径数量将呈指数速度增长，所以学者们也不断地创新，提出新的方法，目前主要的研究方法有： 1、运筹方法和优化方法。运用线性规划、非线性规划数学技术，以便求得最优决策。Dantzig和Ramser最初用整数规划模型来处理一些规模较小的问题，大约10到20个顾客的问题。 2、启发式方法。指通过经验法则来求解运输过程满意解的数学方法。最具代表性的就是由Clarck和Wright提出的节约法以及Gillett和Miller所提出的扫描算法，西南交大的李军针对有时间窗的车辆调度安排问题提出了一种利用节约法的启发式算法。 3、模拟方法。利用数学公式、逻辑表达式、图表、坐标图形等抽象概念表示实际运输系统内部状态和输入输出的关系，以便通过计算机模型进行试验，进而取得改善运输系统或设计新运输系统所需的信息。 4、交互式优化法。这是一种通用方法。在这种方法中，把人的知识、经验结合到问题的求解过程中去。这种方法的早期雏形是由Krolak,Felts和Marble以及Nelson等人提出的。 我国在对车辆路线问题的研究起步较晚，与国外的研究水平还有差距。我国大部分的研究采用的是遗传算法。 目前，除了对VSP问题研究方法的继续探索外， VSP问题的形式已有很大的发展，从最初的汽车运输领域发展至今，在水运、航空、通讯、电力、计算机等领域也有一定的应用，其算法对于轮船公司运送货物经过港口、货物安排的优化设计、交通车线路安排、生产系统中的计划与控制等多种组合优化问题同样适用。 本研究利用最小生成树的特性划分阶段、选择性的增减路径，以及综合考虑路线消耗和停留消耗制定了路线选择指数，有效的减少了参与考虑的可选配送路径方案的数量，合理地选择出了最优运输路径。极大地推动科学化设计最优路径技术的发展，具有重要的学术价值，可以产生重大社会效益和经济效益。
