物流路径优化.docx

《物流路径优化.docx》由会员分享，可在线阅读，更多相关《物流路径优化.docx（49页珍藏版）》请在三一办公上搜索。

1、分 类 号： 密 级：论文编号： 学 号：52141210103重庆理工大学硕士学位论文LS物流公司城市社区超市配送路径优化研究研 究 生: 孙会龙指 导 教 师： 何开伦教授学 位 类 型： 学术学位学 科 专 业： 管理科学与工程研 究 方 向： 现代供应链与物流工程培 养 单 位： 管理学院论文完成时间： 2016年11月25日论文答辩日期： 201X年X月X日Category Number： Level of Secrecy：Serial Number ： Student Number：51312100103Masters Dissertation of Chongqing Unive

2、rsity of Technology Study on the Recycling Network System of Waste Electrical and Electronic Equipment in Chongqing Postgraduate: Cheng ChuangyeSupervisor: Professor He KailunDegree Category： Academic DegreeSpecialty: Management Science and EngineeringResearch Direction: Modern Supply Chain and Logi

3、stics EngineeringTraining Unit: Institute of ManagementThesis Deadline: March 25, 2016Oral Defense Date: May xx, 201x学位论文原创性声明及使用授权声明重庆理工大学学位论文原创性声明本人郑重声明：所呈交的学位论文是本人在导师的指导下，独立进行研究所取得的成果。除文中特别加以标注引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写的成果、作品。对本文的研究做出重要贡献的集体和个人，均已在文中以明确方式标明。本人承担本声明的法律后果。作者签名： 日期： 年 月 学位论文使用授权声

4、明本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权重庆理工大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。本学位论文属于（请在以下相应方框内打”）： 1.保密，在 年解密后适用本授权书。2.不保密。作者签名： 日期： 年 月 日导师签名： 日期： 年 月 日摘要摘要关键词：电子废弃物；回收网络；逆向物流；层次分析法；神经网络VIIABSTRACTAbstractThe main conclusions of this paper

5、include: Chongqing electrical and electronic waste growth with an average annual growth rate of 17.31 percent in the next decade. It proposed four network modes for electrical and electronic waste recycling network system in Chongqing That is, establishing a recycling point for each township; settin

6、g up a storage station for each county; and building a processing center in Jiulongpo, Bishan, Fuling, Wanzhou of Chongqing; and establishing a disposal site in Bishan, Wanzhou of Chongqing .Key words：Electronic Waste; Recycling Network; Reverse Logistics; Analytic Hierarchy Process; Neural Network目

7、录目录摘要IAbstractIII目录V1 绪论11.1研究背景及意义11.1.1 研究背景11.1.2 研究意义21.2 国内外研究现状及述评31.2.1 电子电器废弃物产生量预测研究31.2.2 电子电器废弃物回收网络体系研究41.2.3 电子电器废弃物回收处理运营模式与政策建议研究51.3 研究目标、研究内容与创新点61.3.1 研究目标61.3.2 研究内容71.3.3 创新点71.4研究方法与技术路线81.4.1 研究方法81.4.2 技术路线82 电子电器废弃物回收网络体系理论基础112.1相关概念112.1.1 电子电器废弃物112.1.2 电子电器废弃物回收体系112.1.3

8、电子电器废弃物回收网络体系112.2回收网络体系理论基础122.2.1 循环经济122.2.2 逆向物流122.2.3 生产者延伸责任制133 重庆市电子电器废弃物总量预测153.1 重庆市电子电器废弃物总量预测的基本思路与方法选择153.1.1 重庆市电子电器废弃物总量预测的基本思路153.1.2 重庆市电子电器废弃物总量预测的方法选择173.2 重庆市电子电器废弃物总量预测的具体过程与结果193.2.1 电子电器产品保有量及新增量的估算及预测193.2.2 各类电子电器产品的使用年限及其废弃年限的确定233.2.3 电子电器废弃物产生量与总量的估算和预测243.3 重庆市电子电器废弃物总量

