车辆路径问题
枚举
布线(电子设计自动化)
节点(物理)
放松(心理学)
国家(计算机科学)
数学
变量(数学)
计算机科学
弧(几何)
数学优化
算法
组合数学
计算机网络
工程类
社会心理学
结构工程
数学分析
心理学
几何学
作者
Diego Pecin,Claudio Contardo,Guy Desaulniers,Eduardo Uchoa
标识
DOI:10.1287/ijoc.2016.0744
摘要
The vehicle routing problem with time windows (VRPTW) consists of finding least-cost vehicle routes to satisfy the demands of customers that can be visited within specific time windows. We introduce two enhancements for the exact solution of the VRPTW by branch-price-and-cut (BPC). First, we develop a sharper form of the limited-memory subset-row inequalities by representing the memory as an arc subset rather than a node subset. Second, from the elementary inequalities introduced by Balas in 1977, we derive a family of inequalities that dominate them. These enhancements are embedded into an exact BPC algorithm that includes state-of-the-art features such as bidirectional labeling, decremental state-space relaxation, completion bounds, variable fixing, and route enumeration. Computational results show that these enhancements are particularly effective for the most difficult instances and that our BPC algorithm can solve all 56 Solomon instances with 100 customers and 51 of 60 Gehring and Homberger instances with 200 customers.
科研通智能强力驱动
Strongly Powered by AbleSci AI