（交通运输规划与管理专业论文）基于捕食搜索策略粒子群算法的车辆路径问题研究.pdf

捅芰 随着社会分工深化和经济快速发展，物流的功能和作用也在不断加强。物流系统研 究的重点是物流配送的优化。在现实生活中，为了使物流配送企业优化配送路径、降低 配送成本和提高经营管理水平，增加企业的竞争能力，必须对配送问题中车辆路径问题 进行深入地研究。车辆路径问题不仅是配送问题中的核心，也是研究的焦点之一。在实 际中合理安排车辆路径能有效提高运输效率，降低服务成本。 自车辆路径问题提出以后，国内外的专家学者就对其开展了广泛的研究。目前己经 产生出多种成熟的算法，为后人继续研究提供了基础。 本文首先分析了车辆路径问题的研究现状，给出了车辆路径问题的一般描述及分 类，并对常用求解车辆路径问题的算法进行了总结。其次，介绍了粒子群算法的基本概 念、数学模型和算法流程以及捕食搜索策略的基本思想及算法流程。 在此基础上，本文设计了一种对车辆路径问题进行求解的算法一基于捕食搜索策 略的粒子群算法。该算法通过对捕食搜索策略限制的调节，来实现粒子群算法搜索空间 的增大或减小，从而达到探索能力和开发能力的平衡，使粒子群算法求得更好的最优解。 用c + + 语言编程实现并将其应用于实例，优化了实例中的车辆路径，证明了该算法的有 效性和可行性。最终得出该算法是求解车辆路径问题的一个可行方法的结论。 关键词：配送，车辆路径问题，粒子群算法，捕食搜索策略 a b s t r a c t w i t ht h ed e e p e n i n go ft h es o c i a ld i v i s i o no fl a b o ra n dd e v e l o p i n go fe c o n o m i c ，t h e f u n c t i o na n dr o l eo ft h el o g i s t i c sa r ee x p a n d i n g a sa ni m p o r t a n tp a r to ft h el o g i s t i c ss y s t e m ， t h el o g i s t i c ss y s t e mr e s e a r c hf o c u so nl o g i s t i c sd i s t r i b u t i o no p t i m i z a t i o n p r a c t i c a l l y ，i no r d e r t om a k el o g i s t i c sd i s t r i b u t i o ne n t e r p r i s e so p t i m i z et h ed i s t r i b u t i o np a t h ，r e d u c ed i s t r i b u t i o n c o s t sa n di m p r o v el o g i s t i c sm a n a g e m e n ta n di n c r e a s et h ec o m p e t i t i v e n e s so ft h ee n t e r p r i s e s ， l o g i s t i c sd i s t r i b u t i o no f v e h i c l er o u t i n gp r o b l e m ( v r p ) h a sb e e ni n c r e a s i n g l yi m p o r t a n t t h e v r pi sn o to n l yt h ec o r eo fl o g i s t i c sd i s t r i b u t i o n ，b u ta l s oo n eo ft h ef o c u so fr e s e a r c h 。i n r e a l i t y , r e a s o n a b l ea r r a n g e m e n t s f o rv e h i c l er o u t i n gc a ni m p r o v et r a n s p o r te f f i c i e n c ya n d r e d u c es e r v i c ec o s t se f f e c t i v e l y s i n c et h ev r pw a sp u tf o r w a r d ，t h ee x p e r t sa n ds c h o l a r sh a v ec a r r i e do u te x t e n s i v e r e s e a r c h i th a sb e e nm a n ym a t u r ea l g o r i t h mt h a tp r o v i d e db a s i sf o rc o n t i n u i n gt h eq u e s t i o n f i r s t l y , t h i sp a p e ra n a l y z e dt h es t a t u sq u oo ft h ev r p ，d e s c r i b t e da n d c l a s s i f i e dt h e g e n e r a lv r p ，a n ds u m m a r i z e dt h ee x i s t i n ga l g o r i t h mf o rs o l v i n gv r p s e c o n d l y , i ti n t r o d u c e d t h ep a r t i c l es w a r mo p t i m i z a t i o n ( p s o ) o nb a s i cc o n c e p t s ，m a t h e m a t i c a lm o d e l sa n d a l g o r i t h m sp r o c e s s l a s t l y , i td e s c r i b e dt h ep r e d a t o rs e a r c hs t r a t e g y o nt h i sb a s i s ，i no r d e rt os o l v et h ev r p ，t h ep s oa l g o r i t h mb a s e do nt h ep r e d a t o rs e a r c h s t r a t e g yw a sd e s i g n e di nt h i sp a p e r i tr e g u l a t e dt h er e s t r i c t i o n so ft h ep r e d a t o rs e a r c hs t r a t e g y , f o ra c h i e v i n gi n c r e a s eo rd e c r e a s ei nt h ep s os e a r c hs p a c e m o r e o v e r ，i tb a l a n c e dt h et h e a b i l i t yf o re x p l o r i n ga n dd e v e l o p i n g ，t h a tc a nm a k et h ep s og e tt h eo p t i m a ls o l u t i o n t h e p s ow a si m p l e n t m e n t e dw i t hc + + c o m i l e r , a n da p p l i e dt h et e c h n i q u et oa na c t u a lp r o b l e m ， a n dp r o v e dt h ef e a s i b i l i t ya n dv a l i d i t yo ft h ea l g o r i t h m t h eu s eo ft h ea l g o r i t h mf o rv e h i c l e r o u t i n gp r o b l e mw a sa na d v i s a b l em e t h o d k e yw o r d s ：d i s t r u b u t i o n ，v e h i c l er o u t i n gp r o b l e m ( v r p ) ，p a r t i c l es w a r mo p t i m i z a t i o n ( p s o ) ， p r e d a t o r ys e a r c h 口s ) 论文独创性声明 本人声明：本人所呈交的学位论文是在导师的指导下，独立进行研究工 作所取得的成果。除论文中已经注明引用的内容外，对论文的研究做出重 要贡献的个人和集体，均已在文中以明确方式标明。本论文中不包含任何 未加明确注明的其他个人或集体已经公开发表的成果。 本声明的法律责任由本人承担。 论文作者签名：x l - 睥 矽8 年石月弓e l 论文知识产权权属声明 本人在导师指导下所完成的论文及相关的职务作品，知识产权归属学 校。学校享有以任何方式发表、复制、公开阅览、借阅以及申请专利等权 利。本人离校后发表或使用学位论文或与该论文直接相关的学术论文或成 果时，署名单位仍然为长安大学。 ( 保密的论文在解密后应遵守此规定) 论文作者签名： 夼淬 导师签名：i ) 争澎象， 砌8 年石月3e t 渺孑年多月3 日 长安大学硕j ：学位论文 第一章绪论 1 1 本文研究的背景及意义 1 1 1 本文的研究背景 根据g b t1 8 3 5 4 2 0 0 6 物流术语，物流的定义为：物品从供应地向接收地的实体 流动过程，根据实际需要，将运输、储存、装卸、搬运、包装、流通j n - r 、配送、信息 处理等基本功能实施有机结合。 物流研究的目的是对物流系统进行规划、管理、控制，选择最优的物流方案；寻求 降低物流费用、提高物流效益的途径等【1 】。国际社会一般用物流成本占g d p 的比重来衡 量一个国家的物流发展水平，比重越小越先进。1 9 9 1 2 0 0 3 年物流成本占g d p 的比重， 美国从1 0 6 降到8 5 2 ，其平均值为9 7 9 ；我国从2 4 下降到2 1 4 ，其平均值为 2 1 6 2 t 2 1 。2 0 0 4 年，我国物流成本占g d p 的比重仍然保持在2 1 3 的水平，比美国多 十几个百分点；到2 0 0 5 年，我国的物流费用占g d p 的比重约为1 8 5 t 2 1 。2 0 0 6 年为 1 8 3 。物流费用占g d p 的比重虽然有所下降，但是相比发达国家物流水平，仍明显滞 后。这说明我国物流运作水平是极为粗放的，社会化、专业化水平低，经济增长付出的 物流成本太高。根据中国物流信息中心的核算，中国物流成本每降低1 个百分点，就可 以新增1 3 0 0 亿元的社会经济效益。因此，降低企业巨额物流成本，挖掘“第三利润源泉” 对我国企业有着重要的意义。加入w t o 后，国内外经济全面接轨，促使物流领域全方 位、宽领域、深层次对外开放，加速了国内统一大市场的形成，给我国从传统物流向现 代物流转变带来了前所未有的巨大机遇。 物流系统中，运输是最重要的环节。从物流成本构成上看，运输、库存、管理成本 平均达到5 2 6 、3 1 8 和1 5 6 t 3 1 。从中可以看出运输成本在物流的各项成本当中所 占比重最高，占到物流总成本的一半以上。 面向城市内和区域范围内需求者的运输配送，是物流系统中由运输环节派生出 来的功能。具体地说，配送是根据客户订单将货物送达客户的过程，包括进货、进货检 验、分拣、储存、流通加工、拣选、包装、组配、装车、送货等。配送是市场竞争的产 物，为获得最大效益，物流企业就要面对整个配送过程进行优化。于是，实践上出现了 送货时车辆的合理调配，路线规划，送货前配货，配装等有利于提高配送速度的方法。 1 1 2 本文研究的意义 物流配送的核心部分，主要就是进行配送车辆优化调度。车辆路径问题( v e h i c l e 第一章绪论 r o u t i n gp r o b l e m ，v r p ) 是物流配送调度中具有广泛应用的优化联合问题，在现代物流中 居于中心地位。配送中心需按不同客户不同的订货要求进行组织配送，其主要内容是指 根据确定配送货物量分配车辆和选择优化路线。由于从事物流配送的车辆货运工作，尤 其是从事城市配送的车辆货运工作条件复杂：不仅货运点多、货物种类繁多、道路网复 杂，而且运输服务地区内运输网点分布也不均匀。同时，很多客户还对配送需求提出一 些约束条件的要求。因此应用现代数学方法及计算机快速求解优化调度方案是国内外专 家普遍探讨的重要课题。车辆路径问题成为运筹学与组合优化领域的热点问题。 车辆路径问题，简单的说就是车辆和路径的恰当选取，运输规划的合理制定问题。 合理解决车辆路径问题，不仅可以简化配送程序、降低配送的空载率、减少配送次数； 尤为重要的是可以降低现实世界的交易成本，带来更大的经济效益，而且可加快对客户 需求的响应速度，提高服务质量，增强客户对物流环节的满意度等。如何合理安排车辆 路径问题就显得更加重要。所以研究车辆路径问题的特点及算法具有重要的实际意义。 1 2 车辆路径问题国内外的研究现状 车辆路径问题( v e h i c l er o u t i n gp r o b l e m ，v r p ) 有着现实的经济意义和学术意义。 所以，当v r p 被d a n t z i g 和r a m s e r 4 1 于1 9 5 9 年提出之后，很快就引起各个学科专家与 运输计划制定者和管理者的极大重视，成为运筹学与组合优化领域的前沿问题和研究热 点。目前己经产生出多种成熟的算法，并取得了令人瞩目的成果，为后人的继续研究提 供了极高的参考价值。 1 2 1 国外的研究现状 1 9 6 2 年，b a l i n s k i 等人首先提出v r p 的集分割 5 1 ，直接考虑可行解集合，在此基础 上进行优化，建立了最简单的v r p 模型。 1 9 7 1 年，e i l o n 等人【6 】提出将动态规划法用于固定车辆数的v r p ，通过递归方法求 解。 1 9 7 4 年，w r e n ，g i u e t t 等人【7 1 提出s w e e p 算法( 扫描法) 。目的在于求解车辆调度问 题，并针对当时几个求解相似问题的算法进行了比较，证明该算法所求得的解较优于其 它方法。 1 9 8 1 年，c h r i s t o f i d e s 等人【8 】提出了k 度中心树和相关算法，对固定车辆数m 的m t s p 进行了进行k 度中心树松弛。后来，m l f i s h e t 9 1 对这种方法做了进一步改进，可求解有 1 3 4 个客户的v r p 。 2 长安人学硕士学位论文 1 9 9 1 年，g e n d r e a u 等人【l o 】将禁忌搜索方法应用于v r p ，它是比较好的启发式算法， 可以成功地应用于许多经典的v r p 。 1 9 9 6 年，j l a w r e n c e t l l 】将遗传算法用于v r p 的研究，有效的求解出带时问窗限制 的v r p 。 1 2 2 国内的研究现状 1 9 9 9 年，姜大立等人【1 2 1 在分析v r p 现有启发式算法的基础上，构造了v r p 的染色 体表达，并对染色体进行可行化映射，建立了v r p 的遗传算法。张涛等人【”1 通过遗传 算法来保证搜索的全局性，用3 - o p t 算法来加强局部搜索能力，得到针对v r p 的混合算 法，目前这类算法己可以求解较大规模的问题 2 0 0 0 年，肖鹏等人【1 4 】通过构造v r p 的染色体表达，采用基因换位算子进行染色体 重组，实现了单亲遗传算法。 2 0 0 1 年，李嘉等人【1 5 】通过引入车队模式”，提出了混合车队v r p 求解框架，设计 了基于遗传算法和禁忌搜索启发式的混合算法。 2 0 0 2 年，张丽萍等人【1 6 】通过引入新颖交叉算子，构造了一种改进遗传算法，此算 法摆脱了对群体多样性的要求，不存在传统遗传算法常见的“早熟收敛”问题，最终能收 敛到问题的最优解或满意解。 2 0 0 3 年，方霞等人【1 7 】利用免疫算法的全局搜索能力和收敛性，将新型的启发式算 法用于解决v r p 。 2 0 0 4 年，王正彬等人在分析v r p 现有启发式算法的基础上，建立了考虑线路安 排的物流配送方案模型，并提出了求解该问题的一种搜索算法。陈湘洲等人【1 9 】引入一种 进化逆转算子，改进了遗传算法求解v r p 时的局部搜索能力。崔雪丽等人2 0 1 基于近些 年出现的新型智能优化思想：人工蚂蚁系统，给出了一种可快速求解v r p 的蚂蚁搜索 算法。通过定义基本的人工蚂蚁状态转移概率，并结合局部搜索策略，用迭代次数控制 算法的运行时间，从而使该方法具有使用意义和可操作性。张兢等人【2 1 1 构造了一种免疫 克隆算法来求解v r p ，并在算法中引入了克隆选择、克隆删除、受体编辑、体细胞高频 变异、抗体循环补充等思想。仿真计算结果表明，免疫克隆算法能有效地解决v r p 。 2 0 0 5 年杨善林等人提出了一种基于蚁群优化( a c o ) 的混合算法来解决冲。首 先提出一种a c o 算子，然后加入局部搜索机制并使用基于问题的特定启发信息一节约 量来改进算法。魏俊华等人【2 3 1 提出了一种分段编码方法。基于分段遗传编码，构造了车 辆路径问题的遗传算法，通过对编码各段超载、包容等的判断，得出一个关于需求城市 3 第一章绪论 的最优划分。最后利用改进的迪杰斯特拉算法，根据最优划分中的需求城市，采取最优 的配送路径集。尹晓峰等针对了蚁群算法存在的过早收敛问题，引入节约量以及车辆 载重利用率两种启发式信息对蚁群算法加以改进，并加入2 - o p t 方法对问题求解进行了 局部优化。 由此可见，我国国内学者研究车辆路径问题的算法主要集中启发式算法上。对各种 启发式算法进行改进，然后对不同的v r p 问题进行算法设计。但是对于启发式智能算 法中的另一种算法粒子群算法却应用不是很多。 1 2 - 3 车辆路径问题中粒子群算法的应用现状 2 0 0 4 年，李宁等人【2 5 】基于一种新出现的群智能优化方法，将其应用于车辆优化问 题。构造了车辆路径问题的粒子群算法，并与遗传算法做了对比试验。结果表明，粒子 群算法可以快速、有效的求得车辆路径问题的优化解，是求解车辆路径问题的一个较好 方案。 2 0 0 6 年，罗先国【2 6 1 将局部版粒子群算法应用于非满载车辆路径问题。设计了一种 实数编码方案，线性调整惯性权值，改进了粒子更新公式，建立了改进该问题的粒子群 算法。提高了搜索最优路径的成功率。 2 0 0 7 年，马惠民吲设计引入了模拟退火机制的并行粒子群算法对车辆路径问题进 行求解。该算法结合了基本粒子群优化算法的快速寻优能力和模拟退火算法的概率跳突 性，避免了基本粒子群优化算法易于陷入局部最优的缺点，提高了进化后期算法的的收 敛精度。 目前，粒子群算法在物流领域的应用研究才刚刚起步，但是随着研究的进一步深入， 粒子群算法将会在物流领域中广泛应用，并且在v r p 问题中得到进一步的发展。 1 3 本文主要研究内容及框架 1 3 1 本文主要研究内容 由于车辆路径问题的研究具有重要的现实意义。因此应用现代数学方法及计算机快 速求解优化车辆路径问题是国内外专家普遍探讨的重要课题，应用何种算法才能获得车 辆路径问题的最优解是现在学者研究的热点。本文主要的研究内容是在对车辆路径问题 已有算法研究的基础上，设计了一种基于捕食搜索策略的粒子群算法，并利用这种算法 对车辆路径问题的模型进行求解，用c + + 语言编程实现并通过实例验证该算法的可行性 和有效性。 4 长安大学硕士学位论文 1 3 2 本文的论文框架 本文内容共分为五章。 第一章为绪论。阐述课题研究背景及研究意义。分析了我国的物流水平，指出运输 是影响物流成本的重要因素。由此引出优化车辆路径问题的重要性。其次，给出了车辆 路径问题的国内外研究现状以及粒子群算法在车辆路径问题中的应用现状。最后给出了 全文的主要研究内容。 第二章为物流配送及车辆路径问题。首先对车辆路径问题的研究背景物流配送 进行了介绍。并对车辆路径问题给予一般描述，归纳了车辆路径问题的种类和特点，以 及目前解决该问题的各种算法。 第三章为粒子群算法的研究与改进。分析了粒子群算法的基本思路及粒子群算法的 原理，建立了粒子群算法数学模型及算法流程，并总结了学者们对基本粒子群算法的改 进。随后在分析了捕食搜索策略基本思想的基础上，将捕食搜索策略引入标准粒子群算 法中，构建了基于捕食搜索策略的粒子群算法，并探讨了基于捕食搜索策略的粒子群算 法基本思想和算法流程。 第四章为基于捕食搜索策略的粒子群算法的v r p 研究。首先建立了v r p 的数学模 型，然后利用基于捕食搜索策略的粒子群算法求解模型，对其进行算法设计，用c h 编 程实现了该算法并通过实例验证。实验结果表明改进后的粒子群算法能很好的解决车辆 路径问题，能够找到潜在的更精确的解。 最后是全文总结与未来展望。总结了本文的主要工作，以及有待改进的地方，并提 出进一步的研究方向。 论文的内容框架见图1 1 。 1 4 本章小结 本章主要介绍了本文研究的背景及意义，并对所要研究车辆路径问题的国内外研究 现状进行了分析，最后给出了本文主要的研究内容和论文的框架。 5 第一章绪论 绪论 研究背景与研究意义 车辆路径问题的国内外研究现状 本文的主要研究内容及框架 上上 物流配送及车辆路径问题 物流配送的概述 车辆路径问题 7 粒子群算法的研究与改进 粒子算法的数学模型及算法流程 改进的粒子群算法及比较 基于捕食搜索策略的粒子群算法基本思想及算法实现 上上 基于捕食搜索策略粒子群算法的车辆路径问题研究 车辆路径问题数学模型的建立 基于捕食搜索策略的粒子群算法设计 基于捕食搜索策略的粒子群算法求解车辆路径问题 实例验证的结果与分析 上上 全文总结与未来展望 全文总结 未来展望 图1 1 论文的内容框架 6 长安大学硕士学位论文 第二章物流配送及车辆路径问题 2 1 物流配送概述 ( 1 ) 配送的定义 根据g b t1 8 3 5 4 2 0 0 6 物流术语，配送的定义为：在经济合理区域范围内，根据 客户要求，对物品进行拣选、加工、包装、分割、组配等作业，并按时送达指定地点的 物流活动。 ( 2 ) 配送概念的内涵 1 ) 配送提供的是物流服务，因此满足顾客对物流服务的需求是配送的前提。 由于在买方市场条件下：顾客的需求是灵活多变的，消费特点是多品种、小批量。 从这个意义上说，配送活动绝不是简单的送货活动，而应该是建立在市场营销策划基础 上的企业经营活动。而且单一的送货功能，无法较好地满足广大顾客对物流服务的需求。 因此配送活动是多项物流活动的统一体。有些学者认为：配送就是“小物流”。只是比大 物流系统在程度上有些降低和范围上有些缩小罢了。 2 ) 配送是“配 与“送的有机结合 所谓“合理地配 是指在送货活动之前必须依据顾客需求对其进行合理的组织与计 划。只有“有组织有计划 地“配 才能实现现代物流管理中的“低成本、快速度”地 “送，进而有效满足顾客的需求。 3 ) 配送是在合理区域范围内的送货 配送是在小范围内实施的物流活动，通常仅局限在一个城市或地区范围内进行。 ( 3 ) 配送的特点 配送的实现需要信息网络技术的支持，它包括以下特点【2 8 1 ： 1 ) 配送不仅仅是送货。配送业务中还包含了“拣选 、“分货、“分割、“组配 、 “配货等工作。这些工作难度很大，必须具有发达的商品经济和现代的经营水平才能 做好。 2 ) 配送是送货、分货、配货等活动有机结合的整体，同时它还与订货系统紧密联 系。因此，配送必须依赖现代情报信息，建立和完善整个大系统，使其成为一体化作业 系统。 3 ) 由于现代化技术和装备的采用，使配送的全过程有现代化技术和装备的保证。 从而现在的配送在规模、水平、效率、速度等方面都远远超过了以往的送货形式。 4 ) 以往的送货形式只是作为推销的一种手段，目的仅仅在于多销售一些。而配送 7 第二章物流配送及车辆路径问题 则是一种专业化的分工方式，是大生产、专业化分工在流通领域的表现。因此，如果说 一般的送货是一种服务方式的话，配送则可以说是一种体制形式。 ( 4 ) 配送的分类 在长期的实践中，配送以不同的运作特点和方式满足不同顾客的需求。为了满足不 同产品、不同企业、不同流通环境的要求，经过较长一段时期的发展，产生了多种形式 的配送，从而形成了不同的配送类型。根据配送模式、组织方式的不同，配送可分为以 下类型： 1 ) 按配送模式不同分类： 直达配送模式 配送中心在货物运距较远、顾客较多且需求日趋复杂的情况下，不经过物流基地中 转，直接从工厂或仓库进货，并将装好的货物送达客户。 即时配送模式 即时配送是根据用户提出的时间要求、供货数量和品种要求及时地进行配送的形 式。即时配送可以满足用户( 特别是生产企业) 的急需，它是一种灵活的配送方式。 计划配送模式 物流企业为了兼顾用户满意水平和配送服务效率，在市场竞争中处于优势地位，在 实践中推行“路线发送”和“时间表发送 等计划配送制度。即按照地区和配送货物的 数量进行配送时间间隔和配送具体线路的分配。 共同配送模式 共同配送，即由若干个配送企业联合起来，对某一地区的用户进行配送服务的物流 形式。它是在核心组织( 配送中心) 的统一计划、统一调度下展开的。由于共同配送是 一种协作性的配送活动，因而有利于充分发挥各配送企业的整体优势，便于合理调配、 调度运输工具和综合利用物流设施。对于参加协作的配送企业来说，不仅可以提高配送 的服务水平，而且还可以借此扩大销售渠道和开展联合经营；对于用户来说，不但可以 满足生产经营活动的整体需要，尤其有利于保证重点建设项目的需要。 一体化配送模式 它是将物流与信息流紧密结合在一起的高水平配送管理模式。这里“一体化 有两 层含义：一是“货架一体化 ，该模式以某一货架群作为整体对象，不问进货地点和形 态，将全部商品备齐后集中上货；二是“业务一体化”，该模式不仅包揽进货业务，而 且还要求发货的商品完全不出现差错地以陈列的方式进入店铺。 长安大学硕士学位论文 2 ) 按配送组织者不同分类： 配送中心配送 组织者是专职从事配送的配送中心。规模较大，储存量也较大，可按配送需要储存 各种商品。配送中心专业性强，和用户建立固定的配送关系，一般实行计划配送。所以， 需配送的商品往往都有自己的库存，很少超越自己的经营范围。 商店配送 组织者是商业或物资的门市网点。主要承担零售，规模一般不大，但经营品种齐全。 除日常零售业外，还可以根据用户的要求将商店经营的品种配齐，或代用户定购一部分 商店平时不经营的商品，和商店经营的品种一起配齐送达用户。 仓库配送 以一般仓库为据点进行配送。它可以是把仓库完全改造成配送中心，也可以是在保 持仓库原功能的前提下，以仓库原功能为主，再增加一部分配送职能。一般来讲，仓库 配送的规模较小，配送的专业化较差。 生产企业配送 组织者是生产企业，尤其是进行多品种生产的生产企业。生产企业配送不是配送的 主体，它只是在地方性较强的产品生产企业中应用较多，比如就地生产、就地消费的食 品、饮料、百货等。 3 ) 按配送商品的种类及数量不同分类： 单( 少) 品种大批量配送 工业企业需要量较大的商品，单独一个品种或仅少数品种就可以达到较大输送量， 可实行整车运输，由专业性很强的配送中心配送。 多品种少批量配送 按用户要求，将所需的各种物品( 每种需要量都不大) 配备齐全，凑整装车后由配 送结点送达用户。这种配送作业水平要求高，配送中心设备要求复杂，配货送货计划难 度大，因此需要有高水平的组织工作保证和配合。而且在实际中，多品种少批量配送往 往伴随多用户多批次的特点，配送频度往往较高。 配套成套配送 根据企业的生产需求，尤其是装配型企业的生产需求，把生产每一台件所需要的全 部零部件配齐，按照生产节奏定时送达生产企业，生产企业随即可将此成套部件送入生 产线以装配产品。 9 第二章物流配送及车辆路径问题 还有按配送的时间及数量不同分类、按经营形式不同分类等，可将配送分为其他类 型，见表2 1 所示。这些配送形式都有其各自的优势，但是同时也存在一定的局限性。 表2 1 配送分类表 分类 配送商品的种按配送的时间 标准 配送模式配送的组织者经营形式 类及数量及数量 直达配送模式 单品种大批量定时配送销售配送 即时配送模式 配送中心配送 配送定量配送供应配送 类型计划配送模式 商店配送 多品种少批量定时定量 销售供应一 共同配送模式 仓库配送 生产企业配送 配送 定时、定线路配送体化配送 一体配送模式配套成套配送即时配送代存代供配送 ( 5 ) 配送运输基本作业流程 配送管理受到许多因素的影响：如订单处理很费功夫，难以制订配送计划、难以选 择配送路径，配送效率低、难以按时交货、配送绩效评价基准不明确等。同时在实际配 送的过程中，还受许多不可控因素的影响，如用户的分布区域、道路交通网络、车辆通 行限制、送达时间要求、车流量变化、道路施工、用户变动、车辆变化等。为此，必须 对物流配送系统进行总体规划和设计，如根据客户分布地点划分基本配送区域，完成车 辆配载，暂定配送的先后顺序，考虑货物、车辆的特征及费用安排车辆，选择配送路线， 确定配送顺序，最后完成车辆积载。配送运输作业的基本流程如图2 1 所示。 图2 1 配送运输基本作业流程 1 0 长安大学硕士学位论文 ( 6 ) 我国物流配送现状的不足与发展趋势 1 ) 我国物流配送现状的不足 虽然我国物流现代化的步伐正在不断地加快，但与发达国家相比依旧存在着较大的 差距。相较而言：我国整个物流配送系统还不完善，存在着一系列问题，这些问题也影 响着整个物流行业的发展。 我国物流业配送系统基础设施薄弱，现代化程度低 物流配送系统整体功能落后。主要是因为交通路径和运行设施满足不了要求；其次 是交通装备水平落后、仓库存储设施落后。第三方物流企业拥有的仓库7 0 是普通平房 仓库，现代化立体自动化仓储设施比例极低，具有冷藏、保鲜、气调功能的仓库更少。 还有就是物流运输系统中使用的辅助装备标准化差，运输中使用的集装箱、托盘、货架 等标准化程度低。有的利用欧美标准，有的采取日本标准，这就使物流储运配送各环节 对接不便，影响了物流作业效率。 我国物流配送规模小，配送效率低 由于我国的第三方物流市场发展落后，所以第三方物流市场数量、经营规模小，市 场份额及服务功能少。大多数物流企业只是按用户要求，从事单一功能的运输与仓储， 很少能提供物流策略，深入到整个物流环节链的全过程管理。配送中心客户规模太小， 配送中心难以从供应商手中接收多种大批量商品，不利于转运、分类、保管、流通 和加工，无法做到迅速、准确、便宜地配送货物，不利于实现规模经济效益。 物流企业信息化水平较低 物流企业的信息技术水平较低，是物流和配送发展的巨大障碍。许多现代信息技术， 如条码技术、射频技术、e d i 技术、全球卫星定位系统技术等，都处于学习和起步阶段。 人才的短缺和观念的落后 物流和配送方面的人才短缺，是物流和配送发展的巨大障碍。我国在物流和配送方 面的教育还很落后，虽然有一些高等院校设置了物流专业和课程，但为数较少，高级物 流管理人才更是缺乏。许多企业缺乏现代物流与配送的观念，如对物流配送的功能和作 用的认识尚不全面。对于物流配送中心这一现代流通形式，在功能、设施设备及管理、 技术等方面的科技含量也认识不足，这在一定程度上影响着物流配送活动在全社会的发 展。 2 ) 我国物流配送的发展趋势 在信息化时代，随着网络技术，电子商务、交通运输、物流管理的现代化，现代物 第二章物流配送及车辆路径问题 流企业配送系统也将不断的实现现代化管理模式，从而出现了系统化、自动化、信息化、 智能化的趋势，其主要表现如下： 配送的组织者向第三方物流企业发展 随着物流的发展和分工的深化，专业物流企业，即第三方物流企业将不断出现。专 业化物流配送系统取代了原有生产者和销售商自营的物流配送系统。这样既能使生产者 专心于自己所熟悉的生产业务，又能起到优化资源配置，降低配送费用，提高配送效率。 由第三方物流企业负责商品的配送环节可以提高运输的网络效率，并能更好照顾顾客的 要求，最大限度缩短运输周期，提高物流运输的反应速度。 配送系统的计划化、规模化 以单位企业为主体的配送系统存在着车辆利用率低，运力和仓储投资不合理的现 象。现代物流企业中配送系统的发展将扩大企业的规模，扩大企业经营范围，使配送更 加计划化、运行合理化，达到服务的高效率。从而使物流企业更具有竞争能力。 配送管理技术与方法的现代化 配送管理与电子商务发展相结合。随着运输规模的扩大和计算机的应用，物流业中 配送的信息传递逐渐采用数据交换技术( e d i ) ；还有计算机与自动化装置相结合，使单 位产品运输成本降低，效率提高，同时也提高了服务质量，这就使物流业中配送管理的 技术与方法进入了现代化。 现代物流发展政策环境的进一步完掣2 9 】 关于促进我国现代物流业发展的意见中明确指出：要建立和完善物流技术标准 化体系，加快制定和推进物流基础设施、技术装备、管理流程、信息网络的技术标准， 尽快形成协调统一的物流现代化技术标准化体系。此外，我国有关部门正在进行一系列 物流相关工作：国家发改委制定了全国物流业发展“十一五专项规划；国家统计局决 定建立社会物流业国家统计制度；国家标准委在2 0 0 5 年推行了物流企业分类标准。 展望未来，在中央及地方各级政府、行业管理部门、工商企业、物流相关产业与服 务企业以及各地行业协会的共同努力下，我国现代物流发展将迎来一个机遇与挑战并 存、改革与发展共进的积极、健康、高效的新发展阶段。 2 2 车辆路径问题 车辆路径问题( v e h i c l er o u t i n gp r o b l e m ，v r p ) 是关于车辆配送路径集合问题的通 称。这些路径集合就是一个或多个配送中心( d e p o tc e n t e r ，d c ) 的一组车辆完成地理 上分散的多个城市或者客户的配送所需要运行的路径集。 1 2 长安大学硕士学位论文 在配送运输中，由于配送用户多，城市交通路线又较复杂，如何组成最佳路线，如 何使配装和配送路线有效搭配等，是配送运输的特点，也是难度较大的工作。采用科学 的、合理的方法来确定配送线路，成为提高物流配送车辆效益、实现物流配送科学化的 重要途径。因此，目前该领域许多的研究工作都是以物流配送活动为背景描述的。物流 配送活动中的配送运输路线确定问题，是近二十多年来车辆路径问题的重点研究对象和 应用领域。 2 2 1 车辆路径问题的一般描述 该问题的一般描述是：对一系列给定的顾客需求点设计适当的配送车辆行驶路线， 使其从配送中心出发，有序地通过各需求点，最后返回配送中心，并在满足一定的约束 条件下( 如货物需求量、发货量、车辆容量限制、行驶里程限制、时间限制、交发货时 间等) ，达到一定的优化目标( 如路程最短、费用最少、时间尽量少、使用车辆数尽量 少，车辆利用高等) 。即v r p 的目标就是用最少费用的行车线路完成对所有客户的配送。 其特点在于：顾客群体大，涉及了多辆交通工具的服务对象选择和路线( 服务顺序) 确 定两方面问题。 图2 2 是4 条车辆行驶路线的巡回配送图，方框表示中心站点，箭头表示路线，圆 圈表示顾客需求点。 图2 2 车辆行驶路线图 车辆路径问题受到很多的限制条件，如： ( 1 ) 每辆车有运载能力的限制，存在着最大载质量： ( 2 ) 每个客户必须在特定的时间范围内进行服务； ( 3 ) 物流企业有很多配送中心对客户进行服务； ( 4 ) 客户向配送中心返回一些货物； 第二章物流配送及车辆路径问题 ( 5 ) 客户可以被不同的车辆服务； ( 6 ) 客户数量，配送需求，行使路线等随机出现； ( 7 ) 客户之间服务的次序存在着限制。 在研究工作中，常采用的约束条件假定为：每个顾客被一辆车服务，并且只能被一 辆车服务；每个顾客有一个需求，即要求车辆在此顾客处分发或者带走一定数量的货物， 我们称这个需求为客户需求；车辆在对服务顾客的时候，其载重量不能超过车辆本身的 最大载质量。与实际情况相结合，还可以考虑多个中心、中心的车辆类型不同、顾客服 务的时间性要求以及顾客需求的随机化等等。对某一具体问题，上述约束条件可能全部 存在，也可能只存在一部分。 2 2 2 车辆路径问题的分类 v r p 是一个广阔的研究领域。根据附加条件和任务要求的不同，可以构成不同类型 的v r p 。为更好地了解v r p ，现对其分类作一详细阐述。 ( 1 ) 按配送中心的数目分：有单配送中心问题( 配送系统中仅有一个配送中心) 和多配送中心问题( 配送系统中存在多个配送中心) 。 ( 2 ) 按客户对货物取( 送) 时间的要求程度分：有无时间窗限制问题( 客户对货 物的取走或送到的时间无具体要求) 、有时间窗限制问题( 客户要求将需要的货物在规 定的时间窗内送到，将供应的货物在规定的时间窗内的取走) 和混合型时间窗( 在系统 中有些顾客属于硬时间窗，有些属于软时间窗；对同一顾客，又可能软、硬时间窗混合 使用) 。有时间窗限制问题又分为硬时间窗问题( 客户要求货物必须在规定的时间窗内 送到或取走，不能提前也不能拖后) 和软时间窗问题( 客户要求将货物尽量在规定的时 间窗内送到或取走，但也可以提前或拖后，只不过在提前或拖后时对配送企业实施一定 的惩罚) 。 ( 3 ) 按车辆载货状况分：有满载问题( 由于客户需求或供应的货物数量大于或等 于车辆的载重量，故完成一项配送任务需要一辆或更多辆的配送车辆，配送车辆需要满 载运行) 、非满载问题( 由于客户需求或供应的货物数量小于车辆载重量，多项配送任 务可共用一辆配送车辆，车辆在配送过程中经常处于不满载状态) 以及满载和非满载混 合问题( 由于一部分客户需求或供应的货物数量大于或等于车辆的载重量，而另一部分 客户需求或供应的货物数量小于车辆的载重量，造成一些配送车辆需要满载运行，而另 一些车辆则经常处于不满载状态) 。 ( 4 ) 按配送任务特征分：有纯送货问题( 仅考虑从物流中心向客户送货，也称为 1 4 长安大学硕士学位论文 纯卸问题) 、纯取货问题( 仅考虑把各客户供应的货物取到物流中心，也称为纯装问题) 及取送混合问题( 既考虑将客户需求的货物从物流中心送到各个客户，同时考虑将客户 供应的货物从客户取回到物流中心，也称为装卸混合问题或集货和送货一体化问题) 。 ( 5 ) 按车辆类型分：有单车型问题( 所有配送车辆的载重量相同) 和多车型问题 ( 配送车辆的载重量不完全相同) 。 ( 6 ) 按运输车辆路线分：有车辆开放问题( 即车辆完成配送任务后可以不返回其 发出车场) 和车辆封闭问题( 车辆完成配送任务后必须返回其出发车场) 。 ( 7 ) 按优化目标数分：有单目标问题( 仅考虑一个配送目标) 和多目标问题( 同 时考虑多个配送目标) 。 ( 8 ) 按客户和路网的特点分：有静态问题( 客户位置、客户数目、客户需求、天 气路况等因素是事先确定的) 和动态问题( 客户数目、客户位置、客户需求、天气路况 等因素不是事先确定的，而是随机变化的) 。 ( 9 ) 按任务性质分：有对弧服务问题( 中国邮递员问题) 、对点服务问题( 旅行商 问题) 以及混合服务问题( 交通车路线安排问题) 。 ( 1 0 ) 按已知信息的特征分：有确定性问题( 客户固定、包括位置和数量) 和不确 定性问题( 客户不固定) 。 以上对配送车辆路线问题的附加条件和任务要求不同的分析是进一步对问题进行 建模和求解的基础。本文主要考虑最基本的车辆路径问题，即单仓库、非满载、单车型 的送货车辆路线问题。 2 2 3 配送车辆路径优化的目标 对配送车辆路径进行优化时，必须有明确的目标，遵循基本的原则。配送路线方案 目标的选择可以从下面几个方面来考虑： ( 1 ) 配送效益最高或配送成本最低 效益是企业追求的主要目标，可以简化用利润来表示，或以利润最大化作为目标； 成本对企业效益有直接的影响，选择成本最低化作为目标值与前者有直接的联系。当有 关数据容易得到和容易计算时，就可以用利润最大化或成本最低化作为目标值。 ( 2 ) 配送里程最短 如果配送成本与配送里程相关性较强，而和其他因素相关性较弱时，配送里程最短 的实质就是配送成本最低。此时则可考虑用配送里程最短作为目标值，这样就可以大大 简化路线选择和车辆调度方法。当配送成本不能通过里程来反映，如道路收费、道路运 第二章物流配送及车辆路径问题 行条件严重影响成本时，单以最短路程作为目标就不适宜。 ( 3 ) 配送服务水平最优 如准时配送要求成为第一位时，或需要牺牲成本来确保服务水平时，则应该在成本 不失控的情况下，以服务水平为首选目标。这种成本的损失可能从其它方面弥补回来， 如优质服务可以采取较高的价格策略。 ( 4 ) 配送劳动的消耗最小 即以物化劳动和活劳动消耗最小为目标，在许多情况下，如劳动力紧张、燃料紧张、 车辆及设备较为紧张的情况下，限制了配送作业的选择范围，就可以考虑以配送所需的 劳动力、车辆或其他有关资源作为目标值。 配送路线方案的目标实际上是多元的，但为了便于求解，一般要尽可能选择单一 化的目标值，这样容易求解，实用性较强。 本文对车辆路径问题的优化采用配送里程最短作为优化目标。 2 2 4 车辆路径问题的相关算法 v r p 的求解方法很多，许多学者对v r p 的求解方法的分类进行了研究，基本上可 以分为精确算法和启发式算法两类。 2 2 4 1 求解v r p 问题的精确算法 精确算法指可求出其最优解的算法。精确算法主要有分枝定界解法( b r a n c ha n d b o u n d a p p r o a c h ) 1 3 0 】、割平面法( c u t t i n g p l a n e sa p p r o a c h ) 1 3 1 、网络流算法(