9、的空间分布254 重庆市电子电器废弃物回收网络体系设计274.1 回收网络体系设计的基本原则和总体思路274.1.1 基本原则274.1.2 总体思路274.2 回收网络体系的基本构成及功能284.2.1 回收集成284.2.2 处理集成294.3 回收集成的设计304.3.1 基于AHP的模糊综合评价模型的基本理论304.3.2 基于AHP的模糊综合评价模型的建立324.3.3 基于AHP的模糊综合评价模型的具体实现过程344.3.4 基于AHP的模糊综合评价模型的结果分析384.4处理集成的设计384.4.1 基于成本最小化的区位选址模型的基本理论394.4.2 基于成本最小化的区位选址模

10、型的建立404.4.3 基于成本最小化的区位选址模型的具体实现过程414.4.4 基于成本最小化的区位选址模型的结果分析444.5 重庆市电子电器废弃物回收网络体系的模式总结465 发展重庆市电子电器废弃物回收网络的建议495.1运行模式495.1.1 责任主体495.1.2 回收模式495.2对策建议505.2.1完善法律法规和制度建设，保障回收网络顺利开展505.2.2发展专业化处置企业，提高回收网络的周转效率505.2.3建立专门的管理机制和监督机制，提高回收网络的透明度515.2.4加大政策扶持力度，保障回收处理企业的经济效益515.2.5提高消费者环保意识，调动公众参与的积极性526

11、 结论与展望536.1 结论536.2 展望54致谢55参考文献57个人简历、在学期间发表的学术论文及取得的研究成果613 重庆市电子电器废弃物总量预测 1 绪论1.1研究背景及意义随着我国经济的快速发展，物流发展迅速，物流企业之间的竞争日益激烈，合理地控制物流成本已经成为物流企业生存的根本。而运输成本占物流企业的成本为40%左右，如何优化配送路径进而减少运输成本对提高企业的竞争力非常重要。LS物流公司的配送对象为重庆100多家社区超市，消费品一般是指购买频率较高、使用期限较短、消费规模较大的日用产品。社会消费品零售总额的快速上涨催生了对消费品物流的广泛需求。由于消费品自身的特点，其物流配送也

12、呈现出与其他行业物流差异化的特点：小批量、多品种、高频率，季节波动频繁，对质量和速度的要求高，物流的配送环节多且复杂性高。然而，也正因其服务于人民生活的刚性需求，消费品物流始终是社会的基础性物流和长盛不衰的发展热点。车辆路径问题（VRP）涉及到很多学科，如运筹学、计算机领域、交通运输、物流管理等，具有很强的应用前景，在对社区超市配送过程中，选择合适的路线，是配送企业首要的任务。VRP又称车辆调度问题，通常可以描述为对于不同的服务客户，组织合适的配送路线，在货物需求量、服务时间、车辆容量的前提下，达到优化的目标（如路程最短、使用车辆少、时间少等）。一般认为不涉及时间的配送是路径问题，涉及时间的是

13、调度问题。目前，城市社区超市配送路径存在诸多问题，首先，一家城市社区超市配送公司如LS物流公司配送的中心是固定的，并且配送车辆基本固定，而社区超市对配送的需要量是动态的，有时多有时少，这就加大了配送的费用和难度。其次，个别社区超市不是24小时营业，运输的的商品（如牛奶、速食品）有一些时间限制，而每一辆配送车有一定的载重量限制和最大路程限制，在满足客户需求的同时又必须返回出发的配送中心。这就加大了配送路径选择的难度。城市社区超市配送路径问题突出，一个合理的配送路径是配送企业保证服务质量和增加利润的根本。本文通过优化配送路径，进而利用数学模型建模，遗传算法在MATLAB上编程，设计路径优化的线路，

14、进而为企业配送问题提供相关的配送路线，减少配送企业的运输费用和提高物流企业的服务质量。1.2 国内外研究现状及述评1.2.1 城市社区超市配送路径优化车辆路径问题现状 车辆路径问题一直是研究领域的热点问题。车辆路径问题由Dantzig 和Ramser（1959）首先提出来，在近50多年，各个研究领域都对它非常重视，如物流管理、运筹学、计算机应用等，这些领域的专家学者对车辆路径问题进行深入研究并取得了很多研究成果，对不同的车辆路径问题建立相对的数学模型，并且提出了精确算法和启发式算法等，尤其是现代启发式算法，对车辆路径问题的解决有着重要作用。Lenstra J.K和Rinooy K(1981)的

