车辆路径问题

车辆路径问题模型及算法研究摘要4：辆路径问题(VehicleRoutingProblem-VRP)是组合优化和运咎学领域研究的热点问题Z—，其耍研究滴扯约束条件的最优车辆便川方案以及绘优的车辆路径方案。羞于基本午辆粘径问遊的框架.研究满足生产经會和运作需要的各种车辆路径问题，并构建八有高质吊和高码棒性(roubustness)的问題求解算法对J：提高工产经背管理水平和降低运作成木具有重要的理论意义和现实价值。木文以车辆路径问题为研究对盘，综合运用组合优化和现代启发式算法等工具，对儿类亜要的车辆路径问題模世及氏优化算法进行了系统的研究，卞更研究工作及成果总结如»综述了车辆路径问题在定义车辆路径问题分类和扩展标准的堪础上，给岀了乍辆州径问题的研究综述。尿于不同的分类标准，汗先讨论了主要的标准乍辆路径问题扩展问題。在此械础上详细地综述了求解标旌牟納路径问題的现代启发式算法，系统地描述了并种知法的实现机理以及#种笄法的性能比较结果。2•综述了求解组仟优化问题的现代启发式殊法在给出组介优化问题和计算复杂性定义的基础上，综述了求解以杂组合优化问题的各种现代门发式算法。研究了开放式车辆路径问趣通过松弛标准午辆路栓问题中车辆路线为哈密尔顿巡冋(Hamiltonianlour)的假设，研究了乍辆路线为哈密尔顿路径(Hamiltonianpath)的开放式乍辆路径问题。该问题中卞辆在服务完故肓一个顾客点后不碍要冋到牟场，若要求冋到车场，则必须沿原路返冋。在斤先给出问題数学模型的基础上，捉出了求解开放式乍辆路径问题的蚊群优化并法。该舜法王体是一个在超立方橢架下执厅蚂蚁泵统，算法混合了祭总搜索57法作为局部优化算法，同时集成了•个后优亿过程來进一步优化放优解。肚丁卑准测试问题.系统地研究了笄法性能。同尖它算法的性能比较结果农明本文提出的蚁群优化算法足有效的求解开放式乍辅路径问题的方法。研究了帯时间窗和带时间期限开放式乍辆路径问题通过引入时何约束.研究了两类新的满足时效性要求的开放式车辆路径问题一带时间窗和帶时间期限开放式乍辆路径问题。首先构建了两类问题的数学模型，同时提出了求解两上海交通人学冊十学位论文类制题的基于禁忌捜索的迭代局部搜索算法.该尊法集成了不同的解接曼标准以及-个基J••阈値接受的忘优化过程。呈『僦机产生的测试问题的实验结果衷明：基于禁忌搜索的迭代局部搜索算法町以有效地求解带时间陽和带时间期限开放式车辆路径问题。研究了带时间窗和葩机旅行•时间车辆路径问題通过对标准车辆路径问题的拓展，引入新的边约束条件：时间修.碗机旅行时间和JM务时间，研究了-类新的随机乍辆路径问题一带时间謝和Ki机旅行时间乍辆路径问题V根据不同的优化标准，分别构建了何題的机会约東规划模型以及帶修正葩机规划模熨。机会约束规划模型是在冏机约束以•定的玄信水平成立的条件卜・赧小化运输费川。带修正的Ki机规划模型是一个两阶段优化问題，兀确定笫一阶段的路线集以放小化第二阶段（随机变駅实现厉）的期望运输M用。鉴于问题的随机特件，为了仃效求解该问逢提出了某于随机模拟的禁忌搜索算法。同时棊于随机产生的测试问题通过实验检验了算法有效性。6•研究了固定车辆数异型车辆路径问题加午辆路径问題经典文献叽 般均假设车辆同质目.车辆数无限。然而在实际运作中，车辆集一般是由具刃不同属性（装戦能力、固定成木以及址位公里町变费用）的午轲组成，且受运作成木的约束车辆数也是固定的。通过对车辆同质及车辆数无凰的假设条件的放松，研究了固定乍辆数的牙型乍辆路径问题。九廿先给出问題数学模型的基础I:,提出了求鲫该问题的多起点自适应id忆规划算法•堆于文献中的甚准測试问题，系统地研究了算法在不同多样化策略F的性能。同文献中其它算法的比较结果衣明：捉出的多起点自适应记忆规划邛法是较好的求解同定午辆数异型午辆路径问题的算法，对丁其中五个测试问题，并法发现了新的垠优解。7.研究了年辆路径问题的应用问題以城市H常报汕配送问题为例，进行了午辆路径问邀的应用研究。星于报品配送的实际数据，运用木文研究的儿类车辆路径问题的槛架，研究了不同类旳的最优报品配送加辆辟径方案的制定问題。执行木文提出的优化算法，给出了不同爻熨的报品配送的拟优午辆路径方案。通过实验验证了论文提出的牟辆路径问题优化算法的育效性，实齡结果表明论文提出的算法可以用于生产管理中最优4辆路线方案的制定。本文创新性研究成果及贡献主耍包括以下几方面：I.松弛了标准vr冲乍辆路线为哈密尔顿巡冋的假设，研究了乍辆路线为哈密尔-III--III-领路径的丿F放式午辆路径何题。构建了求解问题的蚁椭优化算法，该算法是・个集成了后优化过用的在超立方梃架卜•执行•的系统。同文献中英它算法性能的比较结果证明本文提出的蚁群优化飪法是有效的求解开放式车辆路径问題的方法，算法改进了文献中其它算法发现的最优解'引入时间约束，研究了两类新的满足时效性耍求的车辆路径问题一带时间囱和带时何期限开放式车辆路径问题。提出了求解上述两类问趣的迭代局部搜索算法，并基于随机产生的测试问系统研究了算法的求解性能•3•引入时间陽.碗机旅行时间和眼务时间约束，研究了带时间窗和甌机旅行时何车辆路径问题.根据不同的优化杯准，分别构建了问題的机会约束规划模空以及带修正M机规划模型。提出了基于同机模拟的禁忌搜索算法，基于随机机产生的测试问題的实验结果验证了算法的有效性。4.通过松弛标准VRP中车辆同质及车辆数无限的假设，研究f固定车辆数异型车辆路從问题。提岀了求解何題的多起点白适应记忆规划算法，同文献中其它算法的比较结果表明：多起点自适应记忆规划算法是较好的求解同定乍辆数界型车辆路径问題的算法，对于任个基准测试问题，算法发现了新的址优解。木文综合运用运写学和组合优化的理论与方法，对几类乍辆路径问題模型及算法进行了系统的研究•木文的研究工作拓展了千输路径问迦以及组合优化的研究空间，丰富了运篦学和管理科学的理论研究成果•同时为运轮、物流和配送管理等领域中最优弔辆捋径方案的规划与设计提供了借鉴和参考。关键词：车辆將径问题：优化模世：现代启发式算法VIIIVIII目录TOC\o"1-5"\h\z\o"CurrentDocument"摘要 1ABSTRACT IV插图目录 XII表格目录 XIII第一章绪论 11.1问題背尿和怠义 11.2研究目标 31.3研究内容 31.4研究方法 61.5论文创新点 6第二章车辆路径问题研究综述 82.1引言 82.2标准车辆路径问题及英数学模型 82.3车辆路径问題扩展问题 11231弔辆路径问题构成要素 H23.2车辆路彳殳问題孑亠展标准 132.33车辆路径问題扩展何題 152.4标准乍辆路径问题求解口法 22241经典启发式算法 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进化计算 493.4.9蚁群优化算法 50车辆路径问题(vehideRoutingProblem，vRP)是组合优化和运筹学领域研究的热点问题之一，其主要研究满足约束条件的最优车辆使用方案以及最优的车辆路径方案。基于基本车辆路径问题的框架，研究满足生产经营和运作需要的各种车辆路径问题，并构建具有高质量和高鲁棒性 (roubustuess)的问题求解算法对于提高生产经营管理水平和降低运作成木具有重要的理论意义和现实价值。本文以车辆路径问题为研究对象，综合运用组合优化和现代启发式算法等工具，对几类重要的车辆路径问题模型及其优化算法进行了系统的研究，主要研究工作及成果总结如下:综述了车辆路径问题在定义车辆路径问题分类和扩展标准的基础上，给出了车辆路径问题的研究综述。基于不同的分类标准，首先讨论了主要的标准车辆路径问题扩展问题。在此基础上详细地综述了求解标准车辆路径问题的现代启发式算法，系统地描述了各种算法的实现机理以及各种算法的性能比较结果。综述了求解组合优化问题的现代启发式算法在给出组合优化问题和计算复杂性定义的基础上，综述了求解复杂组合优化问题的各种现代启发式算法。研究了开放式车辆路径问题通过松弛标准车辆路径问题中车辆路线为哈密尔顿巡回(Hamiltoniantour)的假设，研究了车辆路线为哈密尔顿路径(Hamiltonianpath)的开放式车辆路径问题。该问题中车辆在服务完最后一个顾客点后不需要回到车场，若要求回到车场，则必须沿原路返回。在首先给出问题数学模型的基础上，提出了求解开放式车辆路径问题的蚁群优化算法。该算法主体是一个在超立方框架下执行的侧只刃一侧工加尸蚂蚁系统，算法混合了禁忌搜索算法作为局部优化算法，同时集成了一个后优化过程来进一步优化最优解。基于基准测试问题，系统地研究了算法性能。同其它算法的性能比较结果表明本文提出的蚁群优化算法是有效的求解开放式车辆路径问题的方法。研究了带时间窗和带时间期限开放式车辆路径问题通过引入时间约束，研究了两类新的满足时效性要求的开放式车辆路径问题—带时间窗和带时间期限开放式车辆路径问题。首先构建了两类问题的数学模型，同时提出了求解两上海交通大学博十学位论文类问题的基于禁忌搜索的迭代局部搜索算法，该算法集成了不同的解接受标准以及一个基于阂值接受的后优化过程。基于随机产生的测试问题的实验结果表明:基于禁忌搜索的迭代局部搜索算法可以有效地求解带时间窗和带时间期限开放式车辆路径问题。研究了带时间窗和随机旅行时间车辆路径问题通过对标准车辆路径问题的拓展，引入新的边约束条件:时间窗、随机旅行时间和服务时间，研究了一类新的随机车辆路径问题—带时IbJ窗和随机旅行时间车辆路径问题。根据不同的优化标准，分别构建了问题的机会约束规划模型以及带修正随机规划模型。机会约束规划模型是在随机约束以一定的置信水平成立的条件下最小化运输费用。带修正的随机规划模型是一个两阶段优化问题，其确定第一阶段的路线集以最小化第二阶段(随机变量实现后)的期望运输费用。鉴于问题的随机特性，为了有效求解该问题提出了基于随机模拟的禁忌搜索算法。同时基于随机产生的测试问题通过实验检验了算法有效性。研究了固定车辆数异型车辆路径问题在车辆路径问题经典文献中，一般均假设车辆同质目‘车辆数无限。然而在实际运作中，车辆集一般是由具有不同属性(装载能力、固定成本以及单位公里可变费用 )的车辆组成，且受运作成本的约束车辆数一也是固定的。通过对车辆同质及车辆数无限的假设条件的放松，研究了固定车辆数的异型车辆路径问题。在首先给出问题数学模型的基础上，提出了求解该问题的多起点自适应记忆规划算法。基于文献中的基准测试问题，系统地研究了算法在不同多样化策略下的性能。同文献中其它算法的比较结果表明:提出的多起点自适应记忆规划算法是较好的求解固定车辆数异型车辆路径问题的算法，对于其中五个测试问题，算法发现了新的最优解。研究了车辆路径问题的应用问题以城市日常报品配送问题为例，进行了车辆路径问题的应用研究。基于报品配送的实际数据，运用本文研究的几类车辆路径问题的框架，研究了不同类型的最优报品配送车辆路径方案的制定问题。执行本文提出的优化算法，给出了不同类型的报品配送的最优车辆路径方案。通过实验验证了论文提出的车辆路径问题优化算法的有效性，实验结果表明论文提出的算法可以用于生产管理中最优车辆路线方案的制定。本文创新性研究成果及贡献主要包括以下几方面:松弛了标准VRP中车辆路线为哈密尔顿巡回的假设，研究了车辆路线为哈密尔一工工一顿路径的开放式车辆路径问题。构建了求解问题的蚁群优化算法，该算法是一个集成了后优化过程的在超立方框架下执行的侧只刃一侧工加尸蚂蚁系统。同文献中其它算法性能的比较结果证明本文提出的蚁群优化算法是有效的求解开放式车辆路径问题的方法，算法改进了文献中其它算法发现的最优解。引入时间约束，研究了两类新的满足时效性要求的车辆路径问题—带时间窗和带时间期限开放式车辆路径问题。提出了求解上述两类问题的迭代局部搜索算法，并基于随机产生的测试问系统研究了算法的求解性能。引入时间窗、随机旅行时间和服务时间约束，研究了带时间窗和随机旅行时间车辆路径问题。根据不同的优化标准，分别构建了问题的机会约束规划模型以及带修正随机规划模型。提出了基于随机模拟的禁忌搜索算法，基于随机机产生的测试问题的实验结果验证了算法的有效性。通过松弛标准VRP中车辆同质及