（电工理论与新技术专业论文）基于蚁群算法的烟草配送优化调度的研究.pdf

a bs t r a c t t h ec i g a r e t t eo fo u rc o u n t r yh a sam o n o p o l yi nt h ep a r t i c u l a r i t yd e a l t e x c l u s i v e l ya n de n o r m o u sv o l u m eo fc o n s u m p t i o nt ot h ec i g a r e t t e ，a n d t h ec i g a r e t t ev e h i c l ed e p l o y m e n tq u e s t i o np r o v i d e sa n dd e l i v e r st h ek e y q u e s t i o ni nt h es y s t e ma st h et o b a c c ol o g i s t i c s ，h a v ei m p o r t a n tr e s e a r c h a n du s i n gv a l u e p a p e r sf o rt h et o b a c c od i s t r i b u t i o nl o g i s t i c sd i s t r i b u t i o n c e n t e rp a t ho p t i m i z a t i o np r o b l e m s ，b a s e do na n tc o l o n ya l g o r i t h mt o i m p r o v e t h ed i s t r i b u t i o no ft h eo p t i m i z e ds c h e d u l i n gm e t h o d p a p e rd e s c r i b e st h em e c h a n i s mo fa n tc o l o n ya l g o r i t h mt h e o r ya n d p r i n c i p l e so ft h es y s t e m ，f r o md i s t r i b u t e dc o m p u t i n g ，s e l f - o r g a n i z a t i o n ， p o s i t i v ea n dn e g a t i v ef e e d b a c kh a sd o n ead e t a i l e di n t r o d u c t i o n p a p e r s w il lb es i n g l e l o o pp a t ho ft h ec h o i c eo fd i s t r i b u t i o nr e d u c e dt oas i n g l e 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 ) i ss o l v e d ，c o m b i n e dw i t ht h eb a s i c p r i n c i p l e o fa n t c o l o n ya l g o r i t h mw i t ht h em o d e l ，as i n g l e l o o p d i s t r i b u t i o no fa n tc o l o n yo p t i m i z a t i o np r o b l e mt h r o u g hc o m p a r es e l e c t e d s i m u l a t i o nr e s u l t st h eb a s i ca n tc o l o n ya l g o r i t h mi nt h ei n i t i a lp a r a m e t e r s ， t h eb a s i ca n tc o l o n ya l g o r i t h mf o rt h es l o wc o n v e r g e n c ea n de a s yi n t ot h e s h o r t c o m i n g so fl o c a lo p t i m u m ，a ni m p r o v e da n tc o l o n ya l g o r i t h m i m p r o v e da l g o r i t h mf o rt h em a x - m i na n ta l g o r i t h mf r o mt h eu s eo f r e s t r i c t i o n so nt h es c o p eo ft h ei d e ao f p h e r o m o n e s ，t h es h o r t e s tp a t ha sa r e s u l to fi n h i b i t i o na n di n c r e a s e dt h eg a pb e t w e e nt h el o n g e s tp a t ho ft h e a m o u n to fi n f o r m a t i o na r i s i n gf r o mt h ep h e n o m e n o no fs e a r c hs t a g n a t i o n ； a tt h es a m et i m e ，t h ei n t r o d u c t i o no fp h e r o m o n e p r o l i f e r a t i o ns t r a t e g y a n dt oi m p r o v et h eo v e r a l ls i t u a t i o no fp h e r o m o n eu p d a t em e c h a n i s m ，t o e f f e c t i v e l yc o n t r o lt h ep h e n o m e n o no fp r e c o c i o u sp u b e r t y , s ot h a tf a s t e r c o n v e r g e n c ea l g o r i t h mt oa p p r o x i m a t et h eg l o b a lo p t i m a l 堂l u t i o 坠t h e i s s u eo ft h r e et s ps i m u l a t i o nt e s ts h o w st h a tt h ep r o p o s e da l g o r i t h mi n t h es e a r c hc a p a b i l i t i e sa n dp e r f o r m a n c eh a v eb e e ni m p r o v e ds i g n i f i c a n t l y p a p e r sw i l l a l s ob e i m p r o v e da n tc o l o n ya l g o r i t h ma p p l i e dt o m u l t i - l o o pv e h i c l es c h e d u l i n gp r o b l e m ，t h ee s t a b l i s h m e n to fam u l t i - l o o p m a t h e m a t i c a lm o d e lo ft h ev e h i c l es c h e d u l i n gp r o b l e m ，t h ep r o b l e mw i t h t h et s pa n a l y s i so ft h es i m i l a r i t i e sa n dd i f f e r e n c e sc o m p a r e dt ot h e l i a p p r o x i m a t es o l u t i o no ft h em o d e lp r o p o s e da c q u i s i t i o ns t r a t e g y , g i v e n t h em u l t i - l o o pv e h i c l es c h e d u l i n gp r o b l e mo fa n tc o l o n ya l g o r i t h mt o i m p r o v et h ei m p l e m e n t a t i o no fs p e c i f i cs t e p s ，a n dt h r o u g hac i t yi nt h e t o b a c c od is t r i b u t i o np o i n t2 0o ft h ee x a m p l e so fs o l v i n gt h em o d e l ，t h e v a l i d i t yo ft h ea l g o r i t h mi nm u l t i l o o pa p p l i c a t i o n s ，v e h i c l es c h e d u l i n g p r o b l e mo ft h ev a l i d i t y k e y w o r da n t c o l o n yo p t i m i z a t i o n ，m a x - m i na n t c o l o n y a l g o r i t h m ，t s p 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢 的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不 包含为获得中南大学或其他单位的学位或证书而使用过的材料。与我 共同工作的同志对本研究所作的贡献均已在论文中作了明确的说明。 作者签名：岔旦圭豳日期：型年上月丝日 学位论文版权使用授权书 本人了解中南大学有关保留、使用学位论文的规定，即：学校 有权保留学位论文并根据国家或湖南省有关部门规定送交学位论文， 允许学位论文被查阅和借阅；学校可以公布学位论文的全部或部分内 容，可以采用复印、缩印或其它手段保存学位论文。同时授权中国科 学技术信息研究所将本学位论文收录到中国学位论文全文数据库， 并通过网络向社会公众提供信息服务。 作者签名：盘旦! 塑导师签名监日期：捌年月翌日 硕士学位论文第一章绪论 第一章绪论弟一早瑁比 我国2 0 0 1 年4 月1 7 日颁布的物流术语国家标准定义：物流是“物品从 供应地向接收地的实体流动过程。根据实际需要，将运输、储存、搬运、包装、 流通加工、配送、信息处理等基本功能实施有机结合。”可见，物流活动提供的 是一种以运输、储存为主的，多种功能相结合的服务活动【i l 。 跨入新世纪，世界前1 0 强物流公司纷纷进军中国，迅速在大城市布点，抢 占中国物流市场，力争在新一轮的竞争中抢先一步。中国现代物流业以强劲的态 势快速发展，给传统产业尤其是我们烟草行业也带来了变革的契机。如何抓住这 一有利时机，在“夕阳产业”发掘“朝阳产业”的潜质，实现行业整体的改造升级， 成为摆在烟草行业面前的一个重要课题。 1 1 烟草物流的概况 1 1 1 烟草物流相关概念论述 我国烟草物流的运作对象及主体。我国烟草物流的运作主要由烟草物流运作 对象和运作主体构成。烟草物流运作对象包括卷烟和其上游原料烟叶及辅料等原 材料，其中卷烟是主要部分。而运作主体方面，我国卷烟物流运作主体有三类： 生产商、经销商及烟草物流企业。其中，烟草物流企业是指专门从事烟草物流的 第三方物流企业。目前，这类企业还比较少，提供的物流服务业务主要集中在区 域配送方面【2 j 。 烟草物流，从运作对象来划分，可将烟草物流划分为烟草生产环节物流和烟 草流通环节物流。生产环节物流是指以生产卷烟所需的上游原料烟叶及辅料等原 材料为运作对象，以卷烟生产企业为主体所对应的生产经营活动的物流，这种物 流有四个子系统，即供应物流子系统、生产物流子系统、销售物流子系统及废弃 物物流子系统。流通环节物流是指以卷烟为运作对象，以烟草专卖局、各级烟草 公司和零售户为运作主体，将卷烟送到消费者手中的物流。本文所分析的活动构 成要素是针对烟草商业物流活动。 硪国加入w t o 以来，市场经济体制不断深入发展并日趋完善，同时中国烟 草行业的改革逐步深化，传统的流通模式越来越不能适应新形势的要求，烟草流 通企业纷纷准备或开始筹建物流配送中心，以降低成本，提高服务质量和水平， 扩大经营规模，改进物流与信息流系统。 2 0 0 5 年4 月，国家烟草专卖局国烟办下发了 2 0 0 5 2 1 5 号文件一一全国卷 烟销售网络建设整体推进、全面提升的工作方案。“整体推进、全面提升”工作 硕士学位论文第一章绪论 精神中对烟草物流配送提出了明确的要求，归结起来就是要实现“五化管理”， 即：仓储管理数字化、卷烟库存合理化、卷烟分拣电子化、配送线路最优化、车 辆配载经济化【3 j 。 目前，国内外对卷烟生产环节的物流系统自动化和信息化技术研究比较深 入，也初步形成了一套系统的理论研究方法，但是对于烟草销售商业环节的物流 系统自动化和信息化的研究却是仍然处于起步阶段。因此，烟草商业系统现代物 流自动化和信息化建设成为了摆在烟草系统面前的一项紧迫任务，能否建立套 适用的高效的现代化物流系统，将直接决定烟草商业系统能否长期持续稳定发 展。 卷烟车辆调度问题作为烟草物流配送系统中的核心问题，具有着重要的研究 及应用价值，而且由于我国卷烟专卖专销的特殊性和对卷烟的巨大消费量，造成 了我国各地销售状况都具有一定的特殊性，国外的一些车辆调度系统往往不适用 于我国的现状，而目前我国的卷烟配送研究仍处在起步阶段，学者对于此块问题 的关注并不多，多数车辆调度配送系统是根据国外分拣系统或者邮政物流配送系 统改造而来，均不同程度存在着不适应卷烟合理配送的问题。因此，能否针对我 国卷烟配送的实际情况，研究解决适用于我国卷烟商业行业的新型卷烟物流配送 系统就成了制约卷烟商业系统物流配送发展的重要问题。 1 1 2 发达国家卷烟物流自动化发展现状 在欧美和日本等发达国家，卷烟物流的自动化程度相当高，他们的烟草物流 中心一般占地面积不大，但立体化和自动化程度较高，他们普遍采用自动立体化 仓库进行卷烟的存储和出入库；卷烟分拣普遍采用自动化程度相当高的分拣设备 进行作业，在他的一个物流中心中，需要人工进行的作业很少，基本都有计算机 和各种自动化设备来完成。 例如日本的东京烟草物流中心，位于东京千叶县船桥市，占地面积2 7 3 8 3 平方米，建筑面积1 1 3 7 3 平方米，共4 层，总楼层建筑面积4 2 0 1 9 平方米。 该配送中心是一个精密、快速、无人化、综合了高科技的自动化物流中心。 每天来自全日本香烟制造公司和保税仓库的6 0 辆大型货车的香烟，通过高级计 算机的处理和自动化设备的作业，从入库到出库，物流量的9 0 完全实现自动化 处理。平均一年处理六百亿支香烟，为三万个香烟零店配送货品。每天出车数量 高达一万多辆车，对这一万多辆车做个详细规划方案及恰当的路径线路图对于该 配送中心是一个十分庞大繁重的任务，应用改进策略简化这一繁重任务，对于简 化工作量来说一个十分有意义的工作。 就目前来讲，发达国家的卷烟物流正向着更加自动化、更加集约化、更加及 2 硕士学位论文第一章绪论 时化和更加经济化的方向发展，真正的是卷烟物流配送成为烟草行业的第三利润 源，成为为优质客户服务的窗口。 1 1 3 卷烟物流车辆调度的发展情况 烟草物流在我国尚处于起步阶段，据商务部统计，在我国大部分的烟草企业 当中，原材料物流的3 6 和4 6 是由企业自身和供应商承担的。在产成品物流中， 由企业自营或企业与第三方物流企业共同完成的比例分别是2 4 和6 0 ，完全由 第三方物流企业承担的仅占1 6 。不过由于烟草行业的特殊性，烟草物流在我国 的综合物流业当中属于发展相对比较规范的一个行业。对于烟草制造业来讲，他 们己经在上个世纪9 0 年代末基本上完成了企业的生产物流体系的建设，实现了 卷烟生产物流的自动化和信息化；但是对于烟草商业系统来说，物流系统的建设 滞后了一些，在2 0 0 0 年之后才开始受到重视，由于烟草商业系统遍布全国，而 且各地的发展差异很大，因此，烟草商业系统的物流系统建设存在着严重的不均 衡性。目前，在全国的地市级的烟草商业系统中，大多数还没有实现物流作业的 机械化，对于在商业物流系统中，最关键的物流环节一一车辆配送，仍然大量的 停留在按经验选择的模式上，有一部分虽然己经实现了车辆配送的系统话，但也 只是简单的按照往常经验来派送车辆，存在较大的局限性。目前，实现物流系统 自动化程度较高的地市也只有上海、北京、深圳、青岛、大连等少数中心城市， 而对于一些较小城市的车辆调度路径选择则是完全凭经验摸索，因此对于车辆路 径选择问题的研究对于解决我国烟草物流配送过程中遇到的路径选择难题有十 分重要的意义。 不过，随着计算机网络普及和信息技术的不断进步，为适应形势的发展，物 流企业逐步整合现有资源，统筹信息平台，运用越来越多的现代物流技术，如 g i s 、g p s 、e d 、条码等等，为客户提供系列化、个性化、信息化的综合物流服 务。国外的烟草物流在这方面已经取得了显著的成绩，仅仅就r f i d 而言，已经 成为烟草物流技术突破的一道“利器”。如：美国t r i c o n 公司足r f i d 解决方案 的最大供应商，在烟草物流行业中已经取得了相当叮观的业绩。它向烟草企业提 供包括烟叶追踪管理、非烟草材料追踪、n 1 、m 货盘追踪管理以及过滤盘及纸箱跟 踪等技术服务。在这螳用途当中，有许多都给材料供应商带来了额外的好处一一 可追踪性、操作规范望求和供应链效率提高不仅可以降低供应商的成本，而且最 终也会体现在卷烟制造商成本的降低上。 虽然我国烟草物流近些年来的发展速度非常快，但观念滞后、成本居高不下、 数字鸿沟、终端所有权困扰、资源流失、人才匮乏等因素成为烟草物流业对新技 术的应用和营销网络健康发展的严重制约。烟草物流改革和创新成为必然趋势， 3 硕士学位论文第一章绪论 整合资源、构筑创新体系、完善体制机制、强化应用技术研究和培养及提升创新 能力成为烟草物流未来发展的重点。国家为此进行了一系列的努力，计划通过重 点发展连锁经营、物流配送和电子商务，大力推进流通现代化，以应对经济全球 化挑战，扩大内需，拉动国民经济持续快速健康发展，并把烟草行业确定为推进 流通现代化发展的重点。国家烟草专卖局所积极推广的“全面访销、全面配送、 访送分离、专销结合的现代物流管理模式就是一个很好的例子。 随着用户需求向小批量多样化方向发展，物流中心配送货品的种类和数量急 剧增加，车辆路径的选择在物流配送中的作用更加日趋重要，成为最耗费脑力和 时间的作业。 1 1 4 物流业进入十大产业振兴规划 国务院总理温家宝2 月2 5 日主持召开国务院常务会议，审议并原则通过物 流业调整振兴规划，促进我国物流j 平稳较快发展。 会议上提出了，物流j l 眨足融合运输、仓储、货运代理和信息等行业的复合型 服务产业，涉及领域广，吸纳就业人数多，促进生产、拉动消费作用人。但是我 国物流业总体水平落后，严重制约隧民经济效益的提高。必须加快发展现代物流， 建立现代物流服务体系，以物流服务促进其他产业发展。一要积极扩大物流市场 需求，促进物流企业与生产、灏贸企业互动发展，推进物流服务社会化和专业化。 二要加快企j i k 兼并重组，培育批服务水平高、国际竞争力强的大型现代物流企 业。三要推动能源、矿产、汽车、农产品、医药等重点领域物流发展，加快发展 国际物流和保税物流。四要加强物流基础设施建设，提高物流标准化程度和信息 化水平。 会议还确定了振兴物流业的九大重点工程，包括多式联运和转运设施、物 流园区、城市配送、大宗商品和农村物流、制造业和物流业联动发展、物流标准 和技术推广、物流公共信息平台、物流科技攻关及应急物流等。会议最后要求， 各地区、各有关部门要加强组织泌调，深化物流管理体制改革，完善政策法规体 系，多渠道增加投入，加快物流人才培养，促进我国物流业平稳较快发展。 1 2 烟草商业物流活动构成要素 1 2 1 烟草物流企业活动构成要素 一般来说，企业物流活动的构成要素有六个，运输、储存、包装、搬运、流 通加工、信息处理。运输是用设备和工具将物品从一地点向另一地点运送的物流 活动。储存是指保护、管理、贮藏物品。包装是为在流通过程中保护产品、方便 4 硕士学位论文第一章绪论 储运、促进销售，按一定技术采用的容器、材料及辅助物等的总体名称。搬运是 在同一场所内，对物品进行水平移动为主的物流作业。流通加工物品在从生产地 到使用地的过程中，根据需要施加包装、分割、计量、拴标签、组装等简单作业 的总称。信息处理总是基于一个或者多个信息系统完成的。物流信息系统是其中 之一，它是指由人员、计算机硬件、软件、网络通信设备及其它办公设备组成的 人机交互系统，其主要功能是进行物流信息的收集、存储、传输、加工整理、维 护和输出，为物流管理者及其它组织管理人员提供战略、战术及运作决策的支持， 以达到组织的战略最优，提高物流运作的效率与效益。还包括订单处理系统，销 售系统等。1 9 9 9 年，上海烟草公司逐渐推行了“以电话订货、网上配货、电子结 算、现代物流为手段，以标准化、程序化、信息化管理为内容，以客户满意为追 求”的新的业务模式。它体现了现代流通的本质特征，也代表着中国烟草网建的 发展方向。随后，国家在全国逐渐推行这一新模式，加快传统商业向现代流通的 转变。以电话订货、网上配货、电子结算、现代物流”具体内容是：电话订货。 电话订货就是由烟草公司客户服务中心的电访员主动拨打零售户电话，获取订 单。然后将订单输入微机控制系统，传达到网上结算系统执行扣款，然后由配送 部门按订单进行配送。网上配货。网上配货是通过在零售客户中安装p o s 收银 机，并与有限公司后台联网通讯，从而实现订单的快速获取和配送的自动服务。 电子结算。网上结算系统与银行帐户通过一定方式联网，所有客户订单集中通过 网上结算系统进行扣款操作，一次性将所有订单金额从相应客户的账户中划转。 现代物流。即利用物流中心将信息流、商流和物流三方面资源综合利用起来。 而对于烟草物流来说，烟草商业企业即烟草公司都会建立自己的物流中心， 但这并不代表物流中心就完成了烟草商业物流的全部作业环节。按照目前的烟草 公司的组织结构来看，订单处理环节是由营销中心的订单部来完成的。在储配部， 需要完成的物流活动有装卸搬运、分拣到户、送货。为了在送货过程中能提高送 货效率、保护卷烟、减少差错率，在分拣到户过程中，每完成一户零售户所需卷 烟的分拣就要对这些卷烟进行一次二次包装。最后将这些按户分拣完毕的卷烟装 车，并运送到客户手中。 从上述流程，可将企业一般物流活动构成要素进行细分和具体化，从而得出 烟草商业物流活动构成要素由八个部分组成，分别是卷烟分拣、送货、仓储、二 次包装、装卸搬运、订单处理、信息处理、电话订货。对于进行人工分拣的烟草 公司还会增加流通加工这个部分，即贴激光防伪标签。其中卷烟分拣、送货和仓 储是中心要素。 5 硕士学位论文第一章绪论 1 2 2 烟草配送流程 按照国家局卷烟网络建设规范的要求，目前各烟草分( 市) 公司的卷烟营销基 本上都是采取的是“电话访销、集中物流、分散配送 的方法。在烟草行业“国 家利益至上、消费者利益至上”的共同价值观指导下，我们必须为每一个零售客 户的提供服务。 目前各商业企业主要的配送流程是：送货的线路、送货顺序、送货周期根据经 验提前确定，并且相对稳定；根据不同的送货线路和送货周期集中采集订单( 呼叫 中心) ，通过信息系统传至物流中心；物流中心按照客户送货顺序分拣到户并装车 送货到户。流程如下图： r 。_ 1r 1 广。_ 1 i 送货线路卜_ 1 订单获取h 订单配送l i _ ji 一j1 _ j 图1 1 物流配送流程 从目前国内烟草配送技术的应用情况来看，送货路线的改造对于这一流程中 有重要的意义，但根据经验提前确定，大部分的烟草物流从安全角度考虑，应用 只单纯的利用了g p s 技术实现了查询烟草物流配送车辆的位置、轨迹，对于干 线运输来说，基本可以满足要求，但是对于烟草访销配送最基层地市烟草公司， 特别是适应城网和农网烟草大集中的多点配送应用来说，只知道车的位置是远远 不够的。合理的配送线路优化和按动态烟草定单配载，将直接提高配、运效率， 大大降低烟草物流成本。 能够提出完整的多点物流配送算法的专业公司也非常少，原因是开发商只有 经过长期的积累才能了解烟草及物流行业相关复杂的业务和管理流程，而一些物 流软件开发公司虽然对物流的环节比较熟悉，但是对优化算法及改进技术方面比 较陌生，而城市多点物流配送的算法很难和这两方面脱离开。所以造成以前没有 太多公司能提供完善而成熟的烟草多点物流配送算法模型。 1 3 烟草配送车辆调度优化的研究现状 按照行业的要求，各商业公司每年必须对物流配送线路优化两次以上( 行 业网络建设规范) ，不得不在低水平上重复劳动。而在烟草物流配送实际工作 中又存在着下文中所述的一些问题，因此应用优化算法对于车辆调度问题进行改 进研究十分有必要。 1 3 1 车辆调度问题的分类 车辆调度是物流管理最重要的部门。随着社会的发展以及消费者对服务质量 6 硕士学位论文第一章绪论 要求的不断提高，高效的车辆调度，以提高物流效率、降低物流成本、提高服务 质量对于促进经济健康稳定的发展具有重要意义。所谓的车辆路径问题，就是车 辆和路径的恰当选取，运输规划的合理制定问题。解决此问题，可用加快对客户 需求的响应速度，提高服务质量，增强客户对物流环节的满意度，降低服务商运 作成本。现代物流的基本涵义为“按用户要求，将物的实体从供应地到需求地转 移的过程”。深入分析物流问题，大部分都可以归类为车辆路径调度问题或者说 车辆路径调度问题在物流配送中占有绝对重要的地位，除了铁路、公路等运输业， 装卸、配送等也可以归类为车辆路径一调度问题的有机组成部分。目前，我国物 流产业效率较低，损失浪费十分惊人，有专家估计，我国仅汽车空驶率就达3 7 ， 相当于1 5 0 万辆载重汽车来回空跑。由此可见，车辆路径调度问题能否较好解决， 直接关系到企业的经济效益，影响我国整个物流产业的健康迅速发展。在竞争日 益激烈的今天，企业只有以市场为核心去适应不断变化的环境并及时对市场作出 反应，以低的成本、快的速度，在正确的时间和地点为消费者或用户提供满意的 产品和服务，才能在竞争中占有优势。产品分销渠道的优化是达到上述目标的关 键步骤之一。分销渠道是指产品在其所有权转移过程中从生产领域进入消费领域 的途径，而分销渠道中的物流管理则是指通过有效地安排产品的仓储、管理和转 移，使产品在需要的时间到达需要的地点的经营活动。实际也是车车辆路径问题， 或者称车辆路径调度问题、车辆安排问题等，是现代物流研究中的一项重要内容。 物流配送车辆优化调度问题最早是由d a n z i g 和r a m s e r 在1 9 5 9 年首次提出的， 称之为v e h i c l er o u t i n gp r o b l e m ( 简称v r 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 r p 的一个特例。t s p 和v r p 的相关研究成果对于研究车辆调度问题具有重 7 硕士学位论文 第一章绪论 要的参考和借鉴作用。下面将分别对t s p 和v r p 问题进行简单概述。 优化配送路径问题类似“旅行商( t s p ) ”问题，最早是由d a n t i z g 和r a m s e r 于1 9 5 9 年首次提出。一般指的是：对系列发货点和收货点，调用一定的车辆， 指定适当的行车路线，使车辆有序的访问它们，在满足特定的约束条件下( 如： 货物的需求量与发货量、交发货时间、车辆载重限制、行驶里程限制、行驶时间 限制等) ，力争实现一定的目标( 如：车辆行驶里程最短、运输总费用最低、车 辆按一定时间到达、使用的车辆数最少等) 。由于这一问题的理论涉及多学科， 而且很多实际问题的理论抽象都可归结为这一类问题，所以很快便引起物流科 学、应用数学、图论与网络分析、运筹学、交通运输工程、管理科学与工程、计 算机应用等学科的专家的极大重视。从应用方面看，物流配送路径优化，是物流 配送优化中的一环，也是电子商务活动不可缺少的内容。对货运车辆进行路径优 化，可以提高物流经济效益，实现物流科学化。对货运车辆路径优化理论与方法 进行系统研究是物流集约化发展、建立现代调度指挥系统发展智能运输系统和开 展电子商务的基础。优化配送路径问题是n p 难问题，一般无法给出最优解，研 究者们努力的目标是尽量逼近最优解。因此优化配送路径问题是一个十分有应用 价值的问题【4 j 。 单回路车辆循环问题( 旅行商问题) 问题在物流中的描述是对应一个物流配 送公司，欲将n 个客户的订货沿最短路线全部送到。如何确定最短路线。t s p 问 题最简单的求解方法是枚举法。它的解是多维的、多局部极值的、趋于无穷大的 复杂解的空间，搜索空间是n 个点的所有排列的集合，大小为( n 一1 ) ! 。可以 形象地把解空间看成是一个无穷大的丘陵地带，各山峰或山谷的高度即是问题的 极值。求解t s p ，则是在此不能穷尽的丘陵地带中攀登以达到山顶或谷底的过程。 多回路运输问题( v r p ) 在物流中的解释是对一系列客户的需求点设计适当的路 线，使车辆有序地通过它们，在满足一定的约束条件下，如货物需求量、发送量、 交发货时间、车辆载重量限制、行驶里程限制、时间限制等等，达到一定的优化 目标，如里程最短、费用最少、时间最短，车队规模最少、车辆利用率高。 v r p 问题和t s p 问题的最大区别在于：客户群体的数量大，只有一辆车或一 条路径满足不了客户的需求，必须是多辆交通工具以及运输工具的行车顺序两个 问题的求解。相对于t s p 问题，v r p 问题更复杂，求解更困难，但也更接近实际 情况。 1 3 2 车辆调度问题研究的文献综述 由于情况的不同，v r p 数学模型的构造及求解算法也有较大的差别。目前 有关v r p 模型的研究已经取得了大量的成果1 5 1 。综合过去的相关研究，v r p 模 8 硕士学位论文第一章绪论 型基本可以分为图模型、数学模型和仿真模型【6 l 。v l 冲的求解算法非常丰富，基 本可以分为精确算法和启发式算法两大类。求解v r p 的启发式算法有不同的分 类方法。本文参考l a p o r t e 和s e m e t 的分类方法【7 1 ，将启发式算法进一步分为经 典启发式算法( c l a s s i c a l h e u r i s t i e s ) 和元启发式算法( m e t a - h e u r i s t i e s ) 。 精确算法主要针对v 好图模型和数学模型的求解方法，在这方面代表性的 算法有分支定界法、树状寻优算法、动态规划、整数规划等。具体研究成果主要 有：f i s h e ：提出的k 树澍引、m p a d b e r g 等的分枝剪枝法【9 】、c h r i s t o f i e s d s 等用动态 规划放宽空间变量解决v r p i m 】、f u m e r o 等的修正拉格朗日松弛及子梯度优化方 法【1 、l o r e n al u i z 等对列生成法的改进等【1 2 】。精确算法虽然有着悠久的发展历 史，而且在实际应用中广泛，但是其过于拘泥于数学抽象，人们对这种逻辑模型 很难获得系统的真实感受，因此虽然精确算法可以求得最优解，但不便于对实际 系统进行分析。同时随着现代物流系统规模的不断扩大，在运用精确算法建立表 达式时，如果单纯依靠实际情况，往往要列出数目众多的限制条件，这将使得求 最优解的过程变得非常复杂甚至根本求不出最优解。精确算法由于引入严格的数 学方法，因而无法避开指数爆炸问题，从而使这类算法只能有效求解中小规模的 v i 冲。 因此v r p 求解虽然存在着精确算法，但其求解效率不高，所以寻找近似算 法就变得非常必要，在这种背景下，启发式算法成为研究并解决该问题最有效的 一种途径。 ( 1 ) 传统启发式算法 传统启发式算法主要包括：路径构造启发式算法和路径改进搜索的启发式算 法，其中，路径构造启发式算法主要包括节约法( s a v i n gm e t h o d ) 1 1 3 】、扫描法 ( s w e e p i n g ) 1 1 4 】、最邻近法( n e a r e s t n e i 曲b o r ) 1 1 5 】、插入算法( i n s e n i o n ) i1 6 1 等；路径改 进搜索的启发式算法主要包括k - o p t t l l 7 】【1 引、2 - o p t * t 19 1 、e j e c t i o nc h a i n s l 2 0 1 、 c r o s s e x c h a n g e 2 1 1 、o r - o p t l 2 2 】等 ( 2 ) 现代启发式算法 现代启发式算法有一些共同的特点f 2 3 ) 它们大都引入了随机因素，因此具 有不确定性，不少计算过程实际上是在计算机上作随机过程的模拟；( 2 ) 它们大都 具有自适应机制，在计算过程中体系结构在不断地进行调整；( 4 ) 它们都是针对通 用的= 般目标而设计的，它们不同于针对特殊问题而设计的算法。现代启发式算 法主要包括一些人工智能算法，如：禁忌搜索算法( t a b us e a r c h ，t s ) 2 4 】、模拟退 火算法( s i m u l a t e da n n e a l i n g ，s a ) 2 5 】、遗传算法( g e n e t i ca l g o r i t h m ，g a ) 1 2 6 】，粒 子群算法( p a r t i e l e s w a n n o p t i m i z a t i o n ，p s o ) 【2 7 】，蚁群算法( a n tc o l o n ya l g o r i t h m ， a c a ) 例及人工神经网络算法( a n i f i c i a ln e u r a ln e t w o r k ，a n n ) 。 9 硕士学位论文 第一章绪论 基于本文研究对象，本文将对蚁群算法求解v r p 及t s p 问题作重点介绍。 1 4 烟草物流配送存在的问题及研究内容 1 4 1 烟草物流配送存在的问题 通过对某市烟草公司2 0 0 0 年以来的经营数据统计情况看，旺季平均每天送 货量很大，淡季每天送货量也不小，卷烟需求分布的不平均性，给日常线路的选 择带来诸多问题，不管该线路需求的多少，每天都固定出车来保障工作完成，这 样的工作安排方式存在着一定的弊端： 1 ) 在只需少数车辆就能满足配送任务的情况下，仍然需要全部车辆出动， 车辆的运行维护费用和人员费用以及工作量大大增加，造成不必要的浪费。 2 ) 由于每条线路上每次零售户需求分别不同。每次运输线路都是由司机凭 经验选择路径行驶，盲目性较大，经常走“弯路、远路、冤枉路”，费力费时。 3 ) 不同送货线路之间存在工作量严重不均衡，有的线路“吃不饱”，而有些 偏远线路送货任务繁重，送货人员和司机经常加班送货，产生一系列的安全隐患 和服务质量问题，给公司及员工的利益带来很大的影响。 4 ) 各送货车辆的驾驶人员或配送人员很可能经常性的在上班时间公车私用， 或者跑岗串岗，严重降低烟草配送的效率并且大量浪费公司的车耗与油耗。选择 的各零售商可能素质良莠不齐，有时可能会在售烟过程中出现一些不正当竞争手 段或不法经营的问题，作为卷烟供应商有义务对零售商进行一些必要的监督，还 有时需要给全部或者部分比较大的零售商送出一些公文性文件，这样就需要公司 能够制定出一些单回路循环路线以供出车人员选择，达到省力省时的效果，提高 效率。 1 4 2 本文的研究主要内容 本文正是基于以上阐述，以某正在建设的卷烟物流中心车辆调度系统作为研 究对象，针对国家烟草专卖局提出的烟草商业销售网络物流“五化”管理中的“配 送线路最优化 这一要求进行深入研究，而物流配送车辆优化调度问题的研究正 是用来解决配送线路最优化问题，而蚁群算法作为一种新兴的生化学算法对于解 决问题有着得天独厚的优势。本文的主要研究方向是：基于蚁群算法研究车辆优 化调度问题，并针对蚁群算法的一些缺点提出改进思路，最终用于实现卷烟配送 线路最优化这一要求。 对于改进策略，由于蚁群算法的应用，目前在国内也有较多的研究，前面都 有叙述，本文主要从四个方面进行了研究。 l o 硕士学位论文第一章绪论 首先，针对蚁群算法搜索时间较长的缺点，引入对去交叉点的策略，运用去 凸壳的数学方法对t s p 进行预处理，在一个程度上能够解决算法搜索时间长的 缺点。 接着，在将组合优化极小化问题映射为全连通图的基础上，对蚁群算法的初 始参数设置和构造全局最优解的概率等收敛性问题进行了研究。 其次，针对容易出现搜索停滞现象的缺点，提出最大最小蚁群算法，并 在算法中融合信息算扩散原理及自适应策略，设计出一个搜索能力更强，搜索出 来的结果更佳的模型。 最后，针对配送中心每天派车任务多，派送线路繁杂，以及监管方面的一些 困境，结合蚁群算法及其改进策略求解t s p 及v r p ，选定出合适的派车路线节省 运营成本。 1 5 论文章节安排 基于上述内容，现规划论文的结构如下： 第一章，绪论。首先，介绍物流优化配送的意义；然后，分析物流优化配送 的国内外研究现状和水平：接着结合烟草物流的概况对烟草物流实际问题中的一 些具体要求及问题做出介绍：最后，讲述了该课题的工程背景。 第二章，蚁群算法的原理。首先，介绍了蚁群算法的最初引入模型；介绍了 蚁群算法系统的机制原理；然后详细叙述了算法的系统学原理，从分布式计算、 自组织、正负反馈等方面做了详尽的介绍；最后，对蚁群算法的发展历程和研究 现状进行了详细的叙述，并简单介绍了蚁群算法的特点及优缺点。 第三章，首先介绍了单回路车辆调度模型( t s p ) ，最后就基于t s p 问题提出 了基本的蚁群算法模型、国际上通用的实例仿真；蚁群算法的收敛性研究及初始 参数设置。首先，提出了在组合优化极小化问题映射为全连通图的基础上的收敛 性研究；然后，对蚁群算法的各个参数的设置做个概述，并得出较合适的参数配 置方案；蚁群算法的改进及应用，首先，针对搜索时间长等缺点，引入凸壳问题， 对t s p 进行预处理提出去交叉局部优化策略；其次，针对容易出现搜索停滞现象， 研究了自适应蚁群算法，并进行了仿真研究；然后，研究了基于最大最小蚁群算 法的模型，也进行了仿真比较；之后，研究了基于信息索扩散策略的蚁群算法进 行仿真比较。 第四章，介绍多回路车辆调度问题( v r p ) 模型，对它与t s p 的区别及相同 点做出介绍，并就不同点做出解决方案，并给出v r p 问题的算法流程。用蚁群 算法结合v r p 及t s p 模型解决物流中心的配送方案实例中所遇到的监管难题及线 路选择的最优化问题，进行仿真得出最优路径。 硕士学位论文第一章绪论 第五章，总结与展望。总结了本文的全部研究工作，指出后续的工作要点和 有前景的研究方向。 1 2 硕士学位论文 第二章蚁群算法原理分析 第二章蚁群算法原理分析 随着人类探索脚步的不断前进，复杂性、非线性、系统性的问题越来越多的 呈现在人们眼前。面对系统的复杂性，由于始终没有突破传统计算思想的藩篱， 人工智能在经历了上世纪8 0 年代整整1 0 余年的辉煌之后，已经逐渐陷入困境。 以p e n r o s e 等为代表的各种反思和批驳论著纷纷涌现，人工智能的研究前景又 一次变得黯淡下来。但是大自然始终是开启人类智慧的老师，随着人们对生命本 质的认识的不断深化，生命科学以前所未有的速度发展，使人工智能的研究开始 摆脱经典逻辑计算的束缚，大胆探索起新的非经典的途径。正如人工智能先驱 m i n s k y 所认为的“我们应该从生物学而不是物理学受到启发那样，对生 物启发式计算( b i o 一一i n s p i r e dc o m p u t i n g ) 的研究，成为人工智能迎接新曙光而 重新焕发新春的又一个契机1 2 引。 自然界一直是人类创造力的丰富源泉，人类认识事物的能力来源于与自然界 的相互作用。自然界中的许多自适应优化现象不断给人以启示：生物体和自然生 态系统可通过自身的演化就使许多在人类看起来高度复杂的优化问题得到完美 的解决。伴随着模拟自然与生物机理为特征的仿生优化算法时代的悄然兴起，一 些仿生优化算法已经在经典的n p c 问题的求解和实际应用中显示出强大的生 命力和进一步发展的潜力。生物学家通过对蚂蚁的长期观察研究发现，每只蚂蚁 的智能并