具有同时取送货和不确定信息的车辆路径问题研究

作     者：马明帅 

作者单位：东北大学 

学位级别：硕士

导师姓名：张薇

授予年度：2012年

学科分类：08[工学] 081202[工学-计算机软件与理论] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主      题：车辆路径问题 同时取送货 模糊时间窗 时间依赖性旅行时间 NP-H砌问题 遗传-禁忌搜索算法 

摘      要：在物流配送活动中,配送的车辆的路径问题是实现配送合理化的关键问题之一,选取合理的配送车辆路径方案,可以降低企业成本、提高服务质量、增加经济效益,以及增强客户对物流环节的满意度. 为降低配送成本,即避免传统的纯取货或送货所带来的空载现象,提高客户服务水平,本文从同时取送货、客户模糊时间窗和时间依赖性旅行时间三个方面出发,研究了具有同时取送货和不确定信息的车辆路径问题. 本文主要从以下几方面进行了分析和研究. 首先,对车辆路径问题的概念进行了阐述,对车辆路径问题的原始问题、特点以及分类进行了分析和总结,回顾并总结了车辆路径问题的求解算法. 其次,引入表示客户满意度的模糊隶属度函数和道路的时间依赖性旅行时间,建立了以最小化车辆行驶总距离、最小化车辆使用数、最小化车辆平均等待时间以及最大化客户平均满意度为目标的具有同时取送货和不确定信息的车辆路径问题模型.由于车辆路径问题是NP-Hard问题,所以根据新模型特点,本文结合遗传算法和禁忌搜索算法的优势,设计了遗传-禁忌搜索求解算法. 最后,用Matlab语言实现了新模型的遗传-禁忌搜索算法编程,并用算例进行了仿真测试.仿真结果表明,新模型效果良好,遗传-禁忌搜索算法运行可靠、有效.对比分析表明,解的质量有提升,总体上优于对比算法和他人的结果.