15、论文证明车辆路径问题属于NP问题。Thangiah(1995)运用启发式算法的遗传算法来得到带时间窗的车辆路径问题的次优解，进一步地优化路径，取得了比较理想的实验结果。Alvarenga和 Mateus（2004）运用两阶段遗传算解决带时间窗的路径优化问题，得出比较好的优化路线。Homber和 Gehring（2005）运用混合两阶段优化算法，得出次优的优化路径。Pisinger和Ropke（2007）针对大规模车辆路径问题，把大数据转化为普通的送货问题，实验结果证明了该放方法可以有效地解决大规模车辆路径问题。卫田运用NSGA方法对多目标车辆路径问题进行求解，通过实例证明了算法的有效性。唐建通

16、过遗传算法解决动态车辆路径问题，通过与其他算法作对比，证明了遗传算法的高效性。李兵针对动态路径问题提出虚拟路径来规划和优化车辆路径。赵建有利用节约法对。杨进通过蜂窝算法对带时间窗车辆路径问题进行求解，通过实验验证了算法有效性。胡明伟利用v+编写遗传算法程序对配送系统路径优化进行设计，通过算例验证了遗传算法在大规模路径问题的有效性。王海宾用过遗传算法解决多车场多目标开放式物流路径问题，通过实例验证了遗传算法的有效性。张建强利用禁忌搜索对遗传算法进行改进，增加了遗传算法的收敛性，避免了早熟出现。李峰利用遗传算法对货物配送时变问题进行研究，通过二次规划配送路径，有效地解决了实际问题。陆琳对随机客车车

17、辆路径问题进行求解，结果表明蚁群算法在解决此类问题的有效性。魏明利用离散粒子群算法求解车辆路径问题。张景玲通过预优化和实时优化对多车型动态需求车辆路径进行优化。吴洁明用蚁群算车辆路径优化。王征采用聚类方法首先完成客户分配，让后利用改进型邻域搜索算法对多车辆带时间窗车辆路径问题进行求解。范静利用邻近法以及最廉价插入法对客户满意度同时收发车辆路径问题进行求解，并通过实例对不同参数的情况进行比较。李琳通过蚁群算法求解带时间窗的车辆路径问题。王君利用禁忌搜索算法求解模糊预约时间的车辆路径问题。凃伟利用Voronoi对于大规模物流车辆路径进行优化，结果显示可以快速解出初始解。毛敏采用启发式算法对连锁超市

18、车辆配送路径进行优化。石兆，符卓通过禁忌搜索法对连锁门店配送路径进行优化。陈迎欣利用遗传算法，并用MAT软件求解，对车辆路径进行优化，进行仿真，验证了改进蚁群法的有效性和可行性。赵燕伟利用两阶段法求解多目标随机车辆路径问题，第一阶段利用量子进化算法，第二阶段通过粒子算法进行求解。韩雪梅利用改进节约法对连锁性商业企业的配送库存进行优化。张迅利用集束算法对带有世家你床的快递进行路径优化。熊浩采用旅行商策略，对配送顾客进行分批处理，优先安排不能延迟的顾客，实例验证了方法的有效性。王君采用多目标基因算法求解车辆路径问题，实验表明了该方法的有效性。凃伟利用Voronoi和模拟退火机制对武汉大规模车辆路径

19、进行求解，结果显示减少了运输时间，提高了物流效率。谷炜针对零售业配送采用先分组后排程两阶段启发式算法求解，在GIS上设计开发系统对商品零售业配送路径进行优化，验证了混合智能优化算法的有效性和优越性。李远远利用扫描改进节约法对配送路径进行优化并提出相关建议。吴丽英，胡祥培以燃料消耗率优化目标，通过降低燃料消耗来优化路径。吴天羿，许继恒设计了改进遗传法对军事物流进行路径优化，通过实验仿真，证明了有效性。侯玉梅采用自适遗传算法，通过MATLAB进行编程，生成优化方案求解车辆路径问题，并与扫描法对比，张明了遗传算法具有一定的优势。陈玉光对优化车辆路径降低油耗进行研究并用实例证明了方法的有效性。徐云口利

