（计算机软件与理论专业论文）基于禁忌搜索的复杂情况下的车辆路线问题.pdf

中山大学硕士学位论文基于禁忌搜索的复杂情况下的车辆路线问履 基于禁忌搜索的复杂情况下的车辆路线问题 专业：计算机软件与理论 硕士生：杨永良 指导老师：郭嵩山教授 摘要 随着社会经济的不断发展，作为“第三利润源”的物流越来越引起人们的关 注。当前的物流业正向全球化、信息化和一体化发展，配送在供应链中的作用显 得更加重要其中车辆路线问题( v e h i c l er o u t i n gp r o b l e m ，v r f ) 是物流中关键 的一环，对其进行优化调度，可以提高物流经济效益。 本文研究的问题是有时间窗和车辆数限制的多车场开放式车辆路线问题 ( m = m d o v r v r w ) ，该问题是带时间窗的车辆路线问题( v r p t w ) 、多车场车 辆路线问题( m d u ) 和开放式车辆路线问题( 0 i v r p ) 的一个混合问题，限 制条件较多，具有一定的复杂性。本文首先介绍了v r f 问题目前国内外的研究 现状；然后分析m - m d o v r p t w 问题的特点和优化的目标，并建立了相应的数 学模型；接着根据问题的实际特征，采用改进的禁忌搜索算法( t a b us e a r c h a l g o r i t h m ，t s ) 进行求解，有针对性地设计了混合时间窗模型和相应的惩罚函 数、三种基于贪一1 5 算法的初始解求解方法、四种邻域变换结构、候选解变异方法、 动态禁忌长度、双禁忌表等参数，使得算法具有可操作性；最后在s o l o m o n 标准 测试数据的基础上重构了实验原始数据，并进行了大量的实验，对改进后的 i s 算法进行验证。实验结果表明，本文设计的算法初步解决了m - m d o v r i r r w 问 题。 表 关键词：车辆路线问题，禁忌搜索，多初始解选优，动态禁忌长度，双禁忌 中山大学硕士学位论文 基于禁忌搜索的复杂情况下的车辆路线闻愿 v e h i c l e r o u t i n g p r o b l e mi nc o m p l e xc o n d i t i o n b a s e do nt a b us e a r c h m a j o r c o m p u t e rs o f t w a r ea n dt h e o r y n a m e ：y a n gy o n g i i a n g s u p e r v i s o r p r o f g u os o n g s h a n a b s t r a c t w i t ht h ed e v e l o p m e n to fe c o n o m i c sa n ds o c i e t y , l o g i s t i c sa s t h et h i r di m p o r t a n t s o u r c eo f p r o f i t h a sa t t r a c t e dm o r ea n dm o l ea t t e n t i o n a tp r e s e n t , t h ei n d u m to f l o g i s t i c si sd e v e l o p i n gt o w a r d sg l o b a l i z a t i o n , i n f o r m a t i z a t i n na n di n t e g r a t i o n , a n d l o g i s t i c sd i s t r i b u t i o np l a y san l o i m p o r t a n tr o l ei ns u p p l yc h a i n t h ev e h i c l er o u t i n g p r o b l e m ( v r p ) i sak e yp a r to fl o g i s t i c sd i s t r i b u t i o n , a n do p t i m i z i n gt h ev e h i c l e m u t i n gc a nb r i n gm o r ep r o f i t st o t h ee n t e r p r i s e i nt h i sp a p e r w ef o c u so nt h eo p e nv e h i c l er o u t i n gp r o b l e mw i t hm u l f i o e d e p o t s ，t u n ew i n d o w sa n dl i m i t e dn u m b e ro fv e h i c l e ( m - m d o v i r w ) ，w h i c h c o m p r i s e st h ev e h i c l er o u t i n gp r o b l e m 、砘t ht i m ew i n d o w s ( v m t w ) t h ev e h i c l e r o u t i n gp r o b l e mw i t hm u l t i p l ed e p o t s ( m d a n dt h eo p e nv e h i c l er o u t i n g p r o b l e m ( o 冲) i th a sq u i t em a n y c o n s w a i n sa n di si nc o m p l e xc o n d i t i o ns ot h a ti s h a r dt os o l v e w ef i r s ti n t r o d u c et h ec u r r e n td o m e s t i ce n df o r e i g nr e s e a r c ho nv r pi n d e t a i l t h e nw ea n a l y z et h ec h a r a c t e r i s t i c so fm - m d o v r v i n v , a n db u i l da c o r r e s p o n d i n gf o r m a lm o d e l h e r et h ei m p r o v e dt a b us e a r c hf r s ) a l g o r i t h mi s a d o p t e dt os o l v em - m d o v r f t w a c c o r d i n gt ot h ec o l m t r a i r k w ed e s i g nt h ek e y e l e m e n t ss u c ha sm i x e dl i m ew i n d o w sa n di t sp u n i s h m e n tf u n c t i o n , t h r e ea p p r o a c h e s b a s e do ng r e e d ya l g o r i t h mw h i c h 黜t og e ti n i t i a ls o l u t i o n s , f o u rn e i g h b o r - t r a n s f o r m s t r u c t u r e s ，a b e l t a n c eo f t h ec a n d i d a t es o l u t i o n s ，d y n a m i ct a b ut e n u r e , d o u b l et a b ul i s t s ， t om a k et h ei m p r o v e dt sf e a s i b l et os o l v et h ep r o b l e m f i n a l l y , w er e - c o n s t r u c tt h e t e s t i n gd a t es e tb a s e do ns o l o m o n sb e n c h m a r kp r o b l e m s ，a n dd oag r e a tm a n y e x p e r i m e n t st ov a l i d a t et h ei m p r o v e dt s t h ef i n a lr e s u l ts h o w st h a tt h ei m p r o v e d n 中山大学硬士学位论文 基于禁忌搜索的复杂情况下的车辆路线问题 a l g o r i t h mc a na c t u a l l ys o l v et h ep r o b l e m k e yw o r d s ：v e h i c l er o u t i n gp r o b l e m ( v r p ) ，t a b us e a r c h ( t s ) a l g o r i t h m , m u l t i p l ei n i t i a ls o l u t i o n s ，d y n a m i ct a b ut e n u r e ，d o u b l et a b ul i s t s 1 1 1 中山大学硕士学位论文 第1 章绪论 1 1 研究背景 第1 章绪论 随着社会经济的不断发展，物流越来越引起人们的关注，并面l 临着前所未有 的发展机遇。在现代社会经济中，物流支出费用占生产成本的比重越来越大。现 代物流作为一种先进的组织方式和管理技术，是企业降低成本、提高效益的重要 源泉，在经济和社会发展中发挥着重要的作用。 良好的物流管理可以大大降低企业的成本。早在上个世纪六十年代，彼得啦 拉克就以惊人的睿智预言：物流领域是经济增长的“黑暗大陆”，是降低成本的 “最后边界”，是继“降低资源消耗”和“提高劳动生产率”之后的“第三利润 源泉”。据估算，物流成本可以占到商品总价值的3 0 5 0 ，而物流业可以大 大降低来自该部分的成本。如日本在近2 0 年内，物流业每增长2 6 个百分点， 经济总量就增加1 ；在美国，物流产业的规模已超过9 0 0 0 亿美元，几乎是高新 技术产业的两倍。旱在1 9 9 9 年，美国前2 0 名的第三方物流服务商净收入达9 3 4 亿美元；而在我国，深圳市已经将物流业确定为高科技产业和金融之外的第三个 支柱产业【”。 据中国物流与采购联合会、中国物流信息中心的统计【2 l ；2 0 0 7 年第一季度， 我国物流运行继续保持较快增长，物流需求规模进一步扩大，物流费用增长速度 有所加快，配送、加工、包装等现代物流业务增势突出；全国社会物流总额为 1 5 6 ，0 0 0 亿元，同比增长2 3 8 ；社会经济发展对现代物流业的需求继续增大， g d p 与物流总额相比的物流需求系数由去年同期的2 8 提高到今年一季度的3 1 ， 即我国每单位g d p 产出需要3 1 个单位的物流总额来支持。 1 2 研究意义 当前的物流业正向全球化、信息化和一体化发展，配送在供应链中的作用显 得更加重要。其中车辆路线问题( v e h i c l er o u t i n gp r o b l e m ，v r p ) 是物流中关键 中山大学硕学位论文 第1 章绪论 的一环，对其进行优化调度，可以提高物流经济效益。v r p 问题于1 9 5 9 年由 d a n t z i g 和r a m s e r 提出后【3 1 ，很快便引起运筹学、应用数学、组合数学、图论与 网络分析、物流科学、计算机应用等学科的专家以及运输计划制定者的极大重视， 并一直是运筹学与组合优化领域的前沿与热点问题。在现实生产和生活中，邮政 投递问题、车船调度问题、电力调度问题、管道铺设问题、计算机网络拓扑设计 问题等都可以抽象为v r p 问题。可见，研究v i i i 问题具有重要的现实意义【4 】。 另一方面，v r p 问题已经被证明是n p h a r d 问题，即求解该类问题不存在一 个多项式时间的算法。对其进行求解，就是要在合理的时间内得到一个尽可能优 的解，这样就必须充分利用问题本身的限制来改进所使用的算法。现实中v r p 问题的限制条件可能很复杂，造成v r p 问题的分支非常多，其中某一分支的研 究成果可对其他分支的解决提供借鉴，促进各个分支的共同发展。因此问题的研 究同样具有理论意义和学术价值。 1 3 国内外研究现状 上个世纪五十年代末期，d a n t z i g 和r a m s e r 提出了v r p 问题1 3 】，并给出了 相应的数学模型及求解算法。此后，各国学者对其理论和应用进行大量的研究工 作，取得了数以千计的研究成果，使v r p 研究成为“最近十年运筹学领域最成 功的研究之一”。目前，关于v r p 问题的研究已经取得了大量成果，不同学者提 出了许多不同类型的v r p 分支和相应的模型，以及各种有效的算法。国外对v r p 问题作了大量深入的研究，该领域的代表人物有b o d i n 、c h r i s t o f i d e s 、g o l d e n 、 a s s a d 、b a l l 、l a p o r t e 、r i n n o o yk a n 、d e s r o s i e r s 和d e s r o c h e r s 等人【5 1 。 1 9 9 5 年，f i s h e r t 6 懈v r p 问题的研究分成三个阶段【7 l o 第一阶段是从1 9 6 0 年 到1 9 7 0 年，属于简单启发式方法，包括有各种局部改善启发式算法和贪心算法 ( g r e e d ya l g o r i t h m ) 等，这一阶段处理的客户规模比较小，可移植性较差；第 二阶段是从1 9 7 0 年到1 9 8 0 年，属于以数学规划为主的启发式方法，包括指派法、 集合分割法和集合涵盖法等；第三阶段是从1 9 9 0 开始至今，属于较新的方法， 包括利用亚启发式方法、人工智能方法等，能解决规模比较大的v r p 问题。 在综述性文章方面，早在1 9 8 3 年，b o d i n 、g o l d e i l 【8 】等人在他们的文章里就 列举了有关v r p 研究的7 0 0 余篇文献；2 0 0 2 年，p a o l ot o t h 和d a n i e l ev i g o 9 】全 中山大学硕士学位论文第l 章绪论 面分析了v r p 问题的最新研究进展和发展趋势 在v r f r w 问题上，1 9 8 7 年s o l o 咖【1 0 l 最早将用于求解简单v r p 问题的路 径构造启发式算法扩展应用于v r f i w 问题的求解中，他的研究结果表明这些启 发式方法求解v r p t w 问题的复杂度为o ( n ) ，其中n 为待服务客户的数目，即 可在多项式时间内得到问题的近似最优解，这说明了启发式方法求解v r f f w 问 题的可行性和有效性s o l o m o n 的研究为以后启发式方法在带约束的v r p 问题 中的应用奠定了理论基础1 9 8 8 年，i ) e s r o c h e r s t ”】进一步对用于求解带时间窗的 v r p 问题的各种优化方法做了简明的总结概括上个世纪九十年代以后，v r p t w 问题吸引了运筹学、人工智能领域学者更多的关注，许多学者对其进行了深入的 研究，出现了其他一些用于构建生成v r p t w 解的启发式方法，如p o t v i n 的并行 插入法f 翊，k o s k o s i d i s 的一般分配法【1 3 1 等 相比较，国内对v r p 问题的研究就较少，目前还处于起步阶段。李军、郭 耀煌、杭省策阁f 1 4 】等人在处理多车场问题上，先设立一个虚拟车场，把多车场 v r p 化为单车场v r p ，在此基础上用优化单车场v r p 的方法进行处理；钟石泉 和贺国光n 5 】【1 6 1 提出了有时间窗约束车辆调度优化的一种禁忌算法，运用了多初 始解和全局禁忌表等各种措施，来减小解的不稳定性和扩大搜索范围，并结合惩 罚函数和各约束的性质来联合控制车场的分配：李志业等在第1 7 届i e a a i e 2 0 0 4 上提出了用改进的g r a s p ( g r e e d y r a n d o m i z e d a d a p t i v e s e a r c h p r o c e d u r e ) 算法 和禁忌搜索算法，来求解带时间窗的v r p 问题【1 7 】；随后李志业又进一步用改进 的禁忌搜索算法，来求解有车辆数限制的开放式v r i 问趔埘。尽管近年来我国 理论界逐渐开始关注v r p 问题的研究，并己取得了较为显著的成果，但总体来 说我国目前对v r p 问题的理论研究仍相对匾乏，有待进一步的研究。 总的来说，通过世界各个国家的众多研究人员的共同努力，经过几十年的发 展，v r p 问题的研究已经取得了大量成果，提出了许多不同类型的v r p 的分支 以及相应的模型和各种有效的算法。 1 4 主要研究内容 本文研究的问题是v r p 问题的一个分支有时间窗和车辆数限制的多车 场开放式车辆路线问题( o p e nv e h i c l er o u t i n gp r o b l e mw i t hm u l t i p l ed e p o t s ， 中山大学硕士学位论文第1 章绪论 t i m ew i n d o w sa n dl i m i t e dn u m b e ro f v e h i c l e ，m - m d o v r p t w ) 。该问题是带时 间窗的车辆路线问题( v e h i c l er o u t i n gp r o b l e mw i t ht i m ew i n d o w s ，v r p t w ) 、 多车场车辆路线问题( v e h i c l er o u t i n gp r o b l e mw i t hm u l t i p l ed e p o t s ，m d v r p ) 和开放式车辆路线问题( o p e nv e h i c l er o u t i n gp r o b l e m ，o v r p ) 的一个混合问 题，限制条件较多，属于复杂情况下的v r p 问题，具有一定的复杂性。 本论文的结构安排如下： 第l 章，绪论：简要介绍了本文的研究背景、研究意义、以及目前国内外 v r p 问题的研究现状； 第2 章，v r p 概述：描述了一般的v r p 问题，详细介绍了v r p 的构成要素、 分类和各种经典的求解算法； 第3 章，t s 概述：介绍了t s 的基本概念、基本思想和算法的基本流程，详 细分析了t s 算法的关键参数及其操作，并简单总结了t s 算法的优缺点； 第4 章，求解m m d o v r p t w ：这是本文的核心内容，也是研究的重点；首 先描述了m m d o v r p t w 问题，并针对问题的特点建立了相应的数学模型；然 后用改进的t s 算法对问题进行求解，其中采用的主要技术包括具有较强适应性 的混合时间窗模型和相应的惩罚函数、在标准测试数据的基础上重构实验原始数 据、三种基于贪心算法的初始解求解方法、四种邻域变换结构、引入遗传算法中 的变异思想、动态禁忌长度、以及双禁忌表等； 第5 章，实验结果及分析：在大量的实验的基础上，采用重构的测试数据对 上一章所设计的算法进行验证，用表格列出实验结果，并对其进行分析； 第6 章，总结和展望：对本文所作的研究工作进行总结，并指出进一步的研 究方向。 4 中山大学硕士学位论文第2 章v r p 概述 2 1 问题描述 第2 章v r p 概述 车辆路线问题( v e h i c l er o u t i n gp r o b l e m ，v r f ) 最早由d a n t z i g 和黜m s 口 于1 9 5 9 年提出【3 】，是一类重要的组合优化问题，其应用背景在物流领域处处可 见，如零售业的门店配送、车船调度、管道铺设、邮政快递行业的快件投取等 对于从事这些业务的企业来说，合理安排车辆路线是企业面临的最基本的管理运 作问题。对车辆路线进行优化调度，可以提高企业的经济效益 v r p 问题的一般描述如下：对一系列给定的客户点( 送货点或取货点) ，设 计适当的车辆行驶路线，使车辆从车场( 配送中心) 出发，有序地服务各个客户 点，最后回到( 或者不回到) 车场( 配送中心) ，在满足一定的约束条件( 货物 需求量或发送量、车辆载重量、交发货时间、行驶里程限制、时间窗限制等) 下， 达到一定的目标( 运输费用最少、车辆数尽量少、车辆装载率尽量高、车辆行驶 时间最短、车辆行驶里程最短等) 。如下图2 1 所示。 图2 1 车辆路线问题示意图 从图论的角度来看，冲问题可以这样描述：设g = ( 矿，彳) 是无向完全图， 其中矿= “，v 2 ，v , v ，y + i ，v , v + m ) 为顶点( 车场和客户) 的集合，v j ，v , v 5 中山大学硕l 学位论文 第2 章v r p 概述 为待服务的客户点，+ l ，v u + 吖为车场( 配送中心) ；连接两个顶点的线段的 集合，即边( 路线) 的集合则用a = ( 砖，v ，) i 咋，y ，v ，l s i , j ，f j ) 表示； 此外，在a 上可以定义一个非负的距离矩阵或成本矩阵c = c o ，其中为从 顶点( 客户) i 到顶点( 客户) 的距离或成本。 根据v r p 问题空间特性和时间特性的相对重要性，通常将其划分为两类： 不考虑时间要求，仅根据空间位置安排车辆路线，称为车辆路线问题( v e h i c l e r o u t i n gp r o b l e m ， ) ；安排车辆路线时考虑时间要求的，则称为车辆调度问 题( v e h i c l es c h e d u l i n gp r o b l e m ，v s p ) ，有时也称为v r p t w ( v e h i c l e r o u t i n g p r o b l e m w i t h t i m e w i n d o w s ) 。对v r p 与v s p , 也有学者不加以区分，只是加上 具体约束定语，本文循例称之为v r p 。 2 2v r p 的构成要素 v r p 问题主要包括货物、车辆、车场( 物流中心) 、客户、运输网络、约束 条件和目标函数等要素，具体说明如下【1 9 2 0 1 2 1 l 【2 2 1 ： ( 1 ) 货物 货物是配送的对象，可以将每个客户需求的货物看成是一批货物。每批货物 包括货物名、包装、重量、体积、要求送达的时间和地点、能否分批配送等属性。 其中，货物的重量和体积是进行车辆装载决策的重要依据，当某个客户需求的货 物重量或体积超过车辆的最大装载量或体积时，则需要调度多辆车对该客户进行 配送。 ( 2 ) 车辆 车辆是货物的运载工具，其主要属性包括：车辆的类型、最大装载量、一次 运输的最长行驶距离或最长行驶时间、所属车场、执行任务前的停放位置及完成 任务后的停放位置等。 ( 3 1 车场( 配送中心) 配送中心是指进行集货、分货、配货、送货作业的仓库、车站、港口、车场 等，在本文中主要是指车场。车场的数量可以是一个或者多个，每个车场的特征 由所配备的车辆类型、车辆数量、以及所能处理的货物总量来表示。 6 中山大学硕士学位论文第2 章v l 啦概述 ( 4 ) 客户 客户的属性包括客户所处的位置、需求货物的数量、需求货物的次数、要求 提供服务的时间段、服务所需要的时间等在冲问题中，客户是最主要的构 成要素，客户的地理位置、时间窗要求和需求量在很大程度上决定了车辆的行驶 路线。 有时，有的客户的需求不能全部得到满足，或者车辆不能在其所要求的时间 段内按时提供服务在这种情况下，可以减少运送的货物量，或者是放弃对其中 一部分客户的服务此时，可以根据客户的需求是部分得到满足还是完全得不到 满足、以及服务提前或延迟的时间，引入相应的优先权或惩罚值。 ( 5 ) 运输网络 运输网络通常用一个无向图来表示，该无向图由顶点和无向边组成其中顶 点表示车场或客户，无向边则表示路线。根据需要，还可以用边的权值表示距离、 时间或费用等。在现实生活中，运输网络需要考虑的限制条件比较复杂，如路面 状况、流量及阻塞状况等，这些条件具有一定的随机性并且不是固定不变的，因 此将问题进一步复杂化。 ( 6 ) 约束条件 心问题应满足的约束条件主要包括： 客户对货物品种、规格、数量的要求； 客户对车辆类型、货物发到的时间范围的要求； 运输网络对车辆、时间窗的要求； 运输网络的路面状况； 车辆最长行驶距离、最长工作时间和最大装载量的要求； 在物流中心现有的运力范围内。 ( 7 ) 目标函数 对于v l 廿问题，可以只选用一个目标，也可以选用多个目标。经常选用的 目标函数主要有： 运输总里程最短。运输里程与配送车辆的耗油量、磨损程度、司机 疲劳程度以及运输网络状况等直接相关，它直接决定了运输的成本， 对配送业务的经济效益有很大影响； 7 中山大学硕士学位论文第2 章v r p 概述 配送车辆的吨位公里数最少。该目标将配送距离与车辆的载重量综 合起来考虑，即以所有配送车辆的吨位数( 最大装载量) 与其行驶 距离的乘积的总和最少作为问题优化的目标； 综合费用最低。降低综合费用是实现物流配送业务经济效益的基本 要求。在物流配送中，与取送货有关的费用包括：车辆维护和行驶 费用、车队管理费用、货物装卸费用、有关人员工资费用等； 准时性最高。有些情况下客户对交货时间有较严格的要求，此时就 需要将准时性最高作为确定配送路线的第一目标； 运力利用最合理。该目标要求使用较少的车辆完成配送任务，并使 车辆的满载率尽量高，以充分利用车辆的装载能力。 2 3v r p 的分类 为了便于描述和求解，许多专家、学者根据研究重点的不同从不同的角度、 按照不同的标准，对v r p 问题进行了如下多种分类 4 1 1 2 3 】： ( 1 ) 按车场的数目划分，可分为单车场问题和多车场问题。 单车场问题中所有车辆均来自于同一个车场，而多车场问题中则存在多个车 场，并且各个车场可能拥有不同的车辆数。 ( 2 ) 按车辆载货状况划分，可分为满载问题、非满载问题、以及满载和非满 载混合问题。 满载问题的特征在于客户的需求量大于或等于车辆的最大装载量，因此完成 一项配送任务需要一辆或多辆配送车辆，并且配送车辆大部分需要满载运行；相 应地，非满载问题是由于客户的需求量小于车辆的最大装载量，多项配送任务可 共用同一辆配送车辆，车辆在配送过程中经常处于非满载状态；而满载和非满载 混合问题则是由于一部分客户的需求量大于或等于车辆的最大装载量，而另一部 分客户的需求量小于车辆的最大装载量，造成一些配送车辆需要满载运行，而另 一些车辆处于非满载状态。 ( 3 ) 按配送任务特征划分，可分为纯送货问题、纯取货问题、以及送取货混 合问题。 纯送货问题仅考虑从车场向客户送货，也称为纯卸问题；纯取货问题仅考虑 中山大学硕士学位论文 第2 章v r p 概述 把各客户供应的货物取回到车场，也称为纯装问题；送取货混合问题则既考虑将 客户需求的货物从车场送到各个客户，同时考虑将客户供应的货物从客户取回到 车场，也称为装卸混合问题( 或集货和送货一体化问题) ( 4 ) 按客户对货物送达时间的要求划分，可分为无时限问题和有时限问题 无时限问题的特征是客户对货物的送达时间没有具体要求，而在有时限问题 中，客户要求所需求的货物在规定的时问窗内送达，也称为有时间窗问题 有时限问题又可以进一步分为硬时间窗问题和软时间窗问题。在硬时间窗问 题中，客户要求货物必须在规定的时间窗内送达，不能提前或延后，否则不接受 服务；而在软时问窗问题中，客户要求货物尽量在规定的时间窗内送达，但也允 许提前或延后，只是在提前或延后时，要施以一定的惩罚。 ( 5 ) 按车辆类型划分，可分为单车型问题和多车型问题。 在单车型问题中，所有的配送车辆都属于同一类型，即具有同样的参数( 最 大装载量、一次运输的最大行驶距离和最长行驶时间等) ；多车型问题中配送车 辆的类型不完全相同，即可能存在不同参数的车辆。 ( 6 ) 按车辆对车场的所属关系划分，可分为开放式问题和封闭式问题。 在开放式阀题中，车辆完成配送任务后不必返回其出发的车场，而封闭式问 题则要求车辆完成配送任务后必须返回其出发的车场。 ( 7 ) 按优化目标划分，可分为单目标问题和多目标问题。 单目标问题仅考虑一个配送目标，而多目标问题则同时考虑多个配送目标， 通常是将多个单独的目标依据一定的系数进行加权求和。具体目标函数的选取可 参考2 2 小节，这里就不再重复。 2 。4 求解方法 目前已经提出了许多用于求解v r p 问题的算法，大致上可以将它们分为三 类：精确算法( e x a c t a l g o f i t h m ) 、经典启发式算法( c l a s s i ch e u r i s t i c s a l g o r i t h m ) 和亚启发式算法( m c t a - h c u r i s t i c s a l g o r i t h m ) 。 2 4 1精确算法 精确算法是指可以求出问题的最优化解的算法。精确算法通过严谨的数学模 9 中山大学硕士学位论文 第2 章v r p 概述 型或计算机数据结构规划，利用数学法则或数据结构搜寻的方式，求得问题的解。 由于两种方法都在所有可行解集合中寻找最优解，所以求得的解均为最优解。由 于v r p 问题是n p h a r d 问题，随着变量的增加，精确算法求得的解集合会有组 合爆炸的现象，求解时间也呈指数函数的趋势增长。不能在有限的时间给予决策 者一个可行解，这是该方法最大的缺点f 州，因此该类算法主要用于解决中小规模 的v r p 问题。 求解v r p 问题的精确算法包括动态规划法、割平面法、集分解和列生成法、 分枝定界法、拉格朗日松弛算法等。下面简单介绍其中三种算、法【2 5 】： ( 1 ) 集分割 v r p 的集分割是由b a l i n s k i 2 6 】等人提出的。该方法直接考虑可行解集合，并 在此基础上进行优化，因此建立的v r p 模型最为简单。但其缺陷在于，如果问 题所受约束不严格，则需要计算的状态空间非常大。此外，要确定每个可行解的 最小成本也是件困难的事情。 ( 2 ) 三下标车辆流方程 f i s h e r l 2 7 等人针对带能力约束、时间窗口以及无停留时间的v r p 问题，提出 了三下标车辆流方程。在该方程中，其中两个下标表示弧或边，另外一个下标表 示特定车辆的序号。基于b e n d e r s 的分解技术，他们提出了一种启发式算法，保 证在有限的步骤内找到优化解。f i s h e r 等人用它计算了有5 0 一1 9 9 个客户的v r p 问题。 ( 3 ) 动态规划法 动态规划法( d y n a m i c p r o g r a m m i n g a p p r o a c h ，d p ) 是一种常用的运筹学方 法。在动态规划求解过程中，作为整个过程的最优策略具有这样的性质：无论过 去的状态和决策如何，对其决策所形成的状态而言，余下的诸决策必须构成最优 策略，这就是动态规划的最优化原理。用d p 求解v r p 问题的基本思路是【2 8 1 ： 将v r p 问题视为一个n 阶段的决策问题，每个阶段为一个子问题；各个阶段相 互联系，每个阶段都要做出决策，并且某个阶段的决策，常常影响下一阶段的决 策，从而影响整体决策；进而将其转化为依次求解n 个具有递推关系的单阶段 的决策问题，从而简化计算过程。用这种方法可求得v r p 问题的最优解，但仅 适用于较小规模的情况。 1 0 中山大学硕士学位论文 第2 章v r p 概述 2 4 2经典启发式算法 启发式算法【2 1 1 是一种基于直观或经验构造的算法，通过对过去经验的归纳推 理以及实验分析来解决问题用启发式算法求解问题时强调。满意”，在一般情 况下，求解的目标只是在可接受的花费( 计算时间、占用空问等) 下得出待解决 问题的满意解，而不去追求最优解，尽管这个解并不是最优的，但足以满足实际 应用的需要 用启发式算法求解问题是通过迭代过程来实现的，因此求解的关键在于建立 一套合适的解的搜索规则。为了能够得到满意解，在整个迭代过程中要不断吸收 新的信息，必要时抛弃原来拟定的不合适的策略，建立新的搜索规则，逐步缩小 搜索范围。 求解灌的经典启发式算法主要包括节约法、扫描法和插入法等。经典启 发式算法内容丰富，结构简单，往往具有很好的应用价值。但当问题规模较大时， 一般难以求得比较高质量的解。下面简单介绍其中三种算法： ( 1 ) c l a r k e - w r i g h t 节约算法 c l a r k e - w r i g h t 节约算法嘲( c l a r k ea n dw r i g h ts a v i n g sa l g o r i t h m ) 是c l a r k e 和w r i g h t 提出的一种求解v r p 问题的启发式算法该算法是一种基于节约准则 的路线构造算法，其基本思想是：首先对n 个客户生成n 条从车场到客户的路线， ? 计算合并任意两条路线后可以节约的成本量勺= + ，一略；然后对可节省 的成本量进行排序；最后根据排序结果以及可行性条件，对路径进行归并，直到 无法找到更好的解。 c l a r k e - w r i g h t 节约算法的特点是简单、易于理解、灵活性好。作为最著名的 求解v r p 问题的经典启发式算法，c l a r k e - w r i g h t 节约算法及其思想至今仍常为 许多求解v r p 问题的算法所利用。 ( 2 ) 最近邻插入算法 最近邻插入算法( n e a r e s tn e i g h b o r a l g o r i t h m ) 也是一种非常简单的求解v r p 的路线构造启发式算法算法的基本思想是：首先从距离车场最近的点出发，在 满足约束条件的前提下，从未服务的客户点中选取使得路线成本最小的点作为当 前路线的终点，如此不断对路线进行扩充，直到路线不存在可加入的客户点为止。 此时，如果所有的客户点均已被服务，则算法结束；否则，生成一条新的初始路 中山大学硕士学位论文第2 章v r p 概述 线，重复前面的路线扩充过程。 最近邻插入算法可以认为是求解v r p 问题最原始的算法，它易于实现，至 今仍被许多其它算法用来构造初始解。 ( 3 ) 扫描算法 扫描算法( s w e e pa l g o r i t h m ) 是由g i l l e t t 和m i l l e r 3 0 】于1 9 7 4 年提出的，是一 种先分派再求解的分派启发式算法。该算法可以有效地求解多达2 5 0 个客户点的 问题。算法的基本思想是：分两个阶段来构造一组解，首先以车场为旋转中心转 动一条射线，在满足约束条件的前提下将客户点按区域进行划分成组；然后对每 一区域内的客户点求解一个旅行商问题( t r a v e l i n gs a l e s m a np r o b l e m ，t s p ) ，以 确定一条车辆行驶路线。 2 4 3亚启发式算法 亚启发式算法也称为现代启发式算法，主要包括遗传算法( g e n e t i c a l g o r i t h m ，g a ) 、禁忌搜索算法( t a b us e a r c ha l g o r i t h m ，t s ) 、模拟退火算法 ( s i m u l a t e da n n e a l i n g ，s a ) 、蚁群算法( a n tc o l o n ya l g o r i t h m ) 和神经网络算 法( n e u r a ln e t w o r k a l g o r i t h m ) 等。亚启发式算法结合现代计算机技术在求解大 规模复杂问题的时候表现出很好的优越性，已经成为当今求解v r p 问题的算法 研究热点。目前，先利用经典启发式算法求得较高质量的初始解，再结合亚启发 式算法对初始解进行进一步的优化，已成为求解v r p 问题的重要模式。 为了求得较优解，亚启发式算法要对解空间进行广泛的探测，有时在搜索过 程中接受恶化的、甚至是不可行的中间解。通常亚启发式算法能求出比经典启发 式算法更好的局部最优解，但所花费的求解时间也比较长。下面简单介绍其中三 种算法： ( 1 ) 遗传算法 遗传算法( g e n e t i ca l g o r i t h m ，g a ) 是由美国m i c h i g a n 大学的j o h nh o l l a n d 教授于1 9 7 5 年提出的一种并行优化搜索方法，是一种基于达尔文进化论优胜劣 汰、自然选择、适者生存和物种遗传思想的随机优化搜索算法。它以很强的并行 性和很高的计算效率正日益受到人们的关注。g a 算法的基本思想可描述为：从 问题的一个种群( 一组初始可行解) 开始，模仿自然界生物进化过程，按照适者 生存和优胜劣汰的原理，通过随机选择、交叉、变异等过程，逐代演化产生出更 中山大学硕士学位论文 第2 章v r p 概述 好的种群( 可行解) ，使种群进化到搜索空间中越来越理想的区域，整个进化过 程中的最优个体就作为问题的最终解 g a 算法的优越性主要表现在搜索过程中不易陷入局部最优，即使在所定义 的适应度函数不连续的情况下，也能以极大的概率找到最优解同时，g a 算法 也存在易出现早熟收敛、局部搜索能力差等缺陷 目前国内外已有大量学者讨论了利用g a 算法来解决v r p 问题，包括、r m b r e e d a m 3 ”、b a r m i e 4 3 2 1 、p o t v i na n db e n g i o t 3 3 1 ，李军和郭耀煌 3 4 1 、郎茂祥3 习等 这些研究主要是在经验的基础上，根据具体问题的特征提出各种不同的编码方 式、交叉算子或变异算子，对g a 算法进行比较和改进。 ( 2 ) 禁忌搜索 1 9 8 6 年g l o v d 3 6 1 3 刀首次提出了禁忌搜索( t a b us e a r c h ，t s ) 的概念，并逐步 形成了一套完整的算法理论 i s 算法是对局部邻域搜索算法的扩展，是一种全 局逐步寻优算法，同时也是对人类智力过程的一种模拟，是人工智能在组合优化 算法中的一个成功应用。t s 算法的基本思想是：首先利用简单的算法获取一个 初始解作为当前解，并利用候选解产生函数( 邻域结构) 对初始解进行邻域变换； 然后在初始解的邻域中确定若干候选解，若最佳候选解对应的目标值优于到目前 为止搜索到的“最好解”( b e s t - s o - f a r ) ，则忽视其禁忌特性，用其替代“最好解”， 并作为新的当前解；若不存在上述候选解，则在候选解集中选择非禁忌的最佳候 选解为新的当前解，而无视它与当前解的优劣；上述两种情况下都要将相应的对 象加入禁忌表，并修改禁忌表中各对象的任期；如此重复上述迭代搜索过程，直 到满足停止准则。 t s 的特点在于采用了禁忌技术，即用一个禁忌表记录下已经达到的局部最 优点，在其后的搜索中，根据禁忌表中的信息不再或者有选择地搜索这些点，以 此来跳出局部最优点，从而实现全局最优。这种适应式的记忆能力使算法能够更 加有效地搜索解空间，克服了局部邻域搜索容易陷入局部最优的不足。 从目前的情况来看，t s 算法是解决v p p 的一种比较高效的算法，它的算法 结构比较简单，相对易于实现，主要关注的问题是邻域结构的设计、禁忌表的设 计和禁忌长度的设定等问题。o s m 锄【3 8 】、l a p o r t d 3 9 1 、t a i l l a r d 4 0 1 1 4 ”、钟石泉和贺 国光1 4 2 1 、张炯和郎茂祥删等人已经利用t s 算法对特定条件下的v r p 问题进行 中山大学硕士学位论文 第2 章v r p 概述 了求解，并取得了一定的研究成果。 ( 3 ) 模拟退火 模拟退火算法( s i m u l a t e da n n e a l i n g ，s a ) 是上个世纪八十年代初期发展起 来的一种基于热力学原理的随机搜索算法，适合于求解大规模组合优化问题，特 别是n p 完全问题。s a 算法源于对固体退火过程的模拟，其基本思想是：把每 种组合状态及其对应的目标函数分别看成某一物质系统的微观状态和在该状态 下的内能；用控制参数t 模拟温度，先加温使之具有足够高的能量，然后再逐渐 降温，其内部能量也相应下降；在热平衡条件下，物体内部处于不同状态的概率 服从b o l t z m a n 分布，若退火步骤恰当，则最终会形成最低能量的基态。在迭代 过程中，不但接受对目标函数有改进的状态，还以某种概率接受使目标函数恶化 的状态，从而可避免搜索过早收敛到某个局部极值点。具有跳出局部极值点区域 的能力，并且能寻找到全局最优或近似最优，这正是s a 算法与局部搜索算法的 本质区别。 s a 算法得到的解的好坏与初始状态、温度函数等都有一定的联系，降温较 快的效果不一定很好，效果好的往往降温过程又极其漫长。但由于该方法适用范 围广，并可人为控制迭代次数，反复求解，因此具有很强的实用性。o s m a n 3 8 】、 v a nb r a e d 锄m 噜人已经应用s a 算法求解v r p 问题，而在国内相关的研究则还 比较少。 2 4 4 小结 精确算法由于存在“随着问题规模的扩大，解集合会有组合爆炸的现象，求 解时间也呈指数函数的趋势增长”的缺陷，主要用于解决中小规模的v r p 问题。 而经典启发式方法和亚启发式方法通常只要求在可接受的时间或空间范围内得 出待解决问题的满意解，而不去追求最优解，故可用于求解较大规模的v r p 问 题。相对于经典启发式算法，亚启发式算法是相当费时间的，但同时也能求出更 好的解。一般地，经典启发式算法求