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

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

摘要

随着冷链物流的快速发展，生鲜冷链运输比例逐渐上升，单纯仅考虑一种车型的车

路径问题的研究在实际配送过程中，很容易使冷链产品配送车与常温类产品的配送车发生

冲突，经常出现卸货不及时，互相干扰搬运等问题，这带来最直接的后果就是冷藏车在门

店停留时间过长，运输过程中的制冷成本不断上升。为解决这一问题，本文针对异步路径

车路径问题进行研究。异步车路径问题研究是在基础的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

1

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

2

第1章绪论

1.1研究背景与意义

1.1.1研究背景

随着社会经济的发展和人民生活水平的提高，人们对食品的消费需求，从基本温饱需

求逐渐转为营养型，对奶制品、新鲜果蔬、蛋等等的需求量不断增加，对质量要求也有所

提高，使得冷链配送行业迅速发展。而且，日益增长的冷鲜产品的需求带动了大多数连锁

超市以及网络电商行业的发展，从而促进了冷链物流行业的快速发展。我国是农业生产和

农产品消费大国，截止到2017年，我国的蔬菜产量约占全球总产量的60%,水果和肉类

产量占其中的30%,禽蛋和水产品产量占其中的40%。近几年来，我国的生鲜农产品产量

快速增加，每年约有4亿吨生鲜农产品进入流通领域以满足人们的需要，冷链物流占社会

总物流的比重逐步扩大。截止到目前，我国果蔬、肉类、水产品的冷链流通率达