Formulations and Branch-and-Cut Algorithms for the Generalized Vehicle Routing Problem
Formulations and Branch-and-Cut Algorithms for the Generalized Vehicle Routing Problem
复制标题
DOI：
10.1287/trsc.1100.0352
复制
发表时间：
2011-08-01
影响因子：
4.6
通讯作者：
Ropke, Stefan
中科院分区：
文献类型：
--
作者：
Bektas, Tolga;Erdogan, Gunes;Ropke, Stefan
广义车辆路径问题（GVRP）是指在给定需求的情况下，将图中的顶点划分为若干个簇，在满足所有需求的前提下，使总的出行成本最小化，从而为多个容量受限的车辆寻找一组路径。本文描述和比较了四个新的整数线性规划公式的GVRP，两个基于多商品流和其他两个基于指数大小的不等式集。针对后两种情况提出了分支切割算法。大量的实例上的计算结果。
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.