（载运工具运用工程专业论文）配送和集货一体化下的车辆路线问题研究.pdf

摘要 随着物流业在我国的不断发展以及物流专业化水平的不断提高，我国物流配送业近 年来也得到了迅速的发展。在物流配送活动中，配送车辆的路线问题是配送合理化的核 心问题，对于企业提高服务水平、降低物流成本、增加经济效益的影响也最大。为实现 成本最小化和效益最大化的根本目的，配送和集货一体化将是现代物流配送的发展方 向，因此对配送和集货一体化下的车辆路线问题进行研究是具有一定的理论价值和现实 意义的。 本文对配送和集货一体化下多站点车辆路线问题以及配送和集货一体化下带硬时 间窗的车辆路线问题进行了研究。本文首先建立了配送和集货一体下多站点车辆路线问 题的数学模型，并针对问题特点设计了综合运用多种启发式算法的多阶段求解方法对模 型进行了求解，计算结果表明集成配送和集货时的车辆总行驶路线比分别配送和集货时 节约近一半。 考虑到现代物流的时效性因素，本文建立了配送和集货一体化下带硬时间窗的车辆 路线问题的数学模型，针对问题的复杂性，设计了适合求解该问题的混合遗传禁忌算法。 采用改进节约法构造和随机产生相结合的方法为遗传算法产生初始解群体，并对遗传算 法中较优的一部分染色体进行禁忌搜索以加快收敛速度。用计算机编程实现了该算法， 通过与有关文献中的实例进行比较，所求解的质量提高了2 1 ，说明本文设计算法对 该问题的适应性，以及在遗传算法中采用构造初始群体中部分解及对进化中的较优解进 行禁忌搜索的方法更容易得到更好的解。最后，通过对三组标准测试数据，包括宽时间 窗、紧时间窗和混合时间窗，进行大量的试验证明本文设计算法的科学可行性和有效性 关键词：配送和集货车辆路线问题硬时间窗遗传算法禁忌搜索 a b s t r a c t w i t ht h ec o n t i n u o u sd e v e l o p m e n to fl o g i s t i c si n d u s t r ya n dt h ec o n s t a n t l yi m p r o v e m e n t o ft h es p e c i a l i z a t i o nl e v e lo fl o g i s t i c si no u rc o u n t r y , l o g i s t i c sd i s t r i b u t i o ni n d u s t r yh a sa l s o b e e nd e v e l o p e dq u i c k l y o fa l lt h ea c t i v i t i e si nd i s t r i b u t i o n , t h ev e h i c l er o u t i n gp r o b l e mi st h e k e yp r o b l e m i na d d i t i o n , i th a sg r e a tm u c he f f e c to ne n t e r p r i s et ou p g r a d et h el e v e lo f 默孵i c e t or e d u c et h el o g i s t i c sc o s ta n dt oi n c r e a s ee c o n o m i cb e n e f i t s t oa c h i e v et h eb a s i ca i mo f m i n i m u l nc o s ta n dm a x m u mb e n e f i t s ，u n i t i z i n gt h ea c t i v i t i e so fd e f i v e r ya n dp i c k u pw i l lb e t h et r e n d s o , i ti so ft h e o r e t i c a la n dp r a c t i c a ls e n s e st os o m ee x t e n t st os t u d yt h ev e h i c l e m u t i n g p r o b l e mu n d e rt h ee n v i r o n m e n to fu n i t i z i n gt h ea c t i v i t i e so fd e h v e r ya n dp i c k u pf o r t h i s p a p e z ： t h eo b j e c t so ft h i sp a p e ra r et h em u l t i - d e p o tv e h i c l em u t i n gp r o b l e mw i t hp i c k u p sa n d d e l i v e r i e sa n dt h ep i c k u p sa n dd e l i v e r i e sv e h i c l er o u t i n gp r o b l e mw i t hh a r d - w i n d o w s f i r s t l y , t h i sp a p e rs e t s 叩t h em a t h e m a t i cm o d e lo ft h em u l t i d e p o tv e h i c l em u t i n gp r o b l e mw i t h p i c k u p sa n dd e l i v e r i e st h e ns o l v ei tb yu s i n gm u l t i - p h a s e sc o m p o s i t eh e u r i s t i c sa l g o r i t h m t h er e s u l ts h o w st h a tt h et o t a ld i s t a n c et r a v e l i n gb yv e h i c l e sw h e ni n t e g r a t i n gp i c k u p sa n d d e l i v e r i e si sa b o u tt h eh a l fo fi tw h e ns e p a r a t et h et w o t h i sp a p e rs e t su pt h em a t h e m a t i cm o d e lo ft h ep i c k u p sa n dd e l i v e r i e sv e h i c l em u t i n g p r o b l e mw i t hh a r d - w i n d o w s d e s i g nah y b r i dg e n e t i c t a b us e a r c ha l g o r i t h mt os o l v i n gt h i s p r o b l e m c o m b i n et h e t w om e t h o d so fs t r u c t u r i n gb yi m p r o v e dc - wa l g o r i t h ma n d p r o d u c i n gr a n d o m l yt op r o d u c es t a r t i n gg r o u pf o rg e n e t i ca l g o r i t h ma n du s i n gt a b us e a r c hf o r a p r o p o r t i o no f b e t t e rc h r o m o s o m e s t h ec o m p u t i n gr e s u l ti s2 1 b e t t e rc o m p a r ew i t ht h e r e l a t e dl i t e r a t u r e ，w h i c hs h o wt h es u i t a b i l i t yo fd e s i g n e da l g o r i t h ma n dt h a ts t r u c t u r i n ga p r o p o r t i o nc h r o m o s o m e sf o rt h es t a r t i n gg r o u pa n du s i n gt a b us e a r c hi nt h eg e n e t i ca l g o r i t h m c a nh e l pt og e tb e t t e rs o l u t i o nf a s t a tl a s t , t h ed e s i g n e da l g o r i t h mp r o v e dt ob ep r a c t i c a b l e , s c i e n t i f i ca n de f f e c t i v eb yu s i n gi tt ot e s tt h r e es u i t so fs t a n d a r dt e s t i n gd a t e sw h i c hc o n t a i n t h es m a l lt i m e - w i n d o w s ，b i gt i m e w i n d o w sa n dn o r m a lt m e - w i n d o w s k e y w o r d s ：p i c k u p sa n dd e l i v e r i e s ；v e h i c l er o u t i n gp r o b l e m ；h a r d - t i m ew i n d o w s ；g e n e t i c a l g o r i t h m ；t a b us e a r c h 论文独创性声明 本人声明：本人所呈交的学位论文是在导师的指导下，独立进行 研究工作所取得的成果。除论文中已经注明引用的内容外，对论文的 研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本论 文中不包含任何未加明确注明的其他个人或集体己经公开发表的成 果。 本声明的法律责任由本人承担。 论文作者签名：弥诫土办6 年j 月3 日 论文知识产权权属声明 本人在导师指导下所完成的论文及相关的职务作品，知识产权归 属学校。学校享有以任何方式发表、复制、公开阅览、借阅以及申请 专利等权利。本人离校后发表或使用学位论文或与该论文直接相关的 学术论文或成果时，署名单位仍然为长安大学。 ( 保密的论文在解密后应遵守此规定) 论文作者签名：琦l 诚 j 口咕年占月8 日 导师签名：锏 形 乡加辟f 月8 日 1 绪论 1 1 问题的提出 运输、储存、包装、装卸搬运、流通加工、配送和信息组成了物流的七个功能要素， 而其中运输和配送起着尤为重要的作用。在物流过程中，运输是实现物质实体由供应方 向需求方的移动，也就是创造空间价值的过程。根据一般综合分析计算社会物流费用， 运输费占6 0 的比例，有些产品运输费用甚至高于产品的生产费用“3 。可见，运输成本 是影响物流成本的重要因素，物流总成本的大小和运输成本的大小直接相关。据测算， 我国物流成本占g d p 的比重高达2 0 ( 超过2 万亿元) ，发达国家一般只有1 0 左右，物 流成本降低l 到2 个百分点，将产生社会效益1 0 0 0 到2 0 0 0 亿元。1 ，因此，控制物流总 成本、降低运输成本对我国的经济建设有着十分重要的意义另外，配送制可以使库存 相对集中，有条件也有可能按照统一计划合理分配和使用资源，做到物尽其用；实施配 送也有利于建立起合理的库存结构和运输结构，进而能够提高物流设簏的利用率和物流 设备的工作效率在库存结构和运输结构分散的状态下，汽车的货物实载率一般比较低， 有的只有2 5 ，而在结构合理、运力集中的状态下，车辆的货物实载率可提高到7 0 9 6 8 0 t 3 1 。 在长期的经营实践中，企业的经营者逐渐认识到：如果物流活动缺乏系统管理，不 仅会影响企业各项业务的正常运行，而且还会导致经营成本不断上升。因而，物流工作 不是企业一种派生的经营职能，也不是一种经营的辅助手段，而是经营过程中的一个重 要的组成部分，物流部门工作的好坏直接决定着企业的发展、经营的效益、服务的质量 和竞争的成败。提高物流效率、降低物流成本、提高物流服务水平对于提高企业的竞争 力有着至关重要的作用。由于物流行业本身不生产产品，靠的是节约的思想来提高利润， 所以必须在各个环节中尽可能地节约成本，特别是在货物的流通环节，如配送。配送对 于各个企业来说都具有十分重要的作用。首先在生产企业中，要贯彻j i t 思想，建立高 效的生产供应链管理系统，准时配送是一个必不可少的方面，无论是原材料的供应，还 是产品的配送，都涉及到货物的配送。其次在服务行业中，要提升企业品牌，服务水平 就是一个很重要的方面，企业追求的目标是在保证服务水平的条件下，尽可能的降低物 流成本。以货运公司为例，为了提高企业竞争力，专业服务公司已逐步采用收货、送货 服务到家的经营方式。然而，传统经验表明，提高服务水平将导致成本增加而使利润降 低，要在保证服务水平的条件下降低成本，这就对配送运输提出了更高的要求。所以， 研究在企业物流系统中如何降低车辆空驶率、为车辆安排合理的运输路线具有很强的理 论价值和现实意义 ， 有关满载车辆的最短路径和关于非满载车辆的经典车辆路线问题( v e h i c l er o u t i n g p r o b l e m ，v r p ) 或是带时间窗的车辆路线问题( v e h i c l er o u t i n gp r o b l e mw i t h t i m e - w i n d o w s ，v r p t w ) 的研究无论是国外还是国内都比较多，很难再有大突破，那么 从其它角度来降低成本就成为对配送提出的新要求。在一般的车辆路线问题中，通常由 站点( d e p o t ) 派出一组车辆来服务一组顾客，顾客的需求只有单纯的集货( p i c k u p s ) 或是配送( d e l i v e r i e s ) 时，很明显，采用这种运输方式在回程或去程中车辆就为空载。 而如果用集成的观点同时考虑配送客户和集货客户，则能避免或减少车辆的空载里程， 提高车辆的实载率，于是利用回程车辆的空闲容量来降低成本，增加收入就成为人们新 的追求目标。提倡配送和集货一体化能为企业进一步降低成本、提高利润，为社会节约 资源，成为物流配送的又一发展目标 1 2 1 问题描述 1 2 问题概述 配送和集货一体化下的车辆路线问题( v e h i c l er o u t i n gp r o b l e mw i t hp i c k u p sa n d d e l i v e r i e s ，简称v r p p d ) 是指在为车辆指定路线的过程中，用相同的态度对待配送客 户( 需要货物的客户) 和集货客户( 供应货物的客户) ，而不是把这两者分开考虑，分 别派车，是经典车辆路线问题( v r p ) 当车辆不仅要为客户送货，还要从客户处把货物 带回站点( d e p o t ) 时的情形很显然，这样做可以提高车辆的实载率，因为如果车辆 进行单纯配送( 或单纯集货) 那么车辆路线中的装载量就越来越少( 或越来越多) ，在 回程( 或去程) 时就是空载，而如果同时进行配送和集货( 配送和集货一体化) 则能够 在很大程度上提高车辆实载率，节约运输成本。 1 2 2 应用范围 配送和集货一体化的应用范围很广，如“宅配便”是日本道路货物运输企业中的特 别混装货物运输企业，所谓特别混装货物运输企业，又可称为共同型配送企业，是指在 2 发货地，将货主各式各样的货物收集在货物集散站，再根据发送方向分拣、混合装载在 汽车上，在确定的线路上运输，到了终点的货物集散站，分拣货物，将货物送到收货人 手里。特别混装货物运输企业，是以不特定多数货主为对象，从事多对多的运输工作， 以运费和运送时间为主要因素的运输服务。可见，对于提供服务的第三方物流企业来说， 如果提倡配送和集货一体化，利用先进的信息平台就能够更迸一步地节约成本，提高服 务水平。又如制造企业，需要把原材料从供应商处运到仓库，同时又需要把生产出来的 产品配送到客户处；又如啤酒厂，需要把啤酒产品送到客户处，同时又需要把客户喝完 的空瓶回收到工厂；还有如纯净水厂，既要把纯净水送到客户处，又要从客户处带回用 完的空桶等。在上述这些情形中，采用配送和集货一体化的思想就能起到很大的节约成 本的作用。另外，在邮政系统中，如果能把取信送信、取包裹和送包裹看成一体、集成 操作，不仅能提高服务水平，而且能够降低运营成本。 配送和集货一体化的思想在国外已有一定的应用，有关研究也正在深入的进行，在 实际中的应用也正在扩展中。在该问题的一些初步尝试应用中，已经取得了明显的效果， 这对促进有关该问题的进一步深入研究起到了很大的作用。美国州际商业委员会新闻报 ( 1 9 8 0 ) 估算通过使用回程集货每年可节约的燃料为4 2 0 0 万加仑；k e a r n e y ( 1 9 8 4 ) 总结了 企业在1 9 7 8 年到1 9 8 3 年间为了提高物流的多样性而执行的项目，第一个项目就是协调 开出的车和返回的车从而提供自有车辆的回程集货，已被8 3 的支持者采用。y a n o 等 “”描述了以密歇根为中心的铁路链，近4 0 家商店和一个在托利多附近的配送中心的情 形，商店自有或租用了l l 辆货车，其载重量和容量是确定的，这些车是用来配送货物 到商店并从附近的供应商处收集货物，最后，所有配送中心的司机要在路线结束后回到 配送中心。在1 9 8 6 年用配送和集货一体化的思想为车辆分配路线，发现使用自有车辆 从供应商处集货比另外派车节约了4 5 0 ，0 0 0 美元。 物流业务的整合意味着物流技术的整合，在技术上实现各项业务的整合才能真正的 为社会、为企业节约资源，降低成本、提高利润，因此现代物流提倡配送和集货一体化 有着很大的应用空间和前景。 1 3 国内外研究动态 1 3 1 国外有关配送和集货一体化问题的研究 相对于众多研究w p 及v r p t w 问题的文献，研究v r p p d 问题的文献较少，而研究 3 v r p p d t w 的文献则更少此外，在许多文献中提到v r p b ( v e h i c l er o u t i n gp r o b l e mw i t h b a c k h a u l s ) 问题，其特点是回程收货的作业方式强调必须在所有需要配送的货物配送 完毕之后才可以开始集货，但当某个客户点同时有配送、集货需求时，将会造成对同一 客户点需要访问两次的现象，造成车辆资源的浪费；另外限制集货作业只能在配送作业 完成之后才能开始会导致车辆的路线规划缺乏弹性，可能会因为要满足这一约束，增加 运输的距离和成本。混合配送、集货作业类型的问题可分为两种类型的问题啕，第一种 是取消对先配送后集货的限制，但是在每一个客户点只进行单纯的集货或单纯的配送作 业；第二种是不仅取消对先配送后集货的限制，而且允许同一客户点同时有集货和配送 的需求。第一种类型的问题可以看成是第二种类型问题的特例，即客户点处的集货量或 配送量为零，但因第二种类型问题的复杂性，对其的研究还处于初步阶段，这方面的文 献资料相当少。 第一种类型的问题最早由g o l d e n 町等人( 1 9 8 5 ) 提出，在他们的假设中允许有集货 作业需求的客户点在有配送作业需求的客户点之前被访问，使用基于在收货客户 ( d e l i v e r y ) 的路线中插入送货客户( p i c k u p ) 的方法来求解该问题；另外c a s c o 啪1 等 ( 1 9 8 8 ) 利用c l a r k e 和w r i g h t ( 1 9 6 4 ) 吼1 所提出的节约法来构造有配送需求客户的初 始路径，有集货需求客户则是使用修改后的g o l d e n 等人( 1 9 8 5 ) 的插入法，其思路是 当剩余的配送量足够少时，才允许集货点插到配送点之前。 m i n ( 1 9 8 9 ) 蚴首次求解了第二种类型的问题，即当客户既是集货客户又是配送客 户时的情形。解决了如一个站点、两辆车和2 2 个客户的公众图书面临的实际问题。其 解法思路是首先把客户分组，接着求解每组的旅行商问题( 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 ) 。惩罚不可行弧( 把它们的长度设为无限大) ，然后再求解t s p s 。8 a l s e ( 1 9 9 2 ) 嘲 用先分组后分配路线的方法求解了该问题，首先把客户分配给车辆，接着在安排路线的 过程使用3 一o p t 方法优化。g e n d r e a u 等( 1 9 9 9 ) 洲研究了带取货和送货的旅行商问题 ( t s p p d ) ，首先在不考虑取货和送货的情况下求解t s p 问题，然后再在t s p 的路线中确 定取货和送货的次序。 1 3 a 国内有关配送和集货一体化问题的研究 国内研究该问题的文献也十分有限，只有少数几位学者对该类问题进行了研究郎 茂祥分别用模拟退火和禁忌搜索算法求解配送和集货一体化车辆路线问题以及带时间 窗的配送和集货一体化车辆路线问题，并给出了含有2 0 个客户点的实例及其计算结果 4 但是在其研究中只讨论了使用某一种启发式算法求解该问题的情况，没有充分考虑不同 算法的优缺点，也没有利用不同算法的优点，将两种或多种算法综合起来构造混合算法。 另外，在其求解的问题中，同一客户的配送和集货的时间是不一样的，这样每个客户必 须要访问两次，相当于每个客户只有单纯的集或配的需求，于是归为第一种类型的问题。 叶志坚等。1 提出求解配送和集货一体化车辆路线问题的索套启发式解法，该方法没有考 虑时间窗问题，。并且对一些集货量和配送量都很大的客户在路线开始阶段和结束阶段共 访问两次，显然，当集货量和配送量都很大的客户位于离站点较远的位置，用该方法求 解将导致车辆行驶路线迂回过多，其求解结果的质量就不高。 1 4 本文主要研究内容 本文的研究对象是经典车辆路线问题的一个扩展，考虑路线中的客户既需要货物又 供应货物的情形，并且考虑了在有时间窗限制下该问题的模型及其求解方法。在实际应 用中，对于单纯送货或单纯取货的客户，只需把模型中客户的取货量或送货量设为零， 就能使用本文提出的方法求解。 本文的第一章阐述了提高物流服务水平、降低物流成本的必要性和重要性，由此引 出了研究车辆路线问题的重要性及迫切性，并分析了在目前物流发展状况下，提倡配送 和集货一体化物流运作模式的重要意义。此外，还介绍了国内外相关问题的研究现状， 尤其是国内学者的研究成果，并指出其不足之处。 本文的第二章论述配送和集货一体化车辆路线问题的理论基础。介绍配送和集货的 概念，分析求解车辆路线问题这类组合优化问题的技术及各种求解方法的计算复杂性， 说明对于大规模问题，启发式算法是最合适的求解方法。此外，总结了一些常用的启发 式算法，并分析了各启发式算法的优势和不足，从而为本文所研究问题的算法设计奠定 了基础。 论文的第三章分析并建立了配送和集货一体化车辆路线问题的数学模型，设计并用 c 语言编程实现了求解该问题的启发式算法，给出了实例计算，分析、讨论并评价了该 算法的特点。 论文的第四章提出并建立了配送和集货一体化下有时间窗限制车辆路线问题的数 学模型，设计了求解该问题的混合遗传禁忌算法，确定了算法中的各算子及参数，用c 语言编程实现所设计的算法并给出算例与前人的研究结果进行比较，在此基础上通过试 验计算研究并分析算法中各算子及参数对解的质量的影响，从而证明本文设计算法的可 5 6 行性和有效性。 论文的第五章总结本文的主要工作和研究结论，并对需要进一步研究的问题进行简 要说明。 2 配送和集货一体化下的车辆路线问题研究的理论基础 2 1 概念 2 1 1 配送m 配送是物流中一种特殊的、综合的活动形式，是商流与物流紧密结合，包含了商流 活动和物流活动，也包含了物流中若干功能要素的一种形式：它是指在经济合理区域范 围内，根据用户要求，对物品进行拣选、加工、包装、分割、组配等作业，并按时送达 指定地点的物流活动。 从物流角度看，配送几乎包括了所有的物流功能要素，是物流的一个缩影或在某小 范围中物流全部活动的体现。一般的配送集装卸、包装、保管、运输于一身，通过这一 系列活动完成将货物送达的目的；特殊的配送则还要以加工活动为支撑，所以包括的方 面更广。但是，配送的主体活动与一般物流却有不同，一般物流是运输及保管，而配送 则是运输及分拣配货，分拣配货是配送的独特要求，也是配送中有特点的活动，以送货 为目的的运输则是最后实现配送的主要手段，从这一主要手段出发，过去常常将配送简 化地看成运输中的一种。 从经济学资源配置的角度，配送是以现代送货形式实现资源最终配置的经济活动。 第一，配送是资源配置的一部分，因而是经济体制的一种形式。第二，配送的资源配置 作用是“最终配置”，因而是接近顾客的配置。接近顾客是经营战略至关重要的内容。 美国兰德公司对幸福杂志所列的5 0 0 家大公司的一项调查表明“经营战略和接近顾 客至关重要”，证明了这种配置方式的重要性。第三，配送的主要经济活动是送货，这 里强调现代送货，表述了和我国旧式送货的区别，其区别以“现代”两字概括，即以现 代生产力、劳动手段为支撑的，依靠科技进步的，实现“配”和“送”有机结合的一种 方式。第四，配送在社会再生产过程中的位置是处于接近用户的那一段流通领域，是一 种重要的方式，有其战略价值。 从配送的实施形态角度，配送活动可定义为按用户订货要求，在物流结点进行货物 配备，并以最合理方式送交用户整个概念描述了接近用户资源配置的全过程。配送的 实质是送货，但和一般送货有区别；一般送货可以是一种偶然的行为，而配送却是一种 固定的形态，甚至是一种有确定组织、确定渠道，有一套装备和管理力量、技术力量， 7 有一套制度的体制形式。所以，配送是一种高水平的送货形式：配送还是一种“中转” 形式；配送是从物流结点至用户的一种特殊送货形式，是“配”和“送”有机结合的形 式，配送与一般送货的重要区别在于配送利用有效的分拣、配货等理货工作，使送货达 到一定的规模，以利用规模优势取得较低的送货成本配送以用户要求为出发点，在定 义中强调“按用户的订货要求”，明确了用户的主导地位，因此不能从本企业利益出发 而应从用户利益出发，在满足用户利益基础上取得本企业的利益。概念中“以最合理方 式”的提法是基于这样一种考虑：过分强调“按用户要求”是不妥的，用户要求受用户 本身的局限，有时在实际中会损失自我或双方的利益对于配送者讲，必须以“要求” 为据，但是不能盲目，应该追求合理性，进而指导用户，实现共同受益的商业原则。 合理的配送模式对于提高物流企业的经营水平，降低物流成本具有重要作用，我国 物流企业在发展的初期如何选择合适的配送模式对于企业的发展具有重要的意义。 2 1 2 集货 集货和配送的主体活动都包括运输，只是其在方向上相反。在本文中，集货是指运 输终点为企业的物资流，包括供应链上的采购物流和逆向物流等。采购物流是指将采购 的原材料、零部件由供应商处运入厂内，采购是企业物流的起始点，采购物流的科学管 理对于企业生产、运作的科学系统管理有着极其重要的作用。企业生产部门对采购物品 的要求不仅仅局限于数量方面，还有质量、性能与时间等方面的要求。时间要求是指当 生产需要某些物资时能够及时得到供应。采购部门为了满足这个需求，往往会采取大批 量采购的办法来应付，这样又造成了过高的库存水平和较高的资金占用。现代物流管理 要求做到准时化采购，即j r r 采购，基本原理是按照生产部门或客户的需求数量和时间， 及时安排采购计划，对于采购数量与采购时问，尽量做到既不要过量又不要提前，能够 准确及时地满足需要，最大限度地降低采购物资的库存水平。 逆向物流是指物资从产品消费点( 包括最终用户和供应链上的客户) 到产品来源点 的物理性流动。逆向物流由退货逆向物流和回收逆向物流两部分构成。首先，商品在出 售时商家需要向消费者做出保证，必须在承诺的范围内接受客户的退货其次，有些法 律规定，对某些饮料容器和包装材料禁止任意处理或鼓励回收，以至回收的数量不断增 加，最终导致逆向物流的增加。此外，回收用于运输的托板和容器( 如软饮料的包装瓶 和运输蔬菜、水果的托盘、纯净水桶、液化气瓶等) 也是逆向物流的重要组成部分。 逆向物流的重要性体现在下列几个方面 ， 8 逆向物流在促使企业不断改善品质管理体系上，具有重要的地位。企业在退货中 暴露出的品质问题，将透过逆向物流资讯系统不断传递到管理阶层，提高潜在事故的透 明度，管理者可以在事前不断的改进品质管理，以根除产品的不良隐患。 在当今顾客驱动的经济环境下，顾客价值是决定企业生存和发展的关键因素。众 多企业通过逆向物流提高顾客对产品或服务的满意度，赢得顾客的信任，从而增加其竞 争优势。对于最终顾客来说，逆向物流能够确保不符合订单要求的产品及时退货，有利 于消除顾客的后顾之忧，增加其对企业的信任感及回头率，扩大企业的市场份额。 传统管理模式的物料管理仅仅局限于企业内部物料，不重视企业外部废旧产品及 其物料的有效利用，造成大量可再用性资源的闲置和浪费。由于废旧产品的回购价格低、 来源充足，对这些产品回购加工可以大幅度降低企业的物料成本。例如佳能公司投入大 量财力、物力对使用过的设备进行再生产，并通过减少原料、回收、替代、再利用及处 置、清理等方法对保修期内的产品进行更换退回。 随着人们生活水平和文化素质的提高，环境意识日益增强，消费观念发生了巨大 变化，顾客对环境的期望越来越高。另外，由于不可再生资源的稀缺以及对环境污染日 益加重，各国都制订了许多环境保护法规，为企业的环境行为规定了一个约束性标准。 企业的环境业绩己成为评价企业运营绩效的重要指标。为了改善企业的环境行为，提高 企业在公众中的形象，许多企业纷纷采取逆向物流战略，以减少产品对环境的污染及资 源的消耗。 有效的逆向物流管理能够减少企业乃至整个供应链的运营成本，增加利润，改善企 业的现金流，提高客户服务质量，并为企业赢得信用和提高企业与品牌的形象。 2 2 组合优化和计算复杂性 2 2 1 优化技术和组合优化 优化技术是一种以数学为基础，用于求解各种工程问题优化解的应用技术，是一个 重要的科学分支，一直受到人们的广泛重视，在诸多工程领域得到广泛应用，如系统控 制、人工智能、模式识别、生产调度、v l s i 技术、计算机工程等领域。优化技术涉及的 领域、闯题种类和性质繁多，但总体来说可归纳为函数优化问题和组合优化闯题两大类， 其中函数优化的对象是一定区问内的连续变量，可称为连续优化，而组合优化的对象是 解空间中的离散的状态，也叫做离散优化。 9 组合优化是通过对数学方法的研究寻找离散事件的最优编排、分组、次序或筛选等， 是运筹学中的一个经典且重要的分支，所研究的问题涉及信息技术、经济管理，工业工 程、交通运输、通信网络等诸多领域伽 该问题可用数学模型描述为： m i n ，0 ) 一 s j 9 0 ) 之o ， 工d 其中，f 臼) 为目标函数，g 臼) 为约束函数，j 为决策变量，口表示有限点组成 的集合 、， 一个组合优化问题可用三参数( d ，f ，f ) 表示，其中d 表示决簧变量的定义域，f 表示可行解区域f p i 工d ，9 0 ) 对，f 中任何一个元素称为该问题的可行解，表 示目标函数，满足，g ) - m i n f ( 力i x f 的可行解胖称为该问题的最优解。组合优化 的特点是可行解集合为有限点集。由直观可知，只要逐一判别d 中有限点是否满足f “) 的约束条件并比较目标值的大小，就一定能得到该问题的最优解。因为现实生活中的大 量优化问题是从有限状态中选取最好的，所以大量的实际优化问题是组合优化问题。 典型的组合优化问题有旅行商问题( t s p ) 、背包问题( k n a p s a c kp r o b l e m ) ，装箱 问题( b i np a c k i n gp r o b l e m ) 、约束机器排序问题( c a p a c i t a t e dm a c h i n es c h e d u l i n g ) 、 图着色问题( g r a p hc o l o r i n gp r o b l e m ) ，聚类问题( c l u s t e r i n gp r o b l e m ) 等。 2 2 2 计算复杂性 ， p 2 2 2 1 算法复杂性 由组合优化问题的定义可知，每一个组合优化问题都可以通过枚举的方法求得最优 解。但是，枚举是以时间为代价的，有时枚举的时间是可以接受的，有时则是不能接受 的，那么对于复杂的组合优化问题有必要设计出好的求解算法。衡量一个算法的好坏通 常是用算法中的加、减、乘、除和比较等基本运算的总次数的二进制输入数据的大小关 系来度量。 ，一个算法的复杂性由该算法和实例在计算机计算时所需要的最大时间册最大存储 空间缓量。由于一个算法应用于一个问题的不同实例所需要的时间与空间是不相同的， 它们依赖于求解该实例时所需要输入数据的长度7 ，因此常将所需要的时间与空间表示 成刀的函数，记为“刀) 与以而。在求解同一个问题的不同实例时，即使要输入数据的 长度1 1 相同，算法所需要的时间与空间有时差异也很大，因此经常用平均时间复杂函数 亓而与平均空间复杂函数丽表示该算法计算这一问题的复杂性。 若按时间复杂性将算法分类，主要分为多项式时间算法和指数时间算法。多项式时 间算法是指时间复杂函数为d 伽) 的算法，当k = l 时，又称算法是线性时间算法；指数 时间算法是指时间复杂函数为o ( a ( 町) 的算法，其中口，1 。当疗很大时，不同类型算法 的复杂性可能差别很大。例如，若一台计算机每秒能执行1 0 6 条指令，当n = 1 0 6 时，若 “坊= i 7 ，则所需计算时间为1 秒；若“而= _ f 】2 ，则所需计算时间为( 1 0 * ) 2 1 0 6 秒，相当于 1 1 6 天：若，( 而= 2 8 ，则所需时间大约为3 1 0 “6 年。由此可见，设计算法要充分考 虑时间复杂性。当然，由于计算机存储空间的有限性，算法的空间复杂性也要充分考虑。 2 2 2 2 问题复杂性 如果一个问题的每一个实例只有“是”或“否”两种答案，则称这个问题为判定问 题。在研究组合优化问题复杂性时，处理的方法是对给定的一类优化问题，将其转化为 判定问题，使其对每一个实例只有“是”或。否”的回答。介绍一种理想的计算机，称 它为图灵机( t u r i n gm a c h i n e ) ，图灵机具有无限读写能力，并可做无限个并行操作。如 果该机每一步操作结果是唯一确定的，则称它为确定型图灵机；如果每一步操作结果或 下一步操作都可能有多种选择，则称该机为不确定型图灵机在确定型图灵机上可用多 项式时间解决的问题，被认为是易解问题，易解问题的全体称为确定型多项式时间可解 类，记为p 。不确定型图灵机工作分猜测与验证两个阶段，所谓一个问题在不确定型图 灵机上可用多项式时间解决，是指若图灵机猜测一个解，则它可以在多项式时间内验证 此解正确与否，并不是指图灵机可在多项式时间内求出正确的答案。在不确定型图灵机 上可以用多项式时间解决的问题，称为非确定性多项式时间( n o n d e t e r m i n i s t i c p o l y n o m i a l ，简称n p ) 可解问题。显然，p n p ，因为在确定型图灵机上多项式时间可 解的任何问题在不确定型图灵机上也是多项式时间可解的。 n p - - 完全问题( n p c ) 为n p 类中难度最大的问题，具有下列性质：这类问题中任 何一个问题至今未找到多项式时间算法；如果这类问题中的任何一个问题有多项式时 间算法，那么这类问题都有多项式时间算法。把这类问题记为n p c ( n p - - c o m p l e t e ) 。第 一个n p 完全问题由s a 库克在1 9 7 1 年提出，r 卡尔普等人求解了一系列基本的n p 完全问题。 判定问题a e n p c ，其定义为：a n p 且n p 中的任何一个问题可在多项式时间内归 约为判定问题a 。若n p 中的任何一个问题可在多项式时间规约为判定问题a ，则称a 为 1 1 n p 难问题或n p h a r d 问题。于是有n p c c n p h a r d ，n p c 和n p h a r d 两者的区别是n p h a r d 问题无须判断a 是否属于n p 。 验证一个问题a 是否为n p c 的关键有两点，一是n p 中的任何一个问题是否可在多 项式时间内归约为a ；其次，是否存在一个字符串和一个多项式时间的验证算法，其中 字符串的输入长度为实例输入长度的多项式函数当已知一个问题为n p c 或n p h a r d ， 再遇到一个新问题时，如果该问题可在多项式时间内归约为新问题，则可认为该问题属 于n p h a r d ；如果验证该新问题属于n p ，则该问题属于n p c n p 完全问题一定是n p h a r d ，但n p h a r d 问题不一定是n p 完全问题。以上所述四种问题的关系如图 1 所示。 2 3 1 启发式算法理论 图2 - 1 四类问题关系示意图 2 3 启发式算法 启发式算法和精确算法的不同之处在于启发式算法是通过对过去经验的归纳推理 以及试验分析，即借助与某种直观判断或试探的方法来求解问题，求得的是问题的次优 解；而精确算法主要包括运筹学内的各种算法，如分支定界法、动态规划法、穷举法等， 求得的是问题的最优解；但是精确算法计算量大，不适合求解大型问题。启发式算法求 解问题时强调“满意”，即在可接受的时间内去寻找最好的解，但不一定能保证所得解 的最优性，甚至在多数情况下，无法阐述所得解和最优解的偏离程度。 在某些情况下，特别是在实际问题中，精确算法的计算时间使人无法接受或因问题 难度使其计算时间随着问题规模的增加以指数速度增加，或从实际决策的需要出发，有 时要求解具有过高的精度没有意义，此时只能通过启发式算法求得问题的一个可行解。 启发式算法能够迅速发展是因为它有以下长处： 数学模型是实际问题的简化，忽略了一些因素，数据采集具有不精确性，参数估 计具有不准确性，这些因素可能使精确算法所求解比启发式算法所求解与实际情况有更 大的误差。 有些复杂的组合优化问题可能还没有找到精确算法，或者其计算时间不能接受。 有些启发式算法能在精确算法中应用，如在分支定界法中，可用启发式算法估界。 简单易行，比较直观；易被使用者接受。 速度较快，使决策者能迅速反应。 比较灵活，易于修改。 评价启发式算法的好坏，主要有以下几个标准。 解的质量，包括两个方面：目标函数值与最优值的偏离程度、算法产生可行解的 能力。 运行时间和所需存储量，启发式算法的好坏与求解问题的运行时间长短和运行时 所需的存储量大小密切相关。 实现难度，好的算法要易于实现，即容易编码。 灵活性，一个好的算法应该是具有适应性广和比较灵活的特点，即能够容易的处 理模型、约束和目标函数的变化。 简洁性和可分析性，算法应该能够用简洁明了的语言陈述出来，而且易于分析。 随着2 0 世纪8 0 年代初期一些新的启发式算法，如禁忌搜索、模拟退火、遗传算法 和人工神经网络算法等的兴起，科学工作者对这些算法的模型、理论和应用技术等一系 列问题进行着深入的研究，为解决复杂问题提供了新的思路和手段，并在诸多领域得到 了成功的应用。 2 3 2 相关算法介绍 2 3 2 1 初始解构造算法 初始解构造算法主要有c - - v 节约法、最邻近法、贪婪算法、空间填充曲线法 ( s p a c e f i l l i n gc u r v e s ，s f c ) 、扫描法等。 ( 1 ) 节约法o “ 节约法是由c l a r k e 和w r i g h t 在1 9 6 4 首次提出的，其基本原理是首先把各点单独 与站点相连，构成仅含一个点的路线，如图2 2 a ，从站点到两个客户位置并返回到站点 所需的行驶距离( 或费用) 为2 ( l i + l 3 ) 。如果连接两个客户( 如图2 - 2 b ) ，则所需的 行驶距离( 或费用) 为( l i + l 2 + l 3 ) ，则后者比前者节约( l 1 + l 3 一l 2 ) 。把这个值定义为 连接这两个点在一条路线中的节约值，节约值越大，说明把两条路线连接成一条路线后 节约的总路程( 或费用) 越多。路线的构造是根据节约值从大到小的顺序进行的，其具 体步骤如下： 1 ) 计算节约值； 2 ) 选择最大节约值，考察构成该节约值的两点j 和j 检查是否满足下列条件之一： 若1 和均不在己构成的线路上，则可连接j 和得到线路o f 一产0 ，0 表 示站点，转步骤3 ) ； 若f 或在已构成的路线上，但不是路线的内点，则连接f 和二得到路线o j 一产0 或0 。彳一产0 ，转步骤3 ) ； 若，和，在已构成的路线上，但均不是内点，则连接后得到路线o - f 一户一 一o ，转步骤3 ) ； 否则不能连接j 和二直接转步骤3 ) ； v 一謦 a b 图2 2 3 ) 删除这个节约值；+ 4 ) 若所有节约值都被删掉，则已得到最终构造的路线，算法终止，否则转步骤2 ) 。 节约法属于逐次逼近法的一种，用这种方法不一定能求得最优解，但是可以高效的 得到问题的近似最优解。该方法具有计算步骤简单，计算速度较快，且易于考虑各种实 际问题等优点；缺点是未组合点零乱、边缘点难于组合以及有时解的质量不高等。 ( 2 ) 最邻近法 这种方法可能是最简单、最直观的路线构造启发式算法。其主要思想是：总是访闯 离当前所在点最近的点。其主要步骤如下： 1 ) 取站点0 开始作为路线的起点； 2 ) 寻找和上一次加进路线的点距离最近的点，把此点加到路线中；若违反问题约 束则返回站点，转步骤1 ) ； 3 ) 重复步骤2 ) ，直到