车辆路径问题

1、车辆路径问题模型及算法研究摘要车辆路径何题(Vehicle Routing Problem. VRP)姑组合优化和运井学领域研究 的热点问题之一，其L要研究满足约束条件的最优车辆使川方案以及此优的车辆路 径方案。基于基本车辆珞径向题的框架，研究满足生产经肖和运作需要的各种车辆 路径问题，并构建具有高质情和高仰棒性(robustness)的向题求解算法对提高4: 产经昔管理水平卸降低运作成木具有重要的理论意义和现实汾值。木文以车辆路径问题为研究对汝，踪合运用组合优化和现代启发式算法等工 具，对凡类重要的车辆路径问题模型及其优化算法进行了系统的研究，主要研究工 作及成果总结如R1. 综述了车辆路径

2、问题 在定义车辆路径问题分类和扩展标准的基础上，给出了 车辆路径问题的研究综述。血于不同的分类标淋，泞先讨论了主要的标准车辆 路径问题扩展问题。在此姑础上详细地综述了求御标准车辆路径问题的现代启 发式算法，系统地描述了各种算法的实现机理以及各种算法的性能比较结果。2 .嫁述了求解组合优化问题的现代启发式算法 在给出组合优化问题和计算复杂性定义的基础上，综述了求解夏朵组合优化问题的各种现代启发式算法。3 .研究了开放式乍辆路径问题通过松弛标准车辆路径问题中车辆路线为哈密尔顿巡回(Hamiltonian tour)的锻设，研究了牟轲路线为哈密尔顿路径 (Hamiltonianpath)的开放式乍辆

3、路径何题。该问题中乍辆在服务完最后一个 顾客点:后不需要mi到车场，若要求同到车场，则必须沿原路返I叽在n先给出 问袈数学模型的基础上，提出了求解开放式乍辆路径问题的蚊群优化算法。该 算法主体是一个在超立方框架下执行的人亿*人仃MW蚁系统，算法混合了禁 忌搜徵算法作为局部优化算法，同时集成了个后优亿过程来进-步优化最优 解。基丁基滩测忒问题系统地研究了算法性能。同其它算法的性能比较结果 表明本文提出的蚁群优化算法是有效的求解开放式车辆路径问题的方法4. 研究了带时间窗和带时间期限开放式乍辆路径问题 遍过引入时间约束，研究 了两类新的满足时效性要求的开放式车辆物径问题一带时间窗和带时间期限开放式

4、车辆路径问题。首先构建了两类问题的数学校型，同时提出了求解两上海交通大学叫士学位论文类问题的基于禁忌搜索的迭代局部搜索尊法，该算法集成了不同的解接受标准 以及，个基f闽值接受的后优化过程。基f随机产生的测试何题的实验结果表 明:基于禁忌搜索的迭代局部搜索算法可以有效地求解带时间窗和带时间期限 开放式车辆路径问5. 研究了带时间窗和随机旅行时间车辆路径问题通过对标准车辆路径问题的拓 展，引入新的边约束条件：时间窗、随机旅行时间和JM务时间，研究了-类浙 的随机车辆路径向题一带时间窗和随机旅行时间乍辆路径问题。根据不同 的优化标准，分别构建了何题的机会约束融划模塑以及带修正随机规划模型。机会约束规

5、划模型是在随机约束以定的置信水平成立的条件卜.最小化运输费 川。带修正的随机规划模犁是一个两阶段优化间题，底确定第一阶段的路线集 以成小化第二阶段（随机变虽实现后）的期望运输成用。鉴于何题的随机特 性，为r有效求解该问题提出r基于随机模拟的禁忌搜索算法.同时基随机 产生的测试问题通过实验检验了算法有效性。6. 研究了固定车辆数异型车辆路径问题 在车辆玲径何题经典文献中， 般均假 设车辆同质口.车辆数无限。然而在实际运作中，车辆集一般是由具右不同届性（装菽能力、固定成木以及单位公里可变费用）的车辆组成，且受运作:成木的 约束车辆数也是固定的。通过对车辆同质及车辆数无限的假设条件的放松，研 究了固

6、定车辆数的异型车辆路径问题。在首先给出问题数学模型的基础上，提 出了求解该何题的多起点自适应记忆规划算法.族于文献中的暴准测试问题， 系统地研究了算法在不同多样化策略卜的性能。同文献中其它算法的比较结果 表明：提出的多起点自适应讪忆规划尊法是较好的求解固定车辆数异型车辆路 径问题的算法，对丁其中五个测试问题，算法发现了新的最优解。7. 研究了车辆路径何题的应用问题 以城市日常报晶配送问题为例，进行了车辆 路径问题的应用研究基于报品配送的实际数据，运用本文研究的儿类车辆路 径问题的框架，研究了不同类型的最优报品配送乍辆路径方案的制定问题。执 行木文提出的优化算法，给出了不同类型的报品配送的最优车

