【摘要】 带集货和配送的多站点车辆路线问题(M DVRPPD)是经典VRP的扩展,是多个站点和若干客户既有需求又有供给的VRP问题.研究了该问题的模型并提出了求解该问题的多阶段启发式算法,即先用临界客户的思想把多站点转换为单一站点问题,再使用基于SFC的分组方法来构造初始解,并运用3-opt算法优化回路,之后采用插入算法改善解的可行性,从而得到最终优化解.最后通过实例计算证明了该方法解决M DVRPPD问题的实用可行性和科学有效性.更多还原

【Abstract】 Multi-Depot Vehicle Routing Problem with Pickups and Deliveries is an extension to the classic VRP,which has several depots and customers with pickups and deliveries simultaneously.This paper makes research on its model and further more,presents the multi-stages heuristic algorithm to solve this problem.Firstly,using the idea of borderline customers to change MDVRPPD to SDVRPPD.Secondly,constructing the initial solution by using cluster method based on SFC and optimizing the tours by using 3-opt algorithm.Thirdly,improving the infeasibilities by insertion algorithm and then obtains the final optimal solution.Finally,the algorithm is proved to be feasible,practical,scientific and effective by practical cases.更多还原