宁波牛奶集团牛奶配送线路优化应用知识

宁波理工学院 毕业设计（论文）题 目 宁波牛奶集团牛奶配送线路优化 姓 名 李慧仪 学 号 3070125067 专业班级 07物流管理2班 指导教师 何炳华 分 院 管理分院 完成日期 2011 年6月11日 荷叶文档摘 要随着人们对生活质量要求的提高，宁波地区对新鲜乳制品的需求量越来越大。在宁波地区，有两家牛奶企业与宁波牛奶集团竞争，为了争取宁波地区的牛奶市场，对宁波牛奶集团的牛奶配送线路进行规划，从而提高宁波牛奶集团的配送效率。本文通过了解国内牛奶配送的现状，结合宁波地区宁波牛奶集团的牛奶配送情况。通过开展实地考察和在职人员访谈得到相关资料，分析宁波牛奶集团配送路线安排的现状，并从中找出宁波牛奶集团的牛奶配送线路的存在问题，具体问题有牛奶配送质量不高、配送车辆严重超载以及配送路线随意性，根据这些存在问题采用了扫描算法以及Lingo软件来规划路线，缩减了配送路线的距离和合理利用配送车辆。对于牛奶配送质量不高的问题，提出了改善配送车辆的内部设施的建议。关键词:配送；线路；牛奶；宁波AbstractWith the increasing demand on quality of life,people require the fresh dairy products more than before in ningbo. There are two milk enterprise and Ningbo Dairy Group competition in ningbo.The milk distirbution routing of Ningbo Dairy Group should be planning in order to obtain the marketing of milk in ningbo and improve the distribution effiency from Niongbo Dairy Group.In this paper, the paper combines the milk distribution sitduation in Ningbo Dairy Group,by understanding the status of the domestic milk distribution.Accord- ing to inspect Ningbo Dairy Group distribution location and interview their staff,I analyzed the distribution routing of Ningbo Dairy Group and found out the problem of the distrrbution routing.The problem include the low distribution quality,serious overloading of distribution vehicles and abitrary distribution routing.On the basis of those problem,I used the Scan Algorithm and LINGO software to solve distribution routing in order to re- duce the distribution distance and rational use of the distri- bution vehicles.I proposed the suggestion,which is improving the distribution vehicles within the facilites,about the low distribution quality of milk.Keywords: distribution; routing; milk; Ningbo目 录摘 要IAbstractII1引言11.1研究背景11.2研究目的和意义11.3研究方法21.4研究框架22文献综述32.1配送和冷链配送概述32.2配送研究的主要问题32.2.1配送的车辆安排42.3.2配送路线的优化模型43宁波牛奶集团牛奶配送的现状及问题分析63.1宁波牛奶集团牛奶配送的现状63.2宁波牛奶集团牛奶配送的存在问题83.2.1牛奶配送质量不高83.2.2配送车辆超载严重93.2.3 配送路线随意性104宁波牛奶集团牛奶配送对策124.1运用TSP问题建立配送模型124.2使用扫描算法规划配送线路134.3扫描算法结合Lingo软件解决单回路运输问题265实施对策315.1改善牛奶配送的运输工具315.2优化后线路与实际情况相结合316结束语336.1论文的结论336.2论文的重点分析336.3论文的不足与展望33参考文献34附录一35致谢411引言1.1研究背景宁波地处长江三角洲之中，是长江三角洲的发达城市之一，随着人们生活水平的不断提高，乳制品已进入了宁波千千万万个家庭。许多食品行业生产商品都需要乳制品做原料，上班一族由于上班时间匆忙，早上需要吸取营养，让自己有很好的体力迎接一天忙绿的工作，追求快速的上班一族就会选择新鲜牛奶饮品或者奶制品食品，来补充一天人体所需营养，因而宁波人们对牛奶的需求也同时增加。虽然宁波的牛奶需求大幅度上升，但是牛奶的配送工作仍然处于相当低的水平。许多牛奶工序都以人工操作或者半人工操作，出现新鲜牛奶以及新鲜奶制品供需紧张，运送工人们必须凌晨加班加点的工作，否则第二天早晨新鲜牛奶就无法到达门店或者顾客手中。目前，宁波区域内只有宁波牛奶集团有限公司从事牛奶的全过程生产活动。宁波牛奶集团有限公司是由宁波市新康力乳业有限公司、华东奶牛养殖基地、宁波科元家畜胚胎科技有限公司、科研中心、宁波市永宏机械有限公司等企业组合而成，宁波牛奶集团主营早餐新鲜牛奶以及常温盒装牛奶的生产、加工、配送等业务。宁波牛奶集团现在实行企业自营配送牛奶工作，每天将通过低温处理以后生产出来的新鲜牛奶，利用箱式货车将牛奶送往各个配送点或者各个奶站进行下一步配送工作。虽然宁波地区内只有一家宁波牛奶集团从事牛奶整条供应链活动，但是周边的伤害光明和杭州美丽健同时在宁波从事新鲜牛奶的销售活动。这对宁波牛奶集团的发展，有着关键性的影响。1.2研究目的和意义宁波牛奶集团在面对越来越多的竞争对手的情况下，如何在市场上立于不败之地、更胜一筹，是集团需要考虑的问题。除了不断提升自身产品质量、研发新产品、采取各种促销手段之外，快速地将货物传递到顾客手中也非常重要。当今是快鱼吃慢鱼的时代，因此，宁波牛奶集团必须使得配送速度更加快速、准确和有效，才有可能实现生存和发展。为了占据宁波地区的新鲜牛奶市场，宁波牛奶集团提高其集团内部的牛奶配送效率，降低物流成本，从而使得集团拥有更大的利润空间，稳定宁波地区内的市场占有率，对宁波牛奶集团的发展起着重要作用。1.3研究方法本文研究主要采用实地考察法、文献研究法、访谈法。通过查阅文献，提出了研究的背景和初步构思，还有对国内牛奶配送现状的总结和梳理，然后以宁波牛奶集团的牛奶配送体系为研究对象，进行实地考察，并对宁波牛奶集团相关工作人员进行访谈，从理论与实证两方面入手，针对实地考察和访谈中得到的问题，对宁波牛奶集团的牛奶配送提出相应对策。1.4研究框架本文的研究框架按照如图1.1所示：1引 言2文献综述3宁波牛奶集团牛奶配送的现状以及存在问题分析4宁波牛奶集团牛奶配送的对策建议配送的相关内容国内牛奶配送现状图1.1 研究框架2文献综述2.1配送和冷链配送概述配送属于物流范畴，是一个缩小的物流过程，但这并不意味着能以物流概念来代替配送的概念。配送时按用户订货的要求，在配送中心或物流节点进行货物配备，并以最合理的方式送交用户的经济活动。从配送的定义可以看出，配送是一种完善的、高级的输送活动。它不是简单地将连锁门店订的商品送到各个门店处，而是按照各门店的要求，在备货和配货的基础上，以确定的组织和明确的供货渠道，并在相关的制度约束下进行送货的。因此备货、送货时现代物流配送的基本特点。1我国国家质量技术监督局颁布的中华人民共和国国家标准物流术语（修订版GB/T183542006）中，对配送的定义为：“在经济合理区域范围内，根据客户要求，对物品进行分拣、加工、包装、分割、组配等作业，并按时送达指定地点的物流活动。” 2概括而言，配送是一种制度式的送货，是高水平的送货方式。冷链物流是一种向个人和企业消费者提供分拣，配送，冷冻运输，和零担运输，冷藏运输，冷冻和新鲜货品运输的物流活动。3冷链由冷冻加工、冷冻储藏、冷藏配送、冷链销售四个方面构成，其中冷链运输及配送是四个环节中，最容易出现“断链”现象的环节，也就是冷链中最脆弱的环节。冷链配送是冷链物流的一部分，泛指冷藏冷冻类产品在生产以后，对产品进行储藏运输、产品销售到消费者前的各个环节中始终处于规定的低温环境下，以保证产品质量，减少产品消耗的一项系统工程。冷链配送包括食品的中长途运输及短途配送等物流环节的低温状态，主要涉及铁路冷藏车、冷藏汽车、冷藏船、冷藏集装箱等低温运输工具。42.2配送研究的主要问题2.2.1配送的车辆安排通常城市配送属于短途运输，在考虑配送成本时主要关注的是运输车辆的出车次数。车辆配载问题就是使运输车装入尽量多的货物，从而减少出车的次数。对于每辆车的配载问题，每一件货物都是一个参与人，他们要在“装入”和“不装入”这两种行动中作出决策。8因此，配送车辆的合理利用，是物流优化中的一个非常重要的部分，往往与车辆配送线路的规划相成相辅的，整合在一起共同决定着物流效益的高低，这也是一个极具研究的课题。研究配送车辆的安排问题上，即要考虑到配货的要求，也要考虑到配送货物的质量和体积的差异。对于配送车辆安排方面，需要考虑到以下方面。由于车辆的载重和容积有限制，在配送时应该尽量将外观相近、容易混淆的货物分开装载，以免出现配货的差错；车辆中货物的运输方向是否一致是决定配载的先决条件，公路两点间的运输线路有多种选择，因此，这种方式可以减少不必要的车辆浪费问题。9此外，车辆安排方式上不仅仅关注于车辆问题上，驾驶员也是车辆安排的一部分。例如，日本大和运输的宅急便业务的车辆安排。宅急便采取了车辆分离的方法，采用拖车运输。牵引车把拖车甲运到B以后，把车摘下来放在B，再挂上B点的拖车乙开向A。10 车辆的周转率相应地提高了，并且这种方法是车辆利用率最高的方法。因此，配送效率也相应地发挥到最大。2.3.2配送路线的优化模型目前物流配送存在三个主要问题，第一，服务水平、质量较低；第二，控制物流成本困难；第三，影响城市交通状况。为了解决三个问题，配送路线的规划非常重要。配送路线的安排有以下方法：（一）定位运输路线安排问题（Location-Routing Problem,LRP）可以表示为给定与实际问题相符的一系列潜在的设施点，在这些潜在的点中确定出一系列的设施位置，同时要确定出一套以各个设施到各个客户点的运输路线，确定的依据是满足问题的目标。11 客户点的位置和客户的需求量是已知的或者可估算的，货物的数量也是已知的，目标是把那些潜在的设施建立起来，使得总费用最小。有三种智能优化算法可以解决运输路线的安排问题，模拟退火法（SA）、禁忌搜索算法（TS）以及遗传算法（GA）。模拟退火法与遗传算法的全局搜索能力较强，不但向解得好的方向搜索，而且以一定方式向其他方向搜索；而TS法只向使禁忌表的记忆方向进行搜索。由于遗传算法法比较容易操作，通常使用遗传算法解决运输路线安排问题。（二）运输车辆路线安排问题（Vehicle Routing Problem，VRP）运输车辆路线安排问题模型最早是由Dantzig和Ramser在1950年首次提出的，是指在物流服务网络中，已知客户和配送中心的位置，在满足车辆最大负载、客户需求的前提下，设计车辆路径，使达到运输成本最小、时间最短等目标。12解决VRP问题有三种方法，节约算法（Saving Algorithm）、扫描算法（Sweep Algorithm）、TS算法（Tabu Search Algorithm）。节约算法是Clarke和Wright在1964年提出的，节约算法是用来解决运输车辆数目不确定的VRP问题。扫描算法是Gillett和Miller在1974年首先提出的，用于求解车辆数目不限制的CVRP问题。TS算法是一种用来求解组合优化问题的启发式算法，最早是由Fred Glover详细介绍的，是一种局部领域搜索的方法。133宁波牛奶集团牛奶配送的现状及问题分析3.1宁波牛奶集团牛奶配送的现状目前，宁波区域内只有宁波牛奶集团有限公司从事牛奶的全过程生产活动，宁波牛奶集团是目前浙江省最大的保鲜奶生产基地之一，并主要采用巴氏杀菌工艺生产。宁波牛奶集团有限公司是由宁波市新康力乳业有限公司、华东奶牛养殖基地、宁波科元家畜胚胎科技有限公司、科研中心、宁波市永宏机械有限公司等企业组合而成，宁波牛奶集团主营早餐新鲜牛奶以及常温盒装牛奶的生产、加工、配送等业务。宁波牛奶集团现在实行企业自营配送牛奶工作，每天将通过低温处理以后生产出来的新鲜牛奶，利用箱式货车将牛奶送往各个配送点或者各个奶站进行下一步配送工作。宁波牛奶集团从事牛奶业务有巴氏杀菌奶、酸牛奶、灭菌奶等液体乳以及其他各类花色品种，这些牛奶的销售类型也分为超市卖场、奶站经营、每日送奶到户、直销经营、随时送达以及每天团购六大类。对于超市卖场来说，牛奶的温度非常容易被控制，由于送往超市卖场的牛奶数量比较大，可以使用冷藏车实现冷链控制。除了牛奶外包装受损导致影响牛奶质量之外，使用冷藏车进行牛奶配送到各大型超市卖场，是保证牛奶质量的最有效的方法之一。对于奶站经营、直销经营、随时送达和每天团购的牛奶，由于在整个运输的过程上，只有在运输前端和运输终端需要打开货车，其余时间牛奶的温度都处于相对稳定的状态，不容易因为温度的变化而引起牛奶变质。因此，牛奶配送的最大问题是在每日送奶到每家户的过程上。每天新鲜牛奶从总部运往每个地区的配送点上，配送点按照本地区需要的牛奶数量以及牛奶种类，对牛奶进行分拣，然后才从配送点往每家每户派送牛奶，派送牛奶的过程中，使用的运输工具是带有车厢的三轮车。据配送点的送奶员介绍，冬天配送牛奶虽然很寒冷，但是牛奶的质量是可以保证的，基本上没有收到用户的投诉。然而，在夏天炎热高温的天气下，即使提早了配送牛奶的时间，在太阳还没升起时进行配送，但是仍然会出现牛奶变质的问题，发生变质的牛奶占大多数的是纸盒包装的牛奶。因此，本论文主要研究的是每日送奶到户的牛奶配送。 进行每日送奶到每家用户的车辆一共有7辆箱式货车，分别对不同区域进行牛奶配送工作。集团内部的总车辆一共32辆货车，分别对超市卖场、奶站经营、每日送奶到户、直销经营、随时送达以及每天团购进行分配车辆，超市卖场需要的车辆占了全部车辆的二分之一左右，并且这类车具有冷藏功能；奶站经营和每天团购一共占了7辆，每日送奶到户的车辆有7辆，剩下的就是提供给随时送达给用户的。每天送奶到户的路线主要分成7条，分别是慈城线、庄桥线、江北线（洪塘周边）、宁北线（宁波大学北教学区周边）、奉西线、奉东线以及大红鹰线。在访谈中，取得了2009年12月份的每天送奶到户的部分数据，涉及牛奶配送量以及配送时间如表3.1：表3.1 需求信息以及配送时间地点线路全长(KM)配送点数（个）需求总量（瓶）慈城39.9761200庄桥34.961500江北38.4102900大红鹰88.1163050根据物流部主管介绍，慈城线、庄桥线、江北线以及大红鹰线4条线路，是分别用一辆车进行配送的，即一共需要4辆货车才可以完成整个配送工作。而且每一辆货车的最大运送牛奶数量是3000瓶，超过3000瓶的货车属于超载，通常会出现牛奶运送到配送点时，外包装已经受到不同程度的损坏。即使牛奶是用被装入到每个瓶箱的固定位置，但是由于超载的原因，再加上运送途中的跌跌撞撞，牛奶的外包装以及牛奶的质量得不到保证。此外，分拣牛奶所花费的时间在5-10分钟之间，这根据分拣人员进行牛奶分拣的速度和牛奶需求量而定。图3.1 累计需求量根据图3.1显示表明，慈城线、庄桥线以及江北线的一部分需求量可以使用一辆货车进行配送，江北线和大红鹰线的一部分可以用一辆货车进行配送，剩下的牛奶只需要一辆车就可以配送完毕。因此，一共只需要3辆货车进行牛奶配送就可以完成配送作业。然而，只从客户需求量的角度考虑整个配送作业，是不科学的。配送作业不仅仅考虑到客户需求量，也要考虑到配送路线的规划问题。3.2宁波牛奶集团牛奶配送的存在问题宁波牛奶集团在宁波地区拥有相当大的牛奶业务量，但是对于牛奶的配送工作的同时，也存在着一些问题。有效地解决这些问题，有利于提高整个配送效率以及对周边的竞争对手有着抗衡的作用。不仅如此，还为集团节省资源，达到资源利用最大化。3.2.1牛奶配送质量不高对配送点实地考察中发现了一下几个问题。首先，当货车将新鲜牛奶送到配送点后，配送点的送奶员立即将分拣出来的牛奶送到每个客户手中，但是配送的工具是箱式三轮车，不仅仅配送的速度比较缓慢，送奶员和牛奶的配送安全得不到保障，牛奶被装在配送瓶箱里，然后放到箱式三轮车的车厢，车厢内部没有任何的通风或者冷藏功能。特别是夏天的时候，由于牛奶在储存的过程中，温度非常低，遇到外界温度比较高的时候，瓶装鲜奶很有可能会出现“漏奶”现象，这由于瓶盖的热胀冷缩现象而导致牛奶被污染或者造成牛奶质量下降。牛奶除了在储藏中使用了冷冻技术外，在配送车辆上是以常温配送为主，很少车辆安装使用冷藏设备。由于没有三轮车等小型车辆的运输通道，送奶员对牛奶进行配送时比较危险。此外，对于企业的管理层来说，牛奶的配送过程监控得不到保障，不能有效地监督驾驶员的配送工作，从而降低了整个配送工作的效率。也对新员工的要求比较高，必须熟悉宁波周边一带环境，才符合应聘要求，加大了集团招聘人才的难度。3.2.2配送车辆超载严重除了实地考察以外，还对宁波牛奶集团的相关主管部门进行人物访谈，在访谈中发现了以下几点问题，直接地或者间接地危害到牛奶配送的质量。首先，由于宁波牛奶集团的车辆数跟不上牛奶需求量的变动，导致车辆超载严重。其中超100%以上的车辆每天平均5车次，超30%及以上的车辆每天平均在18-20车次，这样不仅仅影响牛奶配送的质量，也对车辆在不同的程度上造成了损坏。据物流部主管周盛强介绍，由于市场需求量每天每周每月都是不稳定的，不能因为一周或者一个月的销售幅度偏大，而购入更多的车辆，这样无疑是一种增加物流成本的表现。因此，需要持续半年或者以上进行观察，才能购入更多的车辆。其次，车辆的全天候使用率并不是都百分之一百的，只是在中午配送时比较紧张。因此，超载车次最多的是中午配送中。普通情况下，早上和晚上车辆使用率就相对较低，可以做到不超载配送。据宁波牛奶集团的姓徐的驾驶员介绍，他们日常工作量比较大，而且那些工作内容也比较烦琐，很容易忘记或者一不留神就会出错。他们每天都必须对已装箱的牛奶进行装车和卸车工作，将牛奶送到目的地后，也需要将瓶箱回收以及送货单回收。不仅如此，如果车辆发生故障，也要对车辆进行维修。再加上大部分驾驶员都是来自农村，文化素质普遍偏低。因此，驾驶员的流动性比较高，往往集团注入的驾驶员已经可以掌握日常工作，但很快驾驶员就跳槽了。这样长期下来，集团的新员工比老员工多，阻碍着整个集团的配送效率的提高。3.2.3 配送路线随意性 对于宁波牛奶集团来说，牛奶配送路线没有统一的规划，一般由驾驶员自行安排，加大了驾驶员的工作量之外，对于集团新员工来说，在没有熟悉工作环境之前，这是一个非常大的挑战。牛奶配送线路是按照区域划分的，对于江北区域和大红鹰区域来说，有四条配送线路分别是江北线（江北线以洪塘周边为主）、庄桥线、慈城线以及大红鹰线。并且以集团总部（洪塘）为配送的初始点，向每条线路的最近点出发。在这个过程中，集团必须分配4辆或以上车辆对这些区域进行配送。（如图3.2）图3.2 配送线路图对于江北线来说，分别经过宅前张、前后潘、上宅、洋市、旧宅、上沈、后张、赵家、叶家斗以及方界，共10个配送点，全长配送路程为38.4公里。在这个区域内的牛奶需求量为2900瓶，每一辆配送车辆最大载重量为3000瓶牛奶，因此，江北线只需要一辆车就可以将所有的牛奶配送完毕。从总部开始出发，到庄桥线的每个配送点分别是上邵、邵余、姚家、李家、冯家以及颜家，最后返回到洪塘总部。在这个过程中历经6个配送点，全长配送路程为34.9公里。这片区域牛奶需求量为1500瓶。所以对庄桥进行配送时，只需要一辆车就可以完成。慈城线分别经过新联、东山、上岙、慈湖、东门和新华，再从新华返回到洪塘总部，一共经过了6个配送点，全长距离为39.97公里。慈城线的牛奶需求量为1200瓶，没有发生超载现象，因此也是只需一辆车就可以完成配送工作。大红鹰线一共有16个配送点，从总部洪塘出发，分别经过金星、高峰、秀水、新丰、蒲家、后屠桥、丰成、横港、宋严王、陈横楼、包家、新庄、藕缆桥、徐家漕、长乐以及陆家庄，再从陆家庄返回到洪塘总部，这个配送路程为88.1公里。大红鹰线的总牛奶需求量为3050瓶，超过了一辆配送车辆最大载重量，因此只有集团车辆使用不紧张的情况下，才会有两辆车辆对大红鹰线的配送点进行配送。通常情况下都是超载50瓶牛奶，用一辆车对这些配送点进行配送。从上述情况可以看出，集团的牛奶配送线路缺乏系统地规划，导致慈城线和庄桥线车辆载重量没有充分地利用，载重量占车辆最大载重量的50%以及50%以下，而使得大红鹰线牛奶载重量超过车辆能够承受的最大载重量，影响牛奶的配送质量。4宁波牛奶集团牛奶配送对策从上述说讲的问题来分析，影响牛奶配送最大的是每日将牛奶配送到用户手上的过程，有效地控制每日送奶到户的配送时间以及配送使用的运输工具，有利于提高整个集团的牛奶配送的效率。由于每日送奶到户是在每天的清晨开始对牛奶进行配送，从总部运送到每个地区的配送点，再从配送点配送到用户手中。如果可以减少牛奶往配送点配送的时间，那么配送点就有更多的时间对客户进行配送工作，减少货车配送的延误导致配送点不能正常工作的概率。除此之外，提前完成每日送奶到户的配送工作，可以更早地提供空余车辆给中午需要配送的配送组，让他们提前配送，减少使用车辆紧张的发生机率，以及减少因中午车辆不足而造成牛奶超载现象，不仅仅危害到牛奶的质量，也危害到驾驶员的人生安全。因此，配送线路规划有利于集团的长远发展。本论文运用了配送路线的规划方法，来解决宁波牛奶集团的每日送奶到户的配送路线问题。4.1运用TSP问题建立配送模型TSP问题在物流中的描述是对应一个配送公司，欲将N个客户的订货用最短路线全部送达，如何确定最短配送路线是TSP问题的核心内容。设S表示从起点v1到某配送点vi所有可能经过的配送点集合，S实际上是包含除v1和vi两点之外其余点的集合，但S中的点的个数要随阶段数改变而变化。状态变量（i，S）表示：从v0出发，经过S集合中所有点一次最后到达vi；最优指标函数fk（i，S）表示：从v1出发经由K个中间配送点的S集合到vi的最短距离；决策变量Pk（i，S）表示：从v1经K个中间配送点的S集合到vi的最短路线上邻接某配送点的前一个配送点，动态规划的顺序递推关系为：根据宁波牛奶集团现在的配送地理位置的情况，可将v0替换成洪塘总部，vi可替换为某一配送点，上述顺序递推公式表示，从洪塘总部出发，到下一个配送点距离最小的，即每个配送点都寻找出距离其最近的另一个配送点，最后将这些点串联起来，用fk(i,S)表示（v1与vi之间的距离见附录一）。4.2使用扫描算法规划配送线路与节约算法相比，扫描算法比较适合多个配送点的路线规划。扫描算法只需要以洪塘为极坐标系的原点，联通图上的任意一个配送点和原点的连线定义为角度零，建立极坐标系。然后，逆时针方向旋转极坐标，直到需求总量超出一辆货车的载重量，即3000瓶牛奶。接着重复上一步动作，直到所有配送点都被极坐标扫过为止。最后，对这些被分为一组的配送点，进行线路优化。表4.2为配送点的需求量，图4.1为配送点与配送总部的位置图。表4.2 配送点的需求量配送点后张赵家叶家斗宅前张方界前后潘上沈上宅洋市旧宅新联东门东山慈湖需求量280290300350210300300290360220210110150350配送点上岙新华颜家冯家李家姚家上邵邵余秀水高峰金星陆家庄长乐徐家漕需求量180200200260250200310280350150270190250190配送点藕缆桥新庄包家陈横楼宋严王横港丰成后屠桥蒲家新丰需求量180150140170150250160140160150由于每辆货车的运输能力均为4000瓶牛奶，现有足够的车辆对牛奶进行配送。首先，对这些配送点建立极坐标系。(如图4.2) 第二步：分组过程，从角度为零向逆时针方向进行扫描，第一个被分组的配送点是宅前张，Load(1)=350；继续转动下一个被分组的配送点是前后潘，累计Load（1）=350+280=630；由于负载还没有超过限制最大载重量Load（max）=3000，继续转动。继续转动到下一个被分组的配送点是上宅，累计Load（1）=350+280+290=920；继续转动一下个被分组的配送点是洋市，累计Load(1)=350+280+290+360=1280；继续继转动被分组的配送点是颜家，累计Load（1）=350+280+290+360+200=1480；继续转动被依次分组的配送点是冯家、李家、旧宅、上邵、邵余和姚家，累计Load（1）=2990；当继续转动极坐标轴时，姚家下一个配送点是上沈，Load（1）=33003000，按照扫描法的规则，需要重新对上沈进行分组，则第一组里面有宅前张、前后潘、上宅、洋市、颜家、冯家、李家、旧宅、上邵、邵余以及姚家，一共有11个配送点被分成一组进行配送。（如图4.3）图4.1 配送点和总部的位置图图4.2 求解过程用上述的方法，重新建立一个新的组，也是以洪塘为极坐标轴的原点，逆时针转动（如图4.4），直到牛奶的总瓶数量达到一辆车的最大载重量为止，如超过最大载重量，则立即停止转动（每一步骤计算下来的牛奶累计瓶数见表4.3）。因此，根据表4.3可知，第二组里面有上沈、后张、上岙、慈湖、东山、新联、赵家、东门、新华、叶家斗、方界以及金星，一共有12个配送点被分成一组进行配送（如图4.5）。图4.3 第一组配送组图4.4 重新建组扫描表4.3 第二组配送组的牛奶累计瓶数配送点配送点所需牛奶量累计牛奶量上沈300300后张280580上岙180760慈湖3501110东山1501260新联2101470赵家2901760东门1101870新华2002070叶家斗3002370方界2102580金星2702850图4.5 第二组配送组如此类推，得出第三组配送组有高峰、新丰、陆家庄、秀水、后屠桥、蒲家、长乐、丰成、徐家漕、藕缆桥、横港、新庄、包家、宋严王和陈横楼，一共15个配送点，其载重量为Load（3）=27803000（累计牛奶瓶数见表4.4），即满足一辆货车的负载量（如图4.6）。表4.4 第三组配送组的牛奶累计瓶数配送点配送点所需牛奶量累计牛奶量高峰150150新丰150300陆家庄190490秀水350840后屠桥140980蒲家1601140长乐2501390丰成1601550徐家漕1901740藕缆桥1801920横港2502170新庄1502320包家1402460宋严王1502610陈横楼1702780图4.6 第三组配送组第三步：组内的路线优化，对上面已经分好的3个组进行组内的单回路优化，即解决组内的单回路运输问题。运用最近邻点法分别对3组配送组进行路线安排。最近邻点法的步骤是：首先，从宁波牛奶集团总部开始，作为整个回路的起点；其次，找到离刚加入到回路的上一个点的最近的一个点；最后，重复同一个动作后，将顶点和总部连接起来。首先计算出第一组配送组的配送回路，每个配送点之间的距离（如表4.5）以KM为单位：表4.5 一组配送组的距离矩阵配送点总部宅前张前后潘上宅洋市旧宅颜家冯家李家姚家上邵邵余总部3.86.70.782.14.54.53.64.49.26.37.7宅前张42.53.83.56.25.2610.97.79.4前后潘64.68.95.54.55.310.278.7上宅0.984.63.64.49.36.17.8洋市84.13.13.98.85.67.3旧宅6.44.86.281.96.4颜家2.32.87.74.56.2冯家1.96.12.94.6李家8.14.86姚家63.7上邵5邵余首先，将节点“总部”加入到回路中，T=总部，从总部开始出发，比较总部到各个配送点的距离，选择距离最小的加入到回路中。从表4.3 可得：从总部到上宅的距离最小S（1）=0.78，因此将上宅加入到回路中，再从上宅出发，观察离上宅最近的配送点。为了方便计算，1表示总部，2表示宅前张，3表示前后潘，4表示上宅，如此类推。MinC4i|iN，1i12，且i1,4=C4，5=0.9然后将洋市加入到回路中，即T=总部，上宅，洋市，再从洋市开始寻找离其最近的配送点，现在累计总距离S（1）=1.68。MinC5i|iN，1i12，且i1,4,5=C5，8=3.1再将冯家加入到回路中，即T=总部，上宅，洋市，冯家，再从冯家开始寻找距离其最近的配送点，现在累计总距离S（1）=4.78。MinC8i|iN，1i12，且i1,4,5,8=C8，9=1.9将李家加入到回路中，即T=总部，上宅，洋市，冯家，李家，再从李家开始寻找距离其最近的配送点，累计总距离S（1）=6.68。MinC9i|iN，1i12，且i1,4,5,8,9=C9，10=2.8把颜家加入到回路中，即T=总部，上宅，洋市，冯家，李家，颜家，从颜家开始寻找距离颜家最近的配送点，累计总距离S（1）=9.48。依次类推，分别再将上邵、旧宅、宅前张、前后潘、邵余和姚家加入到回路中，最后得到第一组配送组的回路T（1）=总部，上宅，洋市，冯家，李家，颜家，上邵，旧宅，宅前张，前后潘，邵余，姚家，总部，累计总距离S（1）=44.98KM。运用最近邻点法将第二组配送组和第三组配送组的单回路运输路线求解出来（如表4.6和表4.7）。表4.6 第二组配送组的距离矩阵元素总部后张赵家叶家斗方界上沈新联东门东山慈湖上岙新华金星总部3.84.34.76.88.19.99.511.815.21213.113.9后张0.841.32.85.26.86.68.912.39.19.216.4赵家1.32.85.87.37.19.412.89.69.817.2叶家斗2.36.27.87.69.813.310.110.217.7方界7.79.39.111.414.811.611.719.2上沈6.46.28.511.98.78.921.4新联5.78.211.48.28.422.9东门2.32.92.5422.7东山2.40.97625慈湖2.67.529.2上岙6.225.2新华25.4金星表4.7 第三组配送组的距离矩阵元素总部秀水高峰陆家庄长乐徐家漕藕缆桥新庄包家陈横楼宋严王横港丰成后屠桥蒲家新丰总部11.913.5139.89.910.31213.616.113.614.314.417.614.113秀水2.42.93.64.67.59.210.814.310.86.111.622.33.33高峰3.84.43.76.66157.311.919.97.33.22.81.1陆家庄4.13.36.15.514.510.711.519.46.96.66.24.5长乐5.32.94.277.58.216.26.46.65.54.5徐家漕66.3116.29.315.98.58.97.87.6藕缆桥2.410.55.55.313.64.57.75.45.6新庄2.43.43.712.64.57.95.66.6包家8.18.512.113.817.61615.8陈横楼0.964.16.25.56.4宋严王105.59.77.48.4横港9.812.313.114.5丰成53.54.9后屠桥32.1蒲家1.8新丰计算第二组、第三组配送组的单回路线路：利用TSP模型的数学描述:minCij|i,jN，1i,jn,将第二组配送组和第三组配送组的回路分别求出为T（2）和T（3），T（2）=总部，后张，赵家，叶家斗，方界，上沈，东门，东山，上岙，慈湖，新华，新联，金星，总部，累计总距离S（2）=80.71KM（累计距离见表4.8 ）。表4.8 第二组配送组的累计距离配送点与上游配送点的距离累计距离后张3.83.8赵家0.844.64叶家斗1.35.94方界2.38.24上沈7.715.94东门6.222.14东山2.324.44上岙0.9725.41慈湖2.628.01新华7.535.51新联8.443.91金星22.966.81总部13.980.71第三组配送组的回路T（3）=总部，长乐，藕缆桥，新庄，包家，陈横楼，宋严王，丰成，蒲家，新丰，高峰，秀水，陆家庄，徐家漕，后屠桥，横港，总部，累计总距离S（3）=82.2 KM（累计距离见表4.9）。表4.9第三组配送组的累计距离配送点与上游配送点的距离累计距离长乐9.89.8藕缆桥2.912.7新庄2.415.1包家2.417.5陈横楼8.125.6宋严王0.926.5丰成5.532蒲家3.535.5新丰1.837.3高峰1.138.4秀水2.440.8陆家庄2.943.7徐家漕3.347后屠桥8.955.9横港12.368.2总部1482.2根据宁波牛奶集团现状配送的总路程S现=210.21KM，运用扫描算法后，总路程S=44.98+80.71+82.2=208.19KM，节约了2.02KM的路程，而且使用扫描算法计算出来后的路线，只需要3辆货车就可以做好现有的配送工作，比原来节约了1辆货车。由于牛奶配送非常注重时间因素，配送时间过长会导致牛奶质量下降，因此，配送时间越短越好。在扫描算法之后，我们需要进一步分析配送时间是否有缩减，从而确定扫描算法计算出来的配送路线为优化之后的配送路线。下表4.10为第一组配送点之间所需要的配送时间（时间单位为分钟），此表格所提供的数据为大概时间，即忽略了配送过程中可能发生的其他影响配送效率的因素，如堵车、路障以及途中加油等不可预测因素。表4.10 第一组配送点之间的配送所需时间配送点总部宅前张前后潘上宅洋市旧宅颜家冯家李家姚家上邵邵余总部1214151212383242381929宅前张57810131214291527前后潘871810910192220上宅413121012211825洋市14111011202224旧宅18243435821颜家67161620冯家5131517李家122527姚家2616上邵14邵余根据表4.10 上的数据得出，T（1）=总部，上宅，洋市，冯家，李家，颜家，上邵，旧宅，宅前张，前后潘，邵余，姚家一共需要花费时间为154分钟。如此类推，可大概求出第二组以及第三组配送组花费的时间，分别为154分钟和229分钟（其他配送点之间的配送时间可见表4.11和表4.12），讲三组配送组所花费的时间相加，既一共花费时间T=154+154+229=537分钟。表4.11第二组配送点之间的配送所需时间元素总部后张赵家叶家斗方界上沈新联东门东山慈湖上岙新华金星总部10141622918182728242527后张36101613132223191727赵家561915162425222030叶家斗92118182728222244方界2022152332211333上沈12112422181636新联112320171220东门91061038东山1051847慈湖81548上岙1644新华53金星表4.12第三组配送点之间的配送所需时间元素总部秀水高峰陆家庄长乐徐家漕藕缆桥新庄包家陈横楼宋严王横港丰成后屠桥蒲家新丰总部323630263129333738363536424336秀水989111817272826191812158高峰1014152020303028222113157陆家庄111218172728261918192212长乐914182223211919192213徐家漕15122025191615201814藕缆桥81415131211241920新庄1717151211241819包家1081223353031陈横楼61423363031宋严王1221332829横港7151421丰成131321后屠桥1010蒲家12新丰由于未优化之前的配送线路所花费的时间为538分钟，在此的配送时间已经忽略了车辆配送到配送点时，需要进行再次分拣的工作时间以及回收空瓶子所花费的时间，此研究仅限于配送牛奶路径上。因此，此方法计算出来的路径为可行的优化路径。4.3扫描算法结合Lingo软件解决单回路运输问题经过扫描算法之后得到三个单回路配送组，为了寻求更优的方案，使用Lingo软件找出每组配送组的单回路运输路线。每组配送组根据扫描算法可以求得分别为第一组配送组T（1）=总部，上宅，洋市，冯家，李家，颜家，上邵，旧宅，宅前张，前后潘，邵余，姚家，第二组配送组T（2）=总部，后张，赵家，叶家斗，方界，上沈，东门，东山，上岙，慈湖，新华，新联，金星，第三组配送组T（3）=总部，长乐，藕缆桥，新庄，包家，陈横楼，宋严王，丰成，蒲家，新丰，高峰，秀水，陆家庄，徐家漕，后屠桥，横港。使用Lingo软件可以求出第一组配送组的单回路路线为t（1）=总