下载文档原格式
物流配送车辆调度问题算法综述陈君兰;叶春明【摘要】Delivery vehicle routing problems （VRP） is a kind of optimization problems, aiming at solving the vehicle routing problems in delivery section. And they have been a focus of research in logistics control optimization recently. After summarize different kinds of VRP, the article gives the relevant general models. The character and the application of genetic algorithm, simulated annealing, tabu search, ant colony algorithm, particle swarm optimization are analyzed and the current possibilities to solve VRP are also discussed. Finally, the development of VRP solution is presented, and point out that improved combined algorithm as well as new algorithm will be important measures to solve VRP.%配送车辆调度优化问题旨在解决配送中路径和车辆调度问题的一类组合优化问题，是近年来物流控制优化领域的研究热点。
文章对运输调度问题进行了分类总结，给出总体模型的概括描述，分析遗传算法、模拟退火算法、禁忌搜索算法、蚁群算法和微粒群算法的特点及其在求解配送车辆调度优化问题中的求解思路，并讨论了其求解现状，对未来研究方向进行展望，指出改进混合现有算法，开拓新算法将是更有效解决配送车辆调度问题的好方法。
收稿日期:2005201220作者简介:张思伟(19812),男,辽宁鞍山人,硕士研究生,主要研究方向为系统工程、信息管理.单车场多送货点车辆调度优化的一种改进禁忌算法张思伟(天津大学管理学院,天津300072)摘要:为解决单车场容量约束车辆调度问题提出了一种改进禁忌算法。
在传统的禁忌算法思想中,它的解受算法的唯一初始解的状态影响很大,因此优化结果的稳定性得不到保证。
此改进算法使用多初始解和全局禁忌表,它能够减小解的不稳定性和扩大搜索范围。
与标准禁忌算法比较,它的全局搜索能力和稳定性都大大增强。
通过算例试验,取得了良好的结果。
关键词:车辆调度问题:禁忌搜索:容量约束中图分类号:U492.22;O211.1 文献标识码:A 文章编号:100727375(2006)0320055204An Improved T abu Search Algorithm (TS )for the Single 2depotV ehicle Scheduling ProblemZH ANG Si 2wei(School of Management ,T ianjin University ,T ianjin 300072.China )Abstract :In order to s olve the single 2depot and capacity constraint vehicle 2scheduling problem ,an im proved ta 2bu 2searching alg orithm (TS )is presented in the paper.F or a traditional TS alg orithm ,its s olution was greatly in 2fluenced by the state of the only initial s olution of the alg orithm ,and the stability of optimal s olution cannot be guaranteed.In this paper ,a multi 2initial 2s olution and global tabu table is used in the alg orithm to increase the stability and enlarge the search scopes.C om pared with the standard TS ,the proposed TS alg orithm has greatly in 2creased its global search ability and stability.Finally ,the paper gives s ome exam ples and shows g ood results from these experiments.K ey w ords :vehicle scheduling problem ;tabu 2search ;capacity constraints 车辆调度问题(Vehicle Scheduling Problem ,VSP )是一类重要的组合优化问题,在国内外应用非常广泛,如在传统汽车运输领域的牛奶配送、报纸投递、垃圾车线路优化、联锁店送货路线安排等。
基于禁忌搜索算法求解车间作业调度问题戚峰;俞晶菁;黄召杰【摘要】In this paper, we considered a limited economic lot and delivery scheduling in a simple supply chain where a single supplier produces multiple components on a flexible flow line and delivers them directly toan assembly facility. This supply chain consists of two large departments (production department and assembly department). First,variety of components need to be proceed in multiple workshop,and then they are sent to assembly departments to assemble into finished products. The main objective is to find a lot and delivery schedule that can minimize the average of holding, setup,and transportation costs per unit time for the supply chain. It has proved to be an NP-hard problem, so in order to find a satisfactory solution, tabu search algorithm is used to solve this problem. From the efficiency of algorithm in the numerical experiments, we can see that the effectiveness and efficiency are all well.%考虑了一个有限经济批量和交货时间计划的车间作业调度问题.在这条供应链上包含两个大的部门(生产加工部门和组装部门);多种工件首先需要经过加工部门多个车间的加工，然后送到组装部门组装成为成品；目标是如何组织安排各种工件在各个车间的各个机器上的加工顺序和加工开始时间使得此供应链上单位时间内的运输费，组装费和存储费用最小.此问题是一个NP难问题，为了找到满意解，本文利用禁忌搜索算法来解决此问题，并用MATLAB软件编写求解此问题的算法程序.从算法的数值试验过程来看，禁忌搜索的效率和效果均令人满意.【期刊名称】《兰州交通大学学报》【年(卷),期】2011(030)003【总页数】7页(P79-85)【关键词】运筹学；车间作业调度；禁忌搜索算法；供应链【作者】戚峰;俞晶菁;黄召杰【作者单位】兰州交通大学交通运输学院，甘肃兰州730070;兰州交通大学交通运输学院，甘肃兰州730070;兰州交通大学交通运输学院，甘肃兰州730070【正文语种】中文【中图分类】O221.20 引言车间作业调度(Job-shop Scheduling,JSSP)问题,是一个NP难(NP-hard)问题,是目前研究最广泛的一类调度问题,是最难的组合优化问题之一,也是计算机集成系统(CIMS)和企业资源计划(ERP)领域中研究的重要课题,具有重大的现实意义和深远的理论意义.车间作业调度问题大致可以描述为:有M台机器和N个工件,由于工件的加工工艺要求,每个工件使用M台机器的顺序以及每道工序所花费的时间给定,如何安排每台机器上工件的加工顺序,使得某种指标(如总的完工时间)最小.长期以来解决JSSP问题的方法以启发式算法为主,相对来说又以遗传算法居多,象文献[1-5]均是基于遗传算法来求解;该算法鲁棒性强,适应性好,已在各领域得到了广泛的应用,相对于传统优化算法显示出强大的优势;尽管遗传算法在许多领域取得很大成功,但也存在着严重不足,如早熟现象与欺骗问题,不能很好保持个体的多样性等,从而影响了其在一些领域中的正确性与有效性.禁忌搜索的思想最早由Glover(1986)提出[6],它是对局部临域搜索的一种扩展,是一种逐步寻优算法,是对人类智力过程的一种模拟,也是一种较新的启发式算法,它通过引入禁忌表和相应的禁忌准则的方式来避免迂回搜索,并通过特赦准则来赦免一些被禁忌的优良状态,进而保证多样化的有效探索;相对于遗传算法,禁忌搜索具有收敛速度快、局部搜索能力较强、较好的爬山能力等特点,已经成功的解决了许多组合优化问题;在文献[7-8]中利用禁忌搜索算法对两个相对简单的车间作业调度问题进行了求解,均取得了较好的效果;本文尝试利用禁忌搜索算法来求解[5]中的这个复杂的车间作业调度问题,以期在算法的效率、收敛性和问题的评价值三方面取得满意的结果.1 问题陈述文献[5]中考虑的是一个供应链,在这条供应链中,总体分为两个大的部分:加工部门和组装部门.加工部门的生产者在一条灵活的流水线上生产多种工件(或者零部件),每种工件必须经过m种工艺才能完成;每种工艺在不同的车间中完成,每个车间里有相同且相同地位的机器,每种工件的某种工艺只能在相应工艺车间的某一台机器上加工且一次完成;每个车间对每种工件有确定的需求率和生产率,上一个车间完成之后,如果下一个车间不需要则需要在本车间库存,所有工件的所有工艺完成之后,工件变成成品(以前是半成品),最后运送给组装部门进行组装(这个过程如图1所示).这种情况在汽车产业中非常常见,当然在别的一些产业中也常常出现.图1 同一周期的生产活动流程Fig.1 The production process in the same cycle 本文研究的是上面供应链上每种工件的生产批量和所有工件在每个车间里每台机器上的先后加工顺序以及加工开始时间问题.这里有很多参数(如每种工件的需求率)在整个计划时间里是确定不变的.这个供应链包含两个紧密相连的两个问题——一个离散的问题和一个连续的问题:离散的问题就是各个车间里各种工件分派给哪个机器以及分派给每个机器上的工件的先后加工顺序;连续的问题是每种工件的生产批量和在每个车间的加工开始时间.这个问题换句话来说,研究的是每个车间里每台机器上不同工件的加工先后顺序和什么时候开始加工的问题.最终的目标是使平均每单位时间内通过此供应链的运输费、组装费和存储费用最小(直观上相当于如何使图1中横截面最小).为了解决这个问题,本文把整个生产过程的供应链看成是由相同的生产周期组成,总的计划期限是这样周期的整数倍;因为目标是使平均每单位时间内通过此供应链的运输费,组装费和库存费用最小,所以在这里只需考虑一个共同的周期,这个周期包括所有生产活动(对所有工件的加工生产和生产加工完成之后投递给组装部门);用这种方法的主要好处是容易找到可行解、使模型简化、实际的操作更加直观和容易得到近似最优解等.2 数学模型2.1 问题的假设1)每种工件在每个车间必须加工,并且只能在一台机器上加工;2)每种工件在每个车间的批量是相同的;3)不同车间里的机器是连续利用的,每个车间里的每台机器一次只能加工一种工件;4)不允许缺货;5)加工部门产生连续独立的组装时间和费用; 6)组装部门的组装时间和费用忽略不计为零;7)从加工部门到组装部门的投递运输时间忽略为零;8)每个机器上的各种工件的加工先后顺序由算法确定;9)加工部门和组装部门的成品都产生线性的库存费用;10)加工部门的半成品(工艺还没有完成)产生线性的库存费;11)每种工件在加工过程中不能中断,即就是在给定的车间,每种工件一旦开始加工,必须一次性加工完成,不能中断;12)每种工件都加工完成后才能运送入下一个车间进行另一工艺的加工;13)生产过程中的库存是允许的,也就是下一个车间不需要,必须在本车间库存;14)每个车间的能力能充分满足需求,所以至少存在一个可行的批量和投递序列;15)总的计划期限长度是总的周期数的整数倍;16)每个周期每种工件直到它的库存为零时才开始生产.2.2 参数的定义n——工件的种类数m——工件要经过加工的车间数i,u——不同工件标识j——车间标识——车间j的机器数量——第j个车间的第k个机器——工件i的需求率——第j个车间i类工件的生产率——一批i工件在车间j的加工时间——工件i在所有车间总的组装费——工件i在车间j连续独立的组装时间A——每个周期总的的运输费用hij——工件i在车间j到车间j+1期间每单位时间、每个工件的库存费——工件i的成品在加工部门、组装部门每个产品单位时间的库存费H——总的计划时间长度M——一个很大的实数2.3 决策变量的定义σj——车间j的加工顺序向量σkj——车间j里第k个机器上的加工顺序向量T——一个周期的时间长度——不同车间里工件i的加工量F——周期数——工件i在车间j在相关的准备工作后开始加工时间2.4 目标函数目标是求单位时间内通过供应链的平均运输费,组装费和库存费最小;容易知道单位时间内通过供应链的平均运输费为单位时间的平均组装费为而库存费相对比较复杂,库存费产生在每种工件的加工过程中本车间的库存和加工完成后下一个车间暂时不需要以及需要是线性需要时本车间的库存,在这里需要考虑3种情况:1)当所有工件加工完成之后全部投递给组装部门,所有种类的工件在组装部门的库存量(如图2a所示).所有工件在一个周期内的所有车间加工完成之后全部送到组装部门组装,组装部门对每种工件的需求率是确定不变的,所以每种工件的剩余量是线性下降的,每种工件在一个周期内的库存量就是曲线与对应时刻的时间轴围成的面积,故总的单位时间库存i费用为2)每种工件在最后一个车间之前各个车间的库存费用(如图2b所示).每种工件在最后车间之前的各个车间里加工时,先是为零,随着加工的开始,开始线性上升(因为生产率确定不变)直到生产到相邻的下一个车间的需求量为止;下一个车间不一定立刻需要,所以有一段平行时间轴的的部分,最后随着下一车间对本车间的这种工件的需求,本车间的这种工件库存开始线性下降(需求率确定不变)直至为零.每种工件都经历这样相同的过程,每种工件在一个周期内的库存量就是曲线与对应时刻的时间轴围成的面积,故总的单位时间库存费用为3)每种工件在最后一个车间加工时的库存费用(如图2c所示).在加工部门最后一个车间的加工与前面的车间基本相同,不同的是每种工件在最后一个车间加工完成后就是成品,不需要再送到下一个车间加工,所以不会经历线性下降的过程,所以每种工件在一个周期内的库存量同样是曲线与对应时刻的时间轴围成的面积,故总的单位时间库存费用为图2 库存量变化情况Fig.2 Inventory level in three conditions in one cycle 由上面几种情况分析知道目标函数就是上面几种费用:(1)(2)(3)(4)(5)相加得:2.5 模型根据实际问题、问题的假设、定义的已知参数和决策变量建立的模型(模型一)为每个约束条件的含义:约束条件1)表示每个工件在前一车间没有完成,后一车间不能开始;约束条件2)表示如果某车间中只有一台加工机器,在这个机器上加工的相邻位置的两种工件,相邻的前面位置工件没有完成,相邻的后面位置工件不能开始;约束条件3)和约束条件2)基本相同,它是在车间里机器数大于一的情况下,每个机器上相邻的前面位置工件没有完成,相邻的后面位置工件不能开始加工;约束条件4)表示在某个车间里只有一台机器,每种工件只能在这个机器的加工顺序中安排一次;约束条件5)表示在某个车间里只有一台机器,则在这个机器上加工的工件顺序中,每个顺序位置只能安排一种工件;约束条件6)表示当某个车间里的机器数大于一时,每种工件只能安排在某个机器的加工顺序位上一次;约束条件7)表示当某个车间的机器数大于一时,每个机器的每种工件加工顺序位置最多安排一种工件;约束条件8)表示当某个车间的机器数大于一时,每台机器上的工件加工顺序位置中,如果前一位置安排了,则相邻的后一个位置可以安排;约束条件9)表示如果某个车间里只有一台机器,则在这台机器加工的工件必须在此工件组装完成之后才能开始生产;约束条件10)和9)相似,不同的是机器数大于一,每个机器上加工的工件必须在此工件组装完成之后才能开始加工加工;约束条件11)表示每种工件在最后一个车间加工结束时间不能超过生产周期T;约束条件12)、13)、14)分别表示整数、非负以及0～1约束.3 实现方法本文尝试用禁忌搜索解决这个问题.为了解决这个问题,从整个模型的约束条件来看,4)～8)与工件的加工位置顺序有关,是一个离散的问题;别的约束条件与工件的加工开始时间有关,可在任何时刻,是一个连续的问题.故可把模型分成两个部分:一个部分是各类工件在各个车间如何指派给机器以及它们在所指派的机器上的加工先后顺序(即加工的序列问题);另一个部分是当它们的顺序指定之后,确定各类工件在各个车间的开始生产时间以及总计划时间内整个周期的长度和周期数,这是一个非线性规划问题.当工件在所有车间的加工序列确定后,此时的模型一可以化简为模型二(去掉模型一中4)～8)约束条件).鉴于此,在这里,第一部分考虑用禁忌搜索来实现;而当第一部分的一种可行加工序列指定后,一定对应第二部——模型二下的一个最优解,即求一个非线性规划的最优解.一种可行的加工序列和其对应的模型二的最优解就构成整个问题的一个可行解.一般来说,解非线性规划问题要比求解线性规划问题困难得多,而且也不像线性规划那样有统一的数学模型及单纯形法这一通用解法.非线性规划的各种算法大都有自己特定的适用范围,都有一定的局限性,到目前为止还没有适合于各种非线性规划问题的一般算法.本文选择Matlab优化工具箱中提供的求解非线性规划的函数——fm incon来求解,编程相对简洁和直观.3.1 解的形式每个车间为n种工件的一个排列,如果某个车间的机器数大于1为台,那么将这个1～n的排列分成mi段(如★分段),一台机器只占其中一段(表1).表1 解的形式Tab.1 The form of solution车间1 2 … m-1 m排列1,2,…,n1,2,…,n … 1,2,…,★,…,n 1,2,…,n3.2 初始解初始解随机产生,例如有3个车间,每个车间一台机器(表2).表2 初始解Tab.2 Initial solution第一车间第二车间第三车间产生1～n随机排列产生1～n随机排列产生1～n随机排列3.3 邻域结构临域映射为对换两种工件的加工顺序位置的2 -op t,因为有多个车间,每个车间里的工件位置顺序都可以变换,即存在同时变化的情况,这样相对很复杂.为了解决这个问题,产生一个1～m的随机整数,由这个随机整数来确定变换哪个车间里的工件在各个机器上的先后顺序.例如有3个车间(m= 3)3种工件(n=3)的情况,在某次由当前最优解产生其临域时,产生1～3的随机整数为2,那么就变换第二个车间的位置顺序(图3).图3 临域产生方法Fig.3 Generation method in the demain3.4 候选集视问题的规模而定,当问题规模小,当前最优解邻居较少,采用全临域搜索;当规模大时,从邻居中选择若干个相对最优的邻居组成候选集.3.5 禁忌表和搜索策略禁忌对象:某个车间交换的两种工件(单向的).禁忌长度:大约为 n1(n1为当前最优解邻居的个数),在数值试验时根据计算结果再加以调整.特赦规则:如果当前候选集都被禁忌了,则选择当前候选集中评价值最小的,同时此对象的禁忌长度增加.3.6 终止条件经过试验,分别采用一个解找到的次数、连续无改进原则以及总的循环次数三种终止原则,从效果上看,都还不错.由于M atlab循环的效率较低,需要的时间相对较长,所以不宜采用总的循环次数限制作为终止原则;当采用连续无改进原则时,运行时间相对较短(连续30次无改进大约需要531.795 566 7 seconds左右);而采用一个解找到的次数为终止原则时,用的时间非常长,因为找到的近似最优解都带有几位小数,所以找到几次相同的解很难(除非是同一个加工序列,平均再次找到同一个解的概率为1/(C2n)m),故用时很长.综合上面几方面,采用连续无改进原则最合适,运算时间短,解的质量也能保证.(上面的实验规模为车间数为3,每个车间一台机器,工件种类为10).4 数值试验4.1 试验环境M atlab7.5(R2007b),CPU:AMD A thlon 64× 2 Dual Processor 4000+,主频:2.1,1G内存.4.2 试验参数的确定参数的取值如下[5]:4.3 禁忌搜索实验结果另外在规模(n=5,m=2)下,平均用时17.922 0 s,平价值的均值为66 627;6种规模下的收敛情况如图4所示.在每种规模下分别计算了十次,平均用时分别为:8 559.80 s、851.45 s、291.707 s、225.659 s、51.77 s和17.922 s,在同等规模下均比文献[5]用时少;评价值的变异系数分别为:0.055 7、0.130 8、0.062 8、0.110 6、0.127 7和0.092 1,波动幅度小;从6种规模下的收敛情况图看出,收敛性好;体现本算法的优越性.表3 试验结果Tab.3 Results of the experiment规模次数n=10,m=10n=10,m=5 n=10,m=2 n=5,m=10 n=5,m=5评价值时间/s 评价值时间/s 平均值时间/s 评价值时间/s 评价值时间/s 1 233 120 10 726.25 166 600 454.23 121 900 258.56 117 380 123.78 97 852 47.54 2 234 040 15 258.53 157 930 874.11 141 490 265.58 108 690 126.88 97 768 50.61 3 208 570 5 622.43 190 570 666.76 138 790 456.91 123 100 168.93 100 960 44.15 4 206 590 5 764.64 168 210 896.80 145 410 442.55 127 050 250.64 118 760 37.37 5 238 850 6 198.25 193 400 1 513.29 144 460 175.55 91 436 199.84 126 840 29.32 6 208 570 5 820.32 135 050 935.41 141 120 339.89 128 540 363.53 83 974 56.81 7 238 850 6 336.70 176 590 801.46 145 140 266.69 124 020 213.11 88 181 74.41 8 224 070 10 484.28 148 810 566.30 132 060 261.50 127 640 380.17 101 720 43.01 9 224 310 6 899.05 135 160 1 013.36 137 600 267.72 141 380 233.28 94 301 74.22 10 224 860 12 487.18 144 280 792.79 123 490 182.12 119 240 196.43 102 200 60.26均值 224 183 8 559.80 161 660 851.45 137 146 291.707 120 850 225.659 101 256 51.77图4 6种规模的收敛性Fig.4 The convergenceon six scales5 结束语禁忌搜索算法已经较好地应用于许多组合优化问题,本文利用此算法来求解一个有限经济批量和交货时间计划的车间作业调度问题.从禁忌搜索的数值试验结果来看,效率高,收敛性好,评价值波动幅度小,体现了本算法的优越性,达到了预期的目标.但是也存在一些不足:当规模增大时,运算的时间增加较快;这主要是由三个方面的原因造成的:一是规模的增大;二是程序中需要写很多循环结构,而M atlab处理循环结构的效率较低,需尽量避免;三是每迭代一次需要多次求解一个连续的非线性规划模型(模型二),即使计算一次此非线性规划模型, Matlab也需要迭代多步,而且会随模型的增加而增加;C语言处理循环的效率很高,如果改用C语言编程或者M atlab和C 语言混合编程效率应该要更高一些.参考文献:【相关文献】[1] 安晶,秦珂.一种基于遗传算法的车间调度算法求解[J].盐城工学院学报,2007,20(1):33-36.[2] 纪树新,钱积新,孙优贤.遗传算法在车间作业调度中的应用[J].系统工程理论与实践,1998(5):34-39.[3] 陈伟达,达庆利.工艺线可变车间作业调度的两级遗传算法[J].系统工程学报,2002,17(2):161-166.[4] 张超勇,饶运清,李培根,等.求解作业车间调度问题的一种改进遗传算法[J].计算机集成制造系统,2004,10 (8):966-970.[5] Torabi SA,Fatem iGhom i SM T,Karimi B.A hybrid genetic algorithm for the finite horizon econom ic lot and delivery scheduling in supp ly chains[J].European Journal of Operational Reseach,2006,173(1):253-258.[6] G lover F.Future paths for integer programm ing and links toartificialintelligence[J].Computer&Peration Research,1986,13(5):533-549.[7] 黄志,黄文奇.一种基于禁忌搜索技术的车间作业调度算法[J].小型微型计算机系统,2005,26(2):222-225.[8] 邓泽林,黄文奇,周立刚.求解车间作业调度的快速禁忌搜索算法[J].华中科技大学学报,2003,31(11):1-3.。
毕业设计物流调度中的混合人工智能算法目录摘要 0Abstract (2)1 引言 (4)2 车辆优化调度问题的描述 (6)2.1 组合优化问题的描述 (6)2.2 车辆调度问题的数学模型 (6)3 主要人工智能群算法研究 (8)3.1 人工鱼群算法原理及其模型 (9)3.1.1 人工鱼群算法原理 (9)3.1.2 人工鱼群的数学模型 (10)3.1.3 人工鱼群算法 (14)3.2 人工蜂群算法及其模型 (15)3.2.1 人工蜂群算法原理及数学模型 (15)3.2.2 人工蜂群算法步骤 (17)4 人工鱼群算法在VRP问题上的改进 (19)4.1 人工鱼群算法的传统处理方法 (19)4.1.1 初始化种群 (19)4.1.2 食物浓度的计算 (21)4.1.3 人工鱼行为的设计 (22)4.1.4 行为选择 (25)4.1.5公告栏 (26)4.2 传统处理方法的改进 (26)4.2.1 基于相似片段的距离 (26)4.2.2 基于相似片段距离的人工鱼觅食行为 (27)4.2.3 人工鱼视域的改变 (28)4.3传统处理方法与改进的方法的实验对比分析 (28)4.3.1 实验参数的设置 (29)4.3.2 实验结果及对结果的分析 (29)5 混合人工蜂群—鱼群算法及VRP应用研究 (32)5.1人工蜂群算法和人工鱼群算法的优缺点分析 (32)5.2 混合人工智能算法的设计 (34)5.3 混合人工蜂群—人工鱼群算法示意图 (35)5.4 混合人工蜂群—人工鱼群算法的实现 (35)5.5 基于混合人工蜂群—人工鱼群算法的VRP问题求解 (36)5.5.1 人工蜂行为的设计 (36)5.5.2 公告栏 (37)6 混合人工智能算法的实验结果分析 (38)6.1混合人工智能算法的参数设置 (38)6.2三种人工智能算法的实验结果 (38)6.3 实验结果的分析 (40)7 结束语..................................................................... 错误!未定义书签。
VRP的数学模型及算法分析什么是VRP？VRP（Vehicle Routing Problem）是一种典型的物流优化问题，通常指有一组车辆要从不同的位置出发，经过一些需要配送的地点，最终回到起点。
在这个过程中，需要最小化配送车辆的总里程数，以节省时间和成本。
VRP的数学模型VRP的数学模型可以用图论来描述，将出发点、配送点、和终点分别看作图的节点，车辆之间的移动和节点之间的连线看作图的边。
根据不同的VRP问题，图的连线可以有不同的权值，最小化车辆的总行驶距离即为这个问题的最优解。
下面是VRP最基本的模型，也是以前由Dantzig等人提出的模型：•定义一个图G(V,A)。
•定义图G中的顶点v表示送货点或机器人停憩点，称之为客户点或节点。
还要定义一个起始点和终止点。
•定义它的边属性为a ij，表示从节点i出发到节点j的距离或费用，也可以添加一定的时间和容量限制。
•定义集合S，表示所有的车辆集合。
•对于每个点j,定义各种费用和量：d j整个环节中与顾客j有关的相关费用；t ij是从顾客i到顾客j的行驶时间；q j是顾客j的需求量，对于机器人调度问题，也可以看作是机器人的加载量。
•定义每个车辆的最大容量限制为Q。
VRP常见的算法对于VRP问题，有许多经典的算法和启发式算法：精确算法分支定界法分支定界法是一种求解最优解的精确算法。
通过递归思想，将原问题细分成子问题，对于每个子问题，根据可行解证明和界限函数计算的下界，判断是否需要继续递归。
通过不断地细分问题，最终可以求出最优解。
工业分支定界法工业分支定界法认为节点i到j的费用（距离）a ij是个整数，并且车的数量有限制。
该算法可以检查可选顾客的选择性，以及问题的任何线性松弛。
启发式算法启发式算法主要用于求解大规模问题时的近似解。
常见的算法如下：遗传算法遗传算法是一种进化计算方法，在VRP问题中，它的优势是可以通过多样化的个体生成更好的解，例如不同的车辆数目，不同的节点距离排序等。
基于混合遗传算法的物流配送车辆调度优化问题求解方法廖良才;王栋;周峰
【期刊名称】《系统工程》
【年(卷),期】2008(26)8
【摘要】物流配送车辆调度优化问题是一个NP-hard问题,随着问题规模的扩大,若单纯地应用精确算法将很难获得最优解。
首先对物流配送车辆调度问题进行了深入分析并建立了优化数学模型;然后,根据模型把问题的解决合理地划分为两个阶段,将遗传算法的全局搜索能力和C-W节约启发式算法的局部搜索能力有机结合,由此构造出一种混合遗传算法;最后,通过一个应用实例的分析验证了此算法寻优的有效性。
【总页数】5页(P27-31)
【关键词】组合最优化;物流配送;遗传算法;节约算法;车辆调度
【作者】廖良才;王栋;周峰
【作者单位】国防科学技术大学信息系统与管理学院
【正文语种】中文
【中图分类】O221
【相关文献】
1.基于混合遗传算法的物流配送模糊车辆调度问题研究 [J], 封全喜;刘诚
2.基于遗传算法的物流配送车辆调度优化模型研究 [J], 王海宾;刘霞;高欢
3.基于遗传算法的物流配送车辆优化调度 [J], 王素云;李军
4.基于遗传算法的物流配送车辆优化调度 [J], 王素云;李军
5.基于混合量子遗传算法的外贸企业物流配送车辆优化调度 [J], 赵辉
因版权原因，仅展示原文概要，查看原文内容请购买。
中图分类号:TP273文献标识码:A文章编号:1009-2552(2010)11-0009-05禁忌算法在集装箱码头装卸调度中的应用徐斌,杨德礼(大连理工大学管理学院,大连116021)摘要:集装箱码头装卸调度是研究集装箱装卸工序的组合优化问题,对提高码头生产效率具有重要意义。
该问题属于N phard问题,在形式上非常类似于混合流水车间调度问题,但由于其装卸设备和船舶结构的物理特性比H FS更具复杂性。
文中建立了该问题的数学模型,基于禁忌规则,提出邻域构造和基于Key L i n e和作业制约的邻域收缩方法,结合实例描述了禁忌搜索算法的实现原理。
关键词:禁忌搜索;领域设计;集装箱码头装卸调度Applicati on of t abu searc h i n container ter m i na handli ng sc heduli ngXU B in,YANG De-li(SchoolM anagemen t Da lian Un iversity of T echnology,D alian116021,Ch i na)Abstract:Container dock handli n g schedu li n g is a co mb i n atoria l opti m izati o n proble m.It has i m portant sign ificance to i m prove the dock producti o n effic i e ncy.Th is prob le m be longs to NP-hard proble m s.It is ver y si m ilar to hybri d flo w shop schedu li n g i n the fo r m.But it ism ore co m plex than H FS because of the physica l properties o f sh i p structure and handli n g equ i p m en.t This paper estab lishes a m athe m atical m ode l o f this prob le m.And based on tabu rules,th is paper proposes the nei g hbo r hood structure and ne i g hborhood shrinkage m ethod based on K ey L i n e and assignm ent restriction.Co m b i n i n g i n stances,th is paper illustrates t h e rea liza ti o n pri n ciple of tabu search algo rithm.Key words:tabu search;neighbor hood desi g n;conta i n er ter m i n al hand li n g scheduling0引言集装箱码头装卸调度是研究集装箱装卸工序的组合优化问题,形式上非常类似于混合流水车间调度问题(HFS),属于NP-hard问题[1]。
