课程设计论文——基于节约算法的某建材企业配送路线优化

1、物流系统优化与设计题 目: 基于节约算法的某建材企业 配送线路优化分析 姓 名: 学 院: 专 业: 班 级: 学 号: 2011年 6 月 21 日目 录摘要2关键词21背景介绍21.1研究内容 21.2研究方法31.3研究目的×××31.4研究意义×××32.案例分析33.优化方法 43.1一般VSP模型43.2节约算法44. 优化方案54.1案例数据分析 54.2构造网络图 64.3配送线路优化 75.总结7参考文献8图1 配送中心分布图5图2 配送点中心网络图6表 1 配送点和各零售部的关系6表 2 物资需求量6表 3 点对间

2、的距离cij6表 4 节约值表7基于节约算法的某建材企业配送路线优化 摘要：随着市场经济的发展，作为“第三利润源泉”的物流对经济活动的影响日益明显，越来越引起了人们的重视，成为“当前最重要的竞争领域”。配送是物流中一个重要的直接与消费者相连的环节，物流配送车辆优化调度，是物流配送中关键的一环，对企业节约成本、增加利润起着重要的作用。本文对区域建材配送问题进行了研究，一某建材企业为例，利用节约启发式算法，考虑了约束条件，构建了数学模型，得出该企业最佳配送路线和车辆的综合调度方案。关键词：区域建材配送；节约算法；线路优化 1. 背景介绍1.1研究内容配送是物流中一个重要的直接与消费者相连的环节。配

3、送一般定义为，将货物从物流结点送达收货人的过程。主要包括集货作业、配货作业、车载货物的配装、配送线路的确定四个环节。随着物流配送集约化、一体化的发展，常将配送的各环节综合起来，核心部分为配送车辆的集货、货物配装及送货过程。进行配送系统优化，主要就是配送车辆优化调度，包括激活线路优化、货物配装及送货线路优化，以及集货、货物配装和送货一体化优化。物流配送车辆优化调度，是物流配送优化中关键的一环。对货车车辆进行优化调度，可以提高物流经济效益、实现物流科学化。制定合理的物流配送方案是整个物流环节中最重要的组成部分，也是合理控制物流成本输出的先决条件。整个物流配送的环节都需要围绕着全套的物流配送方案进行

4、，包括对物流系统中各子系统，如运输、储存、配送、装卸、包装等各环节所组成的物流整体活动的规划，做到合理的支配其中的各个环节。建材物流是指包含建材的废弃与还原，连接建材供应商（供给主体）与建筑工程（需要主体），克服时间与空间距离并且创造一部分形质效果的物理性经济活动。具体包括：采购、运输、保管、装卸搬运、流通加工等活动以及有关的信息活动。当前国内建筑业正处于快速繁荣期，奥运工程项目的全面建设和房地产项目投资的巨额增长，势必会带动一个新型的行业建材物流业的发展壮大，建材、家装物流已悄然走进我们的生活。建材种类繁多，性质各异，因此建材物流有其自身特有的多样性和复杂性等特点：供应物流占主导、物流流程长

5、、结点多、物流量的不稳定性、物流服务场所的变动性、物流服务方式的灵活性等。建筑业投资巨大，通常是数亿元以上或者百亿元以上，一般认为，工程建设项目中材料成本占工程项目造价的6070，而物流费用占材料成本的17左右，也就是说，物流费用约占工程项目造价的11左右。可见，物流费用在建筑业的造价中占有很高的比重，而且物流效率的高低还会影响建材占用资金的数量和施工效率，建材物流已然成为建筑业的第三利润源。当前学术界对建材物流的关注程度不高、研究成果不多，因此，有必要对当前国内建材物流现状和未来发展趋势进行分析和研究。建材物流配送受到高度重视。建材与其他商品的一个重要不同点是量大、体重、价值低，物流费用在商

6、品成本中占很大比重。降低物流成本是提高竞争能力的重要途径。因此，规模化、专业化、现代化的建材物流配送中心、功能完善的大型建材物流园区将成为建材物流发展的主流趋势，不仅可以提高物流配送效率和质量，还可以减轻城市建材流通压力。由于经济发展带来了货物的急剧增加，消费向小批量、多批次、多品种转化，销售企业向大型化、综合化发展，使得配送数量迅速增加，同时建材种类的多样性，也使得配送工作难度增加。本文就区域建材配送系统的关键技术中的车辆调度问题进行了研究，关键技术即是指集货、配货及车辆调度优化。其中，重点研究了合理确定配送路线的问题，这是整个配送网络优化的关键环节。合理确定配送路线就是用最少的动力，走最短

