（管理科学与工程专业论文）车辆路径问题的多目标规划模型与算法研究.pdf

学位论文版权使用授权书 江苏大学、中国科学技术信息研究所、国家图书馆、中国学术期 刊( 光盘版) 电子杂志社有权保留本人所送交学位论文的复印件和电 子文档，可以采用影印、缩印或其他复制手段保存论文。本人电子文 档的内容和纸质论文的内容相一致，允许论文被查阅和借阅，同时授 权中国科学技术信息研究所将本论文编入中国学位论文全文数据库 并向 上会提供查询，授权中国学术期刊( 光盘版) 电子杂忐f ：将本论 文编入中国优秀博硕士学位论文全文数据库并向 c 会提供f t f 询。 论文的公布( 包括刊登) 授权江苏大学研究生处办理。 本学位论文属于不保密自( 学位论文作者签名：锵茗0 矽1 7 年月昨日 指导教师签 1 多l1 年 车辆路径问题的多目标规划模型与算法研究 r e s e a r c ho nm u l t i o b je c t i v ep r o g r a m m i n gm o d e la n d a l g o r i t h m f o rv e h i c l er o u t i n gp r o b l e m 姓 2 011 年6 月 江苏大学硕士学位论文 摘要 物流配送中的车辆路径问题( 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 。由于中西方国家在地理环境、 人口密度和经济发展水平等方面都存在着较大的差异，传统的数学模 型不能准确的反映我国实际的配送情况。因此，针对中国的配送实际， 对v r p 数学建模和算法研究进行了探讨。 首先，详细介绍了物流配送的相关概念和特点，通过对配送网络 结构进行分析，结合实际问题，将研究对象界定为单级配送网络下的 v r p 。针对中国人口密度特点，通过对比中美两国在人口密度上的差 异，分析了客户网点数和运输里程对实际配送效果的综合影响，提出 了“装卸频率 的概念，并将装卸频率作为衡量v r p 规模的一个重 要指标。 其次，以最小化配送车辆数、行驶里程数和平均装卸频率为优化 目标，建立多目标优化模型，利用线性加权法将模型中的多个目标函 数合并成单目标函数。由于三个目标函数之间的量纲不同意且目标函 数值的大小相差较大，不能够直接运用线性加权法。因此，针对存在 问题，对模型中目标函数进行了处理。最后，结合企业调研实际，设 定了目标函数的权系数之间的大小关系。 再次，为了克服传统两阶段启发式算法系统性不足的缺点，按照 车辆路径问题的多目标规划模型与算法研究 分解协调的思想，将c 。w 节约算法与遗传算法进行融合，设计了混 合遗传算法( g a c w ) 求解框架，并进一步引入考虑载重量约束的路 径交叉算子和反转变异算子，通过算例对模型和算法的有效性进行了 验证。 最后，以镇江烟草物流配送中心配送车辆路径优化问题为案例， 分析了配送中心现行的配送方案，通过来自配送中心的大规模数据 ( 2 0 6 个客户网点) 验证了模型和算法对于大规模车辆路径问题 ( l s v r p ) 的适用性。通过模型的优化，公司送货车辆数减少1 4 、 行驶里程降低2 1 程，平均装卸频率降低了4 7 ，达到了一个较好 的水平，实现了企业配送成本和员工劳动强度之间的均衡。 关键词：物流配送，车辆路径问题，多目标规划，装卸频率 江苏大学硕士学位论文 a b s t r a ct t h ev e h i c l er o u t i n gp r o b l e m ( v r p ) i sat y p i c a ll o g i s t i c sd i s t r i b u t i o nr o u t i n g o p t i m i z a t i o np r o b l e ma n dh a sb e e np r o v e dt ob en p h a r dp r o b l e m b e c a u s eo ft h e t h e o r e t i c a la n dp r a c t i c a ls i g n i f i c a n c e ，t h ev r ph a sa l w a y sb e e nt h eh o tt o p i ci nt h e a c a d e m i cc o m m u n i t y t r a d i t i o n a l l y ，m o d e l i n gi nv r pi sr e l a t i v e l ys i m p l e ，a n dt h e p r e v i o u sr e s e a r c h e s a r ep r i m a r i l yf o c u s e do nd e s i g n i n gm o r ee f f i c i e n ta l g o r i t h m w h i c hc a ns o l v ev r p sw i t hl a r g e rn u m b e ro fc u s t o m e rd o t h o w e v e r , t h e r ea r eb i g d i f f e r e n c e si n g e o g r a p h i c a le n v i r o n m e n t ，p o p u l a t i o nd e n s i t y a n de c o n o m i c d e v e l o p m e n tb e t w e e nc h i n e s ea n dw e s t e r n ，t h et r a d i t i o n a lm a t h e m a t i c a lm o d e lc a n n o tr e f l e c tt h es p e c i a lp r a c t i c a ls i t u a t i o ni nc h i n a t h e r e f o r ，a c c o r d i n gt ot h ea c t u a l d i s t r i b u t i o ns i t u a t i o ni nc h i n a , i nt h i sp a p e r , t h em a t h m a t i c a lm o d e lo fv r p ，w h i c hi s f o c u s e do nt h ea c t u a ld i s t i b u t i o ns i t u a t i o ni nc h i n a ，i se s t a b l i s h e da n dt h ea l g o r i t h m w h i c hi ss u i t b a l ef o rt h ev r pi n t h i sp a p e ri sd i s c u s s e d f o l l o w i n ga r et h em a i n r e s e a r c hd u r i n gt h et h r e ey e a r s ： b a s e do nt h ec h a r a c t e r i s t i c so ft h ep o p u l a t i o nd e n s i t yi nc h i n a , t h ed i f f e r e n c ei n p o p u l a t i o nd e n s i t yb e w e e nc h i n aa n da m e r i c a a r ec o n t r a s t e d b ya n a l y z i n gt h e i n f l u e n c eo fc u s t o m e rd o tn u m b e ra n dd i s t a n c eo na c t u a le f f e c to fd i s t r i b u t i o n ，t h e c o n c e p to fh a n d l i n gf r e q u e n c yw a sp r o p o s e d ，f u r t h m o r e ，t h ec o n c e p tw a ss e tt ob ea l l i m p o r t a n tc r i t e r i ao f t h es c a l eo fv r p am u l t i o b j e c t i v e o p t i m i z a t i o n m o d e lw a se s t a b l i s h e dw i t hm i n i m i 。z i n gt h e d i s t r i b u t i o nv e h i c l en u m b e r , t h ed i s t r i b u t i o nd i s t a n c ea n dt h em e a nh a n d l i n g f r e q u e n c y t os o l v et h em o d e le f f e c t i v e l y ，t h el i n e a rw e i g h t i n gm e t h o dw a su s e dt o s i m p l i f yt h eo b j e c t i v ef u n c t i o n s m o r e o v e r ，t h em o d e lw a si m p r o v e dt od e a l w i t h p r o b l e mo ft h em o d e lc a u s e db yt h em e t h o d f i n a l l y ，t h ec o e f f i c i e n t so ft h eo b j e c t i v e f u n c t i o n sw e r es e tb a s e do nt h ea c t u a le n t e r p r i s es i t u a t i o n i no r d e rt oa v o i dt h ed e f i c i e n c yt h a tt h et r a d i t i o n a lt w o - p h a s e da l g o r i t h ml a c ko f s y s t e m a t i c ，b a s e do nt h ed e c o m p o s i t i o na n d c o o r d i n a t i o nm e t h o d ，t h eh y b r i dg e n e t i c a l g o r i t h m ， c a l l e dg a c wa l g o r i t h m ，w i t hi m p r o v e dr o u t e - e x c h a n g ec r o s s o v e r 车辆路径问题的多目标规划模型与算法研究 o p e r a t o rc o n s i d e r e dt h ec a p a c i t yo ft h ed i s t r i b u t i o nv e h i c l ea n dr e v e r s em u t a t i o n o p e r a t o r ，w e r ed e s i g n e d ，c o m b i n e dt h ec - ws a v i n ga l g o r i t h ma n dg e n e t i ca l g o r i t h m a tl a s t ，t h ee f f i c i e n c yo fm o d e la n da l g o r i t h ma le p r o v e db yan u m e r i c a le x a m p l e o nt h eb a s i so fi n v e s t i g a t i o no ft h ed i s t r i b u t i o nc e n t e ri n z h e n j i a n gt o b a c o c o m p a n y , t h ec u r r e n td i s t r i b u t i o np r o g r a mw e r ea n a l y z e d t h ed a t af r o md i s t r i b u t i o n c e n t e ra r eu s e dt ov a l i d a t et h e s ea l o r i t h ma n dt h e ya l ep r o g r a m m e db ym a t l a b a f t e rt h eo p t i m i z a t i o n ，t h ed i s t r i b u t i o nv e h i c l en u m b e rr e d u c e d14 ，t h ed i s t r i b u t i o n d i s t a n c er e d u c e d21 ，a n dt h em e a n h a n d l i n gf r e q u e n c yr e d u c e d4 7 t h e o p t i m i z a t i o nr e s u l ts h o w st h a tt h ee f f e c to ft h ed i s t r i b u t i o no ft h ec o m p a n yi m p r o v e d s i g n i f i c a n t l ya n da c h i e v et h eb a l a n c eb e t w e e nt h ec o s to fd i s t r i b u t i o na n dw o r k l o a do f t h es t a f f k e y w o r d s ：d i s t r i 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 ，m u l t i o b j e c t i v e o p t i m i z a t i o n ， h a n d l i n gf r e q u e n c y i v 江苏大学硕士学位论文 目录 第一章绪论l 1 1研究背景l 1 2研究意义3 1 3国内外研究现状。3 1 3 1 国外研究现状3 1 3 2国内研究现状4 1 3 3相关商业软件。4 1 4研究工作和结构5 第二章物流配送与车辆路径问题研究综述7 2 1物流配送概述7 2 1 1物流概述7 2 1 2配送概述一8 2 1 3配送线路选择问题1 1 2 2车辆路径问题国内外研究综述l3 2 2 1车辆路径问题的一般描述13 2 2 2车辆路径问题的数学模型1 5 2 2 3车辆路径问题的分类l6 2 2 4车辆路径问题的求解复杂性1 8 2 2 5常见求解算法19 2 3大规模车辆路径问题研究综述2 2 第三章多目标l s v r p 分析与建模。2 6 3 1l s v r p 的特点2 6 3 2装卸频率概念的提出2 8 3 3多目标优化问题概述2 9 3 3 1多目标优化问题的数学描述2 9 3 3 2线性加权算法3l 3 4多目标l s v r p 模型3 2 3 4 1多目标l s v r p 描述3 2 3 4 2多目标l s v r p 模型建立。3 2 3 4 3多目标l s v r p 模型处理3 4 v 车辆路径问题的多目标规划模型与算法研究 第四章 多目标l s v r p 问题求解与算法分析3 6 4 1多目标l s v r p 求解思路3 6 4 2 遗传算法概述3 7 4 2 1遗传算法基本概念3 7 4 2 2遗传算法构成要素4 0 4 2 3遗传算法运算流程4 3 4 3节约算法概述4 5 4 4多目标l s v r p 求解算法设计4 7 4 4 1编码策略4 7 4 4 2 初始种群一4 7 4 4 3适应度函数定义4 7 4 4 4单车线路优化4 8 4 4 5遗传操作4 9 4 5数值算例51 4 5 1 实验数据一5 1 4 5 2参数设定及结果分析5 2 第五章镇烟配送车辆路径优化研究与应用5 4 5 1镇烟配送网络现状5 4 5 2 镇烟配送主要流程分析：5 4 5 3仿真实现及结果分析5 6 5 3 1多目标l s v r p 模型应用。5 6 5 3 2仿真结果分析5 7 第六章研究结论与展望5 9 6 1研究结论5 9 6 2研究展望6 0 参考文献。6 1 j i ：谢6 8 攻读硕士期间的科研工作概况一6 9 附录镇江烟草客户网点位置坐标数据7 0 江苏大学硕士学位论文 第一章绪论弟一早殖比 1 1 研究背景 随着现代科学技术迅猛发展，全球经济一体化的趋势加强，物流作为一种先 进的管理技术和组织方式，能够有效的将各项新技术融合在一起，实现经济的高 效运行，因此受到了广泛的关注，发展十分迅速。在实际操作过程中，在占用最 低的费用和最少的资金的前提下，物流以为用户提供准时、安全、高质量地一体 化综合服务为目标，但这并非是各项功能、环节的简单相加，而是通过计划、协 调和控制等手段对仓储、装卸、包装、配送、流通加工等各环节的系统性整合。 所以，现代物流被广泛认为是继降低物资消耗，提高劳动生产率之后的“第三利 润源泉”，也是企业降低生产经营成本，提高产品市场竞争力的重要途径，在国 民经济和社会发展中发挥着重要作用。在经济发达的国家和一些经济水平较高的 发展中国家，物流的服务水平己成为企业获得竞争优势的一个重要因素。 我国是一个发展中国家，在过去长期执行的计划经济模式下，采购、制造、 运输、仓储、配送、销售等环节彼此分割，造成企业原材料和产成品库存量过大， 从而导致资金大量积压，产品生产成本过高；另一方面，由于运输、仓储等企业 现有设施能力利用不足，运输环节衔接不畅而造成运输成本高居不下。随着市场 经济的发展和物流产业的兴起，我国不少企业已经开始改变上述情况。 2 0 0 9 年3 月，国务院通过并颁发的物流业调整和振兴规划( 2 0 0 9 2 0 1 1 年) 中明确指出，物流是融合运输业、仓储业、货代业和信息业等的复合型服 务产业，是与国内外市场连接的重要载体，是国民经济的重要组成部分，由于物 流业涉及领域广，吸纳就业人数多，拉动消费作用大，在促进产业结构调整、转 变经济发展方式和增强国民经济竞争力等方面发挥着重要作用。 近年来，我国物流行业发展迅猛。2 0 1 0 年，我国社会物流总额为1 2 5 4 万亿 元，社会物流总费用7 1 万亿元。全社会各种运输方式累计完成货运量3 1 5 3 4 亿 吨，货物周转量1 3 5 1 6 9 6 亿吨公里。单从各项指标来看，不少指标已经位居世 界前列，但从产业竞争力来看，中国距离物流强国还有很大差距。 配送是在一定经济合理范围内的局部物流活动。企业根据客户订单对产品进 车辆路径问题的多目标规划模型与算法研究 行分拣、包装，并最终准时、准确的将产品送到客户手中。配送可以看作是物流 系统的终端，由于配送是连接企业和客户的直接环节，配送功能完成质量的好坏 及所达到的服务水平将会直接影响到客户对企业的满意度。 经过多年的发展，国外的配送行业已经形成以信息技术为核心，集运输、配 送、装卸、仓储和库存控制等相关专业技术为一身的现代物流配送技术格局。在 未来，配送行业将更加向高新技术应用的方向发展，其主要表现为： ( 1 ) 信息化一一广泛采用无线互联网技术，卫星定位系统( g p s ) ，地理信 息系统( g i s ) 和无线射频标识技术( r f ) 以及条形码技术等。 ( 2 ) 自动化一一广泛采用无人搬运车( a g v ) 技术，搬运机器人( r o b o t s y s t e m ) 技术等。 ( 3 ) 智能化广泛采用电子识别和电子跟踪技术，智能化运输系统( i t s ) 在盘 号手o ( 4 ) 集成化集信息化、机械化、自动化和智能化于一体。 目前，就我国而言，配送在我国的发展是近十年的事，虽然取得一些进步， 但总体上讲，进展缓慢、设备落后、信息化程度低是目前的一个基本状况，行业 整体运行效率仍然偏低，社会化物流需求和专业化物流供给能力不足，现有的物 流配送系统还远不能满足经济发展对物流的需求，基础设施之间不能有效的配套 衔接，资源整合和一体化运作仍面临一些障碍。在物流现代化建设的大趋势下， 国内许多行业部门虽然都纷纷建立配送中心，但设施落后，没有专业的分拣设备 和电子扫描装置，仍普遍采取货架、叉车式的设备和人工分拣的工作方式。许多 配送中心功能相对单一，缺乏对商品深加工的能力。另外，随着经济全球化发展 和我国融入世界经济步伐的加快，一些国际著名的快递企业，如美国联邦快递、 u p s 等，已经进入我国抢占市场，一方面为原有客户提供延伸服务，另一方面凭 借其先进的物流技术、丰富的管理经验和完善的配送体系，进入我国配送领域， 对我国刚起步的配送企业造成很大冲击。目前，外资物流配送企业已经形成以长 三角、珠三角和环渤海地区等经济发达区域为基地，分别向东北和中西部扩展的 态势。 实践证明，配送是高效的物流形式，随着企业生产方式的专业化和人们生活 方式的个性化，高效的配送管理变得更加迫切。如何在满足用户需要的前提下， 2 江苏大学硕士学位论文 降低物流成本，如何在降低物流成本与提高物流服务质量之间找到一个应用的均 衡点，已成为国内外许多理论及应用学者们关注的焦点。物流配送中的车辆路径 问题( v e h i c l er o u t i n gp r o b l e m ，v r p ) 是其中一个重要而迫切的研究课题。 1 2 研究意义 v r p 是物流配送过程中的一个关键问题，具有极强的实际意义。对于v r p 的研究，国外开展的相对较早，如今已有相当一批研究成果问世，并且广泛应用 于生产、生活的各个方面。国内对该问题的研究远远落后于国外，大都是在借鉴 国外已有的研究成果的基础上进行算法设计层面上的改进，对问题的研究还主要 是从西方国家的视角而展开的。但我国在人口密度、地理环境和经济发展水平等 方面与西方发达国家均有着较大的差异，不能简单照搬西方学者的研究思路开展 我们的研究工作。因此，我们有必要在借鉴国外已有研究成果的基础上，立足于 中国的国情，积极探索新的问题形式，提出新的方法技术，使研究成果更好的适 用于中国的配送实践。 1 3 国内外研究现状 1 3 1 国外研究现状 v r p 是一类具有极强应用性的优化调度问题，它在物流配送、交通运输等 领域获得了广泛的应用，其范例大量存在于日常生活之中。由于v r p 在应用上 的广泛性和经济上的重要价值，自1 9 5 9 年由d a n z i g 和r a m s e r 提出以来，一直 是学界研究的重点和热点问题，5 0 多年来已经取得了大量的研究成果。早在1 9 8 3 年，b o d i n 和g o l d e n 等人就综述了7 0 0 余篇文献【1 1 ，而其后，l a p o r t e ( 1 9 9 2 ) f 2 】， b u r a ke k s i o g l u ( 2 0 0 9 ) 【3 】等人的综述文章对v r p 的研究情况都做了详细阐述。 从解法上来看，对v r p 的求解算法主要可分为精确算法和启发式算法，而最 近1 0 年来，对于v r p 的求解算法研究，主要集中在现代启发式算法。这类算法 大多是人们从生物进化的机理中受到启发而提出来的，又叫做仿生算法或智能优 化算法。如t a nkc ( 2 0 0 1 ) 【4 】结合遗传算法和禁忌搜索算法的优点，运用人工 智能的方法求解v r p ，b a r r i em ，b a k e r ，m a ( 2 0 0 3 ) 【5 】采用遗传算法解决了一 类单车场，需求量己知的v r p ，m a r cr e i m a n n ( 2 0 0 4 ) 【6 】针对大规模车辆路径 问题设计了基于蚁群系统的节约算法，提高了算法的效率和求解能力，f u ，e g l e s e 和l i ( 2 0 0 5 ) 【7 1 采用禁忌搜索算法解决了一类带路径长度约束的开放式v r p ， 3 车辆路径问题的多目标规划模型与算法研究 b y u n g - i nk i m ( 2 0 0 6 ) 【8 1 研究了关于废弃物回收的v i 冲，设计了扩展插入算法结 合聚类算法的混合启发式算法对问题进行求解，模型考虑了配送车辆数、道路紧 凑度和员工工作量均衡三者之间的优化问题，y a n n i sm a r i n a k i s ( 2 0 10 ) 【9 】结合遗 传算法和粒子群算法，设计了新的混合启发式算法，提高了传统遗传算法的局部 搜索能力。 国外对于v r p 的研究有较长的历史，研究成果丰富，对我国的v r p 研究具 有重要的指导意义。 1 3 2 国内研究现状 国内对v r p 的研究始于2 0 世纪9 0 年代，我国学者对于v r p 的算法研究主 要是通过对各种启发式算法进行改进，来解决某一类v r p 。如姜大立等人( 1 9 9 9 ) 【1 0 】较早的采用遗传算法研究v r p ，李大卫等( 1 9 9 9 ) 【l l 】针对遗传算法设计了一 种更加直观的编码方式，并提出了基于优先关系的交叉算子，提高了算法解决复 杂优化问题的能力，张丽萍等( 2 0 0 2 ) 1 2 1 通过引入一种新颖的交叉算子，使遗 传算法摆脱了对种群多样性的要求，克服算法常见的“早熟收敛 现象，符卓 ( 2 0 0 4 ) i t 3 1 采用禁忌搜索算法研究一类带装载能力约束的开放式v r p ，设计了 四种邻域变换方式，进一步增强禁忌搜索算法的机能，李宁等( 2 0 0 4 ) 1 4 1 是较早 的将粒子群算法应用于带时间窗的v r p 研究中，取得了较好的效果，刘志硕等 ( 2 0 0 5 ) 1 5 1 构造自适应蚁群算法来求解v r p ，并对蚁群算法的可行解问题进行 了重点研究，丁秋雷等( 2 0 0 7 ) 1 6 1 针对蚁群算法求解带时间窗的v r p 上的缺陷， 采用信息素调整策略和最优个体灾变策略来防止算法限于局部收敛的问题，孔志 周等( 2 0 0 7 ) 1 7 1 通过设计新的编码方式，提高了染色体的信息表达能力，并进一 步与爬山算法相结合设计了混合进化策略，提高了算法的效率，傅成红等( 2 0 1 0 ) 【1 8 1 提出了毗邻信息指导的动态候选集规模，提高了禁忌搜索算法的效率，适用 于求解大规模v r p 。 总的来说，我国对于v r p 的研究起步较晚，虽然在理论和实践上均取得了 一定的成果，但基本仍集中在启发式算法上，对处理复杂的v r p 仍处于起步阶 段。如何更好的将理论研究同中国的配送实践相结合，仍需要进一步的研究。 1 3 3 相关商业软件 目前最成熟的物流管理软件是e r s i 公司开发的a r c l o g i s t i c 。在美国加州 4 江苏大学硕士学位论文 r e d l a n d s 市的e s r i 公司是世界最大的地理信息系统( g i s ) 技术提供商。全球 2 0 0 多个国家超过百万用户单位正在使用e s r i 公司的g i s 技术，以提高他们组 织和管理业务的能力。a r c l o g i s t i c s 软件旨在为企业提供完整的路径优化车辆调 度方案。该款软件能够动态创建路径分配方案，降低企业的配送成本，提高客户 服务水平。 国内的物流行业起步较晚。2 0 0 1 年，北京杰合伟业公司针对电子商务中物流 环节薄弱的情况，结合当时国内城市物流配送企业的特点，率先推出了中国第一 款专业物流配送管理软件，受到了企业界的广泛好评。2 0 0 2 年，海尔集团在物 流配送环节全面推广条码扫描和r f 技术，提高了物流过程中的准确率和问题的 可追性，并进一步采用g i s 技术构建“海尔物流监控调度系统”，实现对配送车 辆在全国范围内进行全程跟踪。北京烟草物流中心运用计算机系统进行数字控 制，通过地理信息系统和全球定位系统对配送车辆进行跟踪，可对配送路线进行 定期或不定期的调整和优化，按照线路最短、时间最少、装载最多的原则，对全 市4 万多卷烟零售户实行接力式配送，确保快速响应。金启元科技发展( 北京) 有限公司开发的基于g i s 技术的城市物流配送路径优化系统集成了配送线路优 化管理功能，综合查询管理功能和多点配送的合理线路优化功能，能够提高物流 业务部门的工作效率，改善企业综合管理机能。此外，合肥中鼎数字科技有限公 司、济南兰剑物流科技有限公司等都针对城市物流配送业务提出了车辆路径优化 调度方案，在实践中取得了一定的成效。 1 4 研究工作和结构 本文从介绍v r p 的基本理论出发，首先通过详细综述了物流配送和v r p 的 相关理论，对研究对象进行界定。其次，通过分析中西方国家在人口密度上的差 异性结合中国的配送实践，提出了装卸频率的概念，能够更好的反映配送线路间 劳动强度的差异性，从而更加准确的体现v r p 的求解复杂度的变化。再次，从 装卸频率这个概念入手，通过研究传统的v r p 模型，构建了考虑装卸频率的大 规模v r p 模型，并在建立模型的同时给出了相应的求解算法，最后从实验数据 和企业案例两方面验证了模型的正确性和算法有效性以及对大规模v r p 的适用 性。本文的研究工作紧密结合中国的配送实践，为v r p 在中国的研究提供了一 个新的视角。 车辆路径问题的多目标规划模型与算法研究 论文的总体结构如下： 第一章绪论 本章主要通过对物流配送行业发展现状的介绍和研究领域的分析，提出了 v r p 研究的意义。 第二章物流配送与车辆路径问题研究综述 本章首先通过详细介绍物流、配送和配送中线路选择问题等三个方面的相关 理论，对本文的研究对象进行了界定。然后，从问题描述、数学模型、问题分类、 求解复杂性和求解算法等几个方面对v r p 进行了详细的介绍。最后，对大规模 v r p 进行了综述。 第三章多目标l s v r p 分析与建模 本章首先通过对比中西方在人口密度上的差异性，提出了“装卸频率”的概 念，并在此基础上构建了m s l v r p 模型。 第四章多目标l s v r p 问题求解与算法分析 本章根据所建立的多目标l s v r p 模型，通过分析传统求解算法中的不足， 针对所建立的数学模型，设计了合适的求解算法混合遗传算法。最后，将模 型和算法进行仿真实验，以验证模型和算法的有效性。 第五章镇烟配送车辆路径优化研究与应用 本章以镇烟物流配送中心的配送车辆优化应用为案例，在分析镇烟物流配送 中心配送业务流程的基础之上，运用本文的模型和算法进行求解，以验证模型和 算法对于大规模车辆路径问题的适用性。 6 江苏大学硕士学位论文 第二章物流配送与车辆路径问题研究综述 婿自d a n z i g 和r a m s e r 提出以来，由于其具有广泛的应用性和经济研究价 值，因此一直成为学界关注的重点和热点问题。本章从优化目标、问题分类、求 解算法等多个方面对v r p 进行了详细的介绍。 2 1 物流配送概述 2 1 1 物流概述 物流的概念最早起源于美国。1 9 0 1 年，j o h ne c r o w e l l 在政府报告中在分析 影响农产品流通各种因素和费用时最早谈到了物流的概念。第二次世界大战时 期，美国为解决军需品供给问题，运用运筹学知识和计算机技术对运输线路、库 存控制、供给费用等因素进行的合理规划，因此又称为“后勤物流”( l o g i s t i c s ) 。 随着学术研究和物流实践的不断深入，需要对物流进行规范化定义，以统一 对物流的认识。但由于学术界和企业界对物流的理解还有差别，到目前为止，对 物流的定义还远未统一。目前最常用的是c l m 在1 9 8 5 年对物流的定义：为迎 合顾客需求而对原材料、半成品、产成品及相关信息从产地到消费地的高效、低 成本流动和储存而进行的规划、实施和控制过程【1 9 】。c l m 分别在1 9 9 8 年和2 0 0 2 年对物流的概念作了修订，加入了供应链的概念。2 0 0 2 年，c l m 将物流的定义 修订为：物流是供应链流程的一部分，是对货物、服务及相关信息从起源地到消 费地的有效率、有效益的正向和反向流动和储存进行计划、执行和控制，以满足 顾客要求【1 9 1 。 根据上述定义可以看出，物流是由各要素组成的具有特殊功能的复杂系统。 最基本的物流系统由运输、储存、包装、装卸搬运、流通加工、配送和信息加工 等七个子系统有机结合而成，如图2 1 所示。 7 车辆路径问题的多目标规划模型与算法研究 图2 1 物流系统的构成 由于各环节之间存在效益背反关系，部分最优并不能保证整个系统达到最 优。因此，研究物流系统要从稳定物流功能、提高物流效益、降低物流运行费用、 满足各种需求等多方面进行综合考虑。 2 1 2 配送概述 关于配送的概念的表述最早是来自日本政府于1 9 8 5 年发布的权威性工业标 准( j i s ) 。根据j i s 中的表述，配送是将货物由物流结点送至交货人的交货行为。 目前国内主要使用的是中华人民共和国国家标准物流术语中的定义，配送是 指：在经济合理区域范围内，根据用户要求，对物品进行拣选、加工、包装、分 割、组配等作业，并按时送达指定地点的物流活动【1 9 1 。 1 、配送的一般流程 对企业而言，配送是连接企业和顾客的一个重要环节，是将货物从物流节点 送达顾客手中的交货过程，是“配”和“送”的有机结合。配送作业的服务对象 种类繁多，配送作业的流程也极为复杂。如图2 2 所示，一般的配送流程包括： 集货、储存、分拣、配货、送货、送达服务等环节。随着信息技术的发展，很多 企业纷纷开始采用“零库存策略，传统的物流配送已经出现新的特征，储存己 经不是必然的环节。所以，配送运输成本起着决定性作用。 8 ( 2 ) 配送活动是连接企业和客户的重要业务环节，配送业务直接面对客户， 通过恰当的方式、恰当的费用，为客户提供各种所需的服务。但物流配送成本和 客户服务水平之间存在效益背反关系，如何达n - 者之间的均衡是物流企业最为 关注的问题。 2 、配送效果的评价指标 高效的配送活动需要适量的配送人员、适合的配送车辆以及车辆最佳的行驶 路径来相互配合才能达到。因此，人员、车辆及规划方式都是对配送活动的绩效 进行考核的主要方面。 ( 1 ) 人员负担指标 对配送组织中人员负担的研究，有利于评估配送人员的工作分摊及其作业贡 献度，以衡量配送人员的能力负荷与作业绩效。主要指标有平均每人的配送量， 平均每人的配送距离，平均每人的配送车次： 平均每人的配送量= 总送货量配送人员数 平均每人的配送距离= 配送总距离配送人员数 平均每人的配送车次= 配送总车次配送人员数 9 车辆路径问题的多目标规划模型与算法研究 对于配送人员所负担的工作量应随时掌握并予以调整，才能减少员工抱怨， 提高客户服务质量。 ( 2 ) 车辆负荷指标 配送车辆的产能负荷评估，将用于判断是否应增减配送车辆数量，主要指标 有平均每辆车配送吨公里数，平均每辆车的配送距离，平均每辆车的配送重量： 平均每辆车配送吨公里数= 配送总距离x 配送总重量车重 平均每车的配送距离= 配送总距离车重 平均每辆车的配送重量= 配送总重量车重 对于一辆车的产能负荷应从距离和重量的角度来分析，如果平均每辆车配送 吨公里数过高，有可能是车辆的配送距离过长或者是配送货物货物量过重。 ( 3 ) 配送成本指标 配送成本主要用于分析配送过程中所发生的成本费用，这是企业最为关注的 部分。主要指标有每吨配送成本，每容积货物配送成本，每车次配送成本，每公 里配送成本： 每吨配送成本= ( 自车配送成本+ 外车配送成本) 配送总重量 每容积货物配送成本= ( 自车配送成本+ 外车配送成本) 配送货物总容积 每车次配送成本= ( 自车配送成本+ 外车配送成本) 配送总车次 每公里配送成本= ( 自车配送成本+ 外车配送成本) 配送总距离 3 、配送类型 根据配送的概念，从配送主体所处行业，配送商品特征，配送时间及配送数 量和实施配送的结点等方面的不同，将配送划分为多个类型，如图2 3 所示。 图2 3 配送的类型 本文所研究的配送模式属于配送中心、物流企业、多品种少批量和定时定线 路的配送模式。 2 1 3 配送线路选择问题 配送运输是配送功能最终实现的手段，配送线路的合理性对企业配送质量和 成本起着非常重要的作用，因此有必要就配送线路问题进行细致的研究。在实际 的配送运输过程中，送货人员大都根据自身经验随意选择每条配送线路上客户网 点的送货顺序。这种传统而简单的方法在小规模的、运行环境简单的单目标情况 下较为实用；但随着现代物流的不断发展，配送网络规模逐渐增大，网络结构变 得更加复杂，传统的技术已经难以适应新形势的需求。因此，划分一个合理而高 效的配送路径对企业来说就变得非常重要。 l 、配送线路选择问题的结构 车辆路径问题的多目标规划模型与算法研究 根据配送网络中分销节点的不同可将配送网络分为多级配送网络和单级配 送网络，而其中多级配送网络又以二级配送网络为代表，如图2 4 ，图2 5 所示。 图2 - 4 二级配送网络 多级配送网络中包含多个级别的分销设施，其中第一级设施是配送的始发点 和终止点，一般指的是企业的配送中心，第二级及以上的设施是配送网络中的配 送中心与客户之间的中间节点，主要是分销商、批发商或零售商企业。 图2 5 单级配送网络 与多级配送网络相比，单级配送网络中没有中间节点，由配送中心直接面对 客户。单级配送网络是配送网络中最基本的形式，其对应的单级配送线路问题也 江苏大学硕士学位论文 o 坝、0 q 怎围o，渗惫鼍p 誉擎落 车辆路径问题的多目标规划模型与算法研究 1 、道路网络 道路网络是货物运输的基础，是构成v r p 最核心的要素之一。道路网络通 常是由节点和弧组成的赋权图来表示。其中，节点表示配送中心或顾客点，弧表 示节点间的道路连接。根据实际道路网络中道路的特征不同，赋权图中的弧又分 为有向弧和无向弧。对于每条弧，赋予一个非负权重，面对不同的问题，权重表 示的含义也不同。 2 、顾客点 顾客点是一个统称，表示在配送网络中出配送中心外的所有中间节点，如分 销商、零售商、个体家庭等。针对本文研究的一级配送网络，顾客点单指配送网 络中的终端客户。 3 、车场 服务客户的配送车辆始于并终止于车场，在道路网络中，车场也用点来表示。 在某些实际应用中，存在多车场的问题，一般按照车场先对客户进行划分，配送 车辆在完成送货服务后必须返回其所属的车场。这种情况下就将原v r p 分解为 多个子v r p 。一般