下载掌阅APP，畅读海量书库
立即打开
Geismar et al.（2008）、Cakici et al.（2012）、Ullrich（2013）与Low et al.（2013）针对有交付时间约束的生产与运输协同调度问题，分别提出了改进的遗传算法。Geismar et al.（2008）在编码时采取了客户点的全排列形式，中间没有路径断点；解码染色体时，根据点的排列顺序和车辆的容积限制，截取每个可能的子路径，再采取一种最短路径法寻找最优路径。Cakici et al.（2012）预先规定了只有同一个客户的订单才可以在一条路径中运输；编码时对每一个订单随机安排一个路径，不同客户的订单不允许安排到同一路径中；交叉操作时亦需要遵守此原则。Ullrich（2013）对机器生产序列与车辆路径同时进行编码，不需要对染色体进行编码；机器编码与路径编码同时接受遗传操作；并随机选择交叉，变异或复制等遗传策略中的任意一种来生成新的个体。Low et al.（2013）研究了一个配送中心在时间窗范围内向多个零售商配送产品的问题，提出了传统的遗传算法与改进的遗传算法；改进的遗传算法根据种群的适应值动态地变化交叉率与变异率，以此来加强种群的集中与分散机制；染色体解码时先根据零售商序列生成一系列子路径，再挑选最优组合生成最短路径。Van et al.（1999）针对车辆可以重复使用的生产运输问题，基于解的矢量表示法，分别应用了邻域解算法、模拟退火算法及禁忌算法。Chang和Lee（2004）、Li et al.（2011）分别针对单车辆运输问题提出了具有最坏分析的启发式算法。Schmid et al.（2009，2011）针对水泥配送问题，分别提出了一种变邻域搜索算法及一种基于精确算法与变邻域算法的混合算法。Farahani et al.（2012）针对易腐产品的生产运输问题提出了一种大邻域算法。Jha和Shanker（2013）针对不同质车辆的生产运输问题提出了一种二阶段迭代算法，第一阶段采用基于拉格朗日乘子的算法解决生产存储问题，第二阶段采用节约法解决车辆路径问题。Condotta et al.（2013）针对单客户分批次运输问题也采用了一种二阶段算法，先使用禁忌搜索算法得到生产问题的解，再将得到的解作为输入应用于运输问题。Lee et al.（2014）提出了大邻域算法，首先采取构造算法生成订单生产问题的解，再采用构造算法生成运输问题的解，然后根据多种邻域结构生成邻域解，最后取最优的解。
Chen et al.（1996）综述了机器调度问题，详细研究了该类问题的复杂度、启发式算法及多项式近似算法。重点介绍了基于邻域搜索的算法以及遗传算法，基于邻域搜索的算法包括多初始解法、模拟退火算法、禁忌搜索算法等。对于单机调度问题，针对各种不同的目标函数及约束，目前也有许多启发式算法的研究。例如，Valente et al.（2001）提出一种遗传算法，目标是最小化工件提前完成时间与延迟时间之和。Kirlik和Oguz（2012）应用了一种变邻域算法，最小化总的订单完成延迟时间。Xu et al.（2014）研究了目标为最小化总的延迟时间的问题，提出一种基于种群的进化算法，提出了三种交叉策略及两种种群更新机制。Khowala et al.（2014）提出了一种基于SPT-EDD的前向算法等。
车辆路径问题作为经典的NP难问题，各种启发式算法已经被众多学者研究得十分成熟。简单的构造算法最先被应用到车辆路径问题中，例如Clarke和Wright（1964）提出了节约算法；Yellow（1970）在此基础上加入了参数，形成了新的节约算法；Solomon（1987）在此二者基础上又加入了不同的参数；Gillett和Miller（1974）提出了扫描算法。各种复杂的启发式算法也慢慢发展起来，例如Holland（1975）最先提出了遗传算法，该算法在各个领域得到了广泛的应用；Prins（2004）针对遗传算法的编码和解码提出了非常经典的splitting算法，将所有访问点加入一条巨大的路径中，再根据车辆容积及路径长度约束生成一系列所有可行的子路径，最后解决最短路径问题的算法，得到最优路径；Vidal et al.（2014）提出了标准的综合考虑各种因素的遗传算法框架，包括染色体的表现形式，目标值的衡量方式，交叉及变异的操作方法等；还有嵌入局部搜索的遗传算法（Moscato and Cotta，2010）、基于路径重新连接法与分散搜索的算法（Glover，1977；Ho and Gendreau，2006；Resende et al.，2010）、蚁群算法（Dorigo and Stützle，2004）、粒子群算法（Poli et al.，2007）、蜂群算法（Marinakis and Marinaki，2010）。Kirkpatrick（1983）将模拟退火算法引入到组合优化问题，以一定的概率接受差解，以此跳出局部最优。Glover（1986）提出了禁忌算法；Kilby et al.（1999）针对有容积的车辆路径问题提出了有导向的禁忌算法，通过惩罚解的一部分构成因素来促使解朝着最优的方向移动；Cordeau（2001）针对有时间窗约束的车辆路径问题，提出了具有标准框架的禁忌算法；Toth和Vigo（2003）研究了禁忌搜索的一个新形式，称为“颗粒禁忌搜索算法（Granular Tabu Search，GTS）”，该算法提出了严格控制的邻域结构，禁止产生不能带来好的解的移动方式，从而减少了邻域解的个数，减少了计算时间。Mladenovic和Hansen（1997）详细介绍了变邻域搜索算法；Kytöjoki et al.（2007）将干扰机制与记忆模式引入到该方法中；Pisinger和Ropke（2007）在Mladenovic和Hansen（1997）的基础上介绍了自适应大邻域搜索算法，引入了毁灭—创造机制。
随着各种启发式算法的发展，一系列混合算法被提出并应用到车辆路径问题中。例如，启发式算法结合CPLEX求解算法，Alvarenga et al.（2007）首先采用遗传算法生成一系列解，将每次迭代生成的最优解都加入一个集合中，迭代结束后建立整数规划模型，采用分支切割法（Branch and Cut）从此集合中挑选路径组合成为最好的解；Subrananian et al.（2013）采用迭代的局部搜索算法结合变邻域算法产生一系列路径，再建立整数模型用CPLEX求解。还有一类是启发式与启发式的混合算法，例如模拟退火算法与遗传算法结合（Osman，1993）、随机贪婪算法与迭代的局部算法结合（Prins，2009）、变邻域算法与迭代的局部算法结合（Chen et al.，2010）、禁忌算法与迭代的布局算法结合（Cordeau and Maischberger，2012）、遗传算法和禁忌算法结合（Perboli et al.，2008）、路径重组与粒子群算法结合（Marinakis et al.，2010）。
在采用精确算法解决生产与车辆运输协同调度问题时，因车辆运输路径为NP难题，现有文献往往简化了车辆路径。Zhong et al.（2007）、Huo et al.（2010）、Fu et al.（2012）、Wang和Liu（2013）分别根据各生产运输问题的特性提出了各种多项式近似算法。Armstrong et al.（2008）、Mazdeh et al.（2011）、Rasti-Barzoki et al.（2013）与Viergutz和Knust（2014）则采取了分支定界法来解决单机器生产与单客户或多客户运输的协同问题。Li和Yuan（2009）、Steiner和Zhang（2009）针对分组的订单生产与运输问题应用了动态规划算法，只能同一个组的订单在一起运输。Li和Yuan（2009）考虑了订单分批次生产，单台机器存在批次生产准备时间，一辆车来回运输，目标是最小化这辆车运送完最后一批订单回到工厂的时间，证明了该问题为NP难题，且给出了动态规划算法。而Steiner和Zhang（2009）则考虑订单有交付截止时间，目标是最小化订单的迟到成本与交付成本之和，且订单采取直运模式，假定所有批次一旦生成完毕，立即运输。文章首先采取动态规划算法解决了一个特例问题，进而对原问题提出了一个多项式时间的近似方案。Yan et al.（2011）、Kopanos et al.（2012）则研究了易腐产品的生产与运输的协同问题，通过建立数学模型求解，用具体案例来验证提出的模型的正确性。Yan et al.（2011）通过建立购买方与供应方的库存模型，来确定最优的生产批次及数量。Kopanos et al.（2012）则分别建立了单生产单元与多生产单元的生产与配送模型，分别用两个实例来验证模型，确定具体的生产计划与运输计划。Chang et al.（2013）采用了列生成算法，解决了小规模算例的生产与运输的协同问题。
单独的车辆路径问题也在学术界得到了广泛的研究，Laporte（1992）对各种精确算法进行了综述。其将现有的精确算法分为三大类：直接的树搜索算法，包括指派问题的下界及相关的分支定界算法（Laporte et al.，1986；Laporte et al.，1992）、K-degree Center Tree算法（Christofides et al.，1981）；动态规划算法（Eilon et al.，1971）；整数线性规划算法，包括分割与列生成算法（Balinski and Quandt，1964；Desrochers et al.，1990）、Three-index车辆流模型（Fisher and Jaikumar，1978；Fisher and Jaikumar，1981；Desrochers et al.，1992）、Two-index车辆流模型（Laporte et al.，1985）。