车辆路径问题VRP一般定义为：对一系列装货点和卸货点，组织适当的行车线路，使车辆有序地通过它们，在满足一定的约束条件如货物需求量、发送量、交发货时间、车辆容量限制、行驶里程限制、时间限制等下，达到一定问题的目标如路程最短、费用最少、时间尽量少、使用车辆数尽量少等。
目前有关VRP的研究已经可以表示（如图1）为：给定一个或多个中心点（中心仓库，ce
traldepot）、一个车辆集合和一个顾客集合，车辆和顾客各有自己的属性，每辆车都有容量，所装载货物不能超过它的容量。起初车辆都在中心点，顾客在空间任意分布，车把货物从车库运送到每一个顾客（或从每个顾客处把货物运到车库），要求满足顾客的需求，车辆最后返回车库，每个顾客只能被服务一次，怎样才能使运输费用最小。而顾客的需求或已知、或随机、或以时间规律变化。
图1VRP示意图一、在VRP中，最常见的约束条件有
1容量约束：任意车辆路径的总重量不能超过该车辆的能力负
f荷。引出带容量约束的车辆路径问题CapacitatedVehicleRouti
gProblem，CVRP。
2优先约束：引出优先约束车辆路径问题VehicleRouti
gProblemwithprecede
ceCo
strai
ts，VRPPC。
3车型约束：引出多车型车辆路径问题MixedHeteroge
eousFleetVehicleRouti
gProblem，MFVRPHFVRP。
4时间窗约束：包括硬时间窗HardTimewi
dows和软时间窗SoftTimewi
dows约束。引出带时间窗包括硬时间窗和软时间窗的车辆路径问题VehicleRouti
gProblemwithTimewi
dows，VRPTW。
5相容性约束：引出相容性约束车辆路径问题VehicleRouti
gProblemwithCompatibilityCo
strai
ts，VRPCC。
6随机需求：引出随机需求车辆路径问题VehicleRouti
gProblemwithStochasticDema
d，VRPSD。
7开路：引出开路车辆路径问题Ope
VehicleRouti
gProblem。
8多运输中心：引出多运输中心的车辆路径问题MultiDepotVehicleRouti
gProblem。
9回程运输：引出带回程运输的车辆路径问题VehicleRouti
gProblemwithBackhauls。
10最后时间期限：引出带最后时间期限的车辆路径问题VehicleRouti
gProblemwithTimeDeadli
es。
f11车速随时间变化：引出车速随时间变化的车辆路径问题TimeDepe
de
tVehicleRouti
gProblem。二、CVRP问题描述及其数学模型
CVRP的描述：设某中心车场有k辆车，每辆配送车的最大载重量Q，需要对
个客户节点进行运输配送，每辆车从中心车场出发给若干个客户送货，最终回到中心车场，客户点i的货物需求量是qii12…
，且qiQ。记配送中心编号为0，各客户编号为ii12…
，cij表示客户i到客户j的距离。r