工厂内车辆调度模块设计与实现

《工厂内车辆调度模块设计与实现》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、·1.2国内外研究现状车辆路径问题很早就被提出，问题提出后，众多研究者对该问题以及由此引发的相关问题进行了普遍和深刻的探索，截止到现在，研究已经获得了令人瞩目的成绩，但是由于实际问题在建模和求解等方面的复杂性，使得该问题仍然是当前研究的热点问题之一。在研究车辆路径问题时，学者们综合考虑配送中心的个数，客户的时间约束，运送车辆的车型种类，运送过程中装卸方式（是否集货）等因素，形成了众多相关的子问题。1.2.1国外研究车辆路径问题（VRP）在上世纪60年代末被提出，问题提出后便引来了各学科专家学者的重视。该问题可看成是旅行商问题（TSP）

2、的延伸，车辆调度的每个路径都是一个旅行商问题，旅行商问题已经被证明是NP难题，所以VRP是比TSP更复杂的NP难题。一般的，车辆路径问题可以这样描述：对用户需求点安排合理的线路让车辆能够经过每一个需求点，在满足一个或多个限制（如需求时间、车辆载重、节点需求量）下，完成特定的目的（距离最小、成本最少等）。国外专家学者对VRP问题的研究已经有了很长时间，1983年Bodin等人[1]在文章中就已经列举了上百篇文章对该问题进行了综述，1988年Golden和Assad[2]出版了针对此问题的论文集，在接下来的几年里，Altinkemer和G

3、avish[3]，Laporte[4-5]等人也在其文章中对该问题进行了详尽的阐述。其中针对此问题解法有精确算法和启发算法，其中精确算法能求得最优解，研究较多的精确算法有以下几种，MarshallLFisher[6]的最小K树法，GilbertLaporte等人的分枝定界法[7]，Dumas等人结合分枝定界法进行集分割的割平面法[8]，Dethloff等人的基于网络的方法[9]，Kohl等人的拉格朗日松弛算法[10]，Fumeor等人的修正拉格朗日松弛及子梯度优化方法[11]，Eilon等人提出的动态规划法[12]，LorenaLui

4、z[13]等的改进对列生成法等。虽然精确算法能求最优解，但是精确算法在求解大型VRP实际问题时存在诸多问题，如该方法建模及求解比较复杂，适应性差等，有时很难或者根本不能求得最优2···解。启发式算法是求解VRP问题的重要方式，因为启发算法种类繁多，我们将其划分为经典和智能两种。其中经典启发法我们参照CesarRego的方法将其分成“构造法”和“两阶段法”[14]。构造启发算法有摩尔和詹姆森在1976年提出的插值法[15]，即每次往路线里调整入新节点，并能够让路程增加最短；克拉克和莱特在1964年提出C-W节省法[16]，即以节约成本最

5、多的方式进行求解，当无法再节省时结束，后来有人对节省算法进行了不断改进并加入其它约束条件使其与实际更加紧密联系，这些改进包括Nelson[17]于1985利用数据结构对算法进行的优化，Yellow[18]等人对节约计算方法的改进；Gillett等人于1976年提出的扫描构造法[19]，即将位置靠近的节点安排进一个路径中。“两阶段”启发法，就是分两个步骤进行，一般的在第一步先用构造法得到一个解，第二步再对所得到的解进行优化；有人对两阶段法进行了改良，有k-opt法，即将k条边（弧）交换从而达到调整初始解的目的，一直到不能再优化终止，Li

6、n于1965年提出的2-opt、3-opt算法[20]即是此种算法，另外Orloff于1976年提出的Or-opt算法[21]，也是常用的改进方法；其他的两阶段启发算法还有Renaud等于1996年提出的改进的花瓣算法[22]，Toth等人于1999年提出的聚类算法[23]等。智能启发式算法是于20世纪九十年代伴随着人工智能及机器学习等技术发展起来的，这类算法多是受到外界事物启发产生，该类算法常在求解复杂VRP问题时有着自适应性强，求解性能好等优点。其中遗传算法最早由美国的霍兰德教授按照自然生物遗传现象在1975年提出[24]，该方法

7、一出现就被用求于解各种工程问题，J.Lawrence[25]于1996年最早将该算法应用到车辆路径问题并求解了有配送时间约束的问题，后来应用此算法求解各种不同约束种类的车辆问题的研究不断增多，如Roger[26]对多车场有时间约束问题的求解，GeonwookJeon[27]等人对多车场多车型问题的求解等。模拟退火法是梅特罗波利斯仿照退火现象并基于蒙特卡罗迭代提出的，Tarantilis[28]等人于1983年最早将该算法求解组合优化问题，后来，Osman[29]用此方法求解VRP问题，Robert[30]等人运用此方法研究了有时间限制

8、的VRP等。禁忌搜索法由格洛弗提出的，该方法是为了防止陷入局部最优而对其进行禁忌进而达到全局搜索的算法，Gendreau[31]等人于1994年最早用该方法求解了车辆路径问题，后来此方法求解越来越多，如ÉricTaill