7、辆路径方案。通 过实验验证了论文提出的车辆路径问题优化算法的有效性，实驶结果表明论文 提出的算法可以用于生产管理中最优乍辖路线方案的制定。本文创新性研究成果及页献主要包括以下凡方而：I.松弛了标准VRP中乍辆捋线为哈密尔顿巡回的假设，研究了车辆路线为哈密尔中文摺要顿路径的开放式车辆粕径何题。构建了求解何题的蚁群优化算法，该算法是- 个集成r后优化过程的在超立方框架卜执行的蚂蚁系统。同文献 中M它算法性能的比较结果证明本文提出的蚁群优化耸法是有效的求解开放式 车辆路径问题的方法，算法改进了文献中其它算法发现的最优解。2. 引入时间约束，研究了两类新的满足时效性要求的车辆路径问题一带时间 窗和带时

8、间期限开放式车辆路径问题。提出了求解上述两类向题的送代局部搜 索算法，并基于随机产生的测试问系统研究了算法的求解性能。3. 引入时间窗、随机旅行时间和服务时间约束，研究了带时间窗和随机旅行时间 车辆路径问题,根据不同的优化标准，分别构建了问题的机会约束规划模型以 及带修正随机规划模型。提出r基j.随机模拟的禁忌搜索算法，基于随机机产 生的测试何题的实验结果验证了算法的有效性4. 通过松弛标准VRP中车辆同质及车辆数无限的假设，研究了固定车辆数异型车 辆路径问题。提出r求解何题的多起点自适应记忆规划算法，同文献中其它算 法的比较结果表明：多起点自适应记忆规划算法是较好的求解固定车辆数异型 车辆路

9、径问题的算法，对于五个基推测试问题，算法发现了新的最优解。本文综合运用运筹学和组合优化的理论与方法，对几类乍辆路径问题模型及算 法进行了系统的研究.木文的研究工作拓展了车辆路径问题以及组合优化的研究空 间，丰富了运筹学和管理科学的理论研究成果，同时为这输、物流和配送管理等领 域中最优车辆路径方案的期划与设计提供了借鉴和参考。关键词：车辆将径问题：优化模型：现代启发式算法-in-目录摘要1ABSTRACT IV插图目录XII表格目录XIII第一章绪论11.1问魄背景和意义I1.2研究目标31.3研究内容31.4研究方法61.5论文创新点6第二章车辆路径问题研究综述82.1引言82.2标准车辆路径

10、问我及其数学模型82.3车辆路径问题扩展问题1123.1车辆路径问题构成要素 H232车辆路彳仝问题步、展标准 132.33车辆路径问题扩展问题 152.4标准乍辆路径问题求解算法 222.4.1经典启发式算法232.4.2现代启发式算法 272.5小结37第三章组合优化及现代启发式算法393.1组合优化问题393.2计算复杂性4033组合优化问题求解413.4现代启发式算法413.4.1迭代改进算法433.4.2模拟退火算法433.4.3禁忌搜索算法443.4.4贪婪随机自适应搜索过料 463.4.5变邻域搜索算法463.4.6引导局部搜索算法473.4.7迭代局部搜索算法48348进化计算

11、493.4.9蚊群优化算法50VIII车辆路径问题(vehideRoutingProblem , vRP)是组合优化和运筹学领域研究 的热点问题之一，其主要研究满足约束条件的最优车辆使用方案以及最优的车辆路 径方案。基于基本车辆路径问题的框架，研究满足生产经营和运作需要的各种车辆 路径问题，并构建具有高质量和高鲁棒性(roubustuess)的问题求解算法对于提高生产经营管理水平和降低运作成木具有重要的理论意义和现实价值。本文以车辆路径问题为研究对象，综合运用组合优化和现代启发式算法等工 具，对几类重要的车辆路径问题模型及其优化算法进行了系统的研究，主要研究工 作及成果总结如下：1. 综述了车

12、辆路径问题在定义车辆路径问题分类和扩展标准的基础上，给出了 车辆路径问题的研究综述。基于不同的分类标准，首先讨论了主要的标准车辆 路径问题扩展问题。在此基础上详细地综述了求解标准车辆路径问题的现代启 发式算法，系统地描述了各种算法的实现机理以及各种算法的性能比较结果。2. 综述了求解组合优化问题的现代启发式算法在给出组合优化问题和计算复杂 性定义的基础上，综述了求解复杂组合优化问题的各种现代启发式算法。3. 研究了开放式车辆路径问题通过松弛标准车辆路径问题中车辆路线为哈 密尔顿巡回(Hamiltoniantour)的假设，研究了车辆路线为哈密尔顿路径 (Hamiltonianpath)的开放式

