摘要：对VRP问题的求解，长期以来以遗传算法居多。为了取得VRP问题的精确解，本文以GAMS优化软件为计算平台，对经典VRP问题的模型进行求解，并针对计算过程中产生的仅由客户点组成且阶数不断增大的小回路问题，逐步引入破除各阶小回路的约束条件，取得了问题的精确解。在此基础上，论文归纳出了破除小回路的一般约束条件，完善了经典VRP问题的模型。
关键词：VRP GAMS 精确解
配送中心作为物流活动中专职从事配送工作的组织者，具有规模大、配送能力强的特点，从而使得由配送中心对用户进行需求物品配送成为物流配送的主要形式，而其中配送车辆的路径合理与否，对于配送速度、配送费用、运力配备以及配送成本与效益的影响均很大，采用科学合理的方法来确定车辆路径便成为配送中心进行配送活动的一项重要工作。车辆路径问题(Vehicle Routing Problem，VRP)是由G．Dantzig和J．Ramser[1]于1959年首先提出来的，很快引起运筹学、管理学、计算机应用、组合数学、图论等学科的专家学者的高度重视。他们对此问题进行了大量的理论研究和实验分析，取得了很大的研究进展。其研究结果在运输系统、物流配送系统、快递收发系统中都已得到广泛应用。现在，对车辆路径问题的研究仍然相当活跃。
1.VRP问题描述
车辆路径问题（VRP问题）一般定义为[2]：对一系列发货点和／或收货点，组织适当的行车路线，使车辆有序地通过它们，在满足一定的约束条件(如货物需求量、发送量、交发货时间、车辆容量限制、行驶里程限制、时间限制等)下，达到一定的目标(如路程最短、费用最小、时间尽量少、使用车辆尽量少等)。在经典VRP的基础上，车辆路径问题在学术研究和实际应用上产生了许多不同的延伸和变化型态，包括TSP(当VRP只包括一条路径，且没有能力约束时就成为TSP)、带能力约束的车辆路径问题(CVRP)、带时间窗的车辆路径问题(VRPTW)、追求最佳服务时间的车辆路径问题(VRPDT)、多车种车辆路径问题(FSVRP)、车辆多次使用的车辆路径问题(VRPM)、考虑收集的车辆路径问题(VRPB)、随机需求车辆路径问题(VRPSD)、动态车辆路径问题(DVRP)、满载/非满载VRP、双向VRP等。虽然VRP具有多种变化型态，但总的来说，在VRP中，最常见的附加条件有：
(1)能力约束。与每个客户或城市对应的需求是个非负的值，任意车辆路径的总重量不能超过该车辆的能力负荷。
(2)任意路径所含城市数的上界为q。
(3)总时间约束。任意路径的长度不能超过预先给定的界L;该长度由车辆在城市间的旅行时间tij和在该路径里的每个城市i的停留时间Ti所构成。
(4)时间窗口。必须在时间区间[ai,bi]里访问城市i，并允许在城市i等待。
(5)多个城市间存在优先级关系，必须在访问城市i之前访问城市j。