车辆路径规划中的Milk Run问题简介
写在前面
大家好啊，许久不见，新的一年小编在这里向大家拜个年，祝各位新年快乐，身体健康，心想事成。最近由于新冠肺炎，我们正在经历一段较为困难的日子，希望我们可以一起众志成城，共度难关。
相信最近大家为了尽可能减少外出都已经在家数日了，不知道大家游戏玩腻了没有，视频看腻了没有，如果腻了不如来搞学习看我们给大家带来的东西换换口味。本文没有复杂的算法，也没有令人头秃的代码，请放心食用。本文首先介绍什么是Milk Run，然后通过一些案例中的应用来说明这一模式在物流领域中的运用。“数据魔术师”的教授团队在Milk Run问题上有着深厚的技术积累，可以帮助企业优化车辆的调度，降低物流成本。
什么是Milk Run?
首先说一下这个英文单词的来源：送奶工每天需要给订了牛奶的用户送奶，同时拿走空瓶，Milk Run由此得名。这个相信一部分读者应该是使用过这样的服务的，小时候看的猫和老鼠里面也有这样的镜头。当然，这里并不是指送牛奶这一过程，而是指与这个过程有一些相似之处的物流配送方式，即高频次、小批量、定时性。
现在我们一般称这种配送方式为循环取货，即卡车按照既定的路线和时间依次到不同的供应商处收取货物，卸下上一次收走货物的空容器，并最终将所有货物送到整车生产商仓库或生产线的一种公路运输方式。一些企业的供应链会有这样的配送需求，例如汽车制造业和零售业。
国内外的汽车制造企业较早开始使用这种物料集货模式，这种模式不是由物料供应商自己将配件送到客户工厂那里，而是外包给第三方物流公司，第三方物流公司根据客户工厂的物料需求计划，规划最优的车辆路径和排班到供应商处取货再集中送到客户工厂。在未使用这种模式以前，通常是由供应商自行配送至生产厂房或者配送到仓储中心再进行进一步的配送。这两者有什么区别呢？下面看两个简单的图示就明白了
Milk Run这种模式能够很好地实现JIT(Just In Time, 准时制生产方式)供给，值得一提的是JIT最早同样运用于汽车制造业，其基本思想是“只在需要的时候，按需要的量，生产所需的产品”，是一种追求无库存或者库存达到最小的生产系统，需要做好生产的计划和控制以及库存的管理。JIT是许多其他汽车制造商采用的一种降低生产成本的方法，并取得了不同程度的成功。在一个简单的JIT系统中，采购计划的流程大致如下：
首先完成下一阶段生产计划对应的生产量的计算；然后对所需的零件的种类和数量进行分类，并找到能够提供这些零件的供应商。然后根据供应商的位置和对应物料的取货量的信息进行主路径规划，并与供应商进行协商，根据协商结果对路径进行调整，最后安排接收物料的场站排班，在日常的计划中也会根据实际情况对路径规划作一些调整。
运用JIT需要计划和调度生产的每个重要部分都有效和高效地完成。供应采购是生产系统中最重要的部分之一，必须根据生产线的需要进行计划和调度，同时对于物流而言相应的排班和路径规划也非常重要，合理的规划能够节省许多成本。
相关实践案例
上海大众与上海通用汽车公司都曾经有过相关的实践。上海大众于2003年与安吉天地达成相关合作，针对上海大众的多数供应商仍自行负责外部运输的状况，安吉天地将所有供应厂家进行集成，按照地理位置、供货频率和体积进行综合规划，采取了循环取货等优化的运输方式，大幅减少了车辆数及驾驶员数，减少工厂收货区卸货车辆，从而降低了总成本；
上海通用汽车有限公司成立于1997年6月l2日，是由上海汽车工业集团总公司与美国通用汽车公司双方合资组建，总投资15.2亿美元。在一段时期中，国内零部件供应商的供货方式主要还是依靠供应商自己供货，其供应方式大致如下：
- 一些大件供应商实施了“门对门”的直接供货，即供应商直接将零件排序送到上海通用装配车间门口，如座椅等。
- 一些供应商把零件送到上海通用附近的仓库，进行存储、排序，再送到上海通用，如车门外饰板等。
- 绝大多数供应商先把零件送到上海通用的第三方物流零件再包装中心，再配送到上海通用
但是上述方式有一些缺点例如：
- 随着国内供应商绝对数量的增加，零件配送中心以及上海通用的接收更复杂，更繁忙。
- 有些生产小零件的供应商在运输成本的压力下，会一次生产产量大、输送运输成本最低、容积率最高的零件，其结果要么是库存高、要么是运输成本高。
- 许多供应商把零件的运输外包委托给社会运输单位；而这些运输单位由于在管理技术、服务方面有种种差距，不得不在价格方面恶性竞价，其结果是车况差、安全运输差、及时性差，造成安全隐患层出不穷。
而循环取货是闭环拉动式取货，它把原先的供应商送货这一推动方式转换变为上海通用委托的物流运输者取货的拉动方式，相较于上述的方式，有以下优点：
- 有利于标准化作业，同一种零件、同一条路线、同一时间可以按小时计取货
- 有利于运输效率及容积率的提高，在相同产量下，运输总里程将大大下降，容积率可以事先计划和在实施中尽量提高从而运输成本将大大下降。
- 循环取货有利于JIT模式的执行，使取货、到货窗口时间计划更合理，零件库存更少、更合理。
- 循环取货是由整车厂委托专业物流运输承包商进行运作，运输车辆的状态、司机的素质和专业要求以及培训等因素得到保证，从而使安全供货得到保证。
上海通用通过此模式，零部件运输成本每年可以节约300万元人民币，下降了30%以上。
在2005年，国内物流公司海格物流在国内将Milk Run运用于国际采购物流，为国际零售商沃尔玛设计并运行此模式，帮沃尔玛做订单管理，优化仓库作业环节，节约物流成本，海格物流一个集装箱可以帮客户省1000美元。2006年的时候，海格物流凭借Milk Run模式获得了“深圳市首届物流创新奖”。 Milk Run在国外也有比较成功的应用案例，日本丰田公司在泰国建厂的时候就应用了这样的模式搭配JIT，通过循环取货来沟通泰国丰田装配厂、零部件供应商和第三方物流，为了使得这个系统有效且高效，丰田汽车公司在实践过程中提出了三个概念来应对实践过程中的问题。
第一个概念是能够应对需求波动的“柔性物流”。在建立了混合量产体系之后，需要通过JIT运输来维持。有一个安全的物流系统也是必要的(针对运输损坏，错误的项目交付和缺货)，物流系统不仅要重视速度，也要重视运输质量。
第二个概念是具有竞争优势的物流，竞争优势来源于“最短的交货时间(lead time, LT)和更低的成本”。包括通过推进零部件供应商的本地化和重新规划循环取货的运行区域来降低物流成本。在对生产和采购问题进行重新评估后，将寻求缩短交货时间和降低分销成本的策略。
第三个概念是“对环境影响最小”的物流。环境问题是全球性的问题。在物流领域，最终目标是减少运输活动产生的二氧化碳排放，减少包装和包装材料的使用量。
小结
综合上述的案例，我们可以看到Milk Run这种模式下可以由签定合同的物流公司根据客户工厂的物料需求计划，按最优的集货运输方案到供应商处取货，再集中送到客户工厂，这样可以提高车辆装载率，使返回空车的数量和行驶距离大大减少，能有效降低供应商送货成本，提高物料供应的敏捷性和柔韧性。此外这样的系统还可以减少二氧化碳的排放，更大限度地达到环境要求。
参考
Nemoto, T., Hayashi, K., & Hashimoto, M. (2010). Milk-run logistics by Japanese automobile manufacturers in Thailand. Procedia - Social and Behavioral Sciences, 2(3), 5980-5989.
Brar, G. S., & Saini, G. (2011). Milk Run Logistics: Literature Review and Directions. 5.
--The End---
文案 && 编辑：庄浩城
审稿人：秦时明岳（华中科技大学管理学院）
指导老师：秦时明岳（华中科技大学管理学院） 还有更多算法学习课件分享哟