河北工业大学

硕士学位论文

基于风险分析的危险品运输路径优化方法研究

姓名：潘瑞民

申请学位级别：硕士

专业：企业管理

指导教师：康凯

20100501

河北工业大学硕士学位论文

基于风险分析的危险品运输路径优化方法研究

摘要

随着我国经济的快速发展，对危险品的需求量与日俱增，给人类健康和社会环境安全带来了极大的挑战。2009年，在国家良好政策支持下，销售汽车1364.5万辆，同比增长46.15％。机动车辆的增加，无疑加大了危险品在公路运输过程中的运输风险。危险品运输车辆一旦发生泄漏事故，可能造成不可挽回的灾难性损失。所以，采取科学的方法和手段来保证危险品的安全运输，能够有效的提升社会公共安全。

本文从危险品运输风险分析入手，概括总结了国内外危险品运输路径优化方法研究现状和发展趋势，分析了我国危险品运输事故发生的主要原因及影响我国危险品运输的主要风险因素。并在此基础上，将高斯烟羽模型成功的应用于危险品扩散范围上。充用考虑到了危险品发生泄漏事故时，风向及风速在短时间内对附近居民及环境带来的影响。

在路径优化方面，提出了将多目标优化方法转化为单目标的优化方法，在路径不算多的小型路网中，给出了精确的求解方法。在危险品运输路径优化方法的研究基础上，结合实际危险品运输情况，提出并建立了两种全新的模型，即多路径可选风险分散模型和多卸货点风险递减模型。在多路径可选风险分散模型中，将蚂蚁算法应用于路径优化过程中，在一般蚂蚁算法的基础上进行了适当的改进，通过对蚂蚁算法的参数控制，使其符合危险品运输伴随风险的特征。适用于路径及结点较多，危险品运输量较大的中大型路网中，并起到了风险分散的作用。在多卸货点风险递减模型中，充分考虑到了危险品运输车辆的实际承载量对运输风险带来的影响，结合实际运输中的多需求点危险品运输情况，提出了二次建模的思想，提升了算法精度的同时，也在一定程度上减轻了算法难度。

最后，以天津市红桥区为例，在高斯烟羽扩散模型的基础上引入了个人风险。在实际路网中，针对不同的运输情况，分别采用本文提及的三种模型，进行了实例研究。研究表明：将高斯烟羽扩散模型引入危险品运输的个人风险评估中是有效、符合现实情况的；多路径可选路径优化方法研究及多卸货点的路径优化研究，达到了风险分散的目标，具有一定的现实意义。可为危险品运输相关政府监管部门、危险品运输物流企业及相关研究机构提供理论支持。

关键词： 危险品 风险分析 路径优化 风险分散 运输路径

基于风险分析的危险品运输路径优化方法研究

OPTIMIZATION METHODS BASE ON RISK ANALYSIS IN HAZARDOUS MATERIALAS TRANSPORTATION

ABSTRACT With China's rapid economic development, increasing demand on the hazardous materials, a great challenge brought to environment, human health and the safety of the community. 2009, with the government support, the number of sales of automotive has reached 13,645,000, with an increase of 46.15%. Vehicle fleet, no doubt increased in the road transport of hazardous materials during transport risks. The vehicles in case of leakage accident, catastrophic loss may be irreversible. So, take the scientific method and means to ensure the safe transport of hazardous materials, can effectively upgrade the public safety. This paper start with the risk analysis for transport of hazardous materials, summed up the domestic and international transport of hazardous materials route optimization status and development trend of China in recent years occurred in the transport of hazardous materials incidents were analyzed in the transport of hazardous materials and the main reason for the accident affect transport of hazardous materials in China the main risk factors. And on this basis, the Gaussian plume model was successfully applied to the spread of hazardous materials. Fully take into account the leakage of hazardous materials accident, wind direction and speed in a short time to nearby residents and environmental impact.

