物流配送车辆路径问题算法地研究.pdf

国内图书分类号: 学校代码: 10213 国际图书分类号: 620 密级:公开工学硕士学位论文物流配送车辆路径问题算法的研究硕士研究生:郝佳慧导师:崔刚教授申请学位:工学硕士学科:计算机科学与技术所在单位:计算机科学与技术学院答辩日期: 2014年 6月授予学位单位:哈尔滨工业大学万方数据 Classified Index: .: 620 Dissertation for the Master Degree in Engineering ARESEARCH OF LOGISTICS DISTRIBUTION VEHICLE ROUTING PROBLEM ALGORITHM Candidate: Hao Jiahui Supervisor: Prof. Cui Gang Academic Degree Applied for: Master of Engineering Specialty: Computer Science and Technology Affiliation: Computer Science and Technology Date of Defence: June, 2014 Degree-Conferring-Institution: Harbin Institute of Technology 万方数据哈尔滨工业大学工学硕士学位论文-I- 摘要本文主要研究了带随机旅行时间窗口的车辆路径问题,该问题可以广泛的应用到车联网、智能交通和智慧城市等多方面,有着很重要的现实意义。针对带有随机旅行时间和软时间窗口的车辆路径问题给出了问题描述, 建立了相应的数学模型,首次提出了运输成本与服务成本的区别,并设计了解决该问题的混合三阶段算法,第一阶段采用改进的 Solomn插入算法作为初始解算法,第二阶段采用禁忌搜索算法,采用多种邻域结构和改进算子进行算法的改进,第三阶段采用后续优化算法。并在国际标准测试集上测试该算法,求得结果并分析,分析结果表明:本文算法在不同的网络结构的实例中都可以在合理的时间内得到很好的结果,每单位距离旅行时间的变化将直接影响服务的成本,另外,该模型成功的创建了各种解决方案来适应物流配送公司的选择偏好。针对带有随机旅行时间和硬时间窗口的车辆路径问题给出了问题描述, 建立了相应的数学模型,并提出了一种计算混合随机变量的一般方法,该方法可用于具有任意和独立的随机变量的计算,包括加法运算和最大化运算等, 同时,该方法具有很大的通用性。本文还成功的设计并开发了物流配送车辆路径算法的仿真系统,该系统采用 MVC程序架构,使用 JAVA语言进行开发,成功的实现了车辆路径的可视化,该系统将来可以应用到具体的物流等大型企业系统中,具有很大的应用前景。关键词:软时间窗口;硬时间窗口;物流配送车辆路径规划;混合三阶段算法;禁忌搜索万方数据哈尔滨工业大学工学硕士学位论文-II- Abstract This paper studiesvehicle routing problem with stochastic travel time problemcan be widely applied to vehicle networking, intelligent transportation, smart city and so study has important practical significance. For vehicle routing problem with stochastic travel time including soft time windows, a description of the problemand mathematical modelare given. We firstly proposethe distinction between the cost of transportation and service costs, and a hybrid three-phase algorithm to solve this problemis first phase uses the improved Solomn insertion