基于物流配送中车辆路径问题的模型及算法的研(2)
2013-08-29 01:07
导读：货物流模型和车辆流模型是整数线性规划模型中的另外两种：货物流模型明确地考虑通过每条路径的货物量，车辆流模型则体现了系统中车辆的最优运行方
货物流模型和车辆流模型是整数线性规划模型中的另外两种：货物流模型明确地考虑通过每条路径的货物量，车辆流模型则体现了系统中车辆的最优运行方案。在以往的研究中，采用的流变量主要包括两类——双下标变量和三下标变量，如 和 分别表示通过弧i,j的货物量和通过弧i,j驶往顾客l的货物量。使用双下标和三下标变量各有优劣。双下标变量的特点是简便，涉及的变量较少，然而却不能反映不同车辆的与特征，因此只适用于车辆类型相同的情况。Desrosiers等，Laporte等分别采用了双下标变量来建摸，其中Laporte等提出了一种约束松弛算法，应用于约束条件较松的问题，效果较好。相比之下，三下标的VRP模型更通用一些，然而涉及的变量一般较多。Fisher等研究了有容量和时间窗约束VRP的三下标模型，并且基于Bender分解，通过交替求解一般指派问题和有时间窗的旅行商问题来求解该问题。后来Martello等又对该算法进行了一些改进。
2.1.2启发式算法
启发式算法是一种寻找近忧解的算法，目前已提出的启发式算法很多，分类也相当多。按传统的VRP启发式算法分类，可分为构造算法、两阶段法、不完全优化算法和改进算法4类。
（1）构造算法
构造算法是根据一定的准则，每一次将一个不在线路上的点增加进线路，直到所有的点都被安排进线路为止。如Clarke-Wright节约算法、Solomon插入法，Salhi等提出的簇插入法，Gendreau等提出GENI插入法，Altinkemer和Gavish提出的并行节约算法以及Paessens提出的节约算法等。
（2）两阶段法（Two-phase Algorithm）
两阶段法的基本做法是在第一阶段得到一可行解，第二阶段通过对点的调整，在始终保持解可行的情况下，每次迭代产生一个解用以替代原来的解，力图使目标函数值得以改进，一直继续到不能再改进目标函数时为止。如Gillett和Miller的Sweep算法，Renaud等的Petal算法，Toth和Vigo提出的先聚类再安排路径的算法，Lin提出的2-opt和3-opt交换，Or提出的Or-opt交换以及Breedam提出的串重置和串交换，Cordone等提出的改进算法等。
（转载自http://www.ＮＳＥＡＣ.com中国科教评价网） 一些基于规划的算法也属于两阶段法，首先把问题表达成一个
数学规划模型，根据其模型的特殊构形，利用一定技巧进行分划，进而求解易于处理的子问题。如Kohld等先利用Lagrangian松弛技术将有时间窗的VRP变为较简单的指派问题，然后用列生成技术来获得问题的近似解。
另外，还有一些两阶段算法在求解过程中常常采用交互式优化技术，把人的主观能动作用结合到问题的求解过程中。如Cullew、Jarvis和Ratliff提出的两阶段法。
（3）不完全优化算法
以启发式准则代替精确算法中的决策准则，以缩小搜索空间，如Christofides, Mingozzi和Toth提出的算法。
（4）改进算法
从一初始解开始，通过对当前的解进行反复地局部扰乱以达到较好的解。基于启发式的并行算法和亚启发式算法都属于此类。
亚启发式算法包括禁忌搜索算法、模拟退火算法、神经网络和遗传算法等方法。进入20世纪90年代，这些亚启发式算法的应用成为VRP研究中的新趋势。如Gendreau、Hertz和Laporte，Jiefeng和James，Duhamel、Christophe和Potvin，Barbarosoglu、Gulayhe和Ozgur等将禁忌搜索算法应用于VRP的求解，并取得了较好的效果。另外，模拟退火算法、神经网络以及遗传算法等亚启发式算法也已经较成功地解决了确定性VRP中的一些问题。
2.2非确定性VRP
对应于确定性VRP，非确定性VRP指的是：（1）在路径规划开始之前，不是有关路径规划的所有信息，计划人员都是确切知道的，部分信息可能是不确定的、模糊的，甚至是未知的；（2）初始路径构建以后，信息可能会发生变化。很明显，与传统确定型VRP相比，非确定型VRP是一个更一般化的VRP问题。非确定性VRP又可分为随机VRP（SVRP）和模糊VRP（FVRP）。
（科教范文网 lw.nseaC.Com编辑发布） 2.2.1随机VRP
对这种类型的问题，目前出现的算法大部分可以归纳为以先验（即定）序列为基础的方法。该方法分为两个阶段：在信息不完全（随机）的情况下确定先验序列；在获得确定性信息的情况下进行决策。因此，其随机模型的选择基于两点：第一阶段的成本和第二阶段的期望成本。先验序列的确定方法又有两类：一类是按二元可能性理论来确定，另一类则是基于机会约束规划。
第一类方法的思想最早是在Jaillet的博士论文中提出的，并在Bertimas的博士论文中基本建立完整的体系。在该方法中，假定需求分布是二元（即在第i点有单位需求的概率为n，则没有单位需求的概率为）、离散的。根据该假定，可推出先验序列的期望长度，相应的上下界和渐进特性。Michel Gendreau等人以该理论为基础，得到目标函数和罚函数，以Clark-Wright算法生成初始解，然后用禁忌搜索算法对初始解进一步优化，可以求解规模为46的问题。而Laporte基于L-Shaped方法，提出一个精确算法，可解决规模小于50的问题。
另一类方法是Stewart，Laporte等人分别使用机会约束规划，在一定的假定条件下，将SVRP转化为等价的、确定性的VRP，并找到了解的界，其方法的核心是让出错返回的概率不超过一定的界限。机会约束规划模型均以确定性VRP的三下标流和二下标流模型为基础，添加可能性约束条件和罚函数后建立起来的。所用的算法，也与确定性的算法有不少相通之处。如M. Dror就是在建立三下标流机会约束规划模型和罚函数模型后，利用Clark-Wright算法进行求解的。
第二阶段的策略为：按照先验序列，跳过需求为零的客户，直接访问下一个客户，如果车辆负荷超过了车辆最大载重量，则返回出发点卸载，并回到出现超载的地方，继续提供服务。
（科教范文网 lw.nSeAc.com编辑发布）
2.2.2模糊VRP
D. Teodorovic等人是最早着手研究这类问题的人。他以模糊数表示客户点的需求信息，以倾向度为基础建立模糊判定规则，其核心是基于Sweep算法，并省略了Sweep算法的第二阶段，即初始化子路径后对它们的优化过程。
祝崇俊、刘民、吴澄等人以模糊可能性分布，建立了VRP的基于置信度的三下标流模型，并提出了基于可能性分布的2-OPT算法。该算法引入了伪出发点，建立了以置信度为基础的判定规则，以遍历为终止条件，从而在全局层次上进行优化，同时避免过多地扩大搜索空间。该算法已可解决较大规模的问题（大于200个客户）。