In route optimization, the proposed multi-objective optimization methods into a single objective optimization method, in a network with few paths and less nodes, the method gives an accurate solution method. Based on the study of hazardous materials transport optimization method and actual conditions, the paper proposes and establishes two new models, which is multi-path model with alternative risk and decreasing the risk of multiple demand points model. ants algorithm is applied to the optional in the multi-path dispersion model, through the right ant algorithm parameter control, based on general ant algorithm is improved properly, to meet the characteristic of hazardous materials transportation. Applied to the path and junction more hazardous materials transport with a large amount in the larger network. Discharge point in the lot of the risk of decreasing model, fully taking into account the

河北工业大学硕士学位论文

actual transport of hazardous materials vehicles, the risk of carrying capacity on the impact of transport, combined with the actual needs of the transport situation in the multi-point transport of hazardous materials, made a second model of thinking improve the algorithm accuracy is also to some extent, reduce the difficulty of the algorithm. Finally, in Hongqiao District, Tianjin, with our university stay in, using the Gaussian plume diffusion model based on the introduction of personal risk. In the actual road network, for different transport conditions, respectively, the three models mentioned in this paper is to conduct a case study. The results show that: the Gaussian plume dispersion model transport of hazardous materials into individual risk assessment is valid, according to current situation; multi-path Optional path optimization methods and multi-path optimization of discharge point, the risk of discrete objectives achieved has some practical significance. For the transport of hazardous materials relevant government regulatory authorities, hazardous materials transport and logistics companies and research institutions to provide theoretical support.

KEY WORDS: Risk analysis, hazardous Materials, path optimization, risk diversification, transportation path

河北工业大学硕士学位论文

第一章 绪论

§1.1 研究背景及现实意义

危险品，通常又被人称为危险化学品(Hazardous Material)、危险货物(Dangerous Goods)、危险物质(Dangerous Substance)。在我国，一般对危险品的描述如下：易燃、易爆、有强烈的腐蚀性的物品的总称。如汽油、炸药、强酸、强碱、笨、萘、赛璐珞、过氧化物等。同时，在相关规定中，明确规定：危险品在运输和贮藏时，应按照危险品条例处理。

据美国运输部管道和危险材料安全管理局统计，截止到2008年3月，危险品的种类为3614种。美国运输部管道和危险材料安全管理局（US Department of Transportation Pipeline and Hazardous Materials Safety Administration）将符合以下任意条件的事故定为严重事故（Serious Incident），条件如下：由危险品泄露引起的严重事故或导致有人死亡或重伤的；由危险品事故造成的疏散人员达25人及以上的；由危险品事故造成的重要交通干线封闭的；由危险品事故造成飞行计划更改或更改飞行操作的；由危险品事故造成放射性物质泄漏的；由于危险品事故导致超过11.9加仑或88.2磅海洋污染物质泄漏的；根据具在的不同危险性危险物品分为九类，其中有些类别有分为若干项。分类如图1.1所示

危险品运输过程中，90%是由液化石油气、汽油、爆炸物质及其它危险化学物质组成的。据美国2002年商品流量调查显示，该年在美国全境的危险品运输量高达3118.97亿·吨·英里。其中，仅氨水的运输量便高达26.74亿·吨·英里[1][2]。

2007年，在美国旧金山，一辆载有8600加仑的氨水运输车在第580号州际公路上发生严重事故。大火的强度甚至给另一条880号州际公路带来的严重影响[3]。幸运的是，此次事故没有发生的人员密集的地区，否则后里不堪设想。

正是由于危险品具有高危险性，越来越多的国家，政府都对危险品运输的路径有明确的规定，包括路径的选择及行驶的时限。在危险品运输水平较高的美国，更是有专门的部门来管理这项工作，其中包括美国运输部和管道危险品安全管理局(Pipeline and Hazardous Materials Safety Administration)，联邦公路运输安全管理会(Federal Motor Carrier Safety Administration)。这些部门的工作的内容确保了危险品运输车辆最少的通过居民区，或是一旦发生意外后，对周围的环境和居民造成的伤害最小化[3,4-6]。

