Large Neighborhoods with Implicit Customer Selection for Vehicle Routing Problems with Profits
Large Neighborhoods with Implicit Customer Selection for Vehicle Routing Problems with Profits
复制标题
DOI：
10.1287/trsc.2015.0584
复制
发表时间：
2014-01
期刊：
影响因子：
--
通讯作者：
Thibaut Vidal;N. Maculan;L. Ochi;P. Penna
中科院分区：
文献类型：
--
作者：
Thibaut Vidal;N. Maculan;L. Ochi;P. Penna
我们考虑几个具有利润的车辆路径问题（VRP），这些问题寻求选择一部分客户，每个客户都与利润相关，并设计服务行程。当距离约束下利润总和最大化时，该问题通常称为团队定向问题。容量盈利旅游问题寻求在容量限制下最大化利润减去旅游成本。最后，在拥有私人车队和公共承运商的 VRP 中，一些客户可以委托给外部承运商，但需支付一定费用。必须采取三个系列的组合决策：客户的选择、车辆的分配以及每条路线的交付顺序。我们提出了针对这些问题的新邻域搜索，它在伪多项式时间内探索了指数数量的解决方案。搜索是在标准 VRP 社区中以详尽的解决方案表示进行的，并访问了所有客户。由于拜访所有客户通常是不可行或次优的，因此在任何新路线上重复使用基于资源受限的最短路径的有效选择算法，以找到拜访客户的最佳子序列。这些邻域结构的良好性能通过局部搜索、迭代局部搜索和混合遗传算法的大量计算实验得到了证明。有趣的是，即使是针对该邻域的第一个局部最优的局部改进方法，在经典团队定向基准实例上也能达到 0.09% 的平均差距，与当前最先进的元启发法相媲美。关于与更标准的路由邻域的混合的有前景的研究途径也是开放的。
We consider several vehicle routing problems (VRP) with profits, which seek to select a subset of customers, each one being associated with a profit, and to design service itineraries. When the sum of profits is maximized under distance constraints, the problem is usually called the team orienteering problem. The capacitated profitable tour problem seeks to maximize profits minus travel costs under capacity constraints. Finally, in the VRP with a private fleet and common carrier, some customers can be delegated to an external carrier subject to a cost. Three families of combined decisions must be taken: customer’s selection, assignment to vehicles, and sequencing of deliveries for each route.We propose a new neighborhood search for these problems, which explores an exponential number of solutions in pseudo-polynomial time. The search is conducted with standard VRP neighborhoods on an exhaustive solution representation, visiting all customers. Since visiting all customers is usually infeasible or suboptimal, an efficient select algorithm, based on resource constrained shortest paths, is repeatedly used on any new route to find the optimal subsequence of visits to customers. The good performance of these neighborhood structures is demonstrated by extensive computational experiments with a local search, an iterated local search, and a hybrid genetic algorithm. Intriguingly, even a local-improvement method to the first local optimum of this neighborhood achieves an average gap of 0.09% on classic team orienteering benchmark instances, rivaling with the current state-of-the-art metaheuristics. Promising research avenues on hybridizations with more standard routing neighborhoods are also open.