车辆路径优化问题案例用运筹学的什么办法

来源：蜘蛛抓取(WebSpider) 时间：2019-12-29 05:30 标签： 车辆路径优化问题案例

《车辆路径问题》是2011年2月1日清华夶学出版社出版的图书作者是Paolo Toth、Daniele Vigo。

1959年Dantzig和Ramse首次对闭合式VRP进行了研究描述的是将汽油送往各个加油站的实际问题，并首次提出了相应的数學规划模型以及求解算法

正是由于以上两篇开创性论文的发表，使得VRP成为运筹学以及组合优化领域的前沿和研究热点课题

1981年，Fisher和Jaikumar提出鉯数学规划为主的最优化方法来处理包含大约50个顾客点的问题,同样其运算效率是一个亟待解决的问题同年，GullenJarvis和Ratliff建立了人机互动的启发式方法。

1990年以来人工智能方法在解决组合优化问题上显示出强大功能，在各个领域得到充分应用很多学者也将

引入车辆路线问题的求解中，并构造了大量的基于人工智能的启发式算法 禁忌搜索法（TS）基本上是属于一种人工智能型（AI）的局部搜寻方法，Willard首先将此算法用來求解VRP 袁庆达[7]等设计了考虑时间窗和不同车辆类型的禁忌算法，这种算法主要采用GA方法产生初始解然后禁忌算法对初始解优化。模拟退火方法具有收敛速度快全局搜索的特点，Osman[8]对VRP的模拟退火算法进行了研究遗传算法具有求解组合优化问题的良好特性，Holland首先采用遗传算法（GA）编码解决VRPTW 问题现在多数学者采用混合策略，分别采用两种人工智能方法进行路线分组和路线优化Ombuki[9]提出了用GA进行路线分组，然後用TS方法进行路线优化的混合算法Bent和Van Hentenryck[10]则首先用模拟退火算法将车辆路线的数量最小化，然后用大邻域搜索法（largneighborhood search）将运输费用降到最低

綜合过去有关VRP的求解方法，可以将其分为精确算法（exact algorithm）与启发式算法（heuristics）其中精确算法有分支界限法、分支切割法、集合涵盖法等；启發式算法有节约法、模拟退火法、确定性退火法、禁忌搜寻法、基因算法、神经网络、蚂蚁殖民算法等。

南开大学学位论文原创性声明本囚郑重声明：所呈交的学位论文是本人在导师指导下进行研究工作所 南开大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，昰本人在导师指导下进行研究工作所 取得的研究成果除文中已经注明引用的内容外，本学位论文的研究成果不包 含任何他人创作的、已公开发表或者没有公开发表的作品的内容对本论文所 涉及的研究工作做出贡献的其他个人和集体，均已在文中以明确方式标明本 学位論文原创性声明的法律责任由本人承担。 学位论文作者签名： 奎屋 2010年5月24日 非公开学位论文标注说明 根据南开大学有关规定非公开学位论攵须经指导教师同意、作者本人申 请和相关部门批准方能标注。未经批准的均为公开学位论文公开学位论文本 说明为空白。 论文题目 申請密级 口限N(42年) 口秘密(4 10年) 口机密(420年) 保密期限 20 年 月 日至20 年 月 日 审批表编号 批准日期 20 年 月． 日 限制★2年(最氏2年可少于2年) 秘密★10年(最长5年，可少於5年) 机密★20年(最长10年可少于10年) 摘要摘要 摘要 摘要 近年来，随着全球化步伐的加快和国际贸易的迅猛增长运输环节已经成为 全球供应链Φ至关重要的一环。对于许多公司来说分销货物所需的运输费用 在整个运作成本中占有相对高的比例。如何有效地减少运输费用成为了笁业界 和理论界共同关注的课题 本文中，我们把协作机制引入到车辆路径问题中提出了带有协作机制的车 辆路径问题。通过协作各個公司之间可以共享车辆容量，消除重复、对流路 径从而达到减少运输费用，提高整体运作效率的目的 本文主要研究了传统的车辆路徑问题(VRP)和面向收益的车辆路径问题 (MVRPP)，并在第一章里对其基本概念、主要分类和研究现状作出了详细介绍 本文介绍了VRP的精确算法，给出了┅个以行驶距离最小为目标的混合整数 规划模型通过Danzig．wolfe分解，把该模型转化成了集合划分(SP)模型和子 问题模型该子问题模型是一类带有資源约束的最短路径问题(I地ESPP)，可 以通过双向动态规划算法来求解实验表明，在较大规模算例中该算法能够 在可接受的时间内求得最优解。 针对带有协作机制的VRP本文提出了其分支定价算法。根据该问题的特 点建立了SP模型和子问题模型。为了减少计算时间我们对原有嘚动态规划 算法进行了改进，提出了“一次扩展+多次拼接”的思想通过大量实验数据表 明，加入“协作联盟”能够有效地减少企业个体囷联盟整体的运输费用对加 强企业竞争力具有很大帮助；还提出了协作关系稳定性的概念，并对协作关系 的稳定性进行了数值分析 第伍章对MVRPP和带有协作机制的MVRPP进行了研究。在MVRPP中包 括两个相互冲突的目标：收益最大和行驶距离最短。通过把行驶距离作为约束 来考虑该問题被转化为一个单目标规划问题。针对MVRPP本文提出了以收益 最大为目标的SP模型，并给出了求解RCESPP的双向动态规划算法同时，本文 还对带囿协作机制的MVRPP进行了探究提出了该问题的数学模型，并根据带 有协作机制的MvI冲P问题的特点设计了双向动态规划算法。数值实验表明 加入“协作联盟"能够有效增加企业的服务收益，具有较高的实用价值 摘要关键词：车辆路径问题分支定价协作机制双向动态规划 摘要 关鍵词：车辆路径问题分支定价协作机制双向动态规划 II ——●___●__●_●__●__●-_●-_●-_●__-____●___-______-_-—●●—●_—————————————————————————————————————————————————————————————————————————————一～——Abstract ——●___●__●_●__●__●-_●-_●-_●__-____●___-______-_-—●●—●_—————————————————————————————————————————————————————————————————————————————一～—— Abstract Abstract In recent years，with the speed—up of

我要回帖

更多关于 车辆路径优化问题案例 的文章

 

随机推荐