危险品的生产、使用、存储过程中都要涉及到运输问题。据统计，我国95%以上的危险品涉及异地运输问题，例如液氨的年流动量高达80多万吨，液氯的年流动量达170多万吨，其中是80%通过公路运输的[5]。危险品运输风险虽已被社会所认识，政府部门也对有害物品运输实施更严厉的监管，从而使得有害物品运输的事故率比一般物品运输的事故率要低。但是，低概率、高风险的有害物运输事故仍时有发生[5]。

究

研

法

方

化

优

径

路

输

运

品

险

危

的

析

分

险

风

于

基slaireta M 类su分od品raz险a危H fo1 .s1sal图C 1.1 erugiF

河北工业大学硕士学位论文

危险品运输的安全越受到各国政府、居民及相关研究人员的关注。在我国，已有部分城市规定危险品运输车辆必须加装GPS才能上路行驶。2008年奥运期间，为维护奥运会期间安全生产秩序，国家有关部门发布了开展化学危险品运输专项整治活动的要求，各地方交管、安检等部门也就各自情况做出了具体整治计划。对于人民生活必需，如停止运输危险物品，将影响国际声誉、国计民生的，由各市公安局从严掌握审批并备案，规定其行驶路线及行驶时间。

2009年9月2日下午，山东省临沂市兰山区金兰物流城F3区发生一起由装载化学物品的货车在卸车过程中引发的意外爆燃事故，共造成18人死亡，10人受伤。事故发生后，临沂公安消防部门立即调集26部消防车、91名消防官兵赶赴现场实施救援。临沂市委、市政府领导高度重视，立即组织公安、安监、环 保、卫生等部门进行救援。

危险品运输是一个国家经济活动的一部分，在美国，危险品的年运输量已经超过20亿吨[7]。在1997到2002年间，美国运输货物总量以超过20%的速率增长，其中通过公路运输的更是以52.9%的速率高速增长[3]。在危险品事故中，有89%是在公路运输中发生的，总共造成损失约3100万美圆（平均每次事故造成损失8万美圆）[8]。尽管各国在危险品运输方面制定相关法律法规，使危险品运输发生事故停留在个相当小的概率内（10-8-10-6/车·公里），但危险品运输事故给国家、公共当局、托运人、承运人、当地社会和社会群体带来的一系列潜在的、持续的问题却是无法估量的。

在相关危险品安全的研究中，如何合理的安排危险品运输路线，成为国内外学者越来越关注的问题。危险品运输路径优化方法研究，被认为是减轻危险运输风险的关键[9]。在一般物流活动中，一个合理的路径优化方法，能够降低运输费用，减小运输时间，提高客户满意度，提升企业品牌形象，建立企业忠实用户等。在危险品物流中，一个合理的路径优化方法，能够降低运送危险品的事故概率，避免因危险品事故而发生的严重后果，提高事故紧急救援的响应速度，从而降低危险品运输的风险值。

2002年到2004年，国内12个主要城市发生的435起非爆炸品类危险化学品事故，各阶段发生危险品事故的比例如图1.2所示。

基于风险分析的危险品运输路径优化方法研究

图1.2 不同生命阶段的危险品事故比例表

Figure 1.2 Dangerous goods proportion table of different life stages

§1.2 本文的主要研究内容.

危险品运输路径优化方法研究，主要是对危险品的运输路径进行规划，以期使危险品在运输过程对社会及环境造成最小影响。风险分析贯穿于整个路径优化过程之中，考虑多种或单种风险对路径优化的影响，如人口分布因素、路况信息因素、气象因素、路段历史事故率因素等。在本文中，危险品运输路径优化过程中，只限于公路运输部分，不涉及到水路运输、空运，铁路运输和其它运输方式；在对运送的危险品进行研究时，仅限于对常见的危险品的研究，如成品油、氨水、液化天然气及其它在工农业生产中涉及到有毒液体、强腐蚀性液体等，不涉及到具有放射性特点的放射性核材料及不常见危险品运输；在进行危险品路径选择时，仅限于城市内部路网，而不涉及到城市间路网危险品运输路径选择的研究。本文的最终结果为政府或企业决策者提供一个路径选择方案，近而可以有效的避免或减少危险品运输给社会或周边环境带来的伤害。在决策过程中，可能考虑应急方案对路径选择造成的影响，但并不是提供一种应急的解决方案。其主要研究内容如下：

