在生产与运输协同调度问题中，当订单的生产完成时间给定，仅需决策每辆车装载哪些订单以及每辆车的行驶路径。以国内某电商企业为例，其客户通过网络平台下单，每当订单达到30个规模时，系统将该30个订单的信息一起发送到仓库。仓库接到订单信息后，开始拣选商品，当所有商品拣选完毕，仓库再根据每个订单的需求将不同的商品进行打包，然后运输到相应的客户。在仓库接到订单信息后，一系列有限数目的车辆在仓库待命，等待运输打包完毕的订单。目前订单装载采取“先生产先运输”的原则，即先完成打包的订单先装载到可得车辆，第一辆车装载完毕再开启第二辆车的装载。每辆车的运输路径采取“先近后远”的原则，即从工厂出发先服务距离最近的客户，再服务与该客户最近的客户。显然，企业在现阶段对订单装载与车辆路径是分开决策的。为了提高客户服务水平并节约成本，企业希望对订单装载与车辆路径协同考虑。比如将较近的客户的订单集合在一起运输，同时权衡订单的打包完成时间，若等待订单集合的时间过长，也不利于整体的运输活动。另外，在该企业的运营过程中，每个订单的生产（拣选与打包）活动完成时间根据大数据等技术是可以预测得到的，即对于运输阶段而言，订单的生产完成时间是已知的。

本章研究的问题为给定订单加工完成时间的车辆路径问题，可将其看作为一种具有订单可得时间的车辆路径问题。在该问题中，订单的生产（拣选与打包）活动的完成时间是已知的（即订单可得时间已知），在将各个订单装载到各个车辆时，需要将车辆行驶路径与订单的完成时间结合起来考虑。在整个生产与运输活动的周期开始，每辆车需等待各自运输的订单全部生产（拣选打包）并装载完毕，才可以从仓库出发。显然，每辆车的出发时间等于其装载的最晚的订单的生产完成时间，这里将该时间定义为车辆等待时间。车辆出发后，在其服务的所有客户间的行驶时间称为车辆行驶时间。每条路径的完成时间为每辆车的完成时间，其等于车辆等待时间与车辆行驶时间之和。目前为止，仅有Archetti et al.（2015）研究了具有车辆等待时间的车辆路径问题，其假设所有产品在运输初期并不可得，需要车辆在仓库等待一段时间。该研究目标为最小化完工时间，即最小化最后一个订单交付到客户的时间。该文章考虑了客户点的分布呈两种特殊结构（星形结构、线形结构）的图论问题，并采用多项式精确算法来解决不同结构下的问题。本问题考虑了客户点的随机分布结构，以最小化所有路径完成时间之和为优化目标，其等于所有的车辆等待时间与车辆行驶时间之和。以所有路径完成时间之和为优化目标的车辆运输问题的相关文献有：Malandraki和Daskin，1992；Hong和Park，1999；Balseiro et al.，2011；Gong et al.，2012；Dabia et al.，2013；Avella et al.，2013；Zachariadis et al.，2013；Ehmke et al.，2015。

针对给定订单生产完成时间的生产与运输协同调度问题，本章首先建立数学模型；然后提出一种禁忌搜索算法求得原问题的可行方案；接着提出拉格朗日松弛方法与另外一种基于有容积限制的车辆路径问题的最优解的方法分别求解原问题的下界；最后通过多种规模算例分析以上算法效果。 xKpbLduT6JTeOgGHa/29JY09FhDVCS++/gw09iAC7MdEcb9os2/+KgJLTk8vZhHy