车辆路径问题的改进分支切割法

Improved branch and cut algorithm for vehicle routing problem

对容量约束车辆路径问题建立了数学模型并提出了一种改进的分支切割算法.算法结合启发式规则,采用梳子不等式和连接不等式产生切割面,设置参数控制分支客户组合的大小和分支方向,通过不断调整问题下界来删除多余节点.提出了切割面更新策略,设置切割面利用系数和切割面库,通过动态更新来淘汰利用率低的切割面,保存利用率高的切割面.采用多组CVRP算例进行计算,并与其它算法优化CVRP的实验结果作了比较,对运算结果进行了分析,给出了推荐的参数取值方案,说明了提出的分支切割算法对容量约束车辆路径问题的有效性.

The model of Capacitied Vehicle Routing Problem（CVRP） is presented and a branch and cut algorithm is designed to solve CVRP. Based on heuristic rules, the algorithm uses comb inequality and connection inequality to produce cut planes. Parameters are set to control the size and direction of the combination of customers. The lower bound of CVRP is updated constantly to delete nodes of the branch. A cut plane updating strategy is proposed to improve calculation speed. With utilization coefficient and cut plane set, planes of high utilization ratio are saved and planes of low utilization ratio are deleted. Many representative results and the analysis are given in this paper. This proposed algorithm is also applied to illustrate its validity in comparison with the best results in other literatures. The recommended value of parameter is given, and the results and the analysis demonstrate the effectiveness of this algorithm to solve CVRP.