车辆路线安排问题（

车辆路线安排问题（VRP）［4］是由Dantzig和Ramser于1959年提出来的，他们描述了一个将汽油运往各加油站的实际问题，并提出了相应的数学规划模型及求解算法。车辆路线安排问题一般定义为：对一系列客户节点（位置已知或可以估算），在满足一定的约束条件（如货物需求量、交发货时间、车辆容量限制等）下，合理安排车辆配送路线，使车辆有序地通过它们，实现一定的目标（如里程最短、费用最少、时间最短、使用车辆尽可能少等）。

车辆路线安排问题的原型是旅行商问题（Traveling Salesman Problem，TSP），即给定n个城市和两两城市之间的距离，求一条访问各城市一次且仅一次的最短路线。在多路旅行商问题（m-TSP）［5］中，m个旅行商访问所有给定的城市，每个城市只能访问一次，所有的旅行商从同一城市出发，且最终回到该城市，求总路程最短的一组路线。

VRP是m-TSP的扩展，每个城市（客户）有一个需求量，每个旅行商（车辆）有一定的载重量（能力），一条路线上的客户总需求量不能超过行驶该路线的车辆的能力，求从仓库出发并回到仓库的一组总运输费用最少的路线，如图2-3所示。

图2-3 VRP的图示

一般的VRP数学模型如下［4］：

基本假设：

①每辆车从仓库出发后，沿着某条行车路线把装载的所有货物运送到指定的客户后，返回到自己所在的仓库。

②每辆车可以服务多个客户，但每个客户的货物只能由一辆车来配送。

③运输车辆为同一车型，每辆车都有容量限制。

④配送的货物为同一产品，且规格和价值相同。

决策变量和参数符号定义如下：

cij——从节点i到节点j的单位距离运输成本；

dij——从节点i到节点j的距离；

qi——客户i的需求量；

Q——车辆的装载能力；

xijk——车辆k经过节点i到节点j时为1，否则为0；

yik——点i的任务由车辆k完成时为1，否则为0。

数学模型：

xijk∈｛0，1｝，i，j＝1，2，…，n；∀k （2-12）

yik∈｛0，1｝，i＝1，2，…，n；∀k （2-13）

（2-7）式为目标函数，要求运输成本最小；（2-8）式要求车辆装载的货物总量不能超过车辆的载重容量；（2-9）式表示每个客户只由一辆车配送且所有客户都得到服务；（2-10）式和（2-11）式表示两个变量之间的关系；（2-12）式和（2-13）式保证决策变量为整数。

基本的带时间窗约束的车辆路线安排问题（VRPTW）［4］是在一般的车辆路线安排问题的基础上添加了时间窗约束演变而来的，因此可以将带时间窗约束的车辆路线安排问题描述为：要求车辆从仓库出发服务客户，在完成客户需求后仍需返回到仓库，规定每个客户只能被一辆车服务且仅被服务一次，且对客户的服务需要在事先给定的时间窗范围［ETi，LTi］内进行，其中ETi为客户i允许的最早开始服务时间，LTi为客户i允许的最晚开始服务时间，如果车辆抵达客户i的时间早于ETi，则车辆需要在客户i处等待，如果车辆抵达用户i的时间晚于LTi，则客户i的需求要延迟进行。求满足客户需求的费用最小的车辆行驶路线。其数学模型是在上述介绍的一般VRP数学模型的基础上增加时间约束条件。假设ati表示车辆在客户节点i的抵达时间，wti表示车辆在客户节点i的等待时间，sti表示车辆在客户节点i的服务时间，tijk表示第k辆车从节点i到节点j行驶所用时间。则时间约束条件为：

ati≤LTi，i＝1，2，…，n （2-14）

ETi≤ati＋wti≤LTi，i＝1，2，…，n （2-15）

at0＝wt0＝st0＝0 （2-16）

wti＝max｛0，ETi－ati｝，i＝1，2，…，n （2-17）

ati≥0，wti≥0，sti≥0，i＝1，2，…，n （2-18）

（2-14）式表示车辆到达客户i的时间不允许超过客户允许的最晚开始服务时间；（2-15）式要求客户i的开始服务时间必须介于允许的最早开始服务时间和最晚开始服务时间之间；（2-16）式表示起点的时间参数设置；（2-17）式为等待时间的计算公式；（2-18）式要求时间变量为非负数。