现代物流学-2第12章-课件

现现 代代 物物 流流 学学第第12章章 货物运输的优化求解货物运输的优化求解Chapter 12 Freightage Optimization 主要内容主要内容：产销运输问题，分配运输问题，网络流问题，送货集货问题的模型建立、求解过程。重点掌握重点掌握：产销运输问题，分配运输问题，网络流问题，送货集货问题模型建立、最优解求取。7/7/20241货物运输的优化求解：货物运输的优化求解：第一节 产销运输问题第二节 分配运输问题第三节 网络流问题第四节 送货集货问题7/7/20242现现 代代 物物 流流 学学12.1 产销运输问题产销运输问题12.1 Production and Sale Transportation Problem 12.1.1 产销平衡的运输问题产销平衡的运输问题 12.1.1.1 模型分析模型分析 某种物资有m个产地A1,A2,Am，其供应量分为a1,a2,am；有n个销地B1,B2,Bn，其销量分为b1,b2,bn；产地物资供应量总和等于销地物资销量（需求量）总和；从产地Ai到销地Bj的物资量和单位物资运价分别为xij,cij，求此时调运物资最佳方案。7/7/20243现现 代代 物物 流流 学学对此问题可有下述线性规划模型：对此问题可有下述线性规划模型：7/7/20244现现 代代 物物 流流 学学 12.1.1.2 表上作业法求解表上作业法求解 根据上述模型的特殊结构而建立的表上作业法比起用单纯形法要简单得多。其思路为：由初始运输方案开始，通过检验、改进，最后获得最优运输方案。设有两个煤矿供应三个城市用煤，煤矿A1和A2的日产量分别为a1=200t；a2=250t。三城市（B1,B2,B3）的日销量分别为b1=100t，b2=150t，b3=200t。假定每t货物的社会运输费与出行公里线性有关，取cij代表煤矿i至城市j的最短距离。已知c11=90km，c12=70km，c13=100km，c21=80km，c22=65km，c23=80km。问如何安排运输时运输费用最省？例例7/7/20245现现 代代 物物 流流 学学 解：设xij为煤矿i 运往城市j 的煤量，根据每个煤矿产煤总量和城市的用煤总量，xij(i=1,2;j=1,2,3)必须满足下列条件：x11+x12+x13=200 x21+x22+x23=250 x11+x21=100 x12+x22=150 x13+x23=200目标函数为：minz=90 x11+70 x12+100 x13+80 x21+65x22+80 x23。7/7/20246现现 代代 物物 流流 学学1、列运输平衡表、列运输平衡表 列表时要求表内供销平衡，并将运费标入表内空格。需供B1B2B3供应量A1x1190 x1270 x13100200A2x2180 x2265x2380250需求量1001502004507/7/20247现现 代代 物物 流流 学学 2、建立初始调运方案、建立初始调运方案 采用最小元素法，即在平衡表中挑取运价最小或较小的供需点格子尽量优先分配的调运方法。需供B1B2B3供应量A109070200100200A2100801506580250需求量1001502004507/7/20248现现 代代 物物 流流 学学 3、方案的检验和调整、方案的检验和调整 （1）闭回路。从调运方案的任意空格出发，沿水平方向或垂直方向前进，而遇到填有数字的方格，折转90o前进，当然可以直接穿过数字格和空格，但只能遇有数字的格才能折转，只能水平、垂直方向前进，不能对角线移动，这样经过多次折转直到回到原来出发的空格，形成一条闭回路。（2）位势法检验 由方案表列出检验表。表中行列数与方案表一样，运价在每一格的右上角，原方案表中的空格填写检验数，原方案表中的数字格为检验表的空格，原方案表中的供应量、需求量写行与列的位势，称为行或列位势格。7/7/20249现现 代代 物物 流流 学学需供B1B2B3uiA10907020010090A210080150658080vj0-1510位位 势势 表表 求检验数。若空格位于第i行第j列，则其检验数ij按下式求出：ij=cij-ui-vj 求位势。记第i行位势为ui，第j列位势为vj，通常可任选一格填0作为该格的位势。而其他格位势可由则可求得：cij=ui+vj。7/7/202410现现 代代 物物 流流 学学需供B1B2B3uiA190-57010090A28065-108080vj0-1510检 验 数 表 由上表可知，存在负的检验数，表明不是最优的，需要进行调整。7/7/202411现现 代代 物物 流流 学学 （3）调整运输方案 确定闭回路。在需调整的运输方案表上选取对应的检验数为负的且绝对值最大的格为检验格，从检验格出发在运输方案表上作闭回路。需供B1B2B3供应量A109070200100200A2100801506580250需求量100150200450闭 回 路 表7/7/202412现现 代代 物物 流流 学学 在闭回路上做运输量最大的调整，得出新的运输方案。从空格开始，沿闭回路在格偶数格中挑选运量最小的作为调整量，调整闭回路各点的运输量。需供B1B2B3供应量A11009070100100200A2801506510080250需求量100150200450新运输方案1表7/7/202413现现 代代 物物 流流 学学 由于上表中有负检验数，故需继续进行调整，得新运输方案表。需供B1B2B3供应量A11009010070100200A280506520080250需求量100150200450新运输方案2表7/7/202414现现 代代 物物 流流 学学对新运输方案表进行检验。需供B1B2B3uiA190701510090A2-580658085vj0-20-5新运输方案2检验表7/7/202415现现 代代 物物 流流 学学继续进行调整。需供B1B2B3供应量A1509015070100200A250806520080250需求量100150200450新运输方案3表7/7/202416现现 代代 物物 流流 学学 此时，检验数全是正数，因此运输方案3表中的运输方案为最优方案。需供B1B2B3uiA190701010090A2805658080vj0-200新运输方案3检验表7/7/202417现现 代代 物物 流流 学学 12.1.2 产销不平衡时的运输问题产销不平衡时的运输问题 2、销大于产的运输问题 对于销量大于产量，即 的运输问题，必然有一些销地不能得到满足，发生缺货，此时引入虚拟供应点，并设其相应运价为0。这样，就可以用产销平衡的表上作业法求解销大于产的运输问题。1、产大于销的运输问题 对于产量大于销量，即 的运输问题，必然有些产地的产品不能安排运输，此时引入虚拟需求点，令其需量等于总供量与总需量之差，并设其相应运价为0。这样，就可以用表上作业法求解产大于销的运输问题。7/7/202418现现 代代 物物 流流 学学12.2 分配运输问题分配运输问题12.2 Assignment Transportation Problem 12.2.1 模型分析模型分析 某材料厂有B1、B2、B3三台叉车可分配给A1、A2、A3三个仓库进行搬运作业，其中任一叉车都可以再任一仓库进行搬运工作，只是搬运作业费不同，各台叉车相应作业费cij，如表所示，要求一台叉车只分配给一个仓库使用，试求搬运作业费用最小的分配方案。7/7/202419现现 代代 物物 流流 学学效率矩阵表171922B3242015B2353125B1A3A2A1仓库 cij叉车根据问题引入变量xij，并按以下规定取值：其中，i=1,2,n；j=1,2,n。7/7/202420现现 代代 物物 流流 学学当问题要求极小时，有数学模型：7/7/202421现现 代代 物物 流流 学学 12.2.2 匈牙利算法匈牙利算法 匈牙利算法的主要依据主要依据：在效率矩阵的任何行或列中，加上或减去同一常数，并不改变最优分配。利用此性质，可使原效率矩阵变换为含有很多0元素的新效率矩阵，找出在其中的位于不同行、列的n个独立的0元素，将其取值为1，其他元素取值为0，即的原分配问题的最优解。7/7/202422现现 代代 物物 流流 学学 效率矩阵为：例题第一步第一步：变换效率举阵，使其每一行和每一列都至少有一个0元素。7/7/202423现现 代代 物物 流流 学学 第二步：试求最优分配方案。从1行开始，依次检查各行，找出只有一个未标记的0元素的行，并讲该元素用“”表示，与该元素同行同列的其他0元素则用“”表示。对应的任务仅由所对应的单位去完成，此单位不再去完成其他任务，这项任务也不再由其他单位完成。依次检查各列，找出只有一个未标记的0元素的列，并讲该元素用“”表示，与该元素同行同列的其他0元素则用“”表示。重复上述步骤，直到效率矩阵中没有未标记的0元素。7/7/202424现现 代代 物物 流流 学学0第三步第三步：继续调整效率矩阵。对每一个 元素画一条水平线或垂直线，使这些线覆盖所有0元素。在直线不穿过的所有元素中找到最小元素。在没有水平线的各行减去此最小元素，有垂直线的各列加上此最小元素，得到新的效率矩阵。-1-17/7/202425现现 代代 物物 流流 学学已经得3个0元素，故得最优分配方案为：A1B1，A2B2，A3B3则，根据原效率矩阵，3叉车总搬运作业费为：25+20+17=60（元）第四步第四步：回第二步，直到求出最优分配方案。7/7/202426现现 代代 物物 流流 学学12.2.3 巡回运输问题（旅行商问题）巡回运输问题（旅行商问题）在单网点配送中，物流网点向所属用户送货，各用户的需求量bi（i=1,2,3,n），货车载重量为Q，若满足 ，则该网点只需一辆货车即可。显然，这种情况下使费用最省的方案是合理安排货车访问各用户的顺序，使货车的巡回路线的总距离最短，这也就是旅行商问题。7/7/202427现现 代代 物物 流流 学学 已知5用户间距离如表，其中d(i,j)=表示从第i个用户到第j个用户是没有意义的，用户1为物流网点所在位置，如果只考虑将每个用户都当作一个达到用户，则对每个出发用户都要选择一个到达用户，尔每个到达用户只能有一个出发用户到达该地，将问题变成了一个分配问题，可用匈牙利算法求解。到达出发123451234521171655764443253416用户间距表例题例题7/7/202428现现 代代 物物 流流 学学 解解:第一步第一步：令d(i,i)=，不存在通路的也记为，的距离阵，通常d(i,j)与d(j,i)不一定相同，即矩阵不一定对称。第二步第二步：对距离矩阵用匈牙利法求解，若得到无环路的路线，则就是最优路线；如路线有环路，就不是最优路线，但所走总距离给出了旅行商问题总距离的下界。7/7/202429现现 代代 物物 流流 学学 得不考虑环路下的最优方案：12，24，41，35，53 则，所走总距离为：1+3+1+1+4=10 可以看出上述路线存在环路，不是原问题的最优路线，但给出了原问题的下界10。7/7/202430现现 代代 物物 流流 学学 第三步第三步：出现环路时，打开节点个数最少的环路。即在此环路上考虑某段路线不通的各种情况，分别用匈牙利法求解，其中距离最短又无环路的路线即为最优路线。本例中，出现两个环路，1241和353，打开节点数少的环路，分别令d(3,5)=和d(5,3)=求解。7/7/202431现现 代代 物物 流流 学学（1）当d(3,5)=时，用匈牙利法求解。可得无环路的最优方案：534125则，所走总距离为：1+4+2+1+4=12。7/7/202432现现 代代 物物 流流 学学（2）当d(5,3)=时，用匈牙利法求解。可得无环路的最优方案：12,21,35,43,54则，所走总距离为：1+2+1+4+5=13。7/7/202433现现 代代 物物 流流 学学 可以看到，上述方案出现环路121和354 3，如果打开环路求解，其总距离一定不小于13，而已经得到总距离为12的路线，故不必再作计算。因此得上述旅行上的最优路线为：534125；总距离为：12。7/7/202434现现 代代 物物 流流 学学12.2.4 旅行商问题的神经网络求解旅行商问题的神经网络求解1、连续Hopfield神经网络模型（a）Hopfield神经元7/7/202435现现 代代 物物 流流 学学（b）Hopfield神经网络7/7/202436现现 代代 物物 流流 学学 设有n个神经元互连，则可用下述非线性微分方程描述：上式可以定义系统的能量函数为：7/7/202437现现 代代 物物 流流 学学 可以证明，对于该能量函数，恒有 ，即当 ，网络达到稳定。应用网络的这一特性，可以进行优化问题的求解。求解时，只需将优化问题的目标函数转化成能量函数的形式，然后应用上述微分方程运算到网络收敛即可。通常在用Hopfield神经网络求解实际问题时，一般忽略能量式中得积分项，将能量函数简化为下式，以便目标函数的映射。7/7/202438现现 代代 物物 流流 学学12.3 网络流问题网络流问题12.3 Network Flow Problem 12.3.1 网络最大流问题网络最大流问题 1、问题的提出 已知连接产地V1与销地Vn的交通网，每一弧（Vi,Vj）代表从Vi到Vj的运输线，产品经由Vi输送到Vj，弧旁括号外的数字cij为弧的容量，括号内的数字xij为Vi到Vj的货运量，要求合理安排xij，使V1到Vn的货运量最大。7/7/202439现现 代代 物物 流流 学学 2、寻求最大流的标号法 对于包含n个顶点V1,V2,Vn的网络流，V1为发点，Vn为收点，各段弧（Vi,Vj）上容量为cij，设 是一个可行流，判断它是否最大流及对它进行调整，关键在于求出其增广链，标号法就是基于此来寻求最大流的。3、最小费用最大流问题 解最小费用最大流问题的基本思想是，通过已知的由V1到收点Vn的最小费用流x，寻求其对应的最小费用增广链，沿此增广链去调整x，实现最大流。7/7/202440现现 代代 物物 流流 学学 第三步：重复第二步，直到所有的顶点都标号为止，每个顶点标号内的第二个数字即为V1到该顶点得最短距离，运用反向追踪可找出此最短路径。4、最短路径问题Dijkstra算法如下：第一步：给发点V1以标号（1,0），L11=0。第二步：从以标号顶点出发，找出与这些顶点Vi相邻所有顶点，若 ，则对Vj标号为（i,L1j）7/7/202441现现 代代 物物 流流 学学12.4 送货集货问题送货集货问题12.4 Problem of Goods Delivering and Collection 12.4.1 模型分析模型分析 送货问题，是指在中心仓库中，需要向几个分仓库送货，每个分仓库对货物由一定的需求，运送货物的车辆在中心仓库装满货后发出，把货送到各分仓库卸货，完成任务后返回中心仓库，求满足货运需求的费用最小的车辆行驶路线。7/7/202442现现 代代 物物 流流 学学其中，7/7/202443现现 代代 物物 流流 学学12.4.2 扫描法求解扫描法求解（1）在地图或方格图中确定所有分仓库的位置。（2）自中心仓库始沿任一方向向外划一条直线。（3）沿顺时针或逆时针方向旋转该直线直到与某分仓库相交，相交时考虑在线路上增加该分仓库运货任务时，是否会超过车辆的载货容量（显示雍容量最大的车辆），如果不会，线路增加该分仓库，并继续旋转直线到下一分仓库。否则执行步骤（4）。（4）构成一条送货线路。7/7/202444现现 代代 物物 流流 学学（5）从不包含在上一条线路中的分仓库开始，继续旋转直线，继续步骤（3），直到所有得分仓库的送货任务都已安排在不同线路中。（6）应用TSP问题的求解算法，排定各线路中分仓库的先后顺序，使各线路的路径最短。7/7/202445现现 代代 物物 流流 学学 12.4.3 节约节约法求解法求解 在对多个分仓库进行送货时，将其中能取得最大“节约里程”的两个分仓库合并在一条线路上，进行巡回送货，能够获得最大的里程节约。同时，在不超过运输车辆载货容量的条件下，设法使这条选定的巡回路线，尽可能将其他分仓库按其所能取得“节约里程”的打下纳入这条线路中，则能获得更大的里程节约效果。7/7/202446现现 代代 物物 流流 学学 12.4.4 遗传算法求解遗传算法求解 是一种以自然选择和遗传理论为基础，将生物进化过程中适者生存规则与同一群染色体的随机信息变换机制相结合的搜索算法。其通过给解向量编码、形成初始种群，然后用变异、交叉重组、自然选择等算子，进行并行迭代，求得优化解。用遗传算法求解送货集货问题的关键是合理确定车辆与各分仓库的关系，在满足车辆载重量和分仓库需求约束条件的情况下使得总里程最小。7/7/202447现现 代代 物物 流流 学学 1、下图为W仓库，A,B,C,D为4个需要配送的站点，图上每边上的数字为点对间的距离，请安排从W出发，巡回配送每个站点的最短路线。思考题思考题7/7/202448现现 代代 物物 流流 学学 2、已知一个运输公司有两辆货车，一辆载重量为12t，另一辆为10t。该公司在A,B,C,D,E,F等6个城市装载货物，然后运回到货场O。货场和6城市间的距离以及A,B,C,D,E,F等6个城市需要装载的货物量均列在下表中，问如何安排车辆及运输线路比较合理？间距OABCDEFO0342635A2031453B3905268C4340634D2653042E3534204F5726310载货需求6585677/7/202449现现 代代 物物 流流 学学 3、设有某企业在a,b,c,d等4个不同地区设有生产工厂生产同一种产品，每月产量分别为40、30、45和20（单位为t），按计划调运到设在e,f,g的3个分配中心，分别为50、55和30（单位为t）。已知各产第到各销地的单位产品运费（单位为元）如下表，请作出调运计划并时调运费用最少。销地产地efga171614b111413c151114d1211104、请构造出带时间窗的VSP节约法算法，并进行说明。7/7/202450现现 代代 物物 流流 学学