20、用贪心，环。刘云利用单亲遗传法与基本蚁群算法结合，完成总路径最小和车辆数最少的目标。杨翔对模糊时间窗车辆路径问题进行求解。叶勇利用狼群算法对。1.2.2 电子电器废弃物回收网络体系研究从以上学者的研究中可以看出，由于电子电器废弃物处理工作的社会效益显著，单纯考虑成本收益的定量方法不能完全适用回收网络模型的构建，因此将定性分析和定量分析结合是目前研究电子电器废弃物回收网络的主要方法，比如将定性分析转化为定量分析的模糊综合评判方法以及基于总成本角度考量的数学模型等。而这些模型又因不同的学者考虑的影响因素和成本项目不同，导致模型计算得出的回收网络结论具有较大的差异。1.2.3 电子电器废弃物回收处理

21、运营模式与政策建议研究上述学者对电子电器废弃物的回收模式进行了详细的探讨，诸如生产商回收模式、专业第三方企业回收模式、联合回收模式等各种模式下的优缺点，并经过模型或对比分析得出最优模式的结论，然而各位学者研究的结论因其关注的角度不同而截然相反。另外从政策建议上，不同学者也有不同的建议，比如从政策法律角度、从市场监管角度、从回收处理技术角度、从政府补贴角度等等，这些研究为本文研究重庆市发展电子电器废弃物回收网络体系提供了较大的参考价值。另外，从以上的文献综述中可以看出，各学者的研究主要针对上海市、北京市、天津市、深圳市以及全国范围内的电子电器废弃物进行产生量预测和回收网络体系的构建，但对于重庆市

22、电子电器废弃物的回收处理和网络构建的相关研究几乎属于空白，而重庆市作为中国直辖市之一，经济发展迅速，电子电器废弃物的产生量呈快速增长趋势，因此对于重庆市电子电器废弃物回收网络体系的研究填补了各位学者区域研究的空白。1.3 研究内容与创新点1.3.2 研究内容本论文在以LS物流公司城市社区配送的问题的基础，分析了解决配送问题四种情况，主要研究内容如下：（1）绪论。首先分析了城市社区超市配送路径问题的现状与问题，引入本文研究的背景和意义，通过对国内外相关领域的研究文献的研究，了解国内外相关领域的最新研究成果，明确研究目的、研究内容、研究方法和技术路线。 （2）LS物流公司社区超市运作现状与问题。通

23、过对LS物流公司对城市社区超市的配送现状进行分析，了解研究对象的基本情况，并从配送现状中找到存在的问题。（3）城市社区超市配送车辆路径问题概述和遗传算法原理。主要通过车辆路径问题相关理论概述和遗产算法原理的分析，设计出配送路径问题的数学模型。（4）实例分析。利用遗传方法解决LS物流公司的实际配送问题。设计四种任务的优化方案，并在MATALAB上编程。四种方案包括:基于旅行商为基础的临时任务；考虑车辆行程和最大载重量的常规任务；考虑时间窗的临时任务；双配送中心的常规任务。（5）为LS物流公司社区超市配送提出路径优化建议。根据遗传算法的解决方案的优越性为配送路径优化提供相关的建议并展望未来发展趋势

24、。1.3.3 创新点本论文通过分析LS物流公司社区超市配送路径中的现状与问题。主要创新点如下：（1）在车辆路径问题的研究中，首次将常规任务和临时共同分析，构建了多种情景下的车辆路径优化方案。由于实际配送过程中会出现多种情况，研究一种情况不足以解决实际问题，本文构建多种情景的解决模型，把双配送中心问题转化为单配送中心问题，在解决车辆路径优化实际问题的过程，有效性和准确性有了较大提高。（2）。1.4研究方法与技术路线1.4.1 研究方法本论文通过广泛查阅相关文献，采用多种研究方法对LS物流公司社区超市配送路径优进行深入研究。主要采用的研究方法有：（1）文献研究法：在大量阅读和梳理车辆路径问题、电子

25、废弃物产生量预测模型、电子废弃物回收网络体系构建等文献的基础上，进行论文的撰写。（2）实地调研法：本论文依托LS物流公司城市社区超市配送路径优化横向项目，通过到LS物流公司进行调研，对配送人员进行访谈，了解其配送模式，并得到一些配送路径数据和相关资料。（3）数学建模法。在配送路径优化上，本文采用遗传算法对LS物流公司社区超市配送路径进行优化；等。1.4.2 技术路线在总结城市社区超市车辆配送路径现状与问题的基础上，通过数学建模，利用遗传算法对路径优化，然后用MATALAB编程，最后对配送问题的四种情况进行路线优化，最后为社区超市配送提供相关建议。具体技术路线如图1.1所示。图1.1 技术路线2

