《基于分支定价算法异步车辆路径算法设计及实验研究》14000字（论文）.docx

1

基于分支定价算法异步车辆路径算法设计及实验研究

摘要

随着冷链物流的快速发展，生鲜冷链运输比例逐渐上升，单纯仅考虑一种车型的车辆路径问题的研究在实际配送过程中，很容易使冷链产品配送车与常温类产品的配送车发生冲突，经常出现卸货不及时，互相干扰搬运等问题，这带来最直接的后果就是冷藏车在门店停留时间过长，运输过程中的制冷成本不断上升。为解决这一问题，本文针对异步路径车辆路径问题进行研究。异步车辆路径问题研究是在基础的VRP问题上，增加了一种车型而产生的，属于VRP的变体之一，保证在运输过程中生鲜食品的质量，减少食品腐蚀变质等造成的损失，降低配送成本，增加经济利益。该研究通过建立异步车辆路径问题的数学模型，设计异步车辆路径问题算法，具体运用分支定价法、动态规划和列生成算法等精确算法解决配送中心对冷链货物配送与普通货物配送的异步车辆路径优化问题，并通过编程实现大规模问题的求解，并与不考虑异步的车辆路径的结果进行对比分析，验证了该算法解的优越性，证明了本文提出的异步车辆路径问题能够有效地提高冷链运输效率、降低冷链运输成本。

关键词：车辆路径；异步；精确算法；分支定价

目录

摘要 1

目录 1

第1章绪论 3

1.1研究背景与意义 3

1.1.1研究背景 3

1.1.2.研究意义 3

1.2国内外的研究现状 4

1.2.1车辆路径优化模型综述 4

1.2.2VRP问题精确算法求解综述 5

1.3主要研究内容 6

1.3.1异步车辆路径问题的模型建立 6

1.3.2分支定价算法设计 6

1.3.3实验设计与结果分析 6

第2章异步车辆路径问题的模型建立 7

2.1问题描述 7

2

2.2符号说明 7

2.2.1集合 7

2.2.2参数 7

2.2.3决策变量 7

2.3数学模型 7

第3章异步车辆路径问题算法设计 9

3.1分支定价算法的基本思路 9

3.2集合覆盖模型 10

3.3列生成 11

3.4初始化 12

3.5子问题 12

3.6动态规划 13

3.7分支策略 13

3.8算例计算过程 14

3.8.1算例描述 14

3.8.2异步路径算法求解过程 14

3.8.3对比分析 18

第4章实验设计与结果分析 19

4.1实验数据与运行环境 19

4.2实验说明 20

4.3实验结果分析 20

4.3.1不考虑异步情况的实验结果 20

4.3.2考虑异步情况的实验结果 21

4.3.3对比分析 23

第5章结论与展望 25

5.1总结 25

5.2展望 25

参考文献 27

3

第1章绪论

1.1研究背景与意义

1.1.1研究背景

随着社会经济的发展和人民生活水平的提高，人们对食品的消费需求，从基本温饱需求逐渐转为营养型，对奶制品、新鲜果蔬、蛋等等的需求量不断增加，对质量要求也有所提高，使得冷链配送行业迅速发展。而且，日益增长的冷鲜产品的需求带动了大多数连锁超市以及网络电商行业的发展，从而促进了冷链物流行业的快速发展。我国是农业生产和农产品消费大国，截止到2017年，我国的蔬菜产量约占全球总产量的60%,水果和肉类产量占其中的30%,禽蛋和水产品产量占其中的40%。近几年来，我国的生鲜农产品产量快速增加，每年约有4亿吨生鲜农产品进入流通领域以满足人们的需要，冷链物流占社会总物流的比重逐步扩大。截止到目前，我国果蔬、肉类、水产品的冷链流通率达到5%、15%、23%,冷藏运输率分别达到15%、30%、40%,冷链物流的规模快速增长。2016年全国冷链物流市场需求达到2200亿元，同比增长22.3%。

冷链物流是指物品在生产、仓储或运输和销售过程中，一直到消费前的各个环节中始终处于产品规定的最佳低温环境下，才能保证食品质量，减少食品损耗的一项系统工程。目前我国冷鲜产品流通中的腐损率严重，显著落后于发达国家水平。调查研究认为，我国冷鲜产品过低的冷链流通率是造成这一结果的主要原因，而我国冷链物流体系落后主要体现在两个方面：基础设施和配套设施不足，各物流环节间缺乏系统化、规范化、连贯性的运作。如何节约运输距离、减少制冷成本使物流环节更为系统化、规范化成为了当下研究的主要问题，具有重要的理论与现实意义。

1.1.2.研究意义

只研究冷链车