1. 收集国内外危险品运输路径优化研究资料，对国内外危险品运输路径优化问题进行综述。综述内容主要涉及到风险评估及路径选择两个方面。

2. 对危险品运输进行风险分析。分析各个风险因素给危险品运输带来的影响，依本文研究情况，建立本文研究中采用的风险评估模型。

3. 针对不同的运输情况，建立危险品运输模型。

4. 进行实例研究

河北工业大学硕士学位论文

§1.3 本文研究的技术路线

本文从危险品运输的风险分析入手，通过对国内外危险品运输危险评估研究，结合我国危险品运输实际情况，提出适合本文的风险评估模型。并结合一般货物的路径优化方法研究，对普通货运输建模方法、应用算法进行系统学习。结合危险品运输高风险的特点，在一般货物运输的优化方法的研究基础上，提出适用于危险品运输的路径优化方法。最后，结合实际路网，对本文中提出的路径优化方法进行了论证。技术路线图如图1.3所示：

从图1.3中不难看出，本文的研究思路是通过对相关领域知识的研究，结合本文所研实际情况，提出适合于本文的风险评估模型。在结合危险品种类繁杂的特点，总结出一种通用的优化模型，提出两种全新的适用于一定条件下路径优化模型。最后，依实际路网，在模拟真实运输情况的条件下，对三个模型进行了验证。

基于风险分析的危险品运输路径优化方法研究

图1.3 技术路线图

Figure 1.3 Technology Roadmap

§1.4 本文的主要创新点

1. 充分考虑风向对危险品运输路径优化研究中的影响，提出将高斯烟羽风险模型应

用于危险品运输危险评价方法中。

2.

3.

4. 在危险品运输的多目标路径研究中，提出了风险分散原则。 提出将蚂蚁算法应用于危险品运输路径选择中。 提出多卸载点危险品运输模型，并给出求解算法。

河北工业大学硕士学位论文

第二章 文献综述

近年来，随着各国对危险品运输安全的关注的增加，各个危险品运输企业已经将运输安全摆在了首位，取得了实质的进展。危险品运输事故占危险品运输次数的比例也越来越小，但由于危险品的特殊物理性质，危险品运输一旦发生事故，其造成的后果仍远超出一般性交通事故给我们带来的影响。所以，在危险品运输过程中，除要加强安全管理外，还要在将科学的方法运用到上面来。以期得到使危险品运输事故率最小化。且一旦发生事故，使其损失最小化。在减小危险品运输风险方面，已有很多成形的方法，比如加强司机的安全意识，对司机进行技能培训等。但在实际操作中，却显的不尽人意。追其原因，正是由于我国经济发展的速度与我国国民整体文化水平及整体素质的发展速度不相谐调造成的。鉴于此，很多学者将危险品运输安全的研究重点放在运筹学上，希望以科学的方法来解决危险品运输的实际安全问题。

§2.1 危险品运输风险分析的文献综述

运输过程中伴随较大风险是危险品货物运输与普通货物运输的最大区别[10]。在危险品运输过程中，风险不但衡量了危险品运输可能发生运输事故的概率，而且还代表了事故潜在造成伤害的严重程度[11]。在运输过程中发生事故如果处理不当，会对周围人员造成健康威胁及对周围环境带来污染。对运输风险的分析、评估并建立恰当的模型是进行危险品运输路径优化的前提，并起着至关重要的作用。所以，与研究一般交通事故不同，研究危险品运输事故的同时，必然要对危险品运输事故带来的其它相关风险进行研究，在危险运输风险研究中，由于其风险的不可预见性，使对危险品运输的风险分析与评估成为危险品运输路径优化研究的核心问题。

综上，危险品运输风险评估的重点在于概率的分析与评估，在评估危险品运输发生事故概率、事故泄漏概率、发生重大突发性事件概率上，主要有两种方法：一种是基于历史事故频率的分析，另一种是逻辑图法。

