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

一维组合装车问题模型与算法研究

作　者: 张江静
导　师: 陈峰
学　校: 上海交通大学
专　业: 管理科学与工程
关键词: 组合装车混合整数线性规划分支定界启发式算法贪婪技术敏感性分析
分类号: F252;U116
类　型: 硕士论文
年　份: 2012年
下　载: 79次
引　用: 0次
阅　读: 论文下载

内容摘要

整车出厂物流装箱调度所涉及的数据规模大、统计难度高、约束多,其复杂性和所要求的处理速度与精度已经远远超出了人工处理的能力范围。然而,目前第三方物流公司普遍信息化水平较低,程序开发能力较弱,承运人员混杂、管理难度较高,故仍旧采取效率极低的人工调度,由于调度规模庞大,人力成本变得不容忽视。同时,目前的计算能力和速度还无法求解如此大规模的问题,因此,建立简单有效的模型,提高问题的实用价值有着重要的意义。本文根据整车出厂物流装箱调度问题,去掉可以留作后续处理的约束与目标,找出核心约束与目标,将其定义为一维组合装车问题。一维组合装车问题为有n个属于l种类型的相同(单位)尺寸的物品。有w辆车,每辆车对这l种类型的物品有几种装载组合,不同车辆的装载组合不同,每辆车选择一种装载组合并按照物品组合进行装载,优化目标是装载最多的物品,一维组合装车问题是NP-难的组合优化问题。本文旨在提供一个基本的模型,重在提高模型的应用价值。问题的求解时间、各项资源的利用率与各项参数对问题结果的影响是本文的研究重点。因此本文在分析问题的基础上,首先,建立了线性混合整数规划和分支定界算法模型,并提出了基于贪婪技术的启发式算法。其次,进行数值实验,验证各个算法的性能,启发式算法能够在很短的时间内获得大规模问题的解,但求解结果较最优化算法较差,分支定界算法随着求解规模的扩大,算法的运行时间、无解数逐渐加大,对比Cplex的求解结果发现,分枝定界算法在性能上没有显著优势。最后,对影响算法性能的关键参数进行敏感性分析得出:⑴车辆利用率随着装载组合数增加而提高,达到峰值后缓慢下降;⑵随着类型数的增加求解时间消耗降低,同时物品装载数也迅速减少。同时,本文提出的装载组合的概念为解决装箱问题提供了一种不同的思路,是复杂的二维、三维装箱问题的简化,应用范围更广。本文提出的模型与分析结果对实际应用也有一定的指导意义。

一维组合装车问题模型与算法研究

内容摘要

全文目录

相似论文