详情

原文传递面向协同运输的车辆路径问题优化算法研究

论文题名：	面向协同运输的车辆路径问题优化算法研究
关键词：	协同运输;车辆路径问题;数学模型;有效不等式;下界模型;启发式算法
摘要：	协同运输是近年发展并兴起的协同物流运作模式中的重要内容。协同运输要求相对独立的运输企业协同运作，共享物流资源和物流信息，共同承担客户需求，以达到减少车辆空载，降低整体物流成本，提高运行绩效和提高运输服务水平的目的。协同运输是一种新兴的运输模式和理念，面对此新型运输模式，产生诸多新问题有待研究。面向协同运输的车辆路径问题是其中一类基本而重要的问题。通过研究面向协同运输的车辆路径问题，可以确定运输企业在协同运输中最优车辆使用数目和车辆路径。同时，此问题也将为协同运输中的其他问题提供研究基础，对提高物流企业的生产经营管理水平和降低运作成本具有重要的理论意义和现实价值。　　本文以面向协同运输的车辆路径问题为研究对象，提出面向协同运输的几类重要车辆路径问题，建立问题数学模型，综合运用组合优化、图论和启发式算法等方法和工具，设计求解问题的优化算法，并提出问题的有效不等式和紧凑下界，以定量评价所提出优化算法的求解精度。同时作为下一步研究的初步探讨，本文还以所研究的车辆路径问题作为基础，研究了面向协同运输的多企业利益分配问题。本文主要研究工作包括以下几点：　　 (1)综述了传统的车辆路径问题和面向协同运输的车辆路径问题。对车辆路径问题中两大基本问题，点路径问题和弧路径问题，以及面向协同运输特有的几类车辆路径问题，讨论分析了目前已经提出的数学模型、精确求解算法和启发式求解算法，分析了各种算法的求解性能。　　 (2)对基于任务选择的车辆路径问题进行研究。建立了此问题的混合整数规划数学模型。在分析问题数学模型特点的基础上，提出了问题的下界数学模型，采用数学规划软件Cplex实现分支定界算法求解下界数学模型，得到问题的下界。利用所研究问题的特性，基于简单启发式求解算法和最短路标签算法，设计了高效的现代启发式算法求解此问题。通过数值试验证明所提出启发式算法具有求解精度高，求解快速的特点，并验证了所提出的下界数学模型非常紧凑。　　 (3)首次提出开放-闭合混合式车辆路径问题。对此复杂问题建立精确数学模型，并设计现代启发式算法对此问题求解。启发式算法中嵌入利用了求解约束最短路问题的双标签算法，从而使得算法整体结构比较简单且易于实现。同时对此问题提出有效不等式，明显改进了分支定界算法求解问题的上界、下界效果和求解时间。数值试验证明，相对加入有效不等式提高后的Cplex求解结果，本文所提出的启发式算法在求解精度和求解时间两方面具有明显的优势。　　 (4)研究了两点间多次运输的多车场满载弧路径问题。针对目前精确算法求解此问题的不足，建立了该问题的全新数学规划模型和基于图论的模型，并设计了高效的两阶段启发式求解算法。第一阶段利用贪婪算法生成初始解，即形成完全覆盖运输任务弧的回路集；第二阶段组合和连接回路，构造起止于车场的闭通路。最后，利用局域搜索对求得的解改进，以得到最终解。同时，在分析问题特点性质基础上提出了新的下界数学规划模型。通过数值试验，定量分析了所提出启发式算法的求解效率和精度，同时分析对比了本文所提出的新下界模型和已有下界模型的效果。　　 (5)作为面向协同运输的车辆路径问题研究的扩展和进一步研究的探索，研究了面向协同运输的多企业利益分配问题。以面向协同运输的车辆路径问题优化结果为基础，同时采用Shapley值法对协同的利益在企业之间合理分配。对此问题研究深化了协同运输中利益分配问题的研究深度，为后续使用本论文的研究成果深入求解相关问题提供了借鉴和参考。
作者：	刘冉
专业：	机械工程(工业工程)
导师：	江志斌
授予学位：	博士
授予学位单位：	上海交通大学
学位年度：	2011
正文语种：	中文