7、的里程，花最少的费用，经最少的环节，以最快的速度把货物运至用户手中。合理规划配送路线对配送成本的影响要比一般运输大得多，所以必须在全面计划的基础上，制定高效的运输路线，选择合理的运输方式和运输工具。建材行业的配送过程中，根据建材的特殊性，充分考虑了货车装载量的约束以实现运输的优化。1.2研究方法在研究过程中，通过选取案例企业的某一配送区域，就配送系统的优化问题用数学方法进行了定量分析和研究，对各个配送点的需求进行假设，建立了数学模型，通过分析计算得出该配送区域的最优配送路线和车辆数量的需求数量。1.3研究目的对案例企业的物流配送系统进行分析，得出优化方案，节约物流成本，从而提高企业的利润。同时

8、也是通过对案例企业的研究，进一步了解物流配送中车辆优化调度对节约企业成本的重要影响，对提高劳动生产率、提高经济效益、实现物流科学化、促进社会发展和经济建设的重要作用。企业只有改进物流环节，重视配送优化，才能降低物流成本，减少运营费用，提高配送效率，从而取得优势。1.4研究意义现代物流作为一种先进流通方式管理技术在世界广泛范围内得到高度的重视，并在生产、流通、服务领域得到广泛应用而获得快速发展，正在成为改变经济运行方式和企业发展模式的重要手段。特别是供应链物流管理技术的出现和发展，更是提升了物流的发展水平和加快了物流的集成化程度。随着全球经济的一体化的发展，由于集成化物流的理念得到进一步的推广，

9、物流系统比以往任何时候都要复杂，技术的应用和管理具有很强的系统性，如何降低各个环节企业的物流成本，提高物流服务水平，最大限度地满足客户需求，具有积极而现实的意义。物流系统解决方案中，运输与配送问题占有很重要的地位，主要原因是运输和配送过程的成本占物流总成本的很大比重，根据现有的研究成果，大约在70%90%之间。解决运输成本的合理化，集中体现在运输过程的合理组织与安排上，通过路径的优化来体现这种对降低运输成本具有重要作用的管理工具与具体物流活动的运作，是安排合理运输、解决运输与配送问题的重要手段，也是实现物流管理科学化和合理化的重要途径。本文重点通过节约启发式算法，求解物流配送优化路径的问题，通

10、过理论与实践的结合，寻求降低物流成本与提高物流效率的重要途径。2. 案例分析该企业的经营产品为建筑材料，主要的客户位于南京市雨花台区的几大建材装饰城，主要是金虹市场、长江装饰城、西郊物资商场、绿色建材市场等，同时公司自己设有下属的经营销售部。所以拟在需求点附近设置一处配送中心，对各需求点进行建材的配送。由于物流成本在企业中占很大比重，而配送是企业物流中的关键环节，所以需要对该区域的配送线路进行优化，已得到最短路径，节约运输成本，从而降低企业的运营成本，提高利润。该配送中心现有解放牌前四后四的仓栅式货车四辆，每辆车的载重量为15吨，每辆车每趟会产生一定的费用，在实施优化的过程中，要考虑货车载重量

11、的约束，使得出车费用最省。3. 优化方法 3.1一般VSP模型为构造数学模型，将车场编号为0，任务编号为,任务及车场均以点i来表示。定义变量如下：1 点i的任务由车辆k完成；0 否则。1 车辆k从点i行驶到j点；0 否则。则可得到车辆优化调度数学模型如下： 模型中，表示从i点到j点的运输成本，它的含义可以是距离、费用、变量、时间等，一般根据实际情况确定，可同时考虑车辆数和运行费用，如下确定：1) 当i为车场时，包括固定费用和运行费用 2) 当i为任务时，只有运行费用，即 其中，为相对于运行时间的费用系数；为车辆的固定费用，即增加一车辆的边际费用。一般认为，派出一辆车的固定费用远远高于车辆的行驶

12、费用，因此该模型在极小化车辆数的前提下，再极小化运行费用。减小的值将会是使用的车辆数增多，而线路长度缩短。若令，则模型目标是使用的车辆数最少。3.2节约算法节约 算 法 又称C-W 算法，是由Clarke和Wright于1964年首次提出的。它的基本思想是首先把各点单独与源点0(车场)相连，构成1条仅含一个点的线路。总费用为两倍的从原点到各点的距离的费用 。然后计算将点i和j连接在一条线路上费用的“节约值”: S(i,j)=c0i+ ci0+ c0j+ cj0-(c0i+ cij+ cj0)= c0i+ c0j-cijS(j,i)=cij+coi-cijS(i,j) 越大，说明把i和i连接在一

