图3-1描述的是简单的物流配送车辆路径问题，图中简单模拟了物流配送的路线， 每一个节点代表需要配送的顾客地理位置，只有一个配送中心，这其中的路线随着配 送地点的增多而越发复杂。这是最简单的车辆配送路径问题，当然在现实中有很多其 它问题。

图 3-1 简单物流配送车辆路径图

3。1。1 车辆问题类型划分 经过各方面专家几十年来的不断探索发展，VRP问题可以按不同的划分标准分成

不同的种类。将VRP问题的主要类型归结为表3-1。

表3-1 车辆路径问题类型划分

划分标准 车辆路径问题类型

任务特征 集货问题或者送货问题

集送货一体化问题

任务性质 对弧服务问题（如中国邮递员问题）

对点服务问题（如旅行商问题）

混合服务问题（如交通车路线安排问题）

车辆满载状况 满载问题

非满载问题

车场数目 单车场问题

多车场问题

车辆类型数 单车型问题（所有车辆容量相同）

多车型问题（车辆容量不全相同）

车辆对车场的所属 关系 车辆开放问题（车辆可以不返回其出发车场）

车辆封闭问题（车辆必须返回其出发车场）

优化目标数 单目标问题

多目标问题

当然，除了固有的模式问题，由于客户需求的不同，衍生了其他相关的问题。 1、VRPLC问题，指得是VRP问题有时间约束，并且车辆的配送时间点不能超过客户

指定的配送时间，也就是要求配送业务的准时及时。 2、MVRP问题，指的是配送车辆将货物从多个配送中心运出，然后准时地配送给既论文网

定客户。

3、SDVRP问题指的是一个客户的需求，配送方可以利用不同的车辆来进行配送，

最终目的就是满足客户的需求。 4、随机VRP问题指的是，比如客户的数量、客户的特殊需求、客户的需要服务的

时间等都是随机变化的，依照这些条件进行准时快速地配送。 5、VRPTW指的是带有时间窗的车辆路径问题。带有时间窗的车辆路径问题也是现

实中比较常见的问题。大致的模式是假设有多个需要被服务的客户，有一个配送中心， n辆车辆有一定的容量。已知的是客户的位置、需要配送的货物量、每辆车的载重量、 以及客户要求服务的时间（就是配送车辆或者客户希望被配送的一段时间范围。一方 面，配送车辆可以在这段时间之前完成配送业务，最迟不能迟于顾客要求的最迟时间。 另一方面，配送车辆必须在配送中心开放前出发，在关门前返回）[13]。

所以在设计每辆汽车的行驶路线需要满足以下几个约束条件:

①每个客户必须接收到服务，但是服务的次数只能是一次；

②每一条路线的出发点都是在配送中心，返回点也是在配送中心；

③车辆本身固有的总容量不能低于每条路线中各个需求服务点的需求；

④每个客户必须在它的时间窗口内被服务，如果汽车提前到了客户所在地，也必 须等待，直到允许为该客户服务为止。

3。1。2 VRP 中常见的约束条件

在 VRP 问题中有不同的约束条件，以下列出的是最常见的约束条件。

(1) 容量条件的约束：这里的容量一般指的就是车辆的容量和需求服务点的容量， 两者的联系是相辅相成的。