概述

    车辆路径问题（VRP）是运筹学里重要的研究问题之一。VRP关注有一个供货商与K个销售点的路径规划的情况，可以简述为：给定一个或多个中心（中心车库）一个车辆集合和一个顾客集合，车辆和顾客各有自己的属性，每辆车都有容量，所载的货物不能超过它的容量。

    车辆路径问题的特性比较复杂，总的来说包含四个方面的属性：

（1）地址特性包括：车场数目、需求类型、作业要求。 

（2）车辆特性包括：车辆数量、载重量约束、可运载品种约束、运行路线约束、工作时间约束。 

（3）问题的其他特性。 

（4）目标函数可能是总成本极小化，或者极小化最大作业成本，或者最大化准时作业 

    常见问题有以下几类： 

（1）旅行商问题。

（2）带容量约束的车辆路线问题。

（3）带时间窗的车辆路线问题。

（4）收集和分发问题。

（5）多车型车辆路线问题。 

（6）优先约束车辆路线问题。 

（7）相容性约束车辆路线问题。 

（8）随机需求车辆路线问题。

VRP定义

数学模型

   有限连通图G(N,V):顶点集N={n_i |i=0,…,n} ，其中n_0代表出发点，其余n_i代表待经过的节点，任意两节点间多有一条边V_{ij}∈V,代表连接n_i和n_j的道路；

   距离函数d:V→R: 函数值非负，代表路径距离；

   可行解L={l_i }是G(N,V)中环路的集合，满足l_i∩l_j={n_0}, ∀i,j 且⋃_{l∈L}l=N；

   问题的优化目标是使可行解中环路的总长度最小，即

衍生问题类型

问题类型列表

类型间的联系

问题类型分析

实际物流问题有如下的一般性约束条件：

1. 多车型，容量限制，时间窗限制； 

2. 多车场：以伪多车场问题为主，可以拆分为多个单车场问题，真正的多车场问题要求订单和出发点不关联；

3. 开放/封闭路径：前者常见于以运费为优化目标，后者常见于以距离为优化目标

4. 收取货：一般是收货与取货互相独立的backhual模式； 

5. 分次投送：和车型相关，一般在车型相对小时有需求；

6. 优化函数：以装载量为优化目标之一时，可能和主要优化目标互相独立，可单独做后处理；