第1章绪论

1.1 选题背景及研究意义

1.1.1 选题背景

随着商业模式的演变，物流成为企业的第三利润源，在企业竞争中占据着越来越重要的地位。企业调研发现，卷烟生产原料运输成本长期居高不下已成为烟草行业面临的普遍问题。以中部地区某烟草公司为例，该公司下属的8家卷烟厂分别位于省内不同的城市，由于没有原料中心仓库，所以该公司采取分散仓储的方式，即每家卷烟厂只存储某些特定种类的生产原料。另外，该公司生产的卷烟有10多种规格且每种规格的卷烟需要几十种生产原料，而每家卷烟厂生产的卷烟规格并不相同。因此，在这种分散式生产和分散式仓储的模式下，生产原料在不同卷烟厂之间频繁调拨就不可避免。在实际中，每家卷烟厂都会根据提前下达的生产计划和生产配方，结合当前原料库存信息，计算出完成生产任务需要调拨的原料种类和数量；为了快速响应生产计划，每家卷烟厂都提前自行制订具体的原料调拨方案以满足自身的生产需求。目前，该公司采用送货制的方式运输原料，即当卷烟厂1需求某种原料m时，由距离卷烟厂1最近且能供应原料m的卷烟厂2派车把原料m运送到卷烟厂1，然后空车返回。如果卷烟厂2不能单独满足卷烟厂1的需求，则剩下的需求由最近且能供应原料m 的卷烟厂3来满足，这样依次进行直到卷烟厂1的需求得到满足为止。

在此模式下，一方面，原料调拨决策权分散于各个卷烟厂，每家卷烟厂都站在自己的角度对单批次需求做局部最优的供需匹配决策，而没有站在公司的角度考虑整体最优的供需匹配，这是原料运输成本较高的主要原因。另一方面，针对单次调拨，每家卷烟厂也只站在自己的角度考虑局部最优路径决策，而没有站在公司的角度考虑整个运输网络的最优路径规划，使运输路径安排不合理，这也是原料运输成本较高的主要原因。此外，送货制导致车辆空车返回率较高，运输资源严重浪费，当多个卷烟厂有多种原料需求时，易出现车辆紧缺现象。该公司决策权分散，没有部门统一负责原料调拨任务，导致原料调拨效率较低且费用较高。为解决此问题，该公司希望成立一个物流管控部门（物流中心），通过制订集中模式下的原料联合调拨全局最优方案（考虑全局最优的供需匹配决策和车辆路径决策），提高运输资源利用率及原料调拨效率，进而降低原料运输成本。

零售行业中也普遍存在类似的问题，如服装连锁店一旦有新产品上市，为了有效满足客户多元化需求，增加销售机会，总公司会在各家连锁店投放一定数量的某些产品。经过一段时间的销售后，总公司发现有些连锁店的某种或某些类型的产品出现断货，而其他连锁店的该种或该类型的产品却仍有较高的库存量。在目前实际运营中，当客户去某家商店购买某种产品时，恰好该种产品出现断货现象，此商店通常采用就近调货的方式来尽快满足客户的需求。显然，这种调货模式没有考虑其他商店的产品需求情况，所做的供需匹配决策及路径决策同样只是局部最优。为快速响应客户需求，增加销售机会，降低调货成本，最好的选择应是在各商店出现断货之前，总公司从全局的角度对各商店的产品库存进行重新布局。

也有文献对类似问题进行了研究。首先，针对共享单车系统的自行车重新布局问题（Raviv et al.，2013；Chemla et al.，2013；Dell'Amico et al.，2014；Forma et al.，2015），系统中每个车站存放一定数量的自行车，客户根据自己的需求可以在任何站点取走自行车，使用结束后可以归还到任何站点。一段时间后，当前系统中有些车站的自行车数量不能满足客户的需求，而有些车站的自行车数量大于客户的需求。为使系统中自行车的利用率最大化，需要对系统中各个站点的自行车库存重新布局。其次，针对国际原油运输问题（Andersson et al.，2011；Hennig et al.，2012a，2012b；Agra et al.，2013，2014，2015；Siddiqui and Verma，2015），因石油是由多种不同规格的原油炼制而成的，所以每个炼油厂只生产一种或几种规格的原油。在炼制过程中，有些炼油厂需要其他炼油厂提供所需规格的原油，从而需要在各个炼油厂之间转运各种规格的原油来满足每个炼油厂的需求。