26、 车辆路径问题概述和遗传算法原理2.1车辆路径问题概述2.1.1 旅行商问题旅行商问题（Traveling Salesman Problem，TSP）又译为旅行推销员问题、货郎担问题，简称为TSP问题，是最基本的路线问题，该问题是在寻求单一旅行者由起点出发，通过所有给定的需求点之后，最后再回到原点的最小路径成本。最早的旅行商问题的数学规划是由Dantzig（1959）等人提出。TSP是车辆路径问题的最基础模型，是著名的NP问题，也是运筹学研究的重点之一。TSP可以复杂化变化为多个旅行商问题，把每个旅行商看做配送车辆，加上装载限制，就可以看做普通的车辆路径问题（VRP），继续增加条件限制，就演变

27、为各种类型的车辆路径问题。2.1.2 车辆路径问题（VRP）定义Dantzig 和Ramser首先提出VRP，VRP又叫做车辆调度问题，一般可以表述为：对于一系列配送中心和配送对象。组织合适的配送路线，使车辆有序地配送，在一些前提条件下（如客户的需求量、发货量、配送时间、车辆最大装载量和最大车辆最大配送距离），达到一些目标（配送路径最短、时间花费最少、配送车辆数量最少）。一般认为，没有时间约束的是路径问题，有时间约束的是调度问题。通过车辆路径问题的概念可以知道，它包括以下基本要素：（1）配送中心，指接受并处理末端用户的订货信息，对上游运来的多品种货物进行分拣，根据用户订货要求进行拣选、加工、组

28、配等作业，并进行送货的设施和机构。是从供应者手中接受多种大量的货物，进行倒装、分类、保管、流通加工和情报处理等作业，然后按照众多需要者的订货要求备齐货物，以令人满意的服务水平进行配送的设施。（2）配送对象，指物流配送车辆所到达的各个卸货点，如社区超市、连锁店、仓库等。本文的配送对象是社区超市，也可以称为各个连锁商店。配送量多少由社区超市的需求量决定，（3）车辆，指配送货物的运输工具，车辆有最大行驶距离和最大装载量限制，配送车辆的数目由客户的需求量和车辆最大装载量决定；配送车辆的路线由车辆最大行驶距离和客户位置决定。（4）配送网路，由配送端（配送中心、客户）和弧组成。弧的属性包括车辆行驶的方向、

29、权值和车辆流量限制等，弧的权值包括车辆行驶的距离、车辆运行的时间和相关成本等。（5）货物，指我国交通运输领域中的一个专门概念.交通运输领域将其经营的对象分为两大类,一类是人,一类是物,物的这一类统称为货物。在本文中，指城市社区超市配送的货物。（6）限定条件，指客户所需要的货物的种类、数量；客户对时间的要求；车辆的通行时间；车辆的最大行驶距离（指来回的总距离）和最大载货量。（7）车辆路径的优化目标，指通过路径优化要达到的目的，如油耗量最少、路径最短、时间合理、客户满意等。2.1.3 车辆路径问题的基本类型车辆路径问题概念出现后，国内外学者对VRP进行了多种分类。根据研究重点的不同，VRP可以产生

30、很多模型，这些模型有不同的分类方式。总体来说有以下分类：（1） 根据车场（配送中心、仓库等）划分，分为多车场和单车场问题。本文了研究单配送中心车辆路径问题，即所有车辆从一个配送中心出发；也研究了多配送中心为题，即双配送中心车辆路径问题，车辆从两个配送中心出发。（2） 根据配送车辆的型号划分，可以分为单车型车辆路径问题和多车型车辆路径问题，本文重点研究单车型车辆路径问题。（3） 根据客户对车辆达到时间来划分，可以分为无时间要求的车辆路径问题和带时间窗的车辆路径问题。带时间窗的车辆路径问题又可以分软时间窗问题和硬时间窗问题，硬时间窗车辆路径问题对时间要求非常严格，必须在指定时间到达配送收货点，早到

