学位论文 > 优秀研究生学位论文题录展示

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

作　者: 李晨
导　师: 陈秋双
学　校: 南开大学
专　业: 数学
关键词: 车辆路径问题分支定价协作机制双向动态规划
分类号: F274
类　型: 硕士论文
年　份: 2010年
下　载: 155次
引　用: 1次
阅　读: 论文下载

内容摘要

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

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

内容摘要

全文目录

相似论文