分支和切割
车辆路径问题
分界
数学优化
集合(抽象数据类型)
分支机构和价格
布线(电子设计自动化)
列生成
计算机科学
算法
整数规划
数学
计算机网络
程序设计语言
作者
Fernando Afonso Santos,Geraldo Robson Mateus,Alexandre Salles da Cunha
出处
期刊:Transportation Science
[Institute for Operations Research and the Management Sciences]
日期:2014-04-07
卷期号:49 (2): 355-368
被引量:85
标识
DOI:10.1287/trsc.2013.0500
摘要
In this paper, we introduce a branch-and-cut-and-price algorithm for the two-echelon capacitated vehicle routing problem. The algorithm relies on a reformulation based on q-routes that combines two important features. First, it overcomes symmetry issues observed in a formulation coming from a previous study of the problem. Second, it is strengthened with several classes of valid inequalities. As a result, the branch-and-cut-and-price implementation compares favorably with previous exact solution approaches for the problem—namely, two branch-and-price algorithms and a branch-and-cut method. Overall, 10 new optimality certificates and 8 new best upper bounds are provided in this study. New best lower bounds are also presented for all instances in the hardest test set from the literature.
科研通智能强力驱动
Strongly Powered by AbleSci AI