石河子大学商学院毕业论文
引言
随着社会主义市场经济的不断发展，作为“第三利润源泉”的物流对经济活动的影响日益明显，引起了人们越来越多的重视，成为当前“最重要的竞争领域”。配送是现代物流的一个重要环节，随着物流的全球化、信息化及一体化,配送在整个物流系统中的作用变得越来越重要。配送是连接生产与消费之间的一种中介服务。它是指按客户(包括零售商店、用户等)的订货要求(包括货物种类、数量和时间等方面的要求)，在物流中心(包括配送中心、仓库、车站、港口等)进行分货、配货工作，并将配好的货物及时送交收货人的物流活动。
配送合理化与否是配送决策系统的重要内容，配送线路的合理与否又是配送合理化的关键。选择合理的配送路线，对企业和社会都具有很重要的意义。 对企业来说，首先优化配送路线，可以减少配送时间和配送里程，提高配送效率，增加车辆利用率，降低配送成本；其次可以加快物流速度，能准时、快速地把货物送到客户的手中，提高客户满意度；再次使配送作业安排合理化，提高企业作业效率，有利于企业提高竞争力与效益。
对社会来说，它可以节省运输车辆，减少车辆空载率，降低了社会物流成本，对其他企业尤其是生产企业具有重要意义。与此同时，还能缓解交通紧张状况，减少噪声、尾气排放等运输污染，对民生和环境也有不容忽视的作用 。
配送线路优化是指对一系列的发货点和收货点，组织适当的行车路线使车辆有序的通过它们，在满足一定的约束条件下（货物需求量与发送量，车辆容量限制，行驶里程限制），力争实现一定的目标（行驶里程最短，使用车辆尽可能少）。但配送作业情况复杂多变，不仅存在配送点多、货物种类多、道路网复杂、路况多变等情况，而且运输服务地区内需求网点分布也不均匀，使得线路优化问题是一个无确定解多项式难题，需要启发算法去求得近似最优解。
本文将以新疆国美电器当前的配送线路的优化问题作为研究对象，对各县市需求量及运距进行分析计算，建立VRP数学模型，运用节约里程算法对建立的模型进行求解，对国美电器的配送路线进行优化。最后对优化的结果进行分析，从而为该公司提供较合理的配送方案，以期减少配送里程，降低物流运输成本，提高该公司物流运作效率，客户服务质量和整体竞争力。
1
石河子大学商学院毕业论文
第1章 物流配送概述
1.1物流配送的概念
配送（distribution）起源于“送货上门”。20世纪60年代初期，生产企业或中转仓库根据客户的需求，将货物准确的运送到客户手中，形成了配送的雏形——“普通送货”。随着客户对产品多样化和差异化的要求，为了满足客户的需求，原始的普通送货开始转向分拣、配货、送货一体化。因此产生了配送。
按照国家质量技术监督局发布的中华人民共和国国家标准“物流术语”（GB/T 18354—2001），配送是指在经济合理区域范围内根据用户要求，对物品进行拣选、加工、包装、分割、组配等作业，并按时送达指定地点的物流活动。
1.2 物流配送的功能
配送作为一种新型的物流手段，伴随着生产的不断发展而日趋成熟。发展配送，无论对于物流系统的完善，企业的发展，还是整个经济社会效益的提高，都具有重要的作用。
（1）配送完善和优化了物流系统。第二次世界大战后，高水平的干线运输呼唤支线运输和小搬运配套，但支线运输和小搬运在适应性、灵活性、服务性上的欠缺，致使运力不合理、运输成本过高。配送的出现使干线运输、支线运输及小搬运统一，输送过程得以优化和完善。
（2）配送提高了末端物流的效益。配送通过大批量进货，集中发货，以及将多个小批量集中一起大批量发货，都能有效的节省运力，实现经济运输，降低成本，使末端的物流经济效益得到提高。
（3）配送通过集中库存使企业实现低库存或零库存。采取准时制配送方式之后，生产企业完全可以依靠配送中心的准时配送而不需保持自己的库存或保持少量安全库存而不必留有经常库存。
（4）配送简化事物，方便客服。采用配送的方式，客户只需向一处订购，或一个进货单位联系就可以订购到以往需要去许多地方才能顶到的货物，因此大大的减轻了客户的工作量和负担，也节省了事务的开支。
（5）配送可以降低整个社会物资的库存水平。发展配送，实行集中库存，整个社会物资的库存总量必然低于各企业分散的库存总量。同时，配送有利于灵活高度，有利于发挥物资的作用。此外，集中库存可以发挥规模经济优势，降低库存成本 。
2
石河子大学商学院毕业论文
1.3 配送路线优化的意义
配送合理化与否是配送决策系统的重要内容，配送线路的合理与否又是配送合理化的关键。选择合理的配送路线，对企业和社会都具有很重要的意义。
对企业来说，(1)优化配送路线，可以减少配送时间和配送里程，提高配送效率，增加车辆利用率，降低配送成本。(2)可以加快物流速度，能准时、快速地把货物送到客户的手中，提高客户满意度。(3)使配送作业安排合理化，提高企业作业效率，有利于企业提高竞争力与效益。
对社会来说，它可以节省运输车辆，减少车辆空载率，降低了社会物流成本，对其他企业尤其是生产企业具有重要意义。与此同时，还能缓解交通紧张状况，减少噪声、尾气排放等运输污染，对民生和环境也有不容忽视的作用 。
第2章 物流配送模型及方法描述
2.1 多回路运输—VRP模型
多回路运输问题是现实中很普遍的一种调配问题，特别对于有大量服务对象的实体，例如拥有一个上千客户的企业。此类调配的核心问题是如何对车辆进行调度。因此，VRP（Vehicle Routing Problem）模型也应运而生，成了解决多回路问题的一个相当成功的模型。
该问题研究目标是：对一系列顾客需求点设计适当的路线，使车辆有序地通过他们，在满足一定的约束条件下（如货物需求量、发送量、车辆容量限制，行驶里程限制等），达到一定的优化目标（如里程最短，费用最小，时间尽量少等）。它涉及了多辆交通工具的服务对象的选择和路径确定两方面问题。
一个典型的VRP模型可以如下表述：
（1）基本条件 现有m辆相同的车辆停在一个共同的源点v0，它需给n个客户提供货物，顾客为v1、v2,…，vn。
（2）模型目标 确定所需的车辆数N，并指派这些车辆到一个回路中，同时包括回路内的路径安排和调度，使总费用最小。
（3）限制条件：N不大于m；每一个订单都要完成；每辆车完成任务后都要回到源点v0；车辆的容量限制不能超过；特殊问题还需考虑时间限制；运输规章
3
石河子大学商学院毕业论文
限制。
2.2 节约里程算法
节约里程算法（Saving Algorithm）是用来解决运输车辆数目不确定的VRP问题，它是目前用来解决VRP模型最有名的启发式算法。 2.2.1节约里程算法的基本原理
节约里程算法的核心思想是将运输问题中存在的两个回路（0，? ，i，0）和（0，j，? ，0）合并成一个回路（0，? ，i，j，?，0）。在上面的合并操作中，整个运输问题的总运输距离会发生变化，如果变化后总运输距离下降，则称节约了运输距离。相应的变化值，叫做节约距离
?Cij?cio?coj?cji?Cij，如式（1）所示。
（1）
调整过程如图2所示。
调整前 调整后
图2-1 节约算法的图像描述
j j 0 i 0 i
4
石河子大学商学院毕业论文
2.2.2节约里程算法主要步骤
已知条件:需求点集NR={1,2,?, n},各点需求量Ri,各点间最短距离
cij。
I?j第一步,形成一个初始解。确定各车辆配送点集I1,I2,???,Im令j??,
j=1,2,?,n (先采取单点配送)。
第二步,进行节约度的计算。计算所有点对的节约度进行升序排列。
，然后对计算结果
第三步，进行回路的合并。从升序排列的节约度序列中的最上面的值开始，直到节约里程
的队列空为止,重复下列步骤:按照节约里程
队列从大到
小的顺序,分析客户i和j之间合并的可能性(是否满足装载限制条件、不在同一路径内以及合并次数不超过2),将i, j连接起来,即可令
Ii??Ii?Ij;Ij??。如
果不是这样,则从节约里程队列中去除当前的节约里程，分析下一个客户对。
第3章 新疆国美电器配送运作现状分析
3.1 公司简介
新疆国美电器有限公司成立于2004年9月25日。目前，新疆国美电器有限公司在全疆拥有大型家电直营卖场22家，在乌鲁木齐市区设立10家门店；在库尔勒、阿克苏、哈密、昌吉、石河子、奎屯、克拉玛依、伊犁、喀什9个地州城市均设立了分公司，拥有专业的电器直营卖场12家，公司现拥有员工1200余名，年销售额突破10亿元。
3.2 公司配送现状
新疆国美电器配送现状是由设在乌鲁木齐的一级仓库，分别向9个二级仓库按周期（一般为三天）配送货物如图一所示。各分公司按周期上报需求量,由乌鲁木齐总仓统一进行配送。新疆国美电器总仓配送时租赁的是17.5米半挂高低平板车。该车可以装电冰箱一类的大家电27台，洗衣机一类的中型家电56台。在配送时，电冰箱一类的的大家电和洗衣机一类的中型家电是分开配送的，都是整车配送，不会因分公司的需求量出现半车配送的情况。从成本考虑，一车能装电冰箱一类大家电的数量有限，本文主要对洗衣机一类中型家电的配送路线进行优化。
5