本书针对这些行业面临的现实问题进行提炼并加以研究，将为企业的实际运营提供重要的理论支撑和实践指导。

1.1.2 研究意义

1.1.2.1 理论意义

本书对供需未匹配取送货车辆路径问题进行了全面且深入的探究，从客户需求是否可任意拆分和满足两个角度出发，分别研究多次访问条件下的多商品供需未匹配取送货车辆路径问题、单次访问条件下的多商品供需未匹配取送货车辆路径问题，并针对以上问题分别构建模型、分析特性和设计算法，以达到优化的目的。

虽然当前文献中关于车辆路径问题的研究较多，但大多数研究都是“供需匹配关系事先已知”的情况，而关于供需匹配关系事先未知的取送货车辆路径问题的研究较少；在已有的研究供需匹配关系未知的文献中，大多是建立在客户需求一次性满足的条件下，关于供需匹配关系未知和需求可拆分的取送货车辆路径问题的研究则少之又少。尽管目前有少量文献考虑了“供需匹配关系事先未知”的情况来研究取送货车辆路径问题，但主要集中在海上运输系统。然而，在海上运输系统中的研究一般考虑多周期，库存约束、取送货时间窗约束、供应和需求信息均不确定，导致海上运输系统研究的取送货车辆路径问题与本书研究的问题差异较大。具体差异如下：①在海上运输系统中，在每个港口取货或投货时需考虑时间窗约束，而本书研究的问题不考虑取送货时间窗约束。②在海上运输系统中，在每个港口取货或投货时一般需考虑库存约束，而本书研究的问题不考虑库存约束。③在海上运输系统中，网络中每个客户点关于每种产品的供应总量和需求总量随生产变化，并不确定；而在本书研究的问题中，运输网络中每个客户点关于每种产品的供应信息和需求信息事先确定。以上差别导致海上运输系统的研究成果不能被直接应用到本书研究的问题中。因此，本书试图从客户需求是否可任意拆分和满足两个角度进行探究，建立数学模型，设计相应的求解算法，并进行数值测试。对供需未匹配的取送货车辆路径问题进行深入探究并对研究结果进行总结，预期研究成果在解决本书研究问题的同时，能对取送货车辆路径问题相关领域的现有理论进行有益扩展，从理论上为其他相关问题的研究提供借鉴。

1.1.2.2 现实意义

供需未匹配的取送货车辆路径问题来源于企业实际的物流需求。如中部地区某烟草公司有8家卷烟厂，分别位于省内不同城市。这种分散式生产导致物流决策权在一定程度上分散。原料采购回来后存储在各家卷烟厂，每家卷烟厂的原料供应均由厂内的物流部门负责。生产任务下达后，当某家卷烟厂需求某种原料时，经本厂原料部门负责人与其他卷烟厂的原料部门负责人沟通，由能够供应该种原料的卷烟厂派车把所需原料送到，然后空车返回。由于没有从整个公司的角度考虑全局最优的需求匹配决策和路径决策，空车返回率高，运输资源严重浪费，从而导致运输成本较高。除制造行业外，零售行业也存在同样的问题。如服饰、电器销售一段时间后，有些商店某类产品出现断货，有些商店却持有较高的该类商品库存。为增加销售机会，需要对各商店的产品库存重新布局，即在各商店之间调货。另外，在国际原油运输系统（Hennig et al.，2012a，2012b）和共享单车系统（Raviv et al.，2013）中也存在类似的问题。针对企业面临的实际问题构建量化的数学模型，通过设计精确算法来求解中小规模的问题，设计高效的启发式算法来求解大规模问题，有效降低物流成本、提高运输资源利用率和原料调拨效率，从而提高企业的核心竞争力。