带有协作机制的车辆路径问题的分支定价算法

摘要

近年来,随着全球化步伐的加快和国际贸易的迅猛增长,运输环节已经成为全球供应链中至关重要的一环。对于许多公司来说,分销货物所需的运输费用在整个运作成本中占有相对高的比例。如何有效地减少运输费用成为了工业界和理论界共同关注的课题。
　　 本文中,我们把协作机制引入到车辆路径问题中,提出了带有协作机制的车辆路径问题。通过协作,各个公司之间可以共享车辆容量,消除重复、对流路径,从而达到减少运输费用,提高整体运作效率的目的。
　　 本文主要研究了传统的车辆路径问题(VRP)和面向收益的车辆路径问题(MVR.PP),并在第一章里对其基本概念、主要分类和研究现状作出了详细介绍。
　　 本文介绍了VRP的精确算法,给出了一个以行驶距离最小为目标的混合整数规划模型,通过Danzig-wolfe分解,把该模型转化成了集合划分(SP)模型和子问题模型。该子问题模型是一类带有资源约束的最短路径问题(RCESPP),可以通过双向动态规划算法来求解。实验表明,在较大规模算例中,该算法能够在可接受的时间内求得最优解。
　　 针对带有协作机制的VRP,本文提出了其分支定价算法。根据该问题的特点,建立了SP模型和子问题模型。为了减少计算时间,我们对原有的动态规划算法进行了改进,提出了“一次扩展+多次拼接”的思想。通过大量实验数据表明,加入“协作联盟”能够有效地减少企业个体和联盟整体的运输费用,对加强企业竞争力具有很大帮助；还提出了协作关系稳定性的概念,并对协作关系的稳定性进行了数值分析。
　　 第五章对MVRPP和带有协作机制的MVRPP进行了研究。在MVRPP中,包括两个相互冲突的目标:收益最大和行驶距离最短。通过把行驶距离作为约束来考虑,该问题被转化为一个单目标规划问题。针对MVRPP,本文提出了以收益最大为目标的SP模型,并给出了求解RCESPP的双向动态规划算法。同时,本文还对带有协作机制的MVRPP进行了探究,提出了该问题的数学模型,并根据带有协作机制的MVRPP问题的特点,设计了双向动态规划算法。数值实验表明,加入“协作联盟”能够有效增加企业的服务收益,具有较高的实用价值。

目录

文摘

英文文摘

第一章 绪论

第一节 研究背景与意义

1.1.1 研究背景

1.1.2 研究意义

第二节 与运输环节相关的协作问题的研究

1.2.1 运输环节与其它环节的协作

1.2.2 运输环节内部的相互协作

第三节 VRP国内外研究现状

1.3.1 VRP求解算法简介

1.3.2 MVRPP研究综述

第四节 研究内容

1.4.1 研究重点

1.4.2 研究的框架和内容安排

第二章 列生成法与分支定价法

第一节 大型LP与列生成法

2.1.1 Danzig-Wolfe分解原理

2.1.2 列生成法

第二节 分支定价算法

2.2.1 分支定价算法的基本思路

2.2.2 算法初始化

2.2.3 分支策略

第三章 VRP的分支定价算法

第一节 问题描述和数学模型

3.1.1 VRP的混合整数规划模型

3.1.2 VRP的SP模型

3.1.3 VRP的子问题模型

第二节 RCESPP的双向动态规划

3.2.1 RCESPP的问题描述和研究背景

3.2.2 动态规划算法设计

第三节 列生成法

3.3.1 上界双向动态规划

3.3.2 综合的列生成过程

第四节 分支方法

第五节 计算实例与结果分析

第六节 本章小结

第四章 带有协作机制的VRP的研究

第一节 问题描述

第二节 带有协作机制的VRP的数学模型

4.2.1 带有协作机制的VRP的SP模型

4.2.2 带有协作机制的VRP的子问题模型

第三节 改进的双向动态规划算法

4.3.1 状态量

4.3.2 状态的扩展和拼接

4.3.3 统治规则

第四节 分支方法与搜索策略

4.4.1 分支方法

4.4.2 搜索策略

第五节 计算实例与结果分析

4.5.1 协作机制的效果

4.5.2 协作机制的稳定性

第六节 本章小结

第五章 MVRPP及带有协作机制的MvRPP的研究

第一节 MVRPP的研究

5.1.1 问题描述

5.1.2 MVRPP的数学模型

5.1.3 动态规划算法设计

5.1.4 分支方法和搜索策略

第二节 带有协作机制的MVRPP的研究

5.2.1 带有协作机制的MVRPP的数学模型

5.2.2 双向动态规划算法设计

5.2.3 分支方法与搜索策略

第三节 计算实例与结果分析

第四节 本章小结

第六章 总结与展望

第一节 本文的主要研究成果及创新点

第二节 进一步的研究方向

参考文献

致谢

个人简历攻读硕士学位期间完成的论文