31、或者晚到都会被拒绝；软时间窗车辆路径问题要求配送车辆在客户要求的时间范围内到达，在规定范围提前到或者迟到，则需要承担一定的惩罚费用。本文主要研究无时间限制的车辆路径问题和软时间窗车辆路径问题。（4） 按照车辆载重情况划分，可以分为满载和非满载车辆路径问题。本文主要研究两者的混合装载问题，即尽量满载，可以出现非满载情况。（5） 按照配送任务划分，可以分为送货配送，收货配送，送货和收货同时进行的车辆路径问题。（6） 按照配送车辆是否返回配送中心划分，可以分为封闭式车辆路径问题（配送车辆从配送中心出发并且返回配送中心）和开放式车辆路径问题（配送车辆从配送中心出发但是不返回配送中心）。本文重点研究封闭

32、式车辆路径问题。2.1.3 车辆路径问题的求解算法车辆路径问题属于NP问题，求解该问题的算法主要是精确算法和启发式算法。精确算法是通过有限计算和推理得到的路径优化问题的最优解算法，一般包括割平面算法、动态规划算法、网络流法等。启发式算法是通过对以往经验的总结归纳或者通过实验仿真来解决问题的方法，启发式算法不是最求最优解，而是相对满意的次优解。启发式算法一般包括传统启发式算法和现代启发式算法。传统启发式算法主要有节约算法、插入算法、两阶段启发式算法、扫描算法等；现代启发式算法主要有遗传算法、禁忌搜索算法、模拟退火算法、蚁群算法、粒子群算法、量子进化算法等。2.2遗传算法概述遗传算法是一种在自然选

33、择和生物进化的基础上，运用计算机模拟生物群在自然进化过程中基因的选择、交叉、变异，进而香型的一种智能优化搜索算法。2.2.1 遗传算法的相关概念1、基因在遗传算法中的基本单元就是基因，可以表示为X=x1,x2.xn,根据不同的问题，基因可以分为二进制串，整数串，实数串等。2、 编码和解码在实际应用中，需要把实际问题的解转化为遗传的解。编码就是将普通的模型转化到基因模型，这样就把实际的问题转化为遗传算法可以解决的问题；解码是与编码相反的过程，即将遗传算法解决的方案转化实际的问题解。3、 种群种群就是许多基因的集合。遗传算法解决实际问题的过程中，从随机选择的个体初始解开始进行地带搜索，初始解的集合

34、和每次迭代生成新的解就形成了一个种群。种群的规模大小代表所含基因的数量所以种群的大小取值很重要，种群规模越大运行速度越慢。4、 适应度函数为了寻找最优个体，必须对个体位串进行适应性评价。因此，适应度函数就构成了个体的生存环境。根据个体的适应值就可以决定它在次环境的生存能力。一般来说，好的染色体串结构具有比较高的适应度函数值，可以获得较高的评价，具有较强的生存能力。5、遗传算子遗传算法的进化通过遗传算子的作用逐代进化。标准的遗传算子包括选择算子、交叉算子和变异算子三种基本形式。1、 选择算子选择的作用是是从种群中选择优秀的个体，使它出现在下一代中，一般适应度函数越高的个体，出现在下一代的概率越大

35、。选择算子能提高种群的适应度平均值，但是不影响个体的适应度值。选择算子的作用是保存对解决问题有用的遗传信息，可以影响遗传算法的整体结果。选择算子种类繁多，根据不用的选择方式可以产生不同的结果。一般来说，最常见选择方法是转轮盘法。随机选择、优势个体保留等。2、 交叉算子利用遗传算法解决实际问题的过程中，在种群中选择一对个体进行交配；根据位串的长度对要交配的个体随机选择1到L长度的位置作为杂交位置；根据杂交概率实施杂交，配对的给提在杂交位置处，相互交换各自的部分基因，最后形成一对新个体。3、 变异算子 变异算子根据生物进化染色体某位基因的突变，从而改变染色体结构和特征的特性，在利用遗传算法节约实际

36、问题的过程中，主要目的是保持种群的多样性，避免过早收敛。 2.2.2 遗传算法的流程遗传算法在整个进化过程中的遗传操作是随机性的，但是它所沉陷的特性并不是完全随机搜索，它能有效利用历史信息来推测下一代期望性能所有的寻优点集。这样一代代不断进化，最后收敛到一个最适应环境的个体上，求得问题的最优解。遗传算法所涉及的五大要素：参数编码、初始群体设定、适应度函数的设计、遗传操作的设计和控制参数的设定。遗传算法的运行过程是一个典型的迭代过程，其必须完成的工作内容基本步骤如下： 1、选择编码策略，把参数集合X和域转换为串结构空间S； 2、定义适应值函数f(x) 3、确定遗传策略，包括选择群体大小n，选择、

