Exact and Heuristic Algorithms for Capacitated Vehicle Routing Problems with Quadratic Costs Structure
针对工程和物流中两类带二次成本的车辆路径问题，提出三索引车辆流模型、分支切割精确算法和混合元启发式算法，在小中型算例上验证了效果。
In this article we introduce the quadratic capacitated vehicle routing problem (QCVRP) motivated by two applications in engineering and logistics: the capacitated vehicle routing problem with angle penalties (angle-CVRP) and the capacitated vehicle routing problem with reload costs (CVRP-RC). We introduce a three-index vehicle-flow formulation of the problem, which is strengthened with valid inequalities, and we derive a branch-and-cut algorithm capable of providing tight lower bounds and solving small- to medium-size instances in short to moderate computing times. Furthermore, we present a hybrid metaheuristic capable of providing high quality solutions in short computing times. The two algorithms are tested on several instances from the CVRP literature modified to mimic the two problems that motivate our study.