分支和切割
车辆路径问题
布线(电子设计自动化)
数学优化
算法
计算机科学
整数规划
数学
计算机网络
作者
Tolga Bektaş,Güneş Erdoğan,Stefan Røpke
出处
期刊:Transportation Science
[Institute for Operations Research and the Management Sciences]
日期:2011-02-18
卷期号:45 (3): 299-316
被引量:127
标识
DOI:10.1287/trsc.1100.0352
摘要
The generalized vehicle routing problem (GVRP) consists of finding a set of routes for a number of capacitated vehicles on a graph where the vertices are partitioned into clusters with given demands, such that the total cost of travel is minimized and all demands are met. This paper describes and compares four new integer linear programming formulations for the GVRP, two based on multicommodity flow and the other two based on exponential-size sets of inequalities. Branch-and-cut algorithms are proposed for the latter two. Computational results on a large set of instances are presented.
科研通智能强力驱动
Strongly Powered by AbleSci AI