37、杂交、变异方法，以及确定杂交概率pc、变异概率pm等遗传参数； 4、随机初始化生成群体P； 5、计算群体中个体位穿解码后的适应值f(x); 6、按照遗传策略，运用选择、杂交和变异算子作用于新后代形成下一代。 7、判断群性能是否满足某一指标，或者已完成预定迭代次数，如果不满足则返回步骤（6），或者修改遗传策略再返回步骤（6）。2.2.1 遗传算法的特点 与传统的优化算法相比，遗传算法主要有有以下特点：1、遗传算法不是直接作用在参变量集上，而是利用参变量集的某种编码。2、遗传算法不是从单个点，而是从一个点的群体开始搜索。3、遗传算法利用适应值信息，无须导数和其他辅助信息。4、遗传算法利用概率转移规

38、则，而不是确定性规则。遗传算法的主要优点是它在搜索过程中不容易陷入局部最优，即使在所定义的函数是不连续的。非规则的情况下，它也能以很大的概率找到整体最优解；其次，由于它的固有的并行性，遗传算法使用于大规模车辆路径计算。3遗传算法在 LS物流公司城市社区超市配送运作现状与问题3.1LS物流公司简介重庆LS物流有限公司成立于2012年，注册资金8000万元，是一家专业致力于服务重庆及全国范围内干线运输、仓储、配送等一体化物流服务、物流方案设计、大件运输、军品运输、商品贸易及供应链金融服务的物流企业。公司先后为宗申集团、嘉陵集团、潍柴动力、润通动力、两江机械、珠峰大江、佳速汽配、大江信达、瑞方渝美、

39、特发信息、重庆罗森等客户开展民品全国干线运输、仓储、商品批发与代理、冷链物流及城市商超配送业务。3.2LS物流公司配送中存在的问题3.2.1 城市社区超市配送存在的问题 随着城市社区超市配送企业的竞争加剧，城市社区超市物流企业面临着减小订单响应时间、降低物流运输成本以及提高客户满意度等的压力。为了能够在竞争激烈的市场生存，物流企业必须改善自己的物流配送体系，才能满足市场需求。配送路径的的规划是物流配送的核心，超市配送企业对其非常重视。但是，大多数物流公司在规划配送路线时，只考虑了一般情况，而没有考虑客户的临时要求和多配送中心的问题，这可能造成配送路线的局部优化，没要达到系统优化的目的。3.2.

40、2 LS物流公司配送信息系统难以达到配送要求 LS物流公司原来是某国有企业的一个部门，后来发展为股份制有限公司。由于受到传统观念和以前公司制度的固定思维的约束，配送模式陈旧，配送效率缓慢，耗费高。公司的资源配置不合理，在物流信息系统、物流车辆路径规划和决策等软件方面投入不足，导致信息系统落后，物流规划混乱，车辆调度不合理等。物流新技术的应用不足，大多停留在分散的、低水平层面、不能综合、系统地应用新的物流技术。缺乏高效的信息指挥系统，不能随时对车辆配送进行监控和调节路线。配送人员只能在设定的路线配送，盲目性强。3.2.3 LS物流公司物流管理落后根快速消费品的配送要求比较高，城市社区超市每天需求

41、的物品更新速度快，而LS物流公司的配送商品的更新速度慢，满足不了社区超市的灵活性要求。城市社区超市商品的配送效率受到配送中心、车辆配送路线安排以及调度的影响。而LS物流公司配送路线固定，配送中心与配送车辆之间的协调度低，导致满载车辆的数目，空载情况经常发生，车辆的适用效率不高。没有专门的人员协调配送中心的选址和配送路线的合理制定，导致物流配送管理体系混乱，配送人员与管理人员之间的沟通不足，难以对实际配送问题作出有效的解决方案。3.3 总结 本章主要是对LS物流公司的基本情况进行介绍，通过分析社区超市物流公司配送过程中存在的问题。415 发展重庆市电子电器废弃物回收网络的建议4 LS物流公司社区