13、起时总路程减少越多。构造线路时，根据S(i,j) 从大到小的顺序进行，实现时可在表上操作，具体步骤如下:Step1: 计算节约值S(i,j) ，并按从大到小顺序排列成表格形式;Step2:考察表格中最大元素S(i,j) ;Step3:考察S(i,j)对应的点i和点j，检查是否满足下列条件: (1)若 点 i 和点j均不在己构成的线路上，则可连接点i和点j，得到线路段 0->i->j->0，转步骤Step4; (2)若 点 i 或点j在已构成的线路上，但不是线路的内点(即不与源点0直接相连)， 则可以连接，连接后得到线路段0>i->j->0或0->i-&

14、gt;j->0 ，转步骤Step4; (3)若 点 i 和点j位于己构成的不同线路上，且均不是内点，则连接后的得到线路段 0->->i->j->->0，转步骤Step4;(4)若 点 i和 点j位于已构成的同一条线路上，则不能再进行连接，转步骤Step3；Step4:划去第i行和第j列，即i点不能再到其他点，而j点也不能由其他点到达;Step5:若所有元素均被划去，则己得到完整线路，算法终止;否则，在没被划去的元素中选择最大元素，转步骤Step3。4.优化方案4.1案例数据分析该配送中心共有4辆货车，为一种类型，最大载重量为15吨。该配送中心在世纪华联超市附

15、近，设代码为O，各配送点的代码及分布如下图所示：图1.配送中心分布图下表给出了各配送点与零售部的关系：表1.配送点和各零售部的关系编号地址需求点A江苏省南京雨花台区应天大街长江装饰城南京长江装饰城立邦油漆经营部南京长江装饰城东吴木业销售部南京长江装饰城金鸿泰装饰材料配套中心B金虹市场南京市金虹市场鑫华昌铝材经营部C江苏省南京雨花台区南京西郊物资商场南京赛虹桥建材商城云峰建材经营部南京市雨花台区广龙木业D南京市西营村182号南京市雨花台区佳乐门窗材料经营部E南京市雨花台区西云村3号南京市雨花台区中陵发屋F南京市雨花台区应天路10号南京市雨花台区小四汽车租赁服务部G南京市雨花台区集合村103号南京

16、市雨花台区忠余线缆销售部H南京市雨花台区绿色建材市场内南京绿色建材市场飞扬油漆总汇各配送点的物资需求量如下表所示：表2.物资需求量地点ABCDEFGH需求量（吨)8.0 3.0 5.0 2.52.0 4.52.0 2.54.2构造网络图将各配送中心的分布用网络图表示出来：H1.1图2.配送点中心网络图用谷歌测量中配送中心与各配送点、配送点与配送点之间的最短距离，绘制点对间的距离表：表3.点对间的距离cijjiOABCDEFGHO1.1 1.1 2.1 1.2 1.1 2.1 0.6 1.5 A1.1 1.2 1.8 2.0 1.9 1.0 1.3 1.0 B1.1 1.2 1.9 2.1 1.

17、7 1.8 2.6 1.9 C2.1 1.8 1.9 1.5 1.7 1.8 2.6 1.9 D1.2 2.0 2.1 1.5 1.4 2.3 2.5 2.0 E1.1 1.9 1.7 1.7 1.4 2.7 1.2 2.0 F2.1 1.0 1.8 1.8 2.3 2.7 1.6 1.8 G0.6 1.3 2.6 2.6 2.5 1.2 1.6 1.6 H1.5 1.0 1.9 1.9 2.0 2.0 1.8 1.6 4.3配送线路优化用节约算法计算出节约值，如下表右上部分数据所示：表4.节约值表ijOABCDEFGHOA1.1 1.0 1.4 0.3 0.3 3.1 0.4 1.6 B1.

18、1 1.2 0.3 0.2 0.5 0.4 0.3 0.6 C2.1 1.8 1.9 0.8 0.5 1.6 0.1 1.7 D1.2 2.0 2.1 1.5 0.9 1.0 0.0 0.7 E1.1 1.9 1.7 1.7 1.4 0.5 0.5 0.6 F2.1 1.0 1.8 1.8 2.3 2.7 1.1 1.8 G0.6 1.3 2.6 2.6 2.5 1.2 1.6 0.5 H1.5 1.0 1.9 1.9 2.0 2.0 1.8 1.6 1 由表4可知，c(A,F)节约值最大为3.1，连接A-F点，根据表2可知，载重量为8+4.5=12.5<最大载重量15，满足条件，所以A-F可连接，路程为1.0公里；2 C（F,H)节约值为最大1.8,H点独立，F点已连接，但非内点，连接A-F-H,载重量为12.5+2.5=15最大载重量15，A-F-H可连接，路程为1.0+1.8=2.8公里；此时车辆满载，所以第一条线路为O-A-F-H-O;A/F/H均不可连接，划去此三行三列；3 继续按照节约算法，可得出第二条线路O-C-D-E-G-B-O,该线路载重量为14.5；4 第一条线路总里程为5.4里，节约里程4.9公里； 第二