搜索
VRP启发式算法VRP算法分类精确算法启发式算法分枝界定法割平面法网络流算法动态规划法构造启发式算法改进启发式算法亚启发式算法最邻近法(1977)最近插入法(1976)禁忌搜索法(1986,1991)C-W节约法(1964)遗传算法(1975,1996)神经网络算法(1943,2000)模拟退火法(1953,1993)扫描算法(1974)k-opt算法-interchange算法蚁群算法(1991,2003)两阶段算法(1979)粒子群算法(1995)•Constructiveheuristicsgraduallybuildsafeasiblesolutionwhilekeepinganeyeonsolutioncost,butdonotcontainanimprovementphaseperse.(LaporteandSemet[2002]).TrendsinHeuristics•MorecomplexandrichVRPs•Fasterheuristics(disregardingincreasingcomputerspeeds)thatstillproduceshighqualitysolutions•Abilitytohandlelargerinstances•Morepreciseheutistics(bettersolutionqualitywithoutworryingoverlyaboutthetimeneededforthecomputation)•Simplerheuristics•Heuristicsusingmathematicalprogramming(combiningideasfromexactoptimizationwithheuristics)•Parallelimplementations•Morerealistictestinstances一、构造启发式算法•最邻近法算法步骤：1)任取一点作为线路的起点．2)寻找与上一次加进线路中的点距离最近的点，把此点加到线路中去．3)重复2)，直到所有的点都已考虑，这就得到了一条线路．ji123456781-8591213121728-8151771114358-781071249158-31711165121783-1811156137101718-8871211711118-58171412161585-14235678例：•练习•现有一食品公司，位置在v1处，每天用一辆车给固定区域内的5家超市送货，要求货车到每个超市只能去一次，送完货后返回公司，各点之间的距离如下表所示，其中，距离具有对称性，设计一条派送货物的行驶距离最短的路径。V1V2V3V4V5V6V1986712V296151816V3861487V461514410V5718846V612167106一、构造启发式算法•最近插入法•最近插入法（NearestInsertion）是Mole和Jameson于1976年提出的用于求解VRP的一种启发式算法。•算法步骤：–从一个节点出发，找到一个最近的节点，形成一个往返式子回路；–在剩下的节点中，寻找一个离子回路中某一节点最近的节点；–再在子回路中找到一个弧，使弧的两端节点到刚寻找到的最近节点的距离之和减去弧长的值最小，实际上就是把新找到的节点加入子回路以后使得增加的路程最短，就把这个节点增加到子回路中,删去这条弧；•重复以上过程，直到所有的节点都加入到子回路中。•最近插入法关键是依序选择最合适的未分配的节点在路线中进行最佳位置的插入,以构建配送路线,直至不存在可行插入节点时新增一条初始路线。例各点之间距离如图所示，运用最近插入法求解最优路径。ABCD364246205240E655070解：从A点出发，找到一个最近的节点B，形成一个往返式子回路；在剩下的节点中，寻找一个离子回路中A/B最近的节点，得到D，加入子回路中。ABCD364246205240E655070对于C点，再在子回路中找到一个弧，使弧的两端节点到C点的距离之和减去弧长的值最小。即d（C,A）+d（C,B）－d（A,B）52+46-20mind（C,D）+d（C,B）－d（D,B）=42+46-40=48d（C,D）+d（C,A）－d（A,D）70+50-36则去除线路BD，加入线路BC和CD。其余点重复以上过程，直到所有的节点都加入到子回路中。•练习•现有一食品公司，位置在v1处，每天用一辆车给固定区域内的5家超市送货，要求货车到每个超市只能去一次，送完货后返回公司，各点之间的距离如下表所示，其中，距离具有对称性，设计一条派送货物的行驶距离最短的路径。V1V2V3V4V5V6V1986712V296151816V3861487V461514410V5718846V612167106一、构造启发式算法算法思想：设有n个城市（点），取其中的一点，例如点1，作为配送中心，先将每个点与起点相连，构成线路1－j－1(j=2,3,…,n)，即n–1条仅含一个访问点的线路，总费用为：122njjZc其中，假设c1j=cj1．然后，计算将i和j（i,j≠1）连接在一条线路上所引起的路程节约值S(i,j)）：S(i,j)=2c1i+2c1j－(c1i+cij+c1j)=c1i+c1j－cijS(i,j)越大，说明把i和j连接在一起使总费用减少越多，根据S(i,j)的大小来构造线路，就有可能得到总费用较小的解。C-W节约算法算法步骤：1)选取起点，将起点与其它各点连接，得到n–1条线路1－j－1（j=2,3,…,n）；2)对不违背限制条件的所有可连接点对(i,j)计算节约值S(i,j)=c1i+c1j－cij；3)将算出的S(i,j)0，按从大到小的顺序排列；4)按照Sij的上述顺序，逐个进行检查，若存在两条这样的线路，一条包含弧或边（i,1），另一条包含弧或边（1,j），且合并后能保持解可行，则引入弧或边（i,j）将两条线路合并，并删去（i,1）和（1,j）。重复该步骤，直到没有可合并的线路为止。5)返回步骤4)，直至考察完所有可插入弧(i,j)为止。例用C-W节约算法求下述的旅行商问题，其中点1为起（终）点，各点对间的距离由下表给出．ji123456781-8591213121728-8151771114358-781071249157-31711165121783-1811156137101718-8871211711118-58171412161585-(1)将各点分别与点1相连，组成7条线路.(2)计算节约值S(i,j)=c1i+c1j－cij．如S(2,3)=c12+c13－c23=8+5－8=5．(3)将算出的S(i,j)按从大到小的顺序排列于下表中．(4)按照S(i,j)的大小顺序，考虑连接点i和点j．弧(i,j)(7,8)(6,8)(4,5)(6,7)(5,8)(2,6)(5,7)S(i,j)24221817141413弧(i,j)(2,8)(4,7)(4,8)(3,7)(3,8)(2,7)(3,5)S(i,j)111010101098弧(i,j)(3,6)(3,4)(5,6)(4,6)(2,3)(2,5)(2,4)S(i,j)8775532•练习：•现有一个仓库v0，需要对8个客户提供货物，它们的如下表所示，它们的距离矩阵如下表所示，假设每个车辆的运输能力是14个单位的货物，现有足够多的车辆，试用扫描算法对该运输问题进行求解。cijv0v1v2v3v4v5v6v7v8v0111010712131113v11581614151615v26151618812v31213131211v47548v52109v61110v74v8cij需求量v16v24v35v43v56v62v73v84例某配送中心P向10个客户A~J配送货物，其道路网如图1所示。图中连线上的数字表示两结点间的距离（km），各客户点旁括号内的数字表示该客户的需求量（t）。配送中心有载重量为2t和4t的两种车辆可供使用，但车辆一次巡回的行驶距离不能超过30km。试制定其最优的配送线路。D(0.4)5C(0.8)5B(1.5)6247E(1.4)5691048A(0.7)765P7J(0.6)4343410811F(1.5)6G(0.6)29H(0.8)I(0.5)解下面用C-W节约法求解。第一步：根据给出的相邻节点间的距离，求出配送中心至各客户点、各客户点间的最短距离。见下表。表最短距离ABCDEFGHIJPABCDEFGHI1097888341074914181813141145101417121315859151011171361311121815710121815Cij681715211109118第二步：根据最短距离表，计算节约值sij，结果见下表。计算结果有正有负，节约值sij为负数时，无实际意义，故取值为零。表节约值ABCDEFGHIJABCDEFGHI1584000091311730004810600001103000091000sij5410520509第三步：将所有的节约值sij按从大到小的顺序排列，见下表。表节约值排序连接点节约值连接点节约值A~BA~JB~CC~DD~EA~IE~FI~JA~CB~JB~DC~E15131110109998876F~GG~HH~IA~DB~IF~HB~ED~FG~IC~JE~GF~I555444332111第四步：按照节约值sij的大小顺序，以及车辆载重量和行驶距离的限制，逐步构造配送线路。初始线路。对每一个客户分别单独派车送货，如下图所示。形成了10条初始配送线路。D(0.4)C(0.8)2B(1.5)796E(1.4)8P10A(0.7)57J(0.6)3410F(1.5)3G(0.6)H(0.8)I(0.5)线路合并。按照节约值sij的大小顺序，连接A~B、A~J。D(0.4)C(0.8)2B(1.5)7964E(1.4)8PA(0.7)5743410J(0.6)F(1.5)3G(0.6)H(0.8)I(0.5)连接B~C，形成配送线路I。此时该线路的总需求量为3.6t，线路长度为27km。按照sij的大小顺序，现在应考虑是否将C~D连接到配送线路I。但若将C~D连接到该线路，线路长度将超过30km，不可行。D(0.4)C(0.8)25B(1.5)764E(1.4)8P线路IA(0.7)57J(0.6)43410F(1.5)3G(0.6)H(0.8)I(0.5)接下来，连接D~E，开始构造配送线路II。重复该步骤，直到没有可合并的线路为止。得到的最终解如下图所示。共构造出3条配送线路。总的行驶里程为80km。D(0.4)C(0.8)25B(1.5)676E(1.4)线路IIP线路I,27km,3.6t430km,3.9tA(0.7)77J(0.6)43410F(1.5)线路III23km,1.3t6G(0.6)H(0.8)9I(0.5)一、构造启发式算法•扫描算法–扫描算法(SweepAlgorithm)最早是由Gillett和Miller（1974）提出的，是用于求解车辆数目不限制的VRP的一种启发式算法。–扫描算法本质上是将距离近的客户归并到一个子路径中。扫描算法步骤：Step1建立极坐标系Step2分组Step3重复2的过程Step4线路优化Step1建立极坐标系•以起始点（配送中心）作为极坐标的原点，并以图中的任意一客户点和极点（配送中心）的连线定义为角度零，建立极坐标系，然后对所有的客户所在的位置进行极坐标系的变换，把所有客户点全部都转换为极坐标系下的点。STEP2分组•从最小角度的两个客户开始，建立一个组，按逆时针或者顺时针方向，将客户逐个加入到组中，直到客户需求总量超过了车辆负载限制时，结束该条线路。STEP3重复STEP2的过程•建立一个新的组，继续按照逆时针或者顺时针方向，将客户继续逐个加入到组中，生成新的线路，直到所有的客户点都被分到某个组为止。STEP4线路优化•对各个分组内的客户群就是一个个单独