下载掌阅APP，畅读海量书库
立即打开
车辆路径问题（VRP）一般定义为：对一系列装货点和卸货点，组织适当的行车线路，使车辆有序地通过它们，在满足一定的约束条件（如货物需求量、发送量、交发货时间、车辆容量限制、行驶里程限制、时间限制等）下，达到一定目标（如路程最短、费用最少、时间尽量少、使用车辆数尽量少等）。
目前有关VRP的研究已经可以表示为：给定一个或多个中心点（中心仓库，Central Depot）、一个车辆集合和一个顾客集合，车辆和顾客各有自己的属性，每辆车都有容量，所装载货物不能超过它的容量。起初车辆都在中心点，顾客在空间任意分布，车把货物从车库运送到每一个顾客（或从每个顾客处把货物运到车库），要求满足顾客的需求，车辆最后返回车库时，每个顾客只能被服务一次，怎样才能使运输费用最小。而顾客的需求或已知、或随机、或以时间规律变化。
在VRP中，最常见的约束条件有：
（1）容量约束：任意车辆路径的总重量不能超过该车辆的能力负荷。引出带容量约束的车辆路径问题（Capacitated Vehicle Routing Problem，CVRP）。
（2）优先约束：引出优先约束车辆路径问题（Vehicle Routing Problem with Precedence Constraints，VRPPC）。
（3）车型约束：引出多车型车辆路径问题（Mixed/Heterogeneous Fleet Vehicle Routing Problem，MFVRP/ HFVRP）。
（4）时间窗约束：包括硬时间窗（Hard Time Windows）和软时间窗（Soft Time Windows）约束。引出带时间窗（包括硬时间窗和软时间窗）的车辆路径问题（Vehicle Routing Problem with Time Windows，VRPTW）。
（5）相容性约束：引出相容性约束车辆路径问题（Vehicle Routing Problem with Compatibility Constraints，VRPCC）。
（6）随机需求：引出随机需求车辆路径问题（Vehicle Routing Problem with Stochastic Demand，VRPSD）。
（7）开路：引出开路车辆路径问题（Open Vehicle Routing Problem，OVRP）。
（8）多运输中心：引出多运输中心的车辆路径问题（Multi-depot Vehicle Routing Problem，MDVRP）。
（9）回程运输：引出带回程运输的车辆路径问题（Vehicle Routing Problem with Backhauls，VRPB）。
（10）最后时间期限：引出带最后时间期限的车辆路径问题（Vehicle Routing Problem with Time Deadlines，VRPTD）。
（11）车速随时间变化：引出车速随时间变化的车辆路径问题（Time-dependent Vehicle Routing Problem，TDVRP）。
在现实问题中，所有车辆都是有容积限制的，故本书主要研究CVRP问题。
CVRP的描述：设某中心车场有k辆车，每辆配送车的最大载重量Q，需要对n个客户（节点）进行运输配送，每辆车从中心车场出发给若干个客户送货，最终回到中心车场，客户点i的货物需求量是q i （i=1，2，……，n），且q i ＜Q。记配送中心编号为0，各客户编号为i（i=1，2，……，n），c ij 表示客户i到客户j的距离。求满足车辆数最小，车辆行驶总路程最短的运送方案。
定义变量如下：
x ijk ：若车辆k由i到j，则值为1；若车辆k不由i到j，则值为0。
y ki ：若车辆k访问i，则值为1；若车辆k不访问i，则值为0。
建立此问题的数学模型：
约束条件：
公式（2-1）表示目标函数为最小化车辆行驶总路程；约束（2-2）表示每个客户只能由一辆车访问；约束（2-3）与约束（2-4）表示流量守恒约束，约束（2-5）表示每辆车的装载量不得超出车辆容积。
CVRP问题已被认为是NP难题，现介绍几种主要的精确算法，从最早的分支定界到现在的分支定价。
分支定界法（Branch and Bound Method）在20世纪60年代被提出，其实质为一种隐枚举法或部分枚举法，是枚举法基础上的改进。分支是指把可行解集划分为互不相交的子集。如果要求解一个最小化问题，定界就是指计算目标函数值在给定可行解子集上的下界。如果这个可行解子集的下界大于或等于当前最好的目标函数值，那么就可以不考虑这一可行解子集。这个过程称为剪支。反复利用分支、定界和剪支，我们就可以找到最小化问题的一个最优可行解（周黍雨，2012）。
动态规划（Dynamic Programming）是解决多阶段决策过程最优化问题的一种方法，由美国数学家贝尔曼等人在20世纪50年代初提出。可用于解决最优路径、资源分配、生产计划与库存排序等问题。动态规划模型需要用到以下概念：阶段、状态、决策和策略、状态转移方程、指标函数（胡运权、郭耀煌，2012）。
（1）阶段：在动态规划里，将所给问题的过程，按时间或空间特征分解成若干个相互联系的“阶段”，以便能按次序去求解。描述阶段的变量称为阶段变量。通过对阶段的划分，我们就能把问题的过程转化为多阶段决策的过程。
（2）状态：各阶段开始时的客观条件叫作状态，描述各阶段状态的变量称为状态变量。当某阶段状态给定后，在这阶段以后过程的发展不受这段以前各段状态的影响。
（3）决策和策略：当各阶段的状态取定后，就可以做出不同的决策，从而确定下一阶段的状态，这种决定称为决策。表达决策的变量称为决策变量。
（4）状态转移方程：动态规划中本阶段的状态往往是上一阶段状态和上一阶段的决策结果，可以用方程来表示。
（5）指标函数：用于衡量所选定策略优劣的数量指标称为指标函数。
动态规划的关键在于正确地写出基本的递推关系式和恰当的边界条件。需先将问题的过程分成几个相互联系的阶段，恰当地选取状态变量和决策变量及定义最优指标函数，从而把问题化成一组同类型的子问题，然后逐个求解。求解时从边界条件开始，逆过程行进方向，逐段递推寻优，在每一个子问题的求解中，都利用它前面的子问题的最优化结果，最后一个子问题的最优解就是整个问题的最优解（胡运权、郭耀煌，2012）。
组合优化问题可以分为两类：一类简单的问题可以在多项式时间内获取最优解；还有一系列较难的问题在多项式时间内无法获取最优解。拉格朗日松弛（Lagrangian Relaxation）可以为较难的问题提供下界值。
拉格朗日松弛的主要思想是把组合优化问题中的困难约束“对偶化”，即通过“拉格朗日乘子”把这些困难约束增加到目标函数中去。这样的通过拉格朗日乘子把一些约束对偶化的过程就称为“拉格朗日松弛”。原问题经过拉格朗日松弛之后所得到的问题就称为“拉格朗日松弛问题”。假设原问题模型为：
Z =min cx
S.t. Ax=b
Dx≤e
x ≥0且为整数
我们将约束 Ax=b 进行松弛，加入原问题的目标函数中，得到松弛问题的模型：
Z D （ μ ）=min cx+μ （ Ax-b ）
S.t. Dx≤e
x ≥0且为整数
其中， μ =（ μ 1 ， μ 2 ，…… μ m ）为一系列拉格朗日乘子。假设原问题的最优解为 x * ，则 Z D （ μ ）≤min cx * + μ （ Ax * - b ）= Z 。即对于该松弛问题，易于求出其最优解，松弛问题的最优解即为原问题的一个下界解。
在线性规划中，当矩阵的列太多，问题可能变得难以求解。这时，可采取列生成法（Column Generation）与分支定价法（Branch and Cut）来取得较好的结果。
例如，我们把下面的线性规划模型称为主问题
如果要用单纯形法来求解上述问题，那么在每一步迭代中，我们要计算非基变量的检验数，把检验数最小的换到“基”中。也就是说，给定一组非负的对偶向量，我们希望找到一个合适的 j∈S ，来得到最小化检验数。我们用一个相对小的列向量集合 S ′ 来代替原有的 S ，这样产生的问题称为受限主问题。在受限主问题中，检验数可以通过一个定价问题得到。我们就把定价子问题中达到最优值的那一列添加到受限主问题中，然后反复地求解受限主问题和定价子问题，不断进行这样的迭代过程，直到找不到检验数为负的列为止。列生成中的列在研究的具体问题中往往有具体的含义，比如一条路径、一台机器上的调度，等等。
我们可以结合分支定价法求解这种大规模线性规划问题。分支定价法沿用了分支定界法的思路，同时在每个结点中应用了列生成法。在分支定价法中，我们首先松弛原整数规划问题的整数约束，使用列生成法求解松驰后的整数规划问题。然后如分支定界法一样，如果得到的是分数解，就进行分支，在问题中添加相应的约束条件。然后不断使用列生成法求解添加了新的约束条件后的线性规划问题。由于只是添加一些新约束，所以可以基本沿用针对原问题的列生成法的模型。在每个结点，我们还可以通过列生成法的定价算法得到问题的一个下界，如果这个下界不小于当前最好的上界，我们就可以把这个分支剪掉，这个过程就称为定价。反复利用分支和定价，我们就可以求解这种类型的整数线性规划问题（周黍雨，2012）。
传统的优化算法是基于精确数学的方法，这类方法对数据确定性和准确性有严格的要求。实际生活中迫切希望能够直接对具有不确定性的数据乃至语言变量进行计算的优化方法，于是新的优化算法不断出现。
1975年，Holland提出遗传算法（Genetic Algorithm）；1983年，Krikparick提出了模拟退火（Simulated Annealing）算法；1986年，Glover提出禁忌搜索（Tabu Search）算法；1997年，Mladenovi
和Hansen提出变邻域搜索（Variable Neighborhood Search）算法。
遗传算法是根据问题的目标函数构造一个适值函数，对一个由多个解构成的种群进行评估、遗传运算、选择，经多代繁殖，获得适应值最好的个体作为问题的最优解（汪定伟等，2007）。遗传算法的基本构成要素如下。
种群：种群是由染色体构成的，每个个体就是一个染色体，每个染色体对应着问题的一个解。种群中个体的数量称为种群大小或者种群规模。
编码方法：编码方法也称为基因表达方法，染色体是由基因构成的。染色体与要优化的问题的解进行对应，就需要通过基因来表示。
遗传算子：遗传算子包括交叉和变异。遗传算子模拟了每一代中创造后代的繁殖过程，是遗传算法的精髓。
交叉同时对两个染色体进行操作，组合二者的特性产生新的后代。双亲的染色体是否进行交叉由交叉率来进行控制。交叉率定义为各代中交叉产生的后代数与种群中个体数的比。
变异是在染色体上自发地产生随机的变化。染色体是否进行变异由变异率进行控制。变异率定义为种群中变异基因数在总基因数中的百分比。
选择策略：从当前种群中选择适应值高的个体以生成交配池的过程。
停止准则：一般使用最大迭代次数作为停止准则。
模拟退火算法是一种启发式的随机寻优算法，它模拟了物理退火过程，由一个给定的初始高温开始，利用具有概率突跳特征的抽样策略在解空间中随机搜索，伴随温度的不断下降重复抽样过程，最终得到问题的全局最优解（汪定伟等，2007）。模拟退火算法的基本构成要素如下。
状态表达：状态表达是利用一种数学形式来描述系统所处的一种能量状态，一个状态就是问题的一个解，问题的目标函数对应状态的能量函数。
邻域定义与移动：模拟退火算法采取了一种特殊的邻域移动方法，依据一定的概率来决定当前解是否移向新解。
热平衡达到：在给定的一个温度下，模拟退火算法进行随机搜索，最终达到一种平衡状态的过程，这是内循环过程。在每一个温度下，内循环迭代相同的次数。
降温函数：降温函数用来控制温度的下降方式，温度每一步下降的大小都相等，是外循环过程。
禁忌搜索算法的基本思想是在搜索过程中将近期的历史搜索过程放入禁忌列表中，阻止算法重新进入，有效防止搜索过程的循环。禁忌搜索算法采用了邻域选优的搜索方法，为了能逃离局部最优解，算法必须接受劣解，也就是每次迭代得到的解不必一定优于以前的解。算法将最近接受的一些移动放在禁忌表中，在以后的迭代中加以禁止，即只有不在禁忌表中的较好解才被接受作为下一代迭代的初始解。随着迭代的进行，禁忌表不断更新，最早进入禁忌列表的移动就从禁忌表中解禁了（汪定伟等，2007）。
变邻域算法的基本思想是结合局部搜索算法来系统地改变邻域结构。主要包括以下操作：
摇动程序：在变邻域算法中使用摇动程序的目的是跳出局部搜索，具体做法是从某个邻域中随机选择一个邻域解（通常该邻域解被当作该邻域内局部优化的初始解）。
邻域变换：如果当前解在某个邻域结构中发生改进了，则回到第一个邻域结构中继续搜索；否则在下一邻域（根据定义的顺序）中继续搜索。
局部优化：在每次迭代中对当前解的邻域结构，采取局部启发式算法对当前解进行优化。