基于旅行商问题的循环取货模式优化

基于旅行商问题的循环取货模式优化研究黄永强1志远团队2（赣南师范学院商学院，江西赣州341000）摘要：循环取货是一种新型的供货模式，贯穿于整个供应物流之中。文章主要立足于循环取货入厂物流，通过对循环取货的运作方式与特性进行分析，结合相关汽车物流企业的相关问题，提出相应的解决方案。在对供应商进行分类合理性分析之后，建立旅行商问题模型、运用软件设计循环取货初始路线，并结合企业相关情况，优化初始路线。本文旨在通过对汽车零部件循环取货方式进行定性和定量的综合分析,提出有效的优化方案,为汽车制造行业的入厂物流实践提供一些有意义的参考。关键词：循环取货入厂物流客户价值循环取货(MilkRun)，也称为“牛奶取货”“集货配送”“多仓储间巡回装卸货混载运送”“定时定点取货”,是国内最早是汽车制造业使用的一种物料集货模式。其具有小批量、多频次、定时性等特点。循环取货的应用使得物料JIT供应成为可能。有效降低运输过程中的运输成本、仓储成本等，保证了生产的连续性。本文是在安吉现以存在的汽车零部件入场物流循环取货模式的基础上，再度革新，针对运输过程中的运输成本高、装载率低和运输路径复杂及环境的动态性问题，进行循环取货的合理设计。一、汽车零部件入场物流循环取货模式现状分析本文中我们主要从国内安吉汽车物流有限公司3中零部件入厂物流为例，对其循环期货模式中出现的问题进行分析存在的问题主要有以下几个方面：1.运输成本高公司引入循环取货运作模式的目的在于对零部件供应商现有的运输网路加作者简介：1黄永强，男，赣南师范学院商学院讲师，研究方向：物流与供应链管理优化；2志远团队：赣南师范学院商学院10物流本科班学生：罗汉平，张运福，唐玲，熊思英，陈贻红。3安吉物流是国内最大的汽车物流服务供应商，是全球业务规模最大的汽车物流服务供应商。以优化，使之既能满足生产波动的需求，同时又能将运营成本控制在一定范围内。但目前在运用的过程中，物流运作成本仍然偏高，在总的物流费用成本中运输的成本达到了44%，如图1-1所示：图1-1物流费用构成图造成运输成本费用高的一个重要的原因是循环取货模式下的运输车辆的路径设计不合理。2.路径设计复杂运输车辆的路径安排要考虑各个供应商的出货地址、严格的出货窗口设置，需要确定一条Milk-run路径要遍历哪些供应商，针对整个供应商网络需要设计多少条Milk-run路径。当网络规模较小时较易解决，但对于目前192个供应商的网络，原有的运输路径就不能满足。由于供应商不是每天固定不变提供货物，主机厂的生产订单每天的需求也不同，因此，运输车辆的路径设计就变得比较困难。3.装载率低实际运作过程中，通常采用的是在每条Milk-run路径上安排无限的运输车辆来实现货物全部运输完的目标。考虑运输成本，往往是在有限运输车辆的前提下，实现Milk-run与运输车辆调度之间的协调，而安吉目前的装载率远没有达到85%的理想状态。4.生产计划和运输变动性大在零部件物流配送过程中，由于各种原因造成生产商的紧急加单、减单和并单等超过当天零部件正常需求量的25%时；或当天气、道路等出现异常情况时，就需要设计科学的应急运输方案，进行合理决策，以控制运营成本。二．零部件供应商分析物流费用比例表存货持有20%管理4%运输44%客户服务6%仓储26%存货持有管理客户服务仓储运输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，……，150KM—180KM155地区描述安亭及周边金山干巷/奉贤西部/浦东川沙奉贤东部/南汇……江阴周庄、张家港166频次1,2,3,4,5,662.分类合理性分析2.1按照供应商（供应商中文名，提货地点）分类安吉客户的主机厂G有近15,000种的零部件，其中国产零部件近万种，分布在江浙沪等10余个省市的170多家国产零部件供应商,而目前其供应商的范围仍然在扩大。针对安吉零部件目前的循环取货模式，该分类标准是将每个供应商作为单独的个体进行整合分析，而每一个体难以形成完整区域，数量难处理，且划分标准难以确立。因此，按照供应商分类是不合理的。2.2按照大区分类大区的分类是很明确的，即分为D1，D2，D3，D4四种。我们对每个大区进行筛选，发现这一分类和其他分类标准是有联系的，例如和“距离”之间的联系，如表1-2所示：表1-2大区和距离之间的联系表距离供应商数量大区代码距离供应商数量D110KM48D410KM－20KM430KM－50KM120KM－30KM5D210KM－20KM1830KM－50KM220KM－30KM2750KM－70KM5D320KM-30KM170KM-90KM430KM－50KM2290KM-120KM650KM－70KM32120KM-150KM870KM－90KM17150KM-180KM890KM6从表1-2中可以看出，虽然各大区有各距离分布，甚至大区之间的距离有交集，但供应商数量在各区还是有一个相对集中度，大区的分类是根据各个供应商和主机厂G之间的距离来划分的，较近的为D1，较远的为D4。这种分类可将相距近的点联系在一起，方便采用循环取货模式（不同大区之间交集的部分中，由于不同大区的点相距较远，不会产生路径计算影响，如D3和D4交集的70KM－90KM部分）。可知，此分类方式较合理。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地区描述分类结果表2.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本方案将先选取一个大区的供应商按频次分类方式对供应商进行分类,以设计循环取货的优化路径。三．循环取货路径和时间安排所属范围内的地区描述隶属大区、地区位于主机厂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，O8——1.路径优化的假设根据安吉上海地区零部件供应商分析，我们选择按大区分类的D2大区进行车辆的路线设计，首先按频次分类方式对供应商进行分类,然后分别对D2大区中6个频次（1,2,3,4,5,6）的路线进行展开设计及优化。在实际运作过程中，循环取货的路径设计往往要考虑的因素很多，由于案例已给信息的局限性及数据收集的难度很大，在设计路径之前做出如下合理假设：主机厂。本方案中，所有循环取货的零部件都送到主机厂，且仅存在单一的主机厂，位置确定，零部件到达主机厂的时间没有限制。供应商。所有供应商的位置已知，供应商对于取货时间没有限制，原则上服从Milk-run规划所设定的取货时间窗。车辆。车辆数量足够多，所有车辆都必须从主机厂出发，并最终返回，且不允许超载，所有车辆的行驶速度认为相同。车辆的行驶平均速度为40km/h,在每一个供应商的料箱装货平均时间为30min,司机每天工作时间不得超过8h。考虑汽车零部件特点，一般满载情况下，零部件载重量不超过汽车载重限制。道路。所有的供应商之间、供应商与RDC之间均存在可连通的道路。不考虑道路的实际交通情况，运输时间仅取决于运输距离和车辆行驶速度。车辆行驶时暂时不考虑特殊情况，如堵车、天气因素、交通管制等，应急方案将在后文详述。2.路径优化的基本原则安吉零部件在循环取货的运营过程中，本着安全性、可靠性和及时性的思想，为了实现安吉低成本运营、信息化共享，循环取货路径的设计及优化应强调以下几个原则：控制“成本”。通过对装载率、行使路线、应急措施等制定从源头上控制物流运作成本。3PL可通过提高车辆利用率来降低用车总数（循环次数每增加一倍，用车总数可以少一半）。因此，3PL应在充分分析生产线实际需求基础上，合理设计运输的容量、数量和频度。尽量“配载”。只有进行充分的配载，才使得循环取货模式具备成本控制的优势，涉及到运输工具的配载问题，具体原则将在后文配载原则中阐述。提高“频次”。高运输频次是降低零件库存的根本方法，同时也为配载提供充分的可行性。强调“准时”。循环取货模式下的运作是准时运行，准点到达，既是保障生产顺利进行的要求，也是精益物流管理的要求。充分“应急”。只有考虑充分且方案成熟的应急准备，才能最大程度在各种意外情况下保障生产的顺利进行。带动“空箱”。空箱的领取和交付业务贯穿循环取货运作的整个流程，对取货的平稳运行具有极其重要的意义。3.制定循环取货路线3.1模型的建立旅行商问题（TravelingSalesmanProblem,TSP）是一个经典的组合优化问题,问题描述为：一个商品推销员要去若干个城市推销商品，该推销员从一个城市出发，需要经过所有城市后，回到出发地。应如何选择行进路线，以使总的行程最短（或时间、费用等最少）。从图论的角度来看，该问题实质是在一个带权完全无向图4中，找一个权值最小的Hamilton回路。循环取货模式与旅行商问题类似，因此，循环取货的路线设计问题可以转化为旅行商问题的求解，使总的行程最短，时间、费用最少。旅行商问题的数学模型）EVG,(为一个带权图，nV,,2,1为顶点集，),(jieEij│jiVji,,为边集。),,(jiVjidij为顶点i到顶点j的距离，其中0ijd且ijd，同