13、车辆路径问题。该问题中车辆在服务完最后一个 顾客点后不需要回到车场，若要求回到车场，则必须沿原路返回。在首先给出 问题数学模型的基础上，提出了求解开放式车辆路径问题的蚁群优化算法。该 算法主体是一个在超立方框架下执行的侧只刃一侧工加尸蚂蚁系统，算法混合了禁 忌搜索算法作为局部优化算法，同时集成了一个后优化过程来进一步优化最优解。基于基准测试问题，系统地研究了算法性能。同其它算法的性能比较结果 表明本文提出的蚁群优化算法是有效的求解开放式车辆路径问题的方法。4. 研究了带时间窗和带时间期限开放式车辆路径问题通过引入时间约束，研究 了两类新的满足时效性要求的开放式车辆路径问题一带时间窗和带时间期

14、限开放式车辆路径问题。首先构建了两类问题的数学模型，同时提出了求解两 上海交通大学博十学位论文类问题的基于禁忌搜索的迭代局部搜索算法，该算法集成了不同的解接受标准 以及一个基于阂值接受的后优化过程。基于随机产生的测试问题的实验结果表 明:基于禁忌搜索的迭代局部搜索算法可以有效地求解带时间窗和带时间期限 开放式车辆路径问题。5. 研究了带时间窗和随机旅行时间车辆路径问题通过对标准车辆路径问题的拓展，引入新的边约束条件：时间窗、随机旅行时间和服务时间，研究了一类新 的随机车辆路径问题一带时IbJ窗和随机旅行时间车辆路径问题。根据不同的优化标准，分别构建了问题的机会约束规划模型以及带修正随机规划模型

15、。 机会约束规划模型是在随机约束以一定的置信水平成立的条件下最小化运输费 用。带修正的随机规划模型是一个两阶段优化问题，其确定第一阶段的路线集 以最小化第二阶段(随机变量实现后)的期望运输费用。鉴于问题的随机特 性，为了有效求解该问题提出了基于随机模拟的禁忌搜索算法。同时基于随机 产生的测试问题通过实验检验了算法有效性。6. 研究了固定车辆数异型车辆路径问题在车辆路径问题经典文献中，一般均假 设车辆同质目车辆数无限。然而在实际运作中，车辆集一般是由具有不同属性(装载能力、固定成本以及单位公里可变费用)的车辆组成，且受运作成本的 约束车辆数一也是固定的。通过对车辆同质及车辆数无限的假设条件的放松

16、，研 究了固定车辆数的异型车辆路径问题。在首先给出问题数学模型的基础上，提 出了求解该问题的多起点自适应记忆规划算法。基于文献中的基准测试问题， 系统地研究了算法在不同多样化策略下的性能。同文献中其它算法的比较结果 表明:提出的多起点自适应记忆规划算法是较好的求解固定车辆数异型车辆路 径问题的算法，对于其中五个测试问题，算法发现了新的最优解。7. 研究了车辆路径问题的应用问题以城市日常报品配送问题为例，进行了车辆 路径问题的应用研究。基于报品配送的实际数据，运用本文研究的几类车辆路 径问题的框架，研究了不同类型的最优报品配送车辆路径方案的制定问题。执 行本文提出的优化算法，给出了不同类型的报品

17、配送的最优车辆路径方案。通 过实验验证了论文提出的车辆路径问题优化算法的有效性，实验结果表明论文 提出的算法可以用于生产管理中最优车辆路线方案的制定。本文创新性研究成果及贡献主要包括以下几方面：1. 松弛了标准 VRP中车辆路线为哈密尔顿巡回的假设，研究了车辆路线为哈密尔顿路径的开放式车辆路径问题。构建了求解问题的蚁群优化算法，该算法是一 个集成了后优化过程的在超立方框架下执行的侧只刃一侧工加尸蚂蚁系统。同文献 中其它算法性能的比较结果证明本文提出的蚁群优化算法是有效的求解开放式 车辆路径问题的方法，算法改进了文献中其它算法发现的最优解。2. 引入时间约束，研究了两类新的满足时效性要求的车辆路径问题一带时间窗和带时间期限开放式车辆路径问题。提出了求解上述两类问题的迭代局部搜索算法，并基于随机产生的测试问系统研究了算法的求解性能。3. 引入时间窗、随机旅行时间和服务时间约束，研究了带时间窗和随机旅行时间 车辆路径问题。根据不同的优化标准，分别构建了问题的机会约束规划模型以 及带修正随机规划模型。提出了基于随机模拟的禁忌搜索算法，基于随机机产 生的测试问题的实验结果验证了算法的有效性。4. 通过松弛标准 VRP中车辆同