对现有的文献进行研究，不难发现，危险品运输风险是危险品在运输过程中发生事故的可能性，及危险品事故对人及周围环境造成的潜在伤害的衡量值。

危险品运输与普通货物运输相比较，最大的区别是危险品运输涉及到运输风险。这种风险涉及人、环境或是周围的其它物体。危险品运输发生事故，可能导致较严重的后果，比如说死亡、重伤、持续性的放射性影响等，环境影响（石油的泄漏对海洋生物的生存产生影响）、附近的人口被迫在眉睫疏散、或是道路封闭。

基于风险分析的危险品运输路径优化方法研究

风险评估是可以定性或是定量的。定性的风险评估涉及可能的意外情况有对不良后果进行的鉴定。这种方法通常用于必要的历史数据或是资料相对缺乏的情况。定性的风险评估目标的通过分析找到最容易发生问题的事件，然后对这些事件进行进一步的分析。虽然这种方法有很多弊端，但可能是现行方法中找到的最好的方法了。

在研究危险品运输路径优化的问题时，必然要考虑危险品运输事故对客户、都必然涉及到危险品运输风险的评估。Erkut在假设危险品运输路径风险值不变的情况下，提出了三个公理[11][12]，这三个公理在危险品运输风险模型研究中被越来越多的学者所引用。即：

公理1(单调性公理)：如果路径r'包含路径r'',则v(r'') v(r')。

公理2(选线最优公理)：

