Branch-and-Price-and-Cut for the Split-Delivery Vehicle Routing Problem with Time Windows

• 成果类型: Article
• 署名作者: Desaulniers, Guy
• 署名单位: Universite de Montreal; Polytechnique Montreal; Universite de Montreal
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.1090.0713
• 发表日期: 2010
• 页码: 179-192
• 关键词: shortest-path problem; column generation approach; grid network distances; tabu search; resource constraints; scheduling problem; algorithms; inequalities; PROGRAMS

摘要

This paper addresses the split-delivery vehicle routing problem with time windows (SDVRPTW) that consists of determining least-cost vehicle routes to service a set of customer demands while respecting vehicle capacity and customer time windows. The demand of each customer can be fulfilled by several vehicles. For solving this problem, we propose a new exact branch-and-price-and-cut method, where the column generation subproblem is a resource-constrained elementary shortest-path problem combined with the linear relaxation of a bounded knapsack problem. Each generated column is associated with a feasible route and a compatible delivery pattern. As opposed to existing branch-and-price methods for the SDVRPTW or its variant without time windows, integrality requirements in the integer master problem are not imposed on the variables generated dynamically, but rather on additional variables. An ad hoc label-setting algorithm is developed for solving the subproblem. Computational results show the effectiveness of the proposed method.