（企业管理专业论文）城市垃圾收运系统选址和选线优化研究.pdf

| l i i ii ii iii iiit l ll lli ii y 18 7 8 0 8 5 学位论文数据集 中图分类号 c 9 3 学科分类号 6 3 0 4 0 论文编号 1 0 0 1 0 2 0 1 1 0 8 8 7 密级公开 学位授予单位代码 1 0 0 1 0 学位授予单位名称 北京化工大学 作者姓名郇鹏学号 2 0 0 8 0 0 0 8 8 7 获学位专业名称企业管理获学位专业代码 1 2 0 2 0 2 课题来源其他项目研究方向决策优化 论文题目城市垃圾收运系统选址和选线优化研究 关键词垃圾收运系统，选址，带时间窗的车辆路线问题，占线问题 论文答辩日期 2 0 1 1 - 0 5 - 1 9 论文类型基础研究 学位论文评阅及答辩委员会情况 姓名 职称 工作单位学科专长 指导教师辛春林教授北京化工大学运营管理 评阅人1沈凤武副教授北京化工大学战略管理 评阅人2张继红 副教授 北京外国语大学供应链管理 评阅人3 评阕人4 评阅人5 徽员会捕 王明明 教授北京化工大学科技管理 高级工程北京燕华工程建设， 答辩委员1张印红企业管理 师有限公司 答辩委员2姚飞教授北京化工大学管理系统工程 答辩委员3 王江 教授北京化工大学战略管理 答辩委员4方勇副教授北京化工大学企业管理 注：一论文类型：1 基础研究2 应用研究3 开发研究4 其它 二中图分类号在中国图书资料分类法查询 三学科分类号在中华人民共和国国家标准( g b t1 3 7 4 5 - 9 ) 学科分类与代码中 查询 四论文编号由单位代码和年份及学号的后四位组成 摘要 城市垃圾收运系统选址和选线优化研究 摘要 作为城市垃圾综合管理系统的一个组成部分，垃圾收集运输系统占据 着重要位置。由于缺乏理论方面的指导，垃圾收运系统已成为垃圾综合管 理系统中的最薄弱环节之一，因此城市垃圾收运系统的完善和优化对城市 垃圾综合管理系统的高效运行起着至关重要的作用。 本文在对城市垃圾收运系统各个环节进行深入分析的基础上，通过对 城市垃圾逆向物流特点的分析，提出了城市垃圾收运系统的数学模型，具 体包括以下三个方面： 1 、选择城市一定范围内现有垃圾收集点中的一个在此建设垃圾转运 站，使得垃圾转运站到垃圾填埋场的距离加垃圾转运站到收集点之和的最 大距离最小。运用v o r o n o i 技术的选址方法，建立该问题的数学模型，设 ，在收集路 午饭休息时 运输费用最 给出求解步 知道当前的 一辆垃圾车 北京化工大学硕士学位论文 将转运站的垃圾运送至处理场，因此提出垃圾转运的占线车辆路线问题。 建立数学模型，并对占线k 垃圾车调度问题进行限定情形分析，给出竞 争策略和竞争比。 关键词：垃圾收运系统，选址，带时间窗的车辆路线问题，占线问题 摘要 r e s e a r c ho nl o c a t i o na n dv e h i c l er o u t i n go p t i m i z a t i o no f u r b a n m u n i c i p a ls o l i dw a s t e c o l l e c t i o na n d t r a n s p o r t a t i o ns y s t e m a b s t r a c t a sa p a r to fm u n i c i p a l s o l i dw a s t e ( m s w ) i n t e g r a t e dm a n a g e m e n t s y s t e m ，m s w c o l l e c t i o na n d t r a n s p o r t a t i o ns y s t e m h o l d sa n i m p o r t a n t r o l e d u e t ol a c ko f s y s t e m i cg u i d i n gt h e o r y , m s w c o l l e c t i o na n d t r a n s p o r t a t i o n i st h ew e a kl i n ki nt h em s wi n t e g r a t e dm a n a g e m e n t s y s t e m o p t i m i z a t i o na n dp e r f e c t i o no fm s w c o l l e c t i o na n dt r a n s p o r t a t i o ni s v e r yi m p o r t a n tf o rh i g he f f i c i e n c yo p e r a t i o no fm s wi n t e g r a t e dm a n a g e m e n t s y s t e m i nt h ep a p p e r , b ya n a l y z i n gt h ec h a r a c t e r i s t i c so fm s wr e v e r s el o g i s t i c s ， b a s e do nt h ed e 印a n a l y s i so fa l lt h el i n k s i nm s wc o l l e c t i o na n d t r a n s p o r t a t i o ns y s t e ma n dc o m b i n e dw i t ht h el o g i s t i ct h e o r y , t h eo p t i m i z a t i o n m e t h o d sa n dm a t h e m a t i c a lm o d e l sw e r ep r o p o s e df o rt h ee c o n o m i c a l 北京化工大学硕士学位论文 d i s t a n c eo fc o l l e c t i o np o i n tm i n i m u ms u m u s eo p t i m a ls y s t e mi n t e g r a t i o no f s t a rs y s t e m ，s e tu pt h ep r o b l e ml o c a t i o nt h e o r yo ft h em a t h e m a t i c a lm o d e l ， d e s i g nt h es o l v i n ga l g o r i t h m ，a n da n a l y z et h ec o m p u t a t i o n a lc o m p l e x i t yo ft h e a l g o r i t h m a d d r e s saw a s t ec o l l e c t i o nv e h i c l e r o u t i n gp r o b l e m w i t h t i m e w i n d o w s ( v r p t w ) w i t hc o n s i d e r a t i o no fm u l t i p l ed i s p o s a lt r i p sa n dd r i v e r s l u n c hb r e a k s m i n i m i z i n gt h et o t a le x p e n s ei st h em a j o ro b j e c t i v e s o l o m o n s w e l l k n o w ni n s e r t i o na l g o r i t h mi se x t e n d e df o rt h ep r o b l e mt og i v ear o u t e c o n s t r u c t i o ns t e p s t h er e q u i r e m e n to ft h et r a n s f e rs t a t i o ni sd y n a m i c w eo n l yk n o wt h e c u r r e n tr e q u i r e m e n tw i t h o u tk n o w i n gt h ef u t u r er e q u i r e m e n ts e q u e n c e w h e n t h et r a n s f e rs t a t i o nr a i s ear e q u i r e m e n t ，as i n g l ev e h i c l em o v et h ew a s t et oa l a n d f i l l w ep r e s e n tt h eo n l i n ekv e h i c l es c h e d u l i n gp r o b l e mo ft h ew a s t e t r a n s p o r t a t i o n ，b u i l dt h em a t h e m a t i c a lm o d e l ，g i v et h ec o m p e t i t i v es t r a t e g y a n dc o u n tt h ec o m p e t i t i v er a t i o k e y w o r d s ：m u n i c i p a ls o l i dw a s t ec o l l e c t i o na n dt r a n s p o r t a t i o n s y s t e m ，l o c a t i o n ，v i 冲t w , o n l i n ep r o b l e m 目录 第一章绪论 目录 1 1 问题的背景 1 1 1 城市垃圾及其收运系统 1 1 2 城市垃圾逆向物流系统 1 2 国内外研究现状 1 2 1 国外研究现状 1 2 2 国内研究现状 1 3 研究内容和方法 1 3 1 研究内容 1 3 2 研究方法 1 4 创新性工作 1 5 论文框架图 第二章城市垃圾收运系统优化理论基础 2 1 选址优化理论基础 2 1 1 选址问题的产生和分类 2 1 2 经典选址问题模型 2 2 垃圾收集阶段优化理论基础 2 2 1 旅行商问题( t s p ) 2 2 2 车辆路线问题( 冲) 2 2 3 带时间窗的车辆路线问题( v r p t w ) 2 2 4s o l o m o n 的插入算法 2 3 垃圾转运阶段优化理论基础 2 3 1 占线问题与竞争策略 2 3 2 竞争策略与竞争性能 第三章基于v o r o n oi 技术的垃圾转运站选址优化 3 1 问题的描述 3 2 数学模型 3 2 1 模型的建立 3 2 2 算法的设计 3 2 3 计算复杂性分析 3 3 本章小结 2 3 2 3 2 4 2 4 2 5 2 5 2 6 l l 2 4 4 6 7 7 7 9 o - - - - - i ，工 n n b h h b 托m 侈 北京化工大学硕士学位论文 第四章带时间窗的垃圾收集车辆路线优化 4 1 问题的描述 4 2 模型的建立 4 3 关于垃圾收集的v r p t w 问题的插入算法 4 4 本章小结 第五章垃圾转运车辆的占线优化调度 5 1 问题的描述 5 2 模型的建立 5 3 占线k 垃圾车调度问题的限定情形分析 5 3 1i v l = 刀，k j 之调度方案4 5 3 2 i v i = n , k 靠一j 之调度方案4 5 3 3 1 v l = n , k n - s ，k j 之调度方案4 5 4 本章小结 第六章结论与建议 6 1 结论 6 2 建议 参考文献 致谢 研究成果及发表的学术论文 作者和导师简介 2 9 2 9 3 2 3 5 3 7 3 9 4 5 4 5 4 5 4 7 5 3 5 5 9 0 1 l 2 2 4 3 4 4 4 4 4 4 1 ：；2r e s e a r c hm e t h o d s 8 1 4i n n o v a t i v ew o r k 9 1 5f r a m ed i a g r a mo f p a p e r 1 0 c h a p t e r2g u n i o i p a is o ii dw a s t ec o li e c t i o na n dt r a n s p o r t a t i o n s y s t e mf u n d a m e n t a it h e o r y 1 l 2 1l o c a t i o nf u n d a m e n t a lt h e o r y 一1 1 2 1 1l o c a t i o np r o b l e m sb i r t ha n dc l a s s i f i c a t i o n 1 l 2 1 2c l a s s i cl o c a t i o np r o b l e m s 1 3 2 2m u n i c i p a ls o l i dw a s t ec o l l e c t i o no p t i m i z a t i o nf u n d a m e n t a lt h e o r y 1 4 2 2 1 t r a v e l i n gs a l e s m a np r o b l e m 1 4 2 2 2v e h i c l er o u t i n gp r o b l e m 1 5 2 2 31 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 1 6 2 2 4s o l o m o ni n s e r t i o na l g o r i t h m 1 6 2 3m u n i c i p a ls o l i dw a s t et r a n s p o r t a t i o no p t i m i z a t i o nf u n d a m e n t a lt h e o r y 1 7 2 3 1o n l i n ep r o b l e ma n dc o m p e t i t i v es t r a t e g y 1 7 2 3 2c o m p e t i t i v es t r a t e g ya n dc o m p e t i t i v er a t i o 1 9 c h a p t e r3l o c a ti o no p ti m iz a t io no ft r a n s f e rs t a tio n 2 3 3 1 d e s c r i p t i o n 2 4 ：；：! m a t h e m a t i c a lm o d e l 2 4 3 ：! 1b u l i dm o d e l 2 4 3 2 2 a l g o r i t h m s ：! ! ； 3 2 3t i m ec o m p l e x i t y ：1 6 3 3 s u m m a r y ：1 6 c h a p t e r4w a s t ec o ii e c t i o nv e h i c i er o u t i n gp r o b i e mw i t ht i m o w in d o w s 2 9 北京化工大学硕士学位论文 _ 一一 4 1 d e s c r i p t i o n 2 9 4 2m a t h e m a t i c a lm o d e l j z 4 3i n s e r t i o na l g o r i t h mf o rw a s t ec o l l e c t i o nv r p t w 3 5 4 4 s u m m a r y 3 7 c h a p t e r5o n ii r eo p t i m a lv e h i c i es c h e d u ii n go fw a s t e t r a n s p o r t a t io n 3 9 5 1d e s c r i p t i o n 3 9 5 2m a t h e m a t i c a lm o d e l 4 0 5 3 0 n l i n ev e h i c l es c h e d u l i n go fw a s t et r a n s p o r t a t i o nl i m i t e da n a l y s i s 4 1 5 3 1s c h e d u l i n gs c h e m ew h e n i v l - ，l ，k j 4 1 5 3 2s c h e d u l i n gs c h e m ew h e n v i = 刀，k 力一j 4 2 5 3 3s c h e d u l i n gs c h e m ew h e n l v l = 以，k - 咒一s ，k 处理场 y 图1 - 1 垃圾收运处理系统示意图 f i g l - 1s c h e m eo f w a s t ec o l l e c t i o n ，t r a n s p o r t a t i o na n dd i s p o s a ls y s t e m 1 1 2 城市垃圾逆向物流系统 物流在社会再生产过程中占据着很重要的环节，物流的过程不但包括物质的能量 的转化、物质的循环利用，而且也包括价值的转移和实现，因此，物流系统是动态的、 复杂的、开放的大系统，并且与外界环境是密切联系的。随着社会的不断进步、经济 的飞速发展，物流活动对生态环境造成多方面的破坏，如废气污染、噪声污染、垃圾 增加、资源浪费等，这些后果影响了建立环境友好型和资源节约型社会的进展【4 】。 逆向物流( r e v e r s el o g i s t i c s ) 的定义是：与传统供应链反向，为价值恢复 或处置合理而对原材料、中间库存、最终产品及相关信息从消费地到起始点的 有效实际流动所进行的计划、管理和控制过程【5 】。 逆向物流有广义和狭义之分。狭义的逆向物流( r e t u r n e dl o g i s t i c s ) 是指对 那些由于环境问题或产品已过时的原因而产品、零部件或物料回收的过程。它 是将排泄物中有再利用价值的部分加以分拣、加工、分解，使其成为有用的资 源重新进入生产和消费领域。广义的逆向物流( r e v e r s el o g i s t i c s ) 除了包含狭义 的逆向物流的定义之外，还包括废弃物物流的内容，其最终目标是减少资源使 用，并通过减少使用资源达到废弃物减少的目标，同时使正向以及回收的物流 更有效率。 根据中华人民共和国国家标准物流术语( g b t18 3 5 4 2 0 0 1 ) ，废弃物物 流( w a s t em a t e r i a ll o g i s t i c s ) 是指“将经济活动中失去原有使用价值的物品，根据 2 第一章绪论 实际需要进行收集、分类、加工、包装、搬运、储存等，并分送到专门处理场 所时形成的物品实体流动。 因此，城市垃圾收集运输系统是一种逆向物流系统。 城市垃圾物流系统和其他物流系统有共同的四大要素：运输、设施、库存、 信息，但由于其自然属性与社会属性特殊，城市垃圾物流系统和一般的物流系 统相比具有明显的差异，主要表现在【6 】： 产量和组成成分不确定性大 人们的消费习惯、生产活动和生活方式的不同，使得城市垃圾的成分也有 差异。在不同时期内，即使是同一个区域，垃圾的组成成分和比例也不同。 由固态、液态和气态混合组成 一般物流系统中物流的物态相对稳定，如固态、液态或气态。城市垃圾一 般是固、液、气态的混合体。因此，在收集和运输垃圾的过程中，会产生渗滤 液、粉尘和散装物，污染转运站、街道等。 腐蚀性比较大 垃圾的腐蚀性大，收运系统需要特殊的工艺和装备。 城市垃圾物流具有经济价值和社会价值 虽然垃圾中有可回收再利用的成分，但从经济角度看，其整体经济价值相 对较低。城市垃圾物流系统的首要目标是满足建设资源节约型和环境友好型社 会的需要，在最大化环境效益和社会效益的同时也要兼顾经济效益的最大化。 随着公众对生存环境问题的日益关注，城市垃圾处理问题逐渐成为学者们 注的热点。在城市垃圾收运的物流过程中，如果任何一个环节缺乏科学的管 与合理的规划，都会给城市的市容环境和交通运输等多方面带来很大影响。 然城市垃圾物流系统与一般物流系统有着很多的共同点和相似点，但是，由 城市垃圾物流系统的物流对象、目标和处理过程存在特殊性，因此在优化城 垃圾物流系统的时候，应将传统的物流模型和方法加以改进，而不能套用一 的物流系统。 对于城市垃圾物流系统而言，垃圾转运站的选址优化，垃圾收集路线的优 和垃圾转运车辆调度的优化，都能提高城市垃圾物流系统的整体效率，使城 垃圾管理符合可持续发展要求，为构建经济社会环境协调发展的社会体系， 设资源节约型、环境友好型社会做出重要的贡献。 3 北京化工大学硕十学位论文 1 2 国内外研究现状 1 2 1 国外研究现状 国外对于垃圾收运系统的研究主要是在处理场、转运站数量和选址、垃圾收集转 运路线的优化等方面展开的。 1 、垃圾处理场、转运站选址的优化研究： 2 0 世纪6 0 年代末，a n d e r s o n ( 1 9 6 8 ) 7 1 首次提出垃圾管理系统中经济最优化的 概念，应用混合整数规划，对垃圾处理场进行选址并对垃圾收运系统进行规划。 y u r t e r i 和s i b e r 【8 】运用线性规划模型来确定转运站的位置，从此该研究成为了该领 域研究的热点。k i r c a 和e r k i p 9 】给出了一个线性规划模型，用于解决固体废弃物运输 系统中转运站的选址，并且将模型应用于土耳其i s t a n b u l 地区的垃圾收集运输系统中， 为制定科学合理的垃圾管理方案提供了有效的依据。z h u 和r e v e l l e o o 将混合整数规 划应用于固定的费用函数下垃圾处理设备的选址问题中。2 0 世纪9 0 年代初，以运输 费用最小化为目标函数，建立了确定转运站数量和位置的数学模型。t h i e r r yk u l e a r 【i i j 建立了一个混合整数规划模型和一个整数规划模型，研究了比利时首都布鲁塞尔某区 的垃圾收运系统运作情况，已知各点收集路线的情况下，分别对转运站的数量、位置 以及停车场的数量和位置进行优化，使总的运输费用最小。c h a n g e ta 1 1 1 2 j 突破了传统 模型中只考虑经济收益的问题，在原有的垃圾管理中的经济化选址模型中综合考虑了 环境影响因素，如：大气污染，渗滤液，噪声污染和交通等问题，比较全面地反映了 垃圾的产生量、污染源、垃圾的收集和回收之间的关系。i o a n n i sg - i a r m i k o s = 3 运用多 目标模型给出四个目标对垃圾的处理设备和处置场所的选址以及危险废弃物在运输 网络中的运输进行优化。 2 、垃圾收运路线的优化研究： 国外对路线问题的研究主要包括中国邮递员问题( c h i n e s ep o s t m a np r o b l e m ， c p p ) ，旅行商问题( 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 ) ，车辆路线问题( v e h i c l er o u t i n g p r o b l e m ，心) 等。基于这些路线问题，根据实际情况的不同需要将路线问题变形， 加必要的限制约束条件，才能更切合实际，从而产生了一些新的路线问题，如乡村邮 递员问题( r u r a lp o s t m a np r o b l e m ，r p p ) 、带容量限制的弧路线问题( c a p a c i t a t e da r c r o u t i n gp r o b l e m ，c a r p ) 、带时间窗的车辆路线问题( v e h i c l er o u t i n gp r o b l e mw i t ht i m e w i n d o w s ，v r p t w ) 等。由于上述问题是n p h a r d 问题，所以求解路线问题的数学模 型，大都采用启发式算法。主要的算法有插入算法、神经网络算法、改进最小生成树 算法、禁忌搜索算法、遗传算法、平行节约启发式算法等。 4 第一章绪论 论文中主要将垃圾收集问题归纳为带时间窗约束的车辆路线问题( 冲t w ) 进 行研究，并运用启发式算法求解。s o l 锄o n 【1 4 】为带时间窗的车辆调度问题建立了一个 标杆问题集，建立了一系列启发式算法。在这些已经测试过的启发式算法中，s o l o m o n 的插入算法在很多情况下能够产生最好的调度方案。p o t v i n 和r o u s s e a u 1 5 】的选线方法 与之类似。他们用s o l o m o n 的启发式算法找到初始用户和车辆的数目。在每次反复中 他们选择一个用户插入到路线中。如果对于确定数量的车辆有一个可行的算法，那么 他们减少车辆数目并且检验其可行性。如果不可行，则该算法增加车辆数目来寻找可 行方案。 r o c h a 和t a i l l a r d t l 6 】发表了关于车辆调度问题的一个随机性的禁忌搜索算法。在 他们的方法中，多重的初始解决方案通过局部搜索启发式算法得到。每条路线都被标 记该解决方案的目标值( 比如运行时间) ，并且增加到一个路线记录装置，称之为适 应性存储器。取决于路线的标记，它有一个概率被选择。由好方案得出的路线被赋予 更高的概率值。在每次选择中，在适应性存储器中的已经选择好用户的路线将被忽略。 在此之后，如果还剩用户需要插入并且没有更多的路线可以选择的话，将通过插入算 法把用户插入到路线中。该步骤将被重复直到一个可以停止的标准得到确认。 t a i l l a r d t l | 玎运用一个名叫c r o s s 的边缘交换启发式算法和禁忌搜索算法改进了车 辆调度方法。他们限制了任意两条路线中客户的交换。t a i l l a r d 认为车辆路线问题中， 同一辆车可以服务若干条路线，并提出了禁忌搜索启发式算法来解决该问题。站点的 时间窗和一些中间设施如转运站等在他们的研究中没有考虑。 w e i g e l 和c a , 1 8 】做了一个关于希尔斯送货到家和技术员调度问题的v r p t w 算法 应用案例研究。他们也是采用一个先划分集群再选路线的方法，考虑了三个主要程序： 起始点矩阵建设、路线的集群化和路线的改善。他们在最短路线算法中运用了地理信 息系统( g i s ) 获得起始点矩阵和两个站点问的运行时间。对于路线的集群程序，他 们建立了一个多重插入算法，该算法和p o t v i n 和r o u s s e a u 1 5 j 的并行插入算法类似。 服务时间、等待时间、时间窗延误惩罚的加权组合作为目标函数。他们提出了一个路 线内部改进算法和一个相邻的路线内部改进算法，通过传输和交换两条路线中的站点 来提高解法的质量。该算法也应用了禁忌搜索算法。 t u n g 和p i i h l o i 【1 9 】修改了s o l o m o n 的插入算法并且把它应用到了河内的垃圾收集 问题。在标准的冲t w 问题的基础上，他们考虑了垃圾填埋场的作用，是倾倒收集 到的垃圾的地方。还考虑了连续两次访问同一收集点的到达时间约束。他们也假设垃 圾车从车库出发开始一条新路线。他们用o r - o p t 和2 - o p t 算法来改进解。本文考虑的 问题与t u n g 和p i n n o i 的垃圾收集问题有相似之处，但也有明显的不同。他们的研究 中，只有一座垃圾转运站，而我们的研究中有多个垃圾转运站，这使得该问题更加复 杂。他们的问题中，有三种不同种类的移动，所以可以分开来解决；而我们的问题只 有一种移动。他们假设司机的午饭休息时间是介于移动之间，不需要考虑。我们的问 5 北京化工大学硕士学位论文 题中，司机从上午1 1 点到下午1 点有一个小时的午饭休息时间，是明确需要考虑的。 1 2 2 国内研究现状 国内的城市垃圾管理系统优化研究相较于国外的研究还处于起步阶段。贾学斌【2 0 l 运用神经元算法、递归调用理论等优化理论，分析讨论了存在垃圾收集频率时，优化 的收运路线方案的确定方法。建立了数学模型，目标函数是收运线路总路程最短。孙 家珊【2 1 1 、陈海滨【2 2 】等论证了垃圾转运站在城市垃圾综合处理系统中的重要地位和作 用，并给出实例来说明在一定的运输距离条件下建设转运站将有着最大的经济性。王 志刚等【2 3 】分析了城市垃圾转运站等设施的有关设置标准，同时还分析了设计规范中存 在的问题，提出了两点修改建议，说明了如何对广州市区小型垃圾转运站进行设置， 并估算了需求量。 邱江等【冽运用聚类分析方法，研究影响区域垃圾收运模式的主要原因及优化的 垃圾收运模式。研究结果证明，影响垃圾收运模式的关键在于手机密度、运输距离。 并提出了优化的垃圾收运模式。李天威【2 5 】根据我国中小城市垃圾产生量相对较小等特 点，提出了我国中小城市垃圾管理的综合处理化、长期优化和区域优化等基本原则， 并建立优化模型，为我国在规划期间的中小城市用何种方式如何处理城市垃圾给出了 建议。 盛金良【2 6 】阐述了城市垃圾收运模式的设计要求，介绍了有转运站和无转运站的收 运模式，并根据垃圾量、垃圾车装载容量和运输距离等方面进行分析比较，提出了合 理的垃圾收运模式设计方法，举例分析在何种情况采用转运站收运更经济。李东【2 7 1 在对垃圾收运系统规划设计的分析中，对中小型转运站的作用与设置标准、转运站设 施规划设置、垃圾收集车、转运车的选用及数量等问题进行了经济性分析。 刘桐武【2 8 】将线性规划和运输模型应用于垃圾收运，采用运输模型中的最小元素法 和位势法对垃圾调运方案的数学模型求解，得到最优调运方案。证明了线性规划中的 运输模型是解决垃圾收运优化问题的有效方法，建议这一现代管理的科学方法，应广 泛在环卫管理中推广应用。 王志刚、陈新庚、陈炳禄等【2 9 】采用线形规划模型对广州市城市垃圾管理进行系统 规划，运用层次分析法( a h p ) 进行综合效益的评估取值，计算出各个时期垃圾堆肥、 焚烧、资源化回收和填埋的比例和数量的优化方案，预测了各个规划期各种设施的需 求量。运用最小费用规划模型选取运输费用研究了城市垃圾在产生源与各处理设施之 间是如何分配的，设计出方案，计算出广州市区城市垃圾管理系统处理的最少费用， 并给出与垃圾产生量对应的处理设施。 台湾学者张乃斌【3 0 】建立了一个改进的多目标、混合整数规划模型对车辆路线进行 6 第一章绪论 规划，运用地理信息系统( g i s ) 技术对收集车辆路线选择和调度进行优化研究。研 究表明，通过将g i s 技术、关联的数据库管理系统和数学规划软件接合起来，实现在 环境和市政规划发生变化的情形下，对可供选用的垃圾收集方案进行分析比较。 1 3 研究内容和方法 1 3 1 研究内容 本论文研究内容主要为通过深入分析城市垃圾收运系统的各个环节，在此基础 上，结合逆向物流理论，以费用最小化为优化目标，对城市垃圾收运系统的全过程进 行系统地优化。具体包括以下三个方面： 垃圾收集运输系统中，垃圾转运站的选址优化问题。 垃圾收集运输系统中，垃圾收集阶段的路线优化问题。 垃圾收集运输系统中，垃圾转运阶段的路线优化问题。 1 3 2 研究方法 论文研究用到的相关基础理论涉及组合最优化、计算复杂性、最坏情形分析法等 方面的内容，概述如下。 ( 1 ) 组合最优化 组合最优化是寻找离散事件的最优编排、分组、次序或筛选等优化问题的数学方 法，属于数学规划中经典而且重要的分支。 定义1 1 ：组合最优化问题：设e 为一有限集，f 为e 的子集族，c 为定义在e 上的非负实函数( 权) ，对s 4 - 有： c ) = c g ) 则组合优化问题可表示为f m a x c ( s s f ) 或m i n c ) l s f 组合最优化的特点是可行解的集合为有限点集。因此，只要比较f 中元素的目标值的 大小，最优解一定可以找到。现实中有很多组合最优化的问题。 例：给定一个道路交通网络g 缈，e ) ，v = “，屹，屹，1 ，。 为g 的节点集，h 表示 出发地，表示目的地，e = i f 为g 中边的集合，其中勺= d i v j ) ，q e ) 为边 7 北京化工大学硕士学位论文 8 。的权，求v l 到，。的最短路线。 令v 1 到1 ，。的路线集合为f ，则f 为e 的子集族，s 为从h 到1 ，。的一条路线，s g - ， 形 ) 为s 的长，形p ) = 以扩) ，如果s s 使得 矽( s + ) = 1 1 1 i n 杪 】s 星誓 则，为问题的最优解即u 到1 ，。的最短路线。 ( 2 ) 算法与计算复杂性 定义1 2 ：算法：是对特定问题求解步骤的一种描述。它是指令的有限序列，其中每 一条指令表示一个或多个操作。算法有五大特征： ( 1 ) 有限性。一个算法必须总是( 对任意合法的输入值) 在执行有限步后结束，且 每一步都可在有限时间内完成。 ( 2 ) 确定性。算法中每一条指令必须有确切的含义，不能有歧义性。并且，在任何 条件下，算法只有唯一的一条执行路线，即对于相同的输入只能得到相同的输 出。 ( 3 ) 可行性。一个算法是能行的，即算法中描述的操作都是可以通过已经事先的基 本运算执行有限次来实现的。 ( 4 ) 输入。一个算法有零个或多个输入量，这些输入是算法所要求的初始信息，取 自于某一特定的集合。 ( 5 ) 输出。一个算法有一个或多个输出信息。这些输出是同输入有特定关系的量。 必须注意到，在实际应用中，有限性的限制时不够的。一个实用的算法，不仅要 求步骤有限，同时要求运行这些步骤所花费的时间是人们可以接受的。如果一个算法 需要执行数十百亿亿计的运算步骤，从理论上说，它是有限的，最终可以结束，但是， 以当代计算机每秒数亿次得运算速度，也必须运行数百年以上时问，这是人们所无法 接受的，因而是不实用的算法。运算时间是算法有效性的度量，一个算法运算次数是 指所实用基本算数运算( 加、减、乘、除、比较) 的次数。 定义1 3 ：算法的计算复杂性：对输入长度为旧的一切实例，在最坏情况下运算次数 的上界s l l s l ) 。 定义1 4 ：多项式时间算法：若一个算法a 的时间界为厂g ) = d ( 力) ，其中刀为实例 的规模，七为确定的正整数，则称血为多项式时间算法( p o l y n o m i a l - t i m ea l g o r i t h m ) 多项式时间算法亦称好算法或有效算法，而非多项式时间算法称为指数时间算法 或称坏算法。当输入规模不断增大时，任意一个多项式算法终将比任何指数时间算法 更有效。 ( 3 ) 最坏情形分析法 最坏情形分析法( w o r s t c a s e a n a l y s i s ) 是研究占线问题与竞争策略的基本方法。 其核心思想是：对问题设计竞争策略时，需考虑该种策略竞争性能比的最坏情形。 占线决策问题最坏情形分析法的数学描述如下：对于最小化费用的占线决策问题 8 第一章绪论 p ，令巳q ) 和c d 阿乜) 分别表示针对不确定性因素序列r 在策略彳下的费用和对离线 问题的最优费用，如果存在一个不确定因素序列r = 呓，) ，使得 u p 尺器眦赚c 为策略彳的静比。 1 4 创新性工作 本文从垃圾转运站的选址、垃圾收集阶段的路线选择和垃圾转运阶段的路线选择 三个方面对垃圾收运系统进行优化，创新性的工作包括： 1 、运用v o r o n o i 图的技术对垃圾收运系统中的转运站进行选址优化。 2 、在带时间窗的垃圾收集车辆路线优化问题中，考虑了车辆空载和实载两种不 同运行状态，且两种状态下单位距离的运行成本不同。并考虑了具有多个转运站和司 机的午饭休息时间。 3 、运用占线问题及竞争策略的理论方法对垃圾转运阶段的车辆路线进行优化， 设计了竞争策略并给出竞争比。 9 北京化工大学硕士学位论文 1 5 论文框架图 r 一一一一一一一一一一一一一一一一一一一一一一一一一一 ll 1 一一j 图1 - 2 论文结构框图 f i g l - 2f r a m ed i a g r a mo f p a p e r 第二章城市垃圾收运系统优化理论基础 第二章城市垃圾收运系统优化理论基础 城市垃圾产生是分散的，而城市垃圾的处理处置则需要将垃圾集中起来，因此城 市垃圾收运系统的主要功能就是完成一个从分散到集中的转换。转运站是垃圾收运系 统的枢纽，在垃圾收集运输过程中起很大作用。通过转运站，城市垃圾收集运输被分 成两阶段，即转运站之前的收集运输阶段和转运站之后的转运阶段。 城市垃圾的收集运输费用较大，对城市垃圾收运系统各个环节进行优化可以提高 城市垃圾的收运系统的运行效率，从而获得较大的经济效益。论文对城市垃圾收运系 统进行总体优化可以从三个方面开展：首先是对垃圾处理场和转运站进行优化选址； 其次是对城市垃圾的收集路线进行优化；第三可以对城市垃圾转运路线进行优化。下 面将对以上三方面的优化研究分别进行理论基础方法的阐述。 2 1 选址优化理论基础 2 1 1 选址问题的产生和分类 选址问题是一个比较古老的问题，有记载的理论至少可以追溯到十七世纪费马 ( e f e r m a t ) 等人的工作。现代选址研究起源于1 9 0 9 年，当时a l f r e dw e b 贸为解决如 何为单个仓库选址使得仓库到多个顾客间的总距离最小的问题，这就是著名的w e b e r 问题。选址理论因h a k i m i 3 1 】发表的关于选择交通网络中的转接中心及公路系统的警 署位置的而得以复兴。h a k i m i 考虑了一个一般性的问题，即在一个网络中选择一个或 多个设施使得客户到离他最近的设施的距离和最小或距离和最大的最小。2 0 世纪6 0 年代中期，选址理论已发展的非常繁荣。大多数基础设施选址问题可以被刻画为静态、 确定性的形式。随后，由于越来越多领域学者的研究，问题的研究呈现多样化。 据文献【3 2 1 所总结的，选址问题的广泛性主要是由以下五个原因造成的。第一，选 址问题来自人类生活的