OVRP

1、论文中求解OVRP问题的常用算法有：禁忌搜索算法、遗传算法、蚁群算法、禁忌搜索和遗传算法合

2、Schrage在1981年提出OVRP问题。分别有COVRP（容量约束）、DCVRP（路程长度约束）、OVRPTW（带时间窗）

3、这两篇问题都是知网上下载的，以搜名字就能下载

《开放式车辆路径问题及其应用研究》2004年03发表 被引用113次 作者：符卓 博士论文

文中给出OVRP问题描述：开发式车辆路径问题(Open Vehicle RoutingProblem，OVRP)是另一种类型的车辆路径问题。它与基本的车辆路径问题（VRP）的主要区别是不要求车辆完成取送任务后返回原出发点，或者是若要求返回原出发点，则沿原去程路线返回。

文中介绍的是一种能同时求解CVRP和DCOVRP的禁忌搜索算法，但禁忌搜索算法的效能高度依赖于初始解的质量，所以初始解的构造很关键。

禁忌搜索算法模拟人脑记忆功能，禁止重复前面的工作。为了改进局部邻域搜索容易陷入局部最优的不足，禁忌搜索算法引入一个禁忌表记录下已经搜索过的局部最优解，在下一次搜索中，利用禁忌表中信息不再或有选择地搜索这些点，以此来跳出局部最有点，从而实现全局优化。

禁忌搜索的基本思想是：给定一个当前解（初始解）和候选解产生函数（邻域函数），然后再当前解的邻域中确定若干候选解；若候选解对应的目标值优于到目前为止搜索到的“最优解”，则忽略其禁忌特性，用其替代当前解和“最好解”；若不存在候选解，则在候选集中选择非禁忌的最佳候选解为当前解，而无视它与当前解的优劣；两种情况下都将相应地对象加入禁忌表，并修改禁忌表中个对象的任期；重复搜索，直到满足停止准则。禁忌表用于记载在最近的5~10（随机挑选）次迭代中解的变换特征。可以构造一组（n+1）×（n+1）阶矩阵来记录禁忌情

况。若点i被挑选来进行交换（1）（顶点重新指派），则将其禁忌情况存入矩阵的元素（i，i）中。若点i和j被挑选来进行变换（2）~（4），则将禁忌情况存入矩阵的元素（i，j）中。在每次迭代时，都必须将上一步所进行的变换填入到禁忌表中，而表中的其他元素相应地减1直到等于零为止。

这篇文章中提出一种基于最优化方法的“最远者优先启发式算法（FFH）来产生”。在OVRP中，因为车辆的行驶路线是开放的，所以在其最优解中，离车场最远的客户通常是一条线路的端点。基于这样的观察，在所提出的算法中，新路线总是从离车场最远且尚未指派给任何线路的客户点开始构造。

初始解产生：FFH的基本思想是：一条新线路从离车场最远且尚且未指派给任何线路的客户点i开始。沿着从点i到车场的最短路，依次将客户分配给这条新线路（这辆车），直到车辆足够满为止；若车辆未到达到足够满，则舍弃这条线路而转为尝试其次短路。重复这个过程直到一条线路被接受。这个策略的目的在于最小化所需要的车辆数。而依次挑选从点i到车场的最短路、第二短路、......、k-短路，是努力最小化总行驶费用。

经典邻域解：插入和交换。本文邻域解构造：在路线内或两路线间进行顶底重新指派、顶底交换、2-opt和“尾巴”交换的一种组合。

终止准则：当总迭代次数达到给定的值，或在一个给定的连续迭代步数内当前的最好解没有改变时，则算法终止

运算结果：速度慢，但结果更好。50个点以上的测试算例，每个运算20次，与Sariklis和Powell的经典启发式（最快）相比7个问题中有6个提出更好的解，。与Brandao的禁忌搜索相比，16个问题中有9个问题提粗更好的最终解。通过把从FFH产生的初始解开始的求解效果与从随机产生的初始解开始的效果进行比较，表面用本文提出的禁忌搜索算法求解这些基于完备网络的OVRP测试是，其初始解对最终解的质量没有太大的影响。与Van Breedam和Brandao的不同，本文提出的禁忌搜索算法

是健壮的。

《基于禁忌搜索算法的开放式车辆路径问题的研究》

2010年5月发表 被引用4次 作者：李三宾 硕士论文

Schrage在1981年提出OVRP问题。文中给出四种分类：COVRP（容量约束）、DCOVRP（路程长度约束）、OVRPTW（带时间窗约束）、OVRPPD（带取送作业约束）COVRP研究现状：

Sarik和pawell在2000年5月一篇关于OVRP的研究论文，率先对有

CVRP（有装载能力约束的车辆路径问题）进行研究。采用基于最小生成树的两阶段法，先进行聚类在进行排序。第一阶段对所有客户点进行聚类，在满足车辆装载能力的约束下，使形成的类数目最少，再通过规则不断调整类及重新分派客户点，从而使得最终形成的类质量得以进一步提高，也就是使车辆运输费用减少。第二阶段，把每一个类转化为一条开发式的车辆行驶路径，主要采用的是基于最小生成树的方法，该算法属于先分组后构造线路的两阶段法。在构造线路阶段，对于所形成每一个组，求解一个最小生成树问题。如果所求出的解是一条链，则就为该组的最优解；否则，必须执行构造线路阶段中带惩罚过程的第二和第三步骤。

Tarantilis等在2004年和2005年提出基于门槛值接受的智能化算法来求解OVRP。一种是回溯记忆门槛值接受法，另一种是基于门槛值表的门槛接受法。

Letchford在2006年求解CVRP的分支切面法的基础之上提出啊了求解COVRP,此算法是精确算法，是切平面法和分支定界法的结合。

2004年符卓发表了带装载能力约束的OVRP及禁忌搜索算法研究。2008年符卓和聂靖提出求解COVRP的遗传算法，其算法中，采用符号编码方式，选用目标函数值加惩罚函数的方法设计适应度函数，在算法初期使用相对宽松的惩罚系数加大解空间的搜索范围，在算法的末期增大惩罚系数使得算法更快地趋于收敛，使用交叉算子A和加入贪婪策略的

交换变异算子，以及提出采用自适应机制来动态的调整交叉概率和变异概率。