【摘要】 为了克服原有大规模邻域搜索算法不能有效求解时间窗较宽的车辆路径问题的缺陷,介绍了有时间 窗的车辆路径问题(VRPTW)的通用数学模型。通过分析各主要变量之间的关系,构造了一种简单、快速的确定性 初始算法。通过引入”短路径优先策略”,构造了一种改进的大规模邻域搜索算法,该策略也可嵌入到求解时间窗 比较窄的车辆路径问题中,达到加速搜索的目的。试验结果表明,改进的算法可以在较短的时间内有效地求得 VRPTW的优化解,是求解VRPTW的一个较好方案。更多还原

【Abstract】 The vehicle routing problem with time windows (VRPTW) cannot be solved effectively by using the existing Large Neighborhood Search (LNS) algorithm. A universal mathematical model of VRPTW was built. By analyzing the relation of several main variables, a simple, fast deterministic initial algorithm was proposed. An improved LNS algorithm was put forward based on the shortest route priority strategy, which could solve the problems with long scheduling horizon effectively. The strategy could also be applied to solving the problems with short scheduling horizon to accelerate searching process. Experiment results show that the improved algorithm can find the optimal or near optimal solution to VRPTW in short time.更多还原