下载掌阅APP，畅读海量书库
立即打开
随着商业模式的演变，物流成本成为企业第三利润源，在企业竞争中占据着越来越重要的地位。通过企业调研，了解到中部地区某烟草公司卷烟生产原料的运输成本长期居高不下。该公司有几个烟厂分别位于省内不同的城市，由于没有原料中心仓库，所以每个烟厂都存贮某些种类的生产原料（如烟叶等）。为快速响应生产，一旦接到公司下达的生产计划（以旬为周期），每个烟厂自行制订原料调运方案来避免因缺货而影响生产。该公司目前采用以下方式调运原料：当烟厂1需求某种原料 m 时，先把送货请求发送给距离它最近且能供应原料 m 的烟厂（如烟厂2）。一旦接到送货请求，烟厂2就派车把原料 m 运送到烟厂1，然后空车返回。如果烟厂2不能单独满足烟厂1的需求，剩下的需求依次由其他距离烟厂1最近且能供应原料 m 的烟厂来满足，直到烟厂1的需求得到充分满足为止。
在目前的调运模式下，原料调运决策权分散于各个烟厂。当某个烟厂有原料需求时，该烟厂只是站在自己的角度，对单批次需求做局部最优供需匹配决策和车辆路径决策，而没有站在整个公司的角度考虑全局最优供需匹配决策和车辆路径决策，这便造成年度的调运费用较高（每年的调拨次数可达上千次）。另外，车辆执行运输任务后空车返回率较高，运输资源浪费严重。因此，该烟草公司希望通过建立一个物流管控部门（物流中心），从整个公司的角度来优化原料调运问题（即做全局供需匹配决策和车辆路径决策），进而降低原料运输成本、提高运输资源利用率。
零售行业也存在类似问题。例如在日常生活中可以经常观察到，当一个顾客去商店购买一种商品时，恰好此商品已售完。在此情况下，为了增加销售机会，该商店通常从其他最近的商店调货来尽快满足客户的需求。明显地，在此调货模式下，各商店满足自己单批次需求所做的供需匹配决策和车辆路径决策也均是局部最优，没有考虑其他商店的商品需求情况。为了增加消费机会且减少调运成本，最好的办法是在商店出现断货之前，总店从全局的角度对各商店中的商品库存重新布局。类似的问题也存在于国际原油运输系统（Andersson et al.，2011；Hennig et al.，2012a，2012b；Agra et al.，2013，2014，2015；Siddiqui and Verma，2015）和共享单车系统（Raviv et al.，2013；Chemla et al.，2013；Dell'Amico et al.，2014；Forma et al.，2015）中。
文献中关于车辆路径的研究通常考虑“单次访问”（即单车最多访问一个客户点一次），目前烟草行业中的生产原料调运模式也属于单次访问的情况。从直观上看，允许“多次访问”（即单车多次访问一个客户点）使得问题的优化空间更大，将带来更多的经济效益。如图3-1所示，假设网络中有3个工厂、4种生产原料且车辆的最大装载量为3个单位。每个工厂的供应信息和需求信息如“供应、需求”所示，其中括号中的数值表示生产原料的供应/需求量。所有车辆必须从车场出发，执行运输任务后返回到车场且每辆车最多被使用一次。在单次访问模式下[见图3-1（a）]，需要两辆车来满足所有工厂的需求，路线分别是车场→工厂1→工厂2→工厂3→车场（实线部分）和车场→工厂3→工厂1→工厂2→车场（虚线部分）。车辆从一个工厂到另一个工厂的装载信息呈现在两个工厂之间的连线上。然而，在多次访问模式下[见图3-1（b）]，以上两条路线可以合并，即只需一辆车就能完成运输任务且相应的路线为车场→工厂1→工厂2→工厂3→工厂1→工厂2→车场。与单次访问的调运模式相比，单车访问了工厂1和工厂2两次。显然多次访问模式下的调运方案比单次访问模式下的运输方案需要更少的运输车辆和运输成本。因此，多次访问模式下的调运方案更优。
图3-1 单次访问模式下的方案和多次访问模式下的方案
另外，可以通过优化供需匹配决策来进一步优化以上问题。与网络中供需匹配关系事先已知的情况相比，供需匹配关系未知的情况松弛了已固定的供需匹配关系，进而可以通过做出更好的供需匹配决策来减少所需的车辆数和降低运输成本。针对供需匹配关系未知的情况，网络中每个需求点的需求应由哪些供应点来供应以及供应的数量事先未知。显然针对本书所提出的优化问题，供需匹配和车辆路径都需做出决策。更重要的是，这两个决策相互影响，即给定一个路径决策相对应的最优供需匹配决策唯一；反之亦然。在烟草制造行业中，生产计划提前十天下达，这给每个工厂足够时间以调拨原料来满足生产需求。因此，该运输网络不需要考虑取送货时间窗约束。
针对多个行业面临的现实挑战，本章基于无时间窗约束和多商品的运输网络，从优化运输成本的角度，研究了一个允许多次访问的供需匹配与取送货车辆路径问题。通过查阅相关文献可知，该问题高度复杂且在当前文献中没有被研究过。因此，当前的首要任务是探索该问题的线性规划模型及其特性。