供需未匹配取送货车辆路径问题研究最新章节_徐东洋著

1.5 本书特色与创新

创新点1：从不同角度建立并比较了多次访问条件下的供需未匹配多商品取送货车辆路径问题的线性规划模型，提出了采用有效不等式来提高模型的性能，验证了所提出的模型及不等式的有效性。

在当前文献中，多批次取送货车辆路径问题的研究集中于单商品、供需匹配关系事先已知的情况（Dror et al.，1994；Archetti et al.，2008；Archetti and Speranza，2012；Wilck IV and Cavalier，2012a，2012b；Archetti et al.，2014；Silva et al.，2015）；供需匹配关系事先未知的取送货车辆路径问题的研究集中于单车、单商品、单次访问的情况（Hernández-Pérez and Salazar-Gonzalez，2004a，2004b，2007；Hernández-Pérez et al.，2009；Zhao et al.，2009；Mladenović et al.，2012；Ho and Szeto，2014）；允许多次访问的取送货车辆路径问题的研究集中于取送货时间窗约束、库存约束的情况（Christiansen and Nygreen，1998a，1998b；Christiansen，1999；Al-Khayyal and Hwang，2007；Engineer et al.，2012；Agra et al.，2015）。基于企业的实际需求，本书研究了多车、多商品、需求可拆分、允许多次访问、供需匹配关系事先未知的取送货车辆路径问题。这也是首次同时考虑以上5个条件来研究取送货车辆路径问题。针对本书研究的问题，首先，根据相关文献的建模方法建立了一个混合整数规划模型；其次，基于分析问题特性和消除决策变量之间的耦合关系，提出了一个简化数学模型；最后，为进一步简便模型的性能，提出了一系列多项式型有效不等式。通过数值实验验证了简便的模型更容易求解，且提出的模型及不等式对所研究的问题具有有效性。

创新点2：针对多次访问条件下的供需未匹配多商品取送货车辆路径问题，设计了高效的禁忌搜索算法，借助优化软件CPLEX设计了问题下界求解方法，验证了本书提出算法的良好表现及明显优势。

为快速获得符合当前企业需求的运输方案，在分析单元化模型特性的基础上，首先提出一个贪婪式算法来快速构建初始可行解，然后基于优化供需匹配决策和车辆路径决策的思想，提出7个新颖的邻域结构，并设计了高效的禁忌搜索算法来改善初始解质量。为测试算法的性能，先用本书提出的算法测试对应所研究问题随机生成的算例，并将测试结果与基于CPLEX获得的下界做比较，然后使用提出的算法改进去求解相关文献中的算例，并将求解结果与文献中的结果做比较。实验结果表明提出的启发式算法在较短时间内对所研究问题和文献中的相关问题都能够提供最优解或近似最优解，且在求解质量、求解时间和稳定性方面都远远优于相关文献的算法。

创新点3：针对多次访问条件下的供需未匹配多商品取送货车辆路径问题，设计了精确求解算法，验证本书提出的算法的良好表现及明显优势。

从供需匹配关系事先未知的取送货车辆路径问题的研究领域来看，由于本书研究了多车、多产品和多次访问的情况，导致本书所研究的问题高度复杂。针对供需匹配关系事先未知的取送货车辆路径问题，即使只考虑以上3个条件中任意1个条件，问题也将变得非常复杂，因此文献中针对此类问题的精确算法的研究极少（Hernández-Pérez and Salazar-Gonzalez，2004a，2007，2014；Salazar-Gonzalez and Santos-Hernández，2015）。为了精确求解现实中中小规模的问题且丰富相关领域精确算法的研究成果，本书基于单元化模型设计了一个分支切割算法来求解所研究的问题，即精确求解的同时考虑以上3个条件的供需匹配关系事先未知的取送货车辆路径问题。针对此精确算法，除了提出多项式型有效不等式外，还提出了6类指数型有效不等式，并对每类指数型有效不等式设计了相应的分离算法；讨论了初始上界嵌入方法、预处理过程、分支策略、分离算法调用策略。实验结果表明，该算法能够求解问题的规模为9个客户点和5种产品的算例，这些算例的规模均大于相关文献的求解规模。

创新点4：从不同角度建立并比较了单次访问条件下的供需未匹配多商品取送货车辆路径问题的线性规划模型，提出了采用有效不等式来提高模型的性能，验证了所提出的模型及不等式的有效性。

在当前文献中，取送货车辆路径问题的研究集中于单商品、供需匹配关系事先已知的情况（Dror et al.，1994；Archetti et al.，2008；Archetti and Speranza，2012；Wilck IV and Cavalier，2012a，2012b；Archetti et al.，2014；Silva et al.，2015）；供需匹配关系事先未知的取送货车辆路径问题的研究集中于单车、单商品的情况（Hernández-Pérez and Salazar-Gonzalez，2004a，2004b，2007；Hernández-Pérez et al.，2009；Zhao et al.，2009；Mladenović et al.，2012；Ho and Szeto，2014）；基于企业的实际需求，本书研究了多车、多商品、需求可拆分、供需匹配关系事先未知的取送货车辆问题。这也是首次同时考虑以上4个条件来研究取送货车辆路径问题。针对本书研究的问题，首先，根据相关文献的建模方法建立了混合整数规划模型；其次，基于分析问题特性提出了一个简化数学模型；最后，为进一步验证简便模型的性能，提出了一系列多项式型有效不等式。通过数值实验验证了简便模型更容易求解，且提出的模型及不等式对所研究的问题具有有效性。

创新点5：针对单次访问条件下的供需未匹配多商品取送货车辆路径问题，设计了改进的变邻域搜索算法，借助优化软件CPLEX设计了问题下界求解方法，验证了本书提出算法的良好表现及明显优势。

为快速获得符合当前企业需求的运输方案，在分析模型特性的基础上，首先构建一个基于运输效率提升的贪婪式算法来快速构建初始可行解，然后基于优化供需匹配决策和车辆路径决策的思想，整合并改进了Chen等（2014）提出的邻域结构，并设计了高效的变邻域搜索算法来改善初始解质量。为测试算法的性能，用提出的算法测试对应研究问题的随机生成算例，并将测试结果与基于CPLEX获得的下界和文献中已有的相关算法进行比较。实验结果表明提出的启发式算法能在较短时间内对所研究问题提供最优解或近似最优解，且在求解质量、求解时间和稳定性方面都远远优于相关文献的算法。

创新点6：针对单次访问条件下的供需未匹配多商品取送货车辆路径问题设计了精确求解算法，验证了本书提出的算法的良好表现及明显优势。

从供需匹配关系事先未知的取送货车辆路径问题的研究领域来看，本书研究了多车、多产品和单次访问的情况。针对供需匹配关系事先未知的取送货车辆路径问题，由于问题非常复杂，因此文献中针对此类问题的精确算法的研究极少（Hernández-Pérez and Salazar-Gonzalez，2004a，2007，2014；Salazar-Gonzalez and Santos-Hernández，2015）。为了精确求解现实中中小规模的问题且丰富相关领域精确算法的研究成果，本书设计了一个分支切割算法来求解所研究的问题，即精确求解的同时考虑以上3个条件的供需匹配关系事先未知的取送货车辆路径问题。针对此精确算法，提出了3类指数型有效不等式，并对每类指数型有效不等式设计了相应的分离算法；讨论了初始上界嵌入方法、预处理过程、分支策略、分离算法调用策略。实验结果表明，该算法能够求解问题的规模为10个客户点和6种商品的算例，这些算例的规模均大于相关文献中的求解规模。