下载掌阅APP，畅读海量书库
立即打开
在供需匹配关系事先已知的取送货问题中，网络中各客户点之间的供需匹配关系事先已确定，即任意两点之间需转运的商品类型及数量已确定。
相对于供需匹配关系已知的车辆路径问题，供需匹配关系事先未知的取送货车辆路径问题为节约运输成本提供了机遇，因为后者相对于前者松弛了网络中各客户点之间已固定的供需匹配关系，使网络中各客户点之间的供需匹配关系变成一个决策，所以可以通过寻找更好的供需匹配关系来获得更好的运输方案，进而降低运输成本。最近几年，供需匹配关系未知的取送货车辆路径问题吸引了许多学者的关注。Shi等（2009）首次引进单商品取送货车辆路径问题（1-PDVRP）。接着Kadri等（2016）研究了单车情况下的单商品取送货车辆路径问题，并提出了一个分支定界算法。Hernández-Pérez和Salazar-Gonzalez（2014）引进了单车情况下的多商品取送货旅行商问题（m-PDTSP）。在该问题中，运输网络中有多种商品，任何一种商品的供应客户点都可以向任何需求该种商品的客户点供应任何数量的商品。他们提出了一个混合整数线性规划模型，讨论了经典的分解技术，提出了一些有效不等式及一系列分离算法来提高线性松弛规划模型的性能。实验结果表明，其提出的分支切割算法能够求解30个客户点，3种商品的算例。Dell'Amico等（2016）研究了多车情况下的单商品取送货车辆路径问题，提出了一个被称作“破坏后重新构建匹配关系”（Destroy and Repair）的元启发式算法，该算法能够对文献中的算例求出更好的解。Chen等（2014）研究了多车情况下的多商品车辆路径问题，通过考虑单次访问和无限供应（每个供应客户点的商品供应量无限大）引进了多商品取送货车辆路径问题（m-PDVRP）。提出的变邻域搜索算法在1800秒内能够对所研究的问题提供高质量的解。徐东洋等（2021）基于供需匹配关系未知，首次尝试基于“运距×运量”的车辆路径成本和基于额定吨位的固定派车成本之和最低为优化目标，建立同时考虑多车场、多车型、多商品和需求可拆分的取送货车辆路径问题模型，并设计了基于大规模邻域搜索的迭代局部搜索求解算法。