（交通运输规划与管理专业论文）基于改进蚁群算法的蔬菜物流配送车辆优化调度研究.pdf

摘要 我国是一个农业大国，对农业物流的研究和应用尚处于起步阶段。蔬菜产业 是我国农业中具有巨大潜力的一大产业。随着经济的迅速发展，生活节奏的加快， 人民生活水平的不断提高和对更好生活品质的追求，新鲜蔬菜销售走出传统模 式，蔬菜配送成为城市居民消费的客观需要，大量的蔬菜配送中心涌现了。在蔬 菜配送业务中，存在着许多优化决策问题，其中配送车辆调度问题对配送企业加 快配送速度，提高服务质量，降低配送成本及增加经济效益影响较大。 蚁群算法是模仿自然界的蚂蚁行为而发展起来的一种随机搜索方法，它具有 较强的鲁棒性、优良的分布式计算机制、易于与其他方法相结合等优点。然而， 搜索时间长、易限入局部最优解是基本蚁群算法突出的缺点。 本文主要研究内容如下： ( 1 ) 本文对中国蔬菜物流的特点及现状进行了阐述，并提出通过车辆调度可 以优化配送企业配送路径，可以降低企业成本。 ( 2 ) 本文对车辆调度问题的研究现状进行了系统阐述，同时对蚁群算法的研 究现状及应用进行了系统的综述，并提出改进方法，以优化其搜索能力，避免过 早收敛与停滞现象。 ( 3 ) 本文针对软时间窗单配送中心配送调度问题，建立了含时间惩罚函数的 数学模型，并用改进的蚁群算法求解模型，找出最优的配送路线。在求解软时间 窗多配送中心配送调度问题时，本文采用了两阶段法，首先利用距离最近分配法， 将各个客户分配给各个配送中心，将多配送中心问题转变成多个单配送中心问 题。然后利用改进的蚁群算法求解，找出每个配送中心的最优配送路线，最后得 出满意解。 关键词：蚁群算法；蔬菜物流：车辆调度；软时间窗；优化；距离最近分配法 a b s t r a c t c h i n ai sac o u n t r yb a s e do nt h ea 鲥c u l t u r e ，f e wp e o p l es t u d yo na g r i c u l t u r a ll o g i s t i c s v e g e t a b l ei n d u s t r yi sap r o m i s i n gi n d u s t r ya m o n ga g r i c u l t u r e w i t l lt h er a p i de c o n o m i c d e v e l o p m e n t ，t h ep a c eo fl i f es p e e d su p ，t h ec o n t i n u o u si m p r o v e m e n to fp e o p l e sl i v i n g s t a n d a r d sa n db e t t e rq u a l i t yo fl i f ef o rt h ep u r s u i t v e g e t a b l ec o n s u m p t i o nd i s t r i b u t i o n b e c o m et h eo b j e c t i v en e e d so fu r b a nr e s i d e n t s ，al a r g en u m b e ro fv e g e t a b l ed i s t r i b u t i o n c e n t e r sh a v ee m e r g e d a m o n gd i s t r i b u t i o nb u s i n e s st h e r ea r em a n yo p t i m i z i n gs t r a t e g i e s t h e v e h i c l es c h e d u l i n gp r o b l e mh a sg r e a te f f e c to ni m p r o v i n gd i s t r i b u t i o ns p e e d ，q u a l i t yo f s e r v i c ea n de c o n o m yb e n e f i t a n tc o l o n ya l g o r i t h mw a sar a n d o ms e a r c h i n gm e t h o d ，w h i c hs i m u l a t e dt h eb e h a v i o ro f a n ti nn a t u r e i t sm a i nc h a r a c t e r i s t i c sa r e s t r o n g e rr o b u s t n e s s ，e x i m i o u s d i s t r i b u t e d c o m p u t a t i o nm e c h a n i s ma n da p tc o m b i n e dw i t ho t h e ra p p r o a c h e s b u ti th a st h el i m i t a t i o no f s t a g n a t i o n ，a n di se a s yt of a l li n t ol o c a lo p t i m u m s 劢ec o n t e n t so ft h er e s e a r c ha st h ef o l l o w i n g ： ( 1 ) b ya n a l y z i n gt h es i t u a t i o no fc h i n al o g i s t i c s ，t h ec o n c l u s i o nw a sr e a c h e dt h a t o p t i m i z i n gv e h i c l es c h e d u l i n gc a nd e c r e a s e sb u s i n e s sc o s t s ( 2 ) t h eo p t i m i z a t i o no ft r a n s p o r t a t i o nw a ss y s t e m a t i c a l l ya n a l y z e d ，s ow a st h es i t u a t i o n a n da p p l i c a t i o no ft h ea n tg r o u pa l g o r i t h m 1 1 l ep a r a m e t e r sa n dt h ei m p r o v i n gm e t h o do fa n t g r o u p a l g o r i t h mw e r es t u d i e d ( 3 ) am a t h e m a t i cm o d e lw i t ht i m ep e n a l t yf u n c t i o nf o rt h ev e h i c l e - s c h e d u l i n gp r o b l e m b u i l ti nt h i sp a p e ra n du s et h ei m p r o v e da n tc o l o n ya l g o r i t h mt of i n dt h eo p t i m a ld i s t r i b u t i o n r o u t e s i ns o l v i n gt h ed i s t r i b u t i o nr o u t i n gp l a n so fm u l t i d e p o t sv e h i c l es c h e d u l i n gp r o b l e m u s e st w os t a g e s f i r s t l y ，u s et h en e a r e s tp r i n c i p l et od i v i d ea l lc u s t o m e r st od i f f e r e n t d i s t r i b u t i o nc e n t e r sa n dc h a n g em u l t i d i s t r i b u t i o nc e n t e rp r o b l e m si n t oan u m b e ro fs i n g l e d i s t r i b u t i o nc e n t e rp r o b l e m s t h e nu s et h ei m p r o v e da n tc o l o n ya l g o r i t h mt of i n dt h eo p t i m a l d i s t r i b u t i o nr o u t e si ne v e r yd i s t r i b u t i o nc e n t e r f i n a l l y , as a t i s f i e dr e s u l tc o u l db ef o u n d t h r o u g hc o n t i n u e di t e r a t i o n so ft h ep r o c e s s k e y w o r d s ：a n tc o l o n ya l g o r i r h m ，v e g e t a b l e sl o g i s t i c s ，v e h i c l es c h e d u l i n g ，s o f t - t i m e w i n d o w , o p t i m i z a t i o n ，n e a r e s tp r i n c i p l e i i 长沙理工大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得的 研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或 集体己经发表或撰写的成果作品。对本文的研究徽避重要贡献的个人和集体，均 已在文中以明确方式标明。本人完全意识到本声明的法律后果由本人承担。 作者躲矽热欺 噍髫年 鼢圈 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保 留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借 阅。本人授权长沙理工大学可以将本学位论文的全部或部分内容编入有关数揍；库 进行检索，可以采用影印、缩印或扫攒等复制手段保存和汇编本学位沧文。 本学位论文属于 l 、保密1 3 ，在年解密后适用本授权书。 2 、不保密。 ( 请在以上相应方框内打“) 乍者签名： 导师签名： 彬晶防 移越 霉期：眵年，胃如匿 日期：埘年乡月1 寸日 1 1 研究背景 第一章绪论 物流( l o g i s t i e s ) t l 】指在合适时间，将合适的物品以适当的数量准确地送到顾 客手中，它是供应链中最重要的组成部分。在现代社会中，物流与商流、信息流 并称为经济的三大支柱【2 】。其中，物流被公认为是企业在降低物质消耗、提高劳 动生产率以外创造利润的第三个重要源泉，也是企业降低生产经营成本，提高产 品市场竞争力的重要途径。据专家测算，现代物流成本约占企业经营成本的 3 0 5 0 ，当一个有效的物流系统与企业主要商业系统集成后，可使仓储量降低 5 0 ，准时交货率提高4 0 ，营业收入增加1 0 以上【3 1 。可见，系统化、合理化 的物流管理将创造巨大的经济利润。 据中国物流与采购联合会、国家统计局和中国物流信息中心统计的2 0 0 2 年 到2 0 0 6 年社会物流总额、社会物流总成本、运输成本，如表1 1 所示，2 0 0 2 2 0 0 6 年，反应物流需求规模的全社会物流总额从2 3 3 万亿元上升到5 9 6 万亿元，增 长了2 6 倍，年均增长2 6 ，大大高于同期g d p 的年均增速。物流总值的高速 增长，表明经济增长对物流的需求越来越大，经济发展对物流的依赖程度也越来 越高。同期，我国全社会物流总成本从2 19 8 4 亿元扩张到3 8 4 1 4 亿元，增长了 1 7 倍，年均递增1 5 ，高于经济年均递增4 个百分点左右。但这种增长势头趋 于减缓，2 0 0 2 2 0 0 6 年，物流总成本占g d p 总值的比例从2 1 5 下降到1 8 3 。 其中，运输成本占社会物流总成本的比重为5 7 。这说明我国物流总效益在提 高。但物流成本总体水平仍然偏高，与美国、日本、欧盟国家比要高出8 1o 个 百分点。在这种形势下，研究如何通过实施科学的物流管理，以提高物流效率、 降低物流成本、提高服务质量是十分必要的。 表1 12 0 0 2 年2 0 0 6 年中国物流信息表 2 0 0 2 年2 0 0 3 年2 0 0 4 年2 0 0 5 年2 0 0 6 年 社会物流总额( 万亿元) 2 3 32 9 63 8 4 4 8 15 9 6 社会物流总成本( 亿元) 2 1 9 8 42 4 9 7 42 9 1 1 43 3 8 6 03 8 4 1 4 运输成本( 亿元) 1 2 18 7 1 4 0 2 81 6 0 9 8 1 8 6 3 9 2 1 0 1 8 物流总成本占g d p ( ) 2 1 52 1 4l8 818 618 3 配送是物流系统中一个重要的直接与消费者相连的环节，是“配”和“送 的有机结合。它是指按客户的订货要求，在配送中心进行分货、配货工作，并将 配好的货物及时送交收货人的物流活动。主要包括：从生产企业进货并集结的集 货作业；根据各个用户的不同需求，在配送中心将所需要的货物挑选出来的配货 作业；考虑配送货物的质量和体积，充分利属车辆的载重和容积的车载货物的配 装以及配送路线的确定。可见，物流配送是种集集货、分货、配赞、送货等多 种功能为体的物资流通方式。 在物流配送系统中，物流配送中心的成立有效的简化配送程序与减少配送的 频率，以m 个供应商和r 1 个零售商为铡，传统的配送模式是假设n 个零售商盼 需求都是由m 个供应商自行配送，则一共有mxn 次的运送，如图1 1 所示。假 设零售商与供应商之间通过一个物流配送中心来配送，则只需i l l + n 次配送，如 图l 。l 所示，如此一来郎可减少m t q 一( 燃+ 蔽) 碡孽配送次数，当供应商与零售齑 数目越多，节省的配送次数也就会越多。 传统配送模式 配送中心的配送模式 供戍商零售商供成髓零售海 霾l 。l 簧绞醚送模式与配送中心醒送模式魄较图 随着我国经济的迅速发展，生活节奏的加快，人民生活水平的不断提高和对 更好生活品质的追求，新鲜蔬菜销售走出传统模式，蔬菜配送成为城市屠民消费 的客观需要。大量的蔬菜配送中心涌现了，这不仅是现代物流业发展的客观要求， 也是发展蔬菜产品配送，改革我国蔬菜流通关系的根本举措。 湖南省地形地貌多样，气候适宜，地资源丰富，近年来，随着全省种植结 构调整与优化，蔬菜产业发展迅猛，播种面积逐年扩大，产量也逐年提高，蔬菜 产业已成为种植业的主要产业之一。据湖南省统计局的数据统计，从2 0 0 1 年到 2 0 0 7 年湖南省蔬菜播种面积由8 2 8 6 万公顷扩大到1 0 8 5 4 万公顷，年均增长 4 4 。蔬菜总产量由2 0 0 1 年的1 9 8 3 3 6 万吨增至到2 0 0 7 年的2 6 5 2 6 1 万吨，年 均增长4 8 。全省蔬菜总产值也呈现逐年递增的趋势。具体数据如表1 2 所示。 2 表1 22 0 0 1 2 0 0 7 湖南省蔬菜产业信息表 2 0 0 1 年2 0 0 2 年2 0 0 3 年2 0 0 4 年2 0 0 5 年2 0 0 6 年2 0 0 7 年 蔬菜播种面 8 2 8 68 9 9 59 6 4 39 6 2 59 9 4 91 0 4 8 91 0 8 5 4 积( 万公顷) 蔬菜总产量 1 9 8 3 3 62 18 1 9 02 2 9 1 0 22 3 1 5 3 3 2 3 9 1 6 32 5 2 6 8 22 6 5 2 6 1 ( 万吨) 随着湖南省的蔬菜产业蓬勃兴起，产生了专门从事蔬菜物流的第三方物流企 业，即蔬菜配送中心。而物流配送中心作业的重点是如何将车辆有效的使用并决 定其最经济的行驶路线，使商品( 蔬菜) 能在最短的时间内送到顾客的手中，我 们外将此类问题归结为物流配送车辆调度问题。目前有关车辆调度问题的研究， 多致力于单一车种或多车种优化调度问题，很少涉及结合时间窗的车辆调度问 题。所谓时间窗是指顾客希望被服务的时间范围。由于消费者需求趋于多样化， 对送货时间的要求日趋严格，尤其是运送蔬菜这种讲究新鲜度的货物，除了因缺 货造成的机会成本的损失外，由于配送不及时也会造成货物价值的大大降低。因 此，在配送运输上，时间因素显得越来越重要。本文的研究目的就是从理论与实 践相结合的角度出发，将带时间窗的车辆调度理论应用到蔬菜物流配送中，从而 提高企业的效益。 1 2 研究现状 物流配送车辆优化调度问题最早是由d a n t z i g 和r a m s e r 于1 9 5 9 年首次提出 的【8 】，自此，很快引起运筹学、应用数学、组合数学、图论与网络分析、物流科 学、计算机应用等学科的专家与运输计划制定者和管理者的极大重视，成为运筹 学与组合优化领域的前沿与研究热点问题。在现实生产和生活中，邮政投递问题、 车辆调度问题、电力调度问题、管道铺设问题、计算机网络拓扑设计问题等都可 以抽象为物流配送车辆调度问题。 1 2 1 车辆优化调度问题定义与构成要素 车辆调度问题一般定义为：对一系列装货点和( 或) 卸货点，组织适当的行 车线路，使载货车辆有序地通过它们，在满足一定的约束条件( 如货物需求量、 发送量、交发货时间、车辆容量限制、行驶里程限制、时间限制等) 下，达到一 定的目标( 如路程最短、费用最少、时间尽量少、使用车辆尽量少等) 。 配送车辆调度问题主要包括货物、车辆、配送中心、客户、运输网络、约束 条件和目标函数等要素。 ( 1 ) 货物。货物是配送的对象。可将每个客户需求的货物看成一批货物。每 批货物都包括品名、包装、重量、体积、要求送到( 或取走) 的时间和地点、能 否分批配送等属性。 ( 2 ) 车辆。车辆是货物的运载工具。其主要属性包括：车辆的类型、装载量、 一次配送的最大行驶距离、配送前的停放位置及完成任务后的停放位置等。 ( 3 ) 配送中心。是进季亍集货、分货、配赞、配装、送货作业的场所。在某配 送系统中，配送中心的数量可以只有一个，也可以有一个以上。对于篥个配送中 - i i , ，其供应的货物可能有一种，也可能有多种；其供应的货物数量可能能够满足 全部客户的需求，也可能仅能满足部分客户的需求。 ( 唾) 客户。也称为用户，包括分仓库、零售裔店等。客户的属性赶括需求货 物的数量、需求货物的时间、需求货物的次数及需求货物的满足程度等。某客户 需求货物的时间，是指要求将货物送到的时间，对配送时间的要求可分为以下几 种情况：a 无时间限制；b 要求在指定的时闽区间也称为时闻窗) 内送到；c 有 时间限制，但可以不遵守，只是不遵守时要给予一定的惩罚。 ( 5 ) 运输网络。运输网络是由顶点( 指配送中心、客户、停车场) 、无向边和 有向弧组成的。边、弧的属性包括方向、权值和交通流量限制等。 ( 6 ) 约束条彳牛。配送车辆调度问题应满足的约束条件主要包括：8 满足所有客 户对货物品种、规格、数量的要求；b 满足客户对货物送到时间范围的要求；c 在允许通行的时间进行配送( 如有时规定白天不能通行货车等) ；d 车辆在配送 过程中的实际载货壁不得超过车辆的最大允许装载量；e 在配送孛心现有运力范 围内。 ( 7 ) 目标函数。对配送车辆调度问题，可以只选用一个目标，也可以选用多 个目标。经常选用的蟊标丞数主要有： a 配送总里程最短。配送里程与配送车辆的耗油量、磨损程度以及司枧疲劳 程度等直接相关，它直接决定运输的成本，对配送业务的经济效益有很大影响。 由于配送里程计算简便，它是确定配送路线时用的最多的指标。 b 靛送车辆的吨位公摹数最少。该嚣标将配送距离与车辆的载重量结合起来 考虑，即以所有配送车辆的吨位数( 最大载重吨) 与其行驶距离的乘积的总和最 少为网标。 c 综合费用最低。降低综合费用是实现配送业务经济效益豹基本要求。在配 送业务中，与送货有关的费用包括：车辆维护和行驶费用、车队管理费用、货物 装卸费用、有关人员工资费用等。 d 准时性最高。出于客户对交货时间有较严格的要求，为提高配送服务质量， 有时需要将准时性最高作为确定配送路线的目标。 e 运力利用最合理。该目标要求使用的较少的车辆完成配送任务，并使车辆 4 的满载率最高，以充分利用车辆的装载能力。 f 劳动消耗最低。即以司机人数最少、司机工作时间最短为目标。 1 2 2 车辆优化调度问题的分类 一般的车辆调度问题可以分为以下几类： 按车场( 或货场、配送中心等) 数目分，有单车场问题和多车场问题。 按任务特征分，有纯装问题或纯卸问题( 车辆所有任务点装货或卸货，即集 货或送货问题) 及装卸混合问题( 每项任务有不同的装货点和卸货点，即集货、送 货一体化问题) 。 按任务性质分，有对弧服务问题( 如中国邮递员问题) 和对点服务问题( 如旅行 商问题) 以及混合服务问题( 如交通车线路安排问题) 。 按车辆载货状况分，有满载问题( 货运量不小于车辆容量，完成一项任务需 要不止一辆车) 和非满载问题( 货运量小于车辆容量，多项任务用一辆车) 。 按客户对货物取( 送) 时间的要求分，无时限问题( 客户对货物的取走或送到 的时间无要求) 和有时限问题( 客户要求将需求的货物在规定的时间窗内送到， 将供应的货物在规定的时间窗内取走，也称为有时间窗问题) 。有时限问题又分 为硬时间窗问题( 客户要求货物必须在规定的时间窗内送到或取走，不能提前不 能拖后) 和软时间窗问题( 客户要求将货物尽量在规定的时间窗内送到或取走， 但也可以提前或拖后，只不过在提前或拖后时，要对配送企业实施一定的惩罚) 。 按车辆类型数分，有单车型问题( 所有车辆容量相同) 和多车型问题( 执行任务 的车辆容量不完全相同) 。 按优化目标数来分，有单目标问题和多目标问题。 按车辆对车场的所属关系分：有车辆开放问题( 车辆可以不返回出发的配送 中心) 、车辆封闭问题( 车辆必须返回出发配送中心) 。 由于情况的不同，车辆调度问题的模型构造及算法有很大的差别。 1 2 3 本文所研究v r p 的界定 如前所述，现实中的物流配送车辆优化调度问题是十分复杂的，根据蔬菜物 流配送的特点，现对本文研究的物流配送车辆调度问题做如下界定： ( 1 ) 配送中心和多个需求点的位置一定，配送中心供应的货物，能满足多有 需求点的需求。 ( 2 ) 蔬菜物流的特点决定了蔬菜物流配送车辆调度的任务特征，是纯集货( 从 生产者手中收货物) 或纯送货( 往各个消费点送货) 。 ( 3 ) 各个需求点需求( 或供应) 的货物均可以相互混装，即可以装在同一配送车 辆内；每个客户的货物需求量( 或供应量) 不超过配送车辆的最大载重量；每个客 户的送货( 或取货) 要求必须满足，且仅能由一台车辆完成，不允许分批配送。 ( 4 ) 蔬菜具有易腐性，消费者都希望能买到新鲜的蔬菜，因此时间因素显得 尤为重要。所以必须有时问窗限制，本文采用软时间窗。 5 ) 每台配送车辆的最大载震量一定，不允许超载；配送时，设每台车辆都 从配送中心出发，向一些客户提供配送服务后，最终返回配送中心。 ( 6 ) 配送中心与客户之间以及客户相互之间的最短距离已知且固定，且不考 虑运输网络中车辆流量的限制。 1 。2 。4 国内外研究现状 在过去的数十年问，国内外对物流配送车辆调度问题做了大量而深入的研 究。研究证实了车辆调度阀题具有复杂的计算性质，悬个典型的n p 难题。车 辆调度的问题的解法也非常丰寓，m a g n a n t j ( 1 9 8 1 ) ，b o d i n 和g o l d e n ( 1 9 8 3 ) ， l a p o r t e 和o s m a n ( 1 9 9 5 ) 等许多学者对车辆调度问题求解的方法进行了研究，现 在基本上可以分为四大类。 ( 1 ) 精确方法 包括分枝定界算法( b r a n c ha n db o u n da p p r o a c h ) 、割平面法( c u r t i n gp l a n e s a p p r o a c h ) 、网络流算法( n e t w o r kf l o wa p p r o a c h ) 、动态规划方法( d y n a m i c p r o g r a m m i n ga p p r o a c h ) 。精确算法的计算精度高，但随着配送系统的扩大和对 调度的多目标要求，希望利用精确算法获得整个系统的精确优化解越来越困难， 花费的时间和费用是不能接受的，因此精确解法不能应用于规模较大、多目标车 辆调度姻题的求解，仅用于运输调度的局部优化问题。 ( 2 ) 启发式方法 启发式方法指通过经验法则来求取运输过程满意解的数学方法。启发式方法 是针对优化方法的不足，运用一些经验法则来降低优化模型的数学精确程度，弗 透过模仿入的跟踪校正过程求敢物流系统的满意解。窟发式方法能同时满足详细 描绘问题和求解的需要，比优化方法更为实用。其缺点是难以知道什么时候好的 启发式解已经被求得。常用启发式算法有：节省法( s a y i n gm e t h o d ) 、最邻近法 ( n e a r e s tn e i g h b o r ) 、插入法( i n s e r t i o n ) 及扫描法( s w e e p i n g ) 。 ( 3 ) 模拟方法 模拟方法是利用数学公式、逻辑表达式、图表、坐标图形等抽象概念表示实 际配送系统内部状态和输入输啦的关系，以便通过计算机对模型进行实验，通过 实验取得改善运输系统或设计新运输系统所需信怠。模拟方法的缺点是在模型构 造、程序调试、数据精理方面工作量大。 ( 4 ) 交互式优化法 这是一种通用方法，它把入的知识和经验结合到闷题的求解过程孛去。其主 要思想是：有经验的决策者应具有确定和修改参数的能力，并且根据知识直感， 6 把主观的估计加到优化模型中去。这通常总是会增加模型最终实现并实际采用的 可能性。 随着人工智能技术的引入和不断发展，模拟退火算法、禁忌搜索算法、遗传 算法和蚁群算法等新的方法以及人工神经网络和专家系统等新技术，为解决大规 模、多目标车辆优化调度问题提供了新的辅助手段。 模拟退火( s i m u l a t e da n n e a l i n g ，s a ) 算法，最早是由m e t r o p o l i s 在1 9 5 3 年提出的，其特点是以一定的概率选择邻域中目标函数值较差的状态。近年来， o s m a n 、t e o d o r o v i c 、刘浩和韩世通等利用模拟算法求解物流配送车辆调度问题， 取得了很多成果。 禁忌搜索( t a b us e a r c h ，t s ) 算法，g 1o v e r 在1 9 8 6 年首次提出的这一概念， 进而形成一套完整算法。禁忌搜索算法的特点是采用禁忌技术。g e n d r e a u 、 j i e f e n g 、蔡延光、周双贵和钟石全等利用禁忌搜索算法求解物流配送车辆调度 问题或满载物流配送车辆调度问题，取得了一些成果。 遗传算法( g e n e tica l g o r i t h m ，g a ) 是由j h o ll a n d 于1 9 7 5 年提出的，其 特点是整体搜索策略和优化计算时不依赖于梯度信息。o c h i 、l i u z 、李军、蔡延 光等都曾利用遗传算法对物流配送车辆调度问题进行求解，并取得了一些研究成 果。 蚁群算法( a n tc o l o n yo p ti m iz a t i o n ，a c o ) 最初是由意大利学者d o r i g om 于1 9 9 1 年首次提出的【4 】，其特点是通过正反馈、分布式和并行性，来寻找最优 解。l e n s t r ajk ，r i n n o o yk ，李继玲和吴宗彦等都曾利用蚁群算法对物流配送 车辆调度问题进行求解5 】【6 】【7 1 ，取得了一些成果。 上述的禁忌搜索算法、模拟退火算法、遗传算法和蚁群算法在求解物流配送 车辆调度问题中的应用刚刚处于起步阶段，虽然有了一些研究成果，其潜力还有 待于进一步挖掘。因此本文应用蚁群算法来求解物流配送车辆调度问题。 1 3 研究意义 现阶段，在我国的一些物流企业中，一方面物流配送车辆存在着超负荷运行 的情况，另一方面由于缺乏科学组织，造成配送车辆使用效率低下，浪费严重。 车辆调度管理方法落后是一个重要原因，表现为现代的管理手段采用较少，一般 仍凭经验调度，调度质量差，优化程度低，空驶率高，浪费严重，不能充分发挥 运输工具的效能。如果车辆调度方案规划配送路线不合理，会产生一系列的问题， 如服务质量下降，不能满足客户的要求；大量不合理的配送调度的出现会使物流 成本难于控制；车辆调度的不合理会使物流配送车辆的出行次数增加、路线增长， 从而导致城市交通负担的增加。可见，研究物流配送车辆优化调度问题具有很强 7 的理论和现实意义。所以如何实现快速而准确的配送是企业在经营方面必须面对 的重要课题，因此研究物流配送车辆调度的意义重大。 ( 1 ) 合理的物流配送系统可以准确运输，即货物( 蔬菜) 按客户要求的数量 在指定的时间段被运送到客户手中，这样不仅可以提高客户的满意度，也可使企 业实现低库存或零库存，以至可以完全取代客户原有的供应系统，用更高的供应 质量和更低的供应成本，实现对用户的供应，实现企业销售和用户供应的一体化。 ( 2 ) 合理的物流配送调度系统可以合理的配置车辆，科学地制订配送路线， 可以消除重复运输、空载运输，提高运输工具的利用率，减少物流配送的运行车 次、里程。这样不仅可以降低运输成本，同时也有助于缓解城市交通拥挤、减少 运输污染、节约有限能源、减少大气污染等困扰人们的社会问题。 ( 3 ) 有利于减少流通环节，提高蔬菜流通效率。配送企业直接从农户手中大 量采购具有地方特色的蔬菜，通过短时间加工运输配送到消费者手中，这样不仅 减少了蔬菜库存和资金占用，压缩了中间经营环节，形成了规模效益，减少了流 通成本，而且还保证了蔬菜的质量，可以满足消费者对其新鲜程度，营养价值等 方面的要求。 1 4 本文主要研究内容 本论文对蚁群算法理论进行深入研究，针对算法在计算过程中存在的缺点对 其进行有效改进，提高算法的性能，并将改进型蚁群算法引入蔬菜物流配送领域， 针对物流运输车辆调度问题复杂性、不确定性等特点，设计新的算法，合理选择 运输路径，加快运输速度、提高服务质量、降低运输成本及增加经济效益。 论文主要从以下几个方面开展工作： ( 1 ) 改进蚁群算法 从算法的基本思想入手，研究算法原理、特征及性能，并对算法在计算过程 中容易出现过早收敛、停滞等缺点，提出改进方法，以优化其搜索能力，避免过 早收敛与停滞显象。 ( 2 ) 设计物流配送车辆优化调度算法 依据车辆优化调度理论，结合改进蚁群算法，针对软时间窗车辆调度问题， 设计动态确定车辆数和随机搜索路径的新算法，即在蚁群算法计算过程中自动寻 找满足要求的最少车辆数，同时确定搜索路线。 ( 3 ) 实现算法 对设计的算法，用m a t l a b 语言在计算机上模拟，并对算法不断分析、改进。 ( 4 ) 模拟仿真研究 应用实例，利用上述算法进行计算，分析算法的可行性、有效性，得出结论。 8 第二章蔬菜物流配送及v r p 概述 2 1 蔬菜物流的概念及其特点 蔬菜物流【9 】是指蔬菜从生产地到消费地整过程中的实体流动，包括蔬菜生 产、收购、运输、储存、装卸、搬运、包装、配送、流通加工、分销、信息活动 等环节并在这一程中实现蔬菜的价值增值和组织目标。我国是一个蔬菜大国蔬菜 物流在农业经济发展和提高人民生活水平方面的地位举足轻重，大力发展蔬菜物 流有利于稳定蔬菜的产销关系，保证蔬菜的稳定供应；提高蔬菜流通速度，降低 蔬菜流通成本。 我国蔬菜物流的特点【1 0 】【1 1 】： ( 1 ) 鲜活性。随着人们生活水平的提高，人们对蔬菜新鲜度的要求也越高， 蔬菜在采摘后仍是鲜活的有机体，因此需要采用冷链运输降低蔬菜的呼吸和蒸腾 作用，保持蔬菜新鲜度。 ( 2 ) 易损性。蔬菜质地鲜嫩，含水量高，在采收、装卸、运输过程中容易受 到伤害。受损的蔬菜容易遭遇病菌的侵袭，造成蔬菜腐败。在蔬菜采摘之后除了 对包装、运输和装卸过程加强管理之外，还应尽量减少搬运、装卸的次数和缩短 运输距离。 ( 3 ) 及时性。消费者对蔬菜的第一要求就是蔬菜的新鲜，新鲜的蔬菜不仅可 以赢得消费者的喜爱，而且可以使消费者付出较高的价格。蔬菜从原产地采摘后 应该及时地运送到消费者手中，这对蔬菜物流提出了更高的要求。 ( 4 ) 物流成本所占比重较大。据调查，我国蔬菜物流成本在总成本中所占的 比重达到6 0 以上，随着燃油价格及各种道路收费不断增长，物流成本的比重 仍在不断增加。 我国蔬菜物流配送的现状及存在的问题i lz j ： 第一，蔬菜物流损失较大，物流成本居高不下。我国蔬菜产品在采摘、运输、 储存等物流环节上的损失率在2 5 一3 0 之间。 第二，蔬菜物流数量特别大，品种特别多。据湖南统计局统计2 0 0 7 年湖南 省蔬菜产量2 6 5 2 6 1 万吨。这些蔬菜除了农民部分自用外，其余大部分都成为了 商品，可见数量之大，品种之多。 第三，蔬菜物流难度大。由于蔬菜本身的物理特性，首先是易腐易损性，其 次是单位产品价值低。蔬菜的易腐易损性规定了物流时间的上限，可见蔬菜物流 9 比其他货物物流的难度要大很多。 第四，蔬菜物流的分散性。物流服务对象绝大部分是千千万万的农户和超市， 这就决定了客户的数量庞大，而每个客户的物流规模又很小。 第五，物流环节过多，传统物流占主导地位。 2 2 物流配送模式分类 1 按经营主体分类 ( 1 ) 自营配送。这种配送模式是企业根据自己的经营规模、企业的商品配送 量、企业的经营策略以及业务网点布局等多种条件与因素，在合适的地点自己建 造一个或多个配送中心，依靠自己构建的网络体系开展物流配送业务，实现对企 业内部及外部货物配送的模式。 ( 2 ) 外包配送。企业不建配送中心，而以签订合同的形式把企业的配送业务 委托给专业化的第三方物流配送公司，而且与第三方物流配送公司形成长期合作 的战略同盟，互赢互利。这样，对于第三方物流配送公司的选择就显得十分重要， 能力差的物流配送公司不但不能节省物流费用，反而使商品不能准时送达，形成 脱销，对公司信誉造成不良的影响。所以选择与配送业务广、现代化程度高、科 技水平高、按照现代物流理念经营的专业化物流配送公司合作就显得特别重要。 外包式物流配送模式如图2 1 所示。 供应方：第三方物流需求方： 生产企业 配送公司 一 公司企业 偿自后椿位自后馋 图2 1外包式配送模式 ( 3 ) 共同配送。又称协同配送。国内大多数资料是这样定义的：共同配送是 指把过去按不同货主、不同商品分别进行的配送，改为集中运货的“货物及配送 的集约化”，也就是把拟配送的货物都装入在同一条线路上运行的运输车辆里， 用同一辆车为更多的客户运送货物，这是企业间为实现整体的配送合理化。以互 利互惠为原则，互相提供便利的配送服务的协作性配送模式。 ( 4 ) 混合配送。混合配送模式是指企业自身适当地建立小型配送系统，大范 围的配送采用外包配送模式，小范围的配送采用自营配送模式。混合配送模式充 分考虑自营配送与外包配送的优劣势，根据企业本身的特点，建立小范围的配送 体系，如城市配送中心，而长距离的配送问题有专业的第三方配送公司承担，企 业不用太大的投资就可以保证城市内恰当的商品供应，避免因脱销而影响企业的 i o 市场份额；同时，又控制着对客户配送的主动权，一旦市场情况变化，需要调整 企业经营策略，配送就可以积极地配合销售过程。 2 按配送商品的种类及数量划分 ( 1 ) 多品种、少批量配送。这种配送是按用户要求，将所需要的各种货物配 备齐整后，由配送地少量多次送达目的地的一种配送方式。这种配送作业水平要 求较高，配送中心设备复杂，配货送货计划难度大，要求有高水平的组织工作保 证和配合。这种配送方式符合了现代“个性化需求”，发展比较快。由于是小批 量，因此，配送的频率一般比较高。 ( 2 ) 少品种、大批量配送。企业需要量较大的商品，单一品种或少数几个品 种就可以达到较大运输量，可实行整车运输。这种商品往往不需要再与其它商品 搭配，可由专业性很强的配送中心实行配送。 ( 3 ) 成套配送。当用户尤其是装配企业需要多种零配件和配套设备时，可采 用成套配送形式，按其生产节奏定时定量地将企业所需要的货物送到生产装配 线。这种配送方式有利于生产企业实现库存最小化，方便生产企业的生产作业。 3 按配送时间及数量划分 ( 1 ) 定时配送。按规定时间间隔进行配送。这里的时间间隔是指用户多需求 的时间间隔，一般相对固定。每次配送的品种及数量可按计划执行，也可在配送 前以一定的联络方式通知配送品种及数量。这种方式由于时间固定，易于安排工 作计划、易于使用车辆。对用户来讲，也易于安排接货力量( 如工作人员、设备 等) 。但是由于配送品种变化，配货难度较大，在要求配送数量变化较大时，会 使配送运力安排出现困难。 ( 2 ) 定量配送。按规定的数量在一个指定的时间窗内进行配送。由于配送的 数量相对固定，时间范围相对宽松，配送方可以在有效的时间窗内进行备货、装 配和配送，合理使用配送设备，节约运力和选择运输时间与线路，提高配送效率， 节约配送成本。 ( 3 ) 定时定量配送。是指按规定的时间、规定的货物品种和数量进行的配送。 这种配送具有定时配送和定量配送的特点，一般作业的难度较大，成本较高。 ( 4 ) 定时定量定点配送。这是在配送过程中用户普遍需求的配送形式，即将 准确的货物数量在规定的时间内运到规定的目的地。它不仅要求配送方有较高的 管理能力，而且要有较强的配送能力。 ( 5 ) u l j 时配送。完全按用户突然提出的配送时间和数量随即进行配送的方式。 4 根据物流企业配送中心的数量和车辆配送线路的组织形式，从车辆配送的 角度，将配送模式分为三种：单配送中心配送模式、多配送中心配送模式和介于 两者之间的准多配送中心配送模式。 ( 1 ) 单配送中心是指物流公司仅有一个配送中心仓库或车场，所有配送车辆 的起点和终点都是此配送中心。具体形式如图2 2 所示。 图2 2 单酝送中心配送模式 物流公司中心 念库或车场 客户固定业务 客户隧机业务 瀚定业务配送 率辆行驶路线 随机业务配送 攀辆褥驶路线 其中，固定业务摆在物流公司调度计划安排之翦客户己经通知物流公司的业 务；随机业务是提前没有通知、不在计划安排以内的并且对时间要求比较紧，需 要马上或者当天进行配送、运输的业务。 单配送中心配送模式的优点是车辆调度安排比较简单。适用于物流企业规模 比较小，业务较少，客户相对比较集中，范围分布不大的小型物流企业。 单配送中心配送模式进行配送车辆安排的时候，对于固定业务，可以根据货 物的数量、性质及时闻要求进行配送，让每一辆车辆完成相邻的任务盾回到配送 中心，这可按照经典的车辆调度算法( v e h i c l er o u t i n gp r o b l e m 即：v r p ) 进行计 算求解最优线路。对于调度计划安排之后客户提出的随机紧急的业务，可以直接 从配送中心派车完成客户需求。因为整个配送范围比较小，从配送中心派车也不 会很遴，从成本上讲也不会很高，这时候最优路线就是嚣送孛心与客户两点闽的 最优路线。 ( 2 ) 多配送中心配送模式是指物流公司除了有一个配送中心仓库车场以外， 还有另辨的一些分公司或者另外的配送中心，配送车辆以各分公司配送中心为中 心进行配送，起终点都是分公司配送中心，所有的配送相当于多个单配送中心的 组合，但同时各子公司配送中心与总公司配送中心之间也有货物的交换，这个交 换一般是在配送任务比较少的时间如晚上等进行。如图2 3 所示： 1 2 圜o o 一 一 2 3 多配送中心配送模式 物流子公司仓 库或车场 物流公司与子 公司货物交换 物流公司中心 仓库或车场 客户固定业务 客户随机业务 固定业务配送 车辆行驶路线 随机业务配送 车辆行驶路线 多配送中心配送适合城市规模比较大，配送在短时间内难以到达，并且总业 务量比较多的大型物流企业。 这种配送模式首先根据固定客户并结合随机客户的位置和需求数量，进行合 理分区，结合实际情况确定子公司的配送中心位置。在算法上跟准多配送中配送 模式中配送车辆随机等待地点的确定方法类似，只不过对随机业务和固定业务都 要考虑。根据历史数据，利用聚类分析等方法确定重心。在各个分区内按照单配 送中心配送模式进行计划安排，对于客户与子公司配送中心之间的车辆配送路线 用车辆调度算法进行合理求解。同时还要考虑各子公司与总公司之间货物交换， 这是个运输问题，可以根据运筹学中解决运输问题的方法来解决。 另外，对于多配送中心的配送模式还可以进行统一配送，即总公司根据整个 城市所有业务需求综合考虑，对所有车辆进行统一调度，各配送中心没有调度权。 这是一种全局最优的方案，理论上讲比各配送中心独立调度要好，但是这样的复 杂度远远高于各自调度，需要有良好的调度软件进行支撑。另外，在管理方面也 提出了更高的要求，所以比较难以实现。 ( 3 ) 准多配送中心配送模式是指物流公司也仅有一个配送中心仓库或车场。 但是，根据公司的业务情况把配送区域划分成几个小区，部分配送车辆完成固定 业务之后不是直接回到配送中心，而是到所在小区内的一个指定地点等候，准备 完成该小区客户的随机需求。如图2 4 所示。 一 圈o o 一 一 图2 4 准多配送中心配送模式 配送车辆随机 等待地点 物流公司中心 仓库或车场 客户固定业务 客户随机业务 同定业务配送 车辆行驶路线 随机业务配送 车辆行驶路线 准多配送中心配送模式的优点是从时间和空间的角度，充分利用了运力，降 低了成本，提高了服务水平。适合城市规模比较大，较远的配送业务车辆从配送 中心出发在短时间内难以到达；固定业务量不够大，车辆不能全天利用；同时随机 业务较多，占有较大比重中