车辆路径问题论文：规模动态增长的车辆路径优化问题【中文摘要】随着中国经济的快速发展,中国零售业在过去十几年来也得到了迅速发展,开始呈现蜂群式特征,即在区域内门店数量越来越多、单店业务量小,但总需求量大。

伴随不断扩大的企业规模和迅速扩张的店铺数量,使得零售物流成本持续增长。

如何在满足所有店铺的配送请求前提下,有效控制并缩减物流成本,提升企业盈利能力,从而在激烈的市场竞争中脱颖而出,几乎是所有零售业管理者不得不直面的挑战。

本文研究在这种新形势下的配送车辆路径安排问题,并根据其门店数的发展变化特征将其定义为规模动态增长的车辆路径优化问题。

文章分别从配送网络的网点分布、现实约束、规模动态增长特性以及优化目标等不同层面展开详细介绍从零售企业实践中抽象而来的规模动态增长的车辆路径优化问题。

建立以最小化配送费用、最大化不同场次线路间的相似性为目标的运筹优化模型,该模型考虑了运输网络规模大且带有不确定性不断增长的特点。

并提出基于经验划分的三阶段启发式算法来解决规模动态增长的车辆路径优化问题,并用JAVA实现其核心的C-W节约算法和禁忌搜索算法。

第一阶段,依据经验将大规模的车辆路径问题所覆盖的配送网络按照合适的原则划分成多个子配送区域,从而降低问题规模。

第二阶段,对所有子配送区域的所有配送点,采用C-W节约算法产生初始解,并调用禁忌搜索算法优化初始解,形成配送线路方案,即主线路模板。

第三阶段,每天,在收到当天需要配送的配送点及需求量等信息后,在主线路模板基础上,采用C-W节约算法将未出现在主线路模板上的配送点插入至最经济的位置、将线路模板上出现而未有需求的配送点直接剔除,形成每日配送路线方案的初始解；再采用禁忌搜索算法对初始解进行优化而形成最终的每日配送线路方案。

因此,本文的研究目标不仅仅是一次配送线路的成本最小化,而是在整个考虑的时间段内每次配送线路成本总和的最小化。

本文要解决的车辆路径优化问题来源于企业实践,是大规模的VRP问题,要求能够快速求解,并且能将优化的结果用来指导企业实践,因此要求优化解是可行并且可操作的。

因此本文结合企业现有资源,基于经验划分的三阶段启发式算法的实现情况向外拓展,设计简单易用合适的人机交互系统来优化并记录配送线路。

企业实践的结果显示模型和算法是高效且可行的。

【英文摘要】With the rapid economic development in China, the retail industry has developed tremendously in the past decade, and presents colony type characteristics, i.e., the number of stores is increasing, the orders per store is small but the total demand is large. To gain the benefit of the economies of scale, usually a unified distribution center serves all the stores in a region. With the transportation cost taking up to 50 percentage of the whole distribution cost, it is important to reduce the transportation cost which makes the vehicle routing problem crucial in the real business practice. This thesis studies the new problem which we called dynamicvehicle routing problem with an increasing scale (DIS-VRP), i.e., the number of stores is more than one thousand and keeps increasing stochastically.Increase in the number of stores makes the route change every day. However, the driver familiarity with routes and customers conduces to less service time, error and exceptional cost. Also for many other practical reasons, it’s beneficial to control route adjustment by creating regular or consistent routes for the DIS-VRP that assign the same driver to the set of customers to serve them through the same routes. Such consistent routes are easy to adapt to the realization of the daily uncertainty and help logistics improve the service quality.We propose a mixed integer programming formulation for the DIS-VRP, and develop an efficient three-phase heuristic algorithm based on customers cluster and Clarke & Wright and Tabu search. The model represents the uncertainty in stores changing and includes a master plan problem using all the customers at the beginning of period. The master plan routes are created without considering the similarity. After receiving distribution job, the daily schedules obtaining from the master routes are improved using a Tabu search algorithm.The scheme is implemented on real-life data. Application results show thatthe proposed three-phase heuristic provides high quality solutions within a reasonable running time.【关键词】车辆路径问题规模动态增长路线相似性经验划分零售【备注】索购全文在线加好友：1.3.9.9.3.8848同时提供论文写作一对一指导和论文发表委托服务【英文关键词】Vehicle routing problem Scale increasing Route consistent Tabu search Retail【目录】规模动态增长的车辆路径优化问题摘要5-6Abstract6第1章绪论9-18 1.1 选题背景和选题意义9-10 1.1.1 选题背景9-10 1.1.2 选题意义10 1.2 国内外研究现状综述10-15 1.2.1 车辆路径问题的模型研究现状10-12 1.2.2 车辆路径问题的算法研究现状12-15 1.3 本文工作15-18 1.3.1 研究背景15-16 1.3.2 主要研究内容16 1.3.3 论文安排16-18第2章物流配送中车辆路径优化问题研究综述18-30 2.1 物流配送概述18-22 2.1.1 物流概述18-19 2.1.2 配送概述19-21 2.1.3 配送线路21-22 2.2 车辆路径问题的描述22-26 2.2.1 文字描述22-25 2.2.2 数学模型25-26 2.2.3 求解复杂性分析26 2.3 车辆路径问题(VRP)的求解方法26-30 2.3.1 禁忌搜索算法原理简介27-28 2.3.2禁忌搜索算法运算流程28-30第3章规模动态增长的车辆路径优化问题30-37 3.1 网点分布30-31 3.2 现实约束31-33 3.3 规模动态增长33-34 3.4 优化目标34-37 3.4.1 运输成本34-36 3.4.2 前后线路一致性36-37第4章系统建模37-40 4.1 模型假设37 4.2 参数定义37-38 4.3 数学模型38-40第5章算法设计与实现40-51 5.1 基于经验的物流配送区域划分40-43 5.1.1 区域划分原理40-41 5.1.2 区域划分的影响因素分析41-43 5.2 C-W节约算法43-44 5.2.1 C-W节约算法描述43 5.2.2 C-W节约算法实现43-44 5.3 禁忌搜索算法设计分析与实现44-51 5.3.1 初始解44-45 5.3.2 邻域结构45-48 5.3.3 解的评价48 5.3.4 禁忌表48 5.3.5 终止准则48-49 5.3.6 禁忌搜索算法实现49-51第6章人机交互系统实现与案例研究51-56 6.1 人机交互系统实现与优化51-53 6.1.1 维护配送区域51-52 6.1.2 人工调整路线52-53 6.2 案例研究53-56 6.2.1 数据和参数53-54 6.2.2 灵敏度分析54-55 6.2.3 计算结果55-56第7章总结与展望56-587.1 结论56-577.2 展望57-58参考文献58-62致谢62-63攻读硕士期间发表的学术论文63攻读硕士期间参加的科研项目63。