42、超市配送路径优化中VRP模型构建与遗传算法的应用4.1 车辆路径问题的数学模型4.1.1旅行商问题无时限单配送中心TSP问题，即不考虑客户对货物送达时间限制的单配送中心车辆路径问题。该问题可以描述为：在配送中心地理位置、客户地理位置和需求量抑制的条件下，要求从单配送中心派出多辆车为所有客户提供配送服务，要求完成所有配送任务的车辆行驶总里程最短，并满足条件：1、车辆由配送中心出发，最终返回该配送中心；2、所有客户的需求必须得到满足，每个客户只能由一辆车提供服务，且仅被服务一次；3、每条配送路线上，货物的配送量之和不能超过配送车辆的最大载重量，并且运行距离不得超过该车的最大行驶距离。1.2符号说明

43、其中，式（1）目标函数，表示服务完所有客户所需行驶的总里程最短；式（2）确保每辆配送车辆的载重量（即该车所服务所有客户需求量之和）不得超过该车的最大承载量；式（3）表示配送车辆的配送行程不得超过该车的最大行驶距离；式（4）表示车辆从配送中心出发并返回配送中心；式（5）（6）表示客户i,j,在车辆k的行驶路线上，并由车辆k提供服务。4.2.2 单配送中心VRP问题 无时限单配送中心车辆路径问题，即不考虑客户对货物送达时间限制的单配送中心车辆路径问题。该问题可以描述为：在配送中心地理位置、客户地理位置和需求量抑制的条件下，要求从单配送中心派出多辆车为所有客户提供配送服务，要求完成所有配送任务的车辆

44、行驶总里程最短，并满足条件：1、车辆由配送中心出发，最终返回该配送中心；2、所有客户的需求必须得到满足，每个客户只能由一辆车提供服务，且仅被服务一次；3、每条配送路线上，货物的配送量之和不能超过配送车辆的最大载重量，并且运行距离不得超过该车的最大行驶距离。1.2符号说明其中，式（1）目标函数，表示服务完所有客户所需行驶的总里程最短；式（2）确保每辆配送车辆的载重量（即该车所服务所有客户需求量之和）不得超过该车的最大承载量；式（3）表示配送车辆的配送行程不得超过该车的最大行驶距离；式（4）表示车辆从配送中心出发并返回配送中心；式（5）（6）表示客户i,j,在车辆k的行驶路线上，并由车辆k提供服务

45、。jds：城市社区超市的总数量 l,s:单个城市社区超市，l,s=(0,1,2.,n),l,s=0时代表配送中心； j:各车辆的编号，j=(1,2,.k)Cij:从客户l到客户s的配送成本，其中ls；A：车辆单位配送距离的成本；B：单位车辆的启用固定成本；clzz：车辆的最大载重量di：客户l的需求量，并且满足客户最大需求量clzzai：客户l允许的最早服务时间；bi：客户l允许的最晚服务时间；si：车辆j到达客户l的时间点，其中j0=0；llsj:车辆从客户l到达客户s的时间。tw：车辆完成客户l任务所需的服务时间wj：若车辆提前到达客户点必须等待的时间，其中w0=0Tj0：车辆的j的出发时

46、间；Tjh：车辆j的规定返回的时间；xlsj： 其中（2-1）表示车辆配送费用最小的目标，包括车辆行驶距离，车辆的最小量以及时间早到或者延误的成本；（2-2）表示配送的车辆最大数量为K；（2-3）表示每辆车从配送中心出发并且返回配送中心；（2-4），（2-5）表示每个客户只能由一辆车配送。（2-6）表示每辆车的装载量不能超过车辆最大装载量。（2-7）表示车辆到达某个客户后，从该点理科。（2-8）表示整数约束，xlsj只能取1或者0。4.2.2.1染色体编码 针对上文建立的旅行商车辆路径问题的数学模型，本节将根据第三节遗传算法的基本原理来设计该模型的遗传算法。将配送中心编码为0，因为LS公司的配送车辆总数为t，客户的总数为n个，那么染色体的总长度为t+n+1,就可以形成一条t+n+1长度的染色体串（0,i11,i12,i1f,0,.,0,i21,i22,.i2s,0）,0和0之间表示一条配送路径，并且各条路径不重复。例如，2辆车配送9个客户（012340567890），可以表示为第一辆车从配送中心出发，经过客户1,2，3