毕业设计（论文）-基于旅行商问题的循环取货模式优化.doc

基于旅行商问题的循环取货模式优化研究（赣南师范学院 商学院，江西 赣州 341000）摘要：循环取货是一种新型的供货模式，贯穿于整个供应物流之中。文章主要立足于循环取货入厂物流，通过对循环取货的运作方式与特性进行分析，结合相关汽车物流企业的相关问题，提出相应的解决方案。在对供应商进行分类合理性分析之后，建立旅行商问题模型、运用软件设计循环取货初始路线，并结合企业相关情况，优化初始路线。本文旨在通过对汽车零部件循环取货方式进行定性和定量的综合分析,提出有效的优化方案,为汽车制造行业的入厂物流实践提供一些有意义的参考。关键词：循环取货 入厂物流 客户价值循环取货(Milk Run)，也称为“牛奶取货”“集货配送 ”“多仓储间巡回装卸货混载运送”“定时定点取货”,是国内最早是汽车制造业使用的一种物料集货模式。其具有小批量、多频次、定时性等特点。循环取货的应用使得物料JIT供应成为可能。有效降低运输过程中的运输成本、仓储成本等，保证了生产的连续性。本文是在安吉现以存在的汽车零部件入场物流循环取货模式的基础上，再度革新，针对运输过程中的运输成本高、装载率低和运输路径复杂及环境的动态性问题，进行循环取货的合理设计。一、汽车零部件入场物流循环取货模式现状分析 本文中我们主要从国内安吉汽车物流有限公司 安吉物流是国内最大的汽车物流服务供应商，是全球业务规模最大的汽车物流服务供应商。中零部件入厂物流为例，对其循环期货模式中出现的问题进行分析存在的问题主要有以下几个方面：1. 运输成本高公司引入循环取货运作模式的目的在于对零部件供应商现有的运输网路加以优化，使之既能满足生产波动的需求，同时又能将运营成本控制在一定范围内。但目前在运用的过程中，物流运作成本仍然偏高，在总的物流费用成本中运输的成本达到了44% ，如图1-1所示：物流费用比例表存货持有20%管理4%运输44%客户服务6%仓储26%存货持有管理客户服务仓储运输图1-1物流费用构成图造成运输成本费用高的一个重要的原因是循环取货模式下的运输车辆的路径设计不合理。2. 路径设计复杂运输车辆的路径安排要考虑各个供应商的出货地址、严格的出货窗口设置，需要确定一条Milk-run路径要遍历哪些供应商，针对整个供应商网络需要设计多少条Milk-run路径。当网络规模较小时较易解决，但对于目前192个供应商的网络，原有的运输路径就不能满足。由于供应商不是每天固定不变提供货物，主机厂的生产订单每天的需求也不同，因此，运输车辆的路径设计就变得比较困难。3. 装载率低实际运作过程中，通常采用的是在每条Milk-run路径上安排无限的运输车辆来实现货物全部运输完的目标。考虑运输成本，往往是在有限运输车辆的前提下，实现Milk-run与运输车辆调度之间的协调，而安吉目前的装载率远没有达到85%的理想状态。4. 生产计划和运输变动性大在零部件物流配送过程中，由于各种原因造成生产商的紧急加单、减单和并单等超过当天零部件正常需求量的25%时；或当天气、道路等出现异常情况时，就需要设计科学的应急运输方案，进行合理决策，以控制运营成本。二零部件供应商分析1. 供应商分类概况本文根据安吉汽车物流有限公司在上海地区的零部件供应商数据信息（供应商编号为：10000，100001，11107，11108），可以按供应商、大区代码、地区代码、距离、地区描述和频次这几大类别对供应商进行分类分组，分组情况如表1-1所示：表1-1 供应商的分类情况表序号分类标准分类结果数量1供应商（供应商中文名，提货地点）10000,10001,10002,10008，11091，111081922大区代码D1，D2，D3，D443地区代码O1，O2，O8，S1，S2，S8164距离10KM，10KM-20KM，150KM180KM155地区描述安亭及周边金山干巷/奉贤西部/浦东川沙奉贤东部/南汇江阴周庄、张家港166频次1,2,3,4,5,662.分类合理性分析2.1按照供应商（供应商中文名，提货地点）分类安吉客户的主机厂G有近15,000 种的零部件，其中国产零部件近万种，分布在江浙沪等10 余个省市的170多家国产零部件供应商, 而目前其供应商的范围仍然在扩大。针对安吉零部件目前的循环取货模式，该分类标准是将每个供应商作为单独的个体进行整合分析，而每一个体难以形成完整区域，数量难处理，且划分标准难以确立。因此，按照供应商分类是不合理的。2.2按照大区分类大区的分类是很明确的，即分为D1，D2，D3，D4四种。我们对每个大区进行筛选，发现这一分类和其他分类标准是有联系的，例如和“距离”之间的联系，如表1-2所示：表1-2 大区和距离之间的联系表 距离供应商数量大区代码距离供应商数量D190KM6 从表1-2中可以看出，虽然各大区有各距离分布，甚至大区之间的距离有交集，但供应商数量在各区还是有一个相对集中度，大区的分类是根据各个供应商和主机厂G之间的距离来划分的，较近的为D1，较远的为D4。这种分类可将相距近的点联系在一起，方便采用循环取货模式（不同大区之间交集的部分中，由于不同大区的点相距较远，不会产生路径计算影响，如D3和D4交集的70KM90KM部分）。可知，此分类方式较合理。2.3按照地区分类对安吉上海地区零部件供应商分析，对于地区的分类也很明确，紧接着大区的分类下来。因此，在考虑地区分类前，首先要确定地区所属的大区，建立两者之间的联系，将地区和大区联系起来考虑，二者联系如表1-3所示：表1-3 地区大区之间的联系表大区地区每个大区包括地区的数量D1S11D2S2，S32D3S4，S5，S6，S7，S85D4O1，O2，O3，O88不同地区隶属于不同大区且没有交集，可考虑按此分类对供应商进行分类。2.4按照距离分类根据安吉上海地区零部件供应商中“距离”一列给出的数据可知道，此距离是指供应商距主机厂的距离，标注出来将呈现以主机厂为圆心，距离为半径的呈多环状的同心圆状。依据本分析和循环取货系统在实际操作中的经验可知，按照此标准分类的方式，达不到最优化的效果。2.5按照地区描述分类对安吉上海地区零部件供应商中的16种地区描述进行分类，可知供应商分布在主机厂G的各个方位。另外，上海市内及周边的供应商有分布在相同方位的（比如位于西北或者南部），因为分布在不同的大区或地区，所以也有明显的区分。可以考虑按此分类对大量的供应商进行分类。分类结果如表1-4所示：表1-4 地区描述分类结果表所属范围内的地区描述隶属大区、地区位于主机厂G方位上海市内及周边安亭及周边D1 ，S1西北宝山大场、顾村/嘉定北部、东部/青浦东北部D1， S1西奉贤东部/南汇D3 ，S8南嘉定西部、城区D2， S3西北金山干巷/奉贤西部/浦东川沙D3， S7南浦东康桥、金桥、张江/闵行南部/松江西南部/青浦西南部D3 ，S6东市中心区D3 ，S5松江/闵行北部/宝山D3 ，S4西南上海市以外城市昆山/太仓D4 ，O2江阴周庄、张家港D4 ，O6昆山花桥D4 ，O1苏州工业区D4 ，O4苏州市西D4 ，O5太仓西北D4 ，O3无锡D4 ，O7无锡西部、常州/靖江/湖州D4 ，O82.6按频次分类无论按大区或地区分类，都存在1,2,3,4,5,6六种不同频次的配送情况，如表1-5所示。结合实际，在整个物流取货系统中，某个供应商的零件需求数量可能大于或小于车辆的最大装载量，大于最大装载量的可以采取直送的方式，或者分成几批次运行，参与到Milk-run中。既能根据供应商的实际需求以及主机厂的需求确定路线，保证生产，同时也减少了运输总公里数，提高了车辆的装载率，将成本控制在一定范围内。可见，按此方式对供应商进行分类以设计循环取货的优化路径是很合理的。表1-5 各区频次分类结果表大区地区频次D1S11，2，3，4，5，6D2S2，S31，2，3，4，5，6D3S4，S5，S6，S7，S81，2，3，4，5，6D4O1，O2，O3，O81，2，3，4，5，6本方案将先选取一个大区的供应商按频次分类方式对供应商进行分类, 以设计循环取货的优化路径。三 循环取货路径和时间安排1.路径优化的假设根据安吉上海地区零部件供应商分析，我们选择按大区分类的D2大区进行车辆的路线设计，首先按频次分类方式对供应商进行分类,然后分别对D2大区中6个频次（1,2,3,4,5,6）的路线进行展开设计及优化。在实际运作过程中，循环取货的路径设计往往要考虑的因素很多，由于案例已给信息的局限性及数据收集的难度很大，在设计路径之前做出如下合理假设：v 主机厂。本方案中，所有循环取货的零部件都送到主机厂，且仅存在单一的主机厂，位置确定，零部件到达主机厂的时间没有限制。v 供应商。所有供应商的位置已知，供应商对于取货时间没有限制，原则上服从Milk-run规划所设定的取货时间窗。v 车辆。车辆数量足够多，所有车辆都必须从主机厂出发，并最终返回，且不允许超载，所有车辆的行驶速度认为相同。v 车辆的行驶平均速度为40km/h,在每一个供应商的料箱装货平均时间为30min,司机每天工作时间不得超过8h。v 考虑汽车零部件特点，一般满载情况下，零部件载重量不超过汽车载重限制。v 道路。所有的供应商之间、供应商与RDC 之间均存在可连通的道路。不考虑道路的实际交通情况，运输时间仅取决于运输距离和车辆行驶速度。车辆行驶时暂时不考虑特殊情况，如堵车、天气因素、交通管制等，应急方案将在后文详述。2. 路径优化的基本原则 安吉零部件在循环取货的运营过程中，本着安全性、可靠性和及时性的思想，为了实现安吉低成本运营、信息化共享，循环取货路径的设计及优化应强调以下几个原则：v 控制“成本”。通过对装载率、行使路线、应急措施等制定从源头上控制物流运作成本。3PL可通过提高车辆利用率来降低用车总数（循环次数每增加一倍，用车总数可以少一半）。因此，3PL应在充分分析生产线实际需求基础上，合理设计运输的容量、数量和频度。v 尽量“配载”。只有进行充分的配载，才使得循环取货模式具备成本控制的优势，涉及到运输工具的配载问题，具体原则将在后文配载原则中阐述。v 提高“频次”。高运输频次是降低零件库存的根本方法，同时也为配载提供充分的可行性。v 强调“准时”。循环取货模式下的运作是准时运行，准点到达，既是保障生产顺利进行的要求，也是精益物流管理的要求。v 充分“应急”。只有考虑充分且方案成熟的应急准备，才能最大程度在各种意外情况下保障生产的顺利进行。v 带动“空箱”。空箱的领取和交付业务贯穿循环取货运作的整个流程，对取货的平稳运行具有极其重要的意义。3. 制定循环取货路线3.1模型的建立旅行商问题（Traveling Salesman Problem,TSP）是一个经典的组合优化问题,问题描述为：一个商品推销员要去若干个城市推销商品，该推销员从一个城市出发，需要经过所有城市后，回到出发地。应如何选择行进路线，以使总的行程最短（或时间、费用等最少）。从图论的角度来看，该问题实质是在一个带权完全无向图 给定一个完全无向带权图G，其每一条边有一个非负的整数权值。目的是要找出G的一条经过每个顶点一次且仅经过一次的回路，使回路的总权值最小。中，找一个权值最小的Hamilton回路。循环取货模式与旅行商问题类似，因此，循环取货的路线设计问题可以转化为旅行商问题的求解，使总的行程最短，时间、费用最少。l 旅行商问题的数学模型为一个带权图，为顶点集，为边集。为顶点到顶点的距离，其中且，同时，则经典TSP（Classical TSP，CTSP）的数学模型为： （1-1） （1-2） （1-3） （1-4） （1-5）其中S为图S的顶点数。式（1-1）为CTSP的目标函数，求经过所有顶点的回路的最小距离式（1-2）至式（1-4）限定回路上每个顶点仅有一条入边和一条出边。式（1-5）限定在回路中不出现子回路。模型实质上是在一个带权图中求一条Hamilton回路。若对所有，不等式均成立，则称该问题是满足三角不等式的。由于该问题的可行解是所有顶点的全排列，随着顶点数的增加，会产生组合爆炸，它是一个NP完全问题。本方案采用Logware软件求解ROUTESEQ指令程序的ROUTESEQ旅行商问题，求解过程将在下文阐述。3.2. 初始路线求解及路线的优化 根据目前车辆路线安排存在的问题与不足，考虑供应商的出货地址和严格的窗口时间设置进行运输车辆的路径设计，确定一条Milk-run路线上的供应商以及整个网络中的Milk-run路线，以提高配送效率，满足客户需求。选取上海大众汽车一厂作为主机厂，利用谷歌地图确定各个供应商、主机厂的经纬度，再利用百度地图确定他们之间的相对位置，以及供应商两两之间的距离、各供应商与主机厂之间的距离。Logware求解时以(31N、121E)为原点，为方便点与点之间的区分和计算，对其经纬度扩大到原来的10倍，各供应商与主机厂之间的相对位置如图1-2所示：图1-2 各供应商与主机厂的相对位置分布图根据整理出的D2大区的资料，各频次的供应商的情况如表1-6所示：表1-6 各频次下对应的供应商表频次序号频次1频次2频次3频次4频次5频次61100021002310001100001024910118210032102241001910024108731016431059010225100371003410267410635102961008010129107455107751008610137610949101191014871105010169101878102021055191030210726101065310820111066510826121080910956131090714109301511012l 初始路线求解n 频次1的循环取货路线由附件12中D2大区的供应商资料可知，如表1-6所示，频次1、2、5、6的供应商数目小，运用Logware软件可以直接得到Milk-run路线图，图1-6，图1-7、图1-8为频次1的Milk-run路线图。（因篇幅所限，其他频次的循环取货初始路线图详见附件二）。图1-2 频次1各供应商数据输入图图1-3 Logware路径求解结果显示图(Total route distance不作参考)图1-4 频次1路线结果图根据公式：行驶时间=总行程/40（km/h）装卸时间=供应商个数*30/60总时间=行驶时间+装货时间因此，频次1、2、5、6的路线如表1-7所示：频次供应商数量/个Milk-run路线总行程/km行驶时间/h装货时间/h总时间/h频次14主机厂-10635-10002-10032-10590-主机厂87.62.1924.19频次27主机厂-10949-10296-10224-10775-10023-10225-11050-主机厂48.51.213.54.71频次52主机厂-10249-10873-主机厂38.10.9511.95频次64主机厂-10267-10118-10164-10745-主机厂822.0524.05表1-7 频次1、2、5、6路线表n 频次3的循环取货路线由表1-6可知，其供应商数量有十五个，为避免工作时间超过8小时，根据总行程最短，根据Logware软件求得的路线（如图1-5所示），将供应商分成两组，安排不同的车进行取货。图1-5 频次3路线结果图分组情况为：（11012,10653,10665,10169,10080,10086,10930,10302）（10037,10907,10001,10809,10202,10119,10019）整理得表1-8：表1-8 频次3路线表频次供应商数量/个Milk-run路线总行程/km行驶时间/h装货时间/h总时间/h频次38主机厂-11012-10653-10665-10169-10080-10086-10930-10302-主机厂88.32.2146.217主机厂-10037-10907-10001-10809-10202-10119-10019-主机厂110.62.773.56.27n 频次4的循环取货路线由表1-6可知，供应商数量也过多，为避免工作时间超过8小时，根据Logware软件求得的路线（如图1-6所示），将供应商分成两组，安排不同的车进行取货。图1-6 频次4路线结果图分组情况为：（10956,10187,10826,10000,10551,10129,10820,10148）（10726,10034,10137,10024）整理得表1-9：表1-9 频次4路线表频次供应商数量/个Milk-run路线总行程/km行驶时间/h装货时间/h总时间/h频次48主机厂-10956-10187-10826-10000-10551-10129-10820-10148-主机厂822.0546.054主机厂-10726-10034-10137-10024-主机厂781.9523.95l 路线优化以上为初步确定的循环取货路线，如频次5的取货路线，明显存在不合理处。路线内虽然只需为两个供应商取货，但其时间和车辆的装载率没有得到合理利用，容易造成浪费，因此需要对其进行路线优化，频次5的零部件取货由频次1和频次4共同完成，并用Logware软件求解，得出优化后的循环取货路线。综上，我们整理可得优化后的Milk-run线路表，见表1-10表1-10 优化后的Milk-run线路表频次供应商数量/个Milk-run路线总行程/km行驶时间/h装货时间/h总时间/h频次16主机厂-10635-10249-10002-10032-10873-10590-主机厂802.0835.08频次27主机厂-10949-10296-10224-10775-10023-10225-11050-主机厂48.51.273.54.77续表3-10频次38主机厂-11012-10653-10665-10169-10080-10086-10930-10302-主机厂88.32.2146.217主机厂-10037-10907-10001-10809-10202-10119-10019-主机厂110.62.773.56.27频次49主机厂-10956-10187-10826-10249-10000-10551-10873-10129-10820-主机厂68.21.714.56.215主机厂-10148-10726-10034-10137-10024-主机厂110.12.752.55.25频次64主机厂-10267-10118-10164-10745-主机厂822.0524.05如图1-7、图1-8所示，分别为频次1和频次2的循环取货路线图。 图1-7 频次1路线图 图1-8 频次2路线图3.3安排车辆运行时间 定线、定时的取货路线是循环取货的主要特征之一。设计好的路线作为路线的参照模板，在Milk-run中直接调用安排。行车时间设定应注意以下几个事项:v 车辆到达主机厂的时间分布控制要平衡车辆到厂的时间分布，尽量避免车辆在同一时间段内集中到达主机厂，以免给主机厂的收货工作带来很大的压力。v 频次间的间隔一般要求1.5小时及以上，并且要能够为DD-JIT送货预留访问点。原则上各供应商应服从主机厂安排的任何取货时间窗，并且一般不可变。实际也可能遇到特殊的交通及供应商特殊状况等因素，使原有路线在时间窗的约束下做出调整。 v 另外，考虑到取货的平顺化，对于某个供应商来讲，零部件也不可随意地拆分，而是按照路径的运作频次有效拆分。 由Logware软件求得的各频次的循环取货路线，我们绘制了从主机厂出发到各供应商取货再回到主机厂的行车时刻表，本文只列举出频次1的车辆运行时间，其余各频次可根据同样方法进行车辆安排。供应商编号 公司名称距离/km行驶时间窗口时间 第一循环到达时间出发时间从主机厂出发07:0010635上海华中冲压件制品厂 7.400:1200:3007:1207:4210249上海海华传感器有限公司 5.500:0900:3007:5108:2110002上海劳伦茨橡胶制品有限公司2.900:0500:3008:2608:5610032上海汽车股份有限公司-中国弹簧厂 14.200:2200:3009:1809:4810873上海日安电子有限公司15.700:2400:3010:1210:4210590上海索菲玛汽车滤清器有限公司 20.800:3200:3011:1411:44回到主机厂13.500:21-12:05 总计8002:0503:00参考文献1.叶雷.循环取料在上海通用汽车零部件入厂物流中的应用研究.D复旦大学管理学院,20052.张东.TSP问题的算法与应用的研究.D上海大学计算机应用技术，2007【Abstract】 Milk-run is a new mode of supply throughout the entire supply logistics.The article is mainly based on