v(r') minv(r) v(r'') minv(r) r r'r r''

公理3（属性单调性公理）：设v(r) f(u1(r),..,uk(r)),其中k为风险评价的属性数量（例：只考虑传统风险和事故率风险，则k 2），有f(u1(r),..,uk(r)) f(u1(r) h1,..,uk(r) hk)。

按问题焦点不同，Erkut和Ingolfsson将风险分析模型分为9种主要类型，并且对这9种主要风险模型是否符合风险分析的三个公理进行了验证。见表2-1。

表2-1风险评价模型

Table 2-1 Risk Assessment Model

是否符

合三个

公理

YYY 模型名称 方法 参考样本 传统风险模

型

人口覆盖率

模型

事故率模型

可感知风险

模型

条件风险模

型

最大人口覆

盖率模型

负效应预期

模型

均方差模型 ni 1pici Batta and Chiu, 1988; US DOT, 1994; Alp, 1995; Zhang et al., 2000 Batta and Chiu, 1988; ReVelle et al., 1991 Saccomanno and Chan, 1985; Abkowitz et al., 1992 Abkowitz et al., 1992 Sivakumar et al. 1993,1995; Sherali et al., 1997 Erkut and Ingolfsson,2000 Erkut and Ingolfsson,2000 Sivakumar and Batta,1994;

Erkut and Ingolfsson,2000 ni 1ini 1ni 1ni 1c pi pici , 0 pici/ in 1pi NA NA NA YYY YYY NNN NANANA YYY YYY maxei pci ni 1ni 1pi(exp( ci) 1), 0 (pici pici2)4, 0

河北工业大学硕士学位论文

需求满意度

模型

ni 1(1 exp( pi))ci j iexp(pnErkut and Ingolfsson,2005 NANANA

在一个既定网络中，许多学者给出了不同的方法对该网络进行风险评估。事实上，危险品一旦发生事故严重，便会有很短的时间内造成较大的影响，在多数情况下，其具体的风险很难进行评估。美国公路科学研究所为了使危险品运输车辆在运输过程中远离人口密集地区，颁布了许多法津法规。Harwood等学者，在对危险品运输进行风险评估的过程中，为了加大风险评估的准确性，建立了危险品运输事故模型和泄漏模型，在风险评估过程中引入了较多的因素，其中包含公路类型、周边环境、路况、公路设计通行能力和发生事故的历史数据等[13]。

Garrido and Bronfman在对危险品运输进行风险评估时，提出以危险品的影响半径及影响半径内的人口密度相结合的方法[14]。Kara致力于建立一个准确的风险评估模型，并提出一旦危险品事故发生地接近两条线路的交叉点，那么风险应该相对计算两次，因为事故一旦发生在两条路线的交叉点，则将对两个路线上的居民都产生影响[15]。在本文中，对危险评估也不是准确的结果，而对是将要发生危险事故的一种预测。

尽管各个学者在进行危险品运输优化的研究过程中，所用的方法不同，但进行路径优化时，一般都会用到危险品事故造成的损失、行驶时间和路段事故概率三个因素。当然，由于研究的重点不同，较多的学者也引入了其它影响到危险品运输风险的因素。Frank等用启发式算法减少了危险品运径一定半径范围内的人口密度，并成功的开发出可视程序，直接将优化的路径显示在现实路网中[16]。Carotenutoa等使用平均路线风险的方法，对路径进行了优化。该方法更多的考虑的路径整体上带来的风险，相对某些特殊的点考虑较少。算法在进行路径优化的过程中，考虑的因素只有路径的历史事故率。Nembhard和White提出了一种无序保存的路径优化方法，虽然计算出的路径可以接受，但可能不是最佳路径[17]。Erkut和Ingolfsson提出了三个避免危险品灾难性事件发生的模型，该模型减少危险品运输事故对居民带来的伤害，且减小了危险品事故总体危害的方差[18]。同时，在考虑危险品事故可能发生路网的任一地点的可能性的前提下，Erkut和Ingolfsson又建立的新的路线选择模型，但是并没有考虑事故给整个路网带来的影响[19]。Huang和Fery强调在进行路径选择时，必须对运输距离、运输成本和路线周围的人口暴露密度进行权衡[20]。Erkut和Alp对一天中的不同时间的事故率、人口暴露密度和行驶时间进行调查分析汇总，建立了随时间分布的风险函数，依据该分布函数对运输路径进了优化研究[19]。

§2.2 危险品运输路径优化问题的文献综述

车辆调度问题(Vehicle Scheduling Problem,简称VSP)是Dantzig和Ramser于1959年首次提出的。车辆调度问题引入我国已有30多年。从已有的文献中不难看出，大部分学者将VRP（Vehicle Routing Problem 车辆路由问题/路线优化问题）直接翻译为车辆调度。也有学者将

基于风险分析的危险品运输路径优化方法研究

只考虑空间路线安排的问题的翻译为VRP，将考虑时间要求(时间窗)的VRP（VRPTW Vehicle Routing Problem with Time Windows）问题称为VSP（Vehicle Scheduling Problem）。

肖峰在邮政车辆调度问题研究中，将车辆调度问题分为两类：即车辆空间线路的安排问题(vehicle Routing Problem，简记VRP)，以及考虑时间要求的车辆调度问题(Vehicle

Scheduling Problem，简记VSP)。并对车辆调度问题进行定义：组织的行车路线，能否使车辆在满足一定的约束条件(如需求量、发送量、车载容量限制、行程限制、时间限制等)下，有序地通过一系列供应点或需求点，达到诸如路程最短、费用最小，耗费时间尽量少等。从而车辆调度问题可表述为由一个中心向具有确定位置的顾客提供服务，而中心的车辆又有容量和最大行程的限制，求满足顾客需求且行程最短或费用最小的派车方案[20]。

安立定在遗传算法在物流配送车辆优化调度中的研究及应用中指出：国外将物流配送车辆优化调度问题归纳为或称之为Vehicle Routing Problem和Vehicle Scheduling Problem。当不考虑时间要求，仅根据空间位置安排线路时称为车辆线路安排问题(Vehicle Routing Problem, VRP)；考虑时间要求安排线路时称为车辆调度问题(Vehicle Scheduling Problem，VSP)；同时考虑空间位置和时间要求时称为Routing和Scheduling混合问题(Vehicle Routing and

Scheduling Problem，简记VRP&VSP)。对于VRP与VSP，也有不区分两者的，如有具体约束则加上定语，如将有时间要求的车辆调度问题称为Vehicle Routing Problem，with Time Windows[20]。即Scheduling比Routing的范围要广。

潘祖金在一个货运车辆优化调度模型及其应用研究中指出：总体上看，车辆的优化调度问题一般可根据时间特性和空间特性分为车辆路径规划问题和车辆调度问题。当不考虑时间要求，仅根据空间位置安排车辆的线路时称为车辆路径规划问题（VRP-Vehicle Routing Problem）；考虑时间要求安排运输线路时称为车辆调度问题VSP（Vehicle Scheduling

Problem）。某些学者将有时间要求的车辆调度问题称为Vehicle Routing Problem with Time Windows。在求解方法上，由于VSP问题是NP（Nondeterministic Polynomial）难题，即为非确定型的多项式算法，高效的精确算法存在的可能性不太（除非P=NP，即N=1），所以寻找近似算法是必要和现实的[21]。针对上述情况，潘祖金主要对启发式算法进行研究。

孙学农在遗传算法在非满载车辆调度中的应用研究中对各种算法进行了优缺点描述

[22]：

表2-2 VRPTW(VSP)求解方法的优缺点

Table2-2 Advantages and disadvantages of method VRPTW(VSP) 算法

系统仿真法 优点 可直接观察系统的效率与效

果 缺点 可能无法满足实际多变的配送环境

1.相关的专门知识不易获得

并整合

2.决策时间较长，虽然效果

不错，但效率较差可 人机互动法可适时地结合专家的意见 2.寻优的过程中，使用者可以很清楚地看到各限制条件之间的替代关系，以及参数变化

河北工业大学硕士学位论文

可能导致的成本变化

精确解法

启发式算法 求得最优解 解题时可减少搜寻的次数可

快速的求解困难的问题

表2-3 各种算法的对比

Table 2-3 Comparison of various algorithms 求解方法

精确解法

系统仿真

法

启发式方

法

人机互动

法 解精度 精确解 较优解 近优解 满意解 收敛速度 慢 慢 较快 快 程序实现 较难 难 易 易 适用问题 简单、确定型 复杂、不确定型 较复杂、确定型 较复杂、确定型 1受计算机内存容量的限制2.求解效率差 无法确保求得最优，可能为较优的可行解 并对各种算法进行了对比：

孙学农在遗传算法的基础上，提出采用二进制编码，几乎可以对任何问题进行编码，并且遗传算子不包含关于搜索区域的任何知道。缩小了遗传算法在车辆调度问题上的局限性。

张之富在物流配送车辆优化调度研究中指出车辆调度为Vehicle Routing Problem（简称VRP）。对组合优化的经典问题即旅行商问题（TSP Traveling Salesman Problem）进行描述。指出TSP和VRP的相关研究成果对于车辆调度问题具有重要的参考和借鉴作用。提出了合理化运输车辆调度的“五要素”即：运输距离、运输环节、运输工具、运输时间和运输费用。

徒君在蚁群算法在物流配送车辆调度中的应用研究中将VRP的方法分为五类[23]。 a.先安排线路后分组的方法

这种方法首先构造一条或几条很长的线路（通常不可行），它包括了所有需求对象，然后再把这些很长的线路划分为一些短而可行的线路。具体进行时，一般是先解一个经过所有点的旅行商问题，形成一条线路，然后根据一定的约束（如车辆容量等）对它进行分化。

b.先分组后安排线路的方法

这种方法先把节点和（或）弧的需求进行分组或划群，然后对每一组设计一条经济的线路。其目的在于形成需求点的径向区域，从车场发出的射线“扫过”这个区域，使不超过车辆容量的需求点组成一个区域，一个区域就是一个组，当形成一系列这样的组后，再对每一组的各点安排线路。

c.节约/插入算法

根据一定的准则（如节约准则），把不同线路上的点插入线路，直到所有点都被安排进线路。

d.改进/交换法

在初始保持解可行的情况下，力图向最优目标靠近，每一步都产生另一个可行解以替代原来的解，使目标函数得以改进，一直继续到不能再改进为止。