埃及信息学杂志：总机会成本矩阵中的运输问题求解方法

埃及信息学杂志20（2019）131全文总机会成本矩阵Bilqis Amaliaha，Chastine Amaliaha，Erma Suryaniba信息学系，信息和通信技术学院，Institut Teknologi Sepuluh Nopalan，Surabaya 60111，印度尼西亚b信息系统系，信息和通信技术学院，Institut Teknologi Sepuluh Nopalan，泗水60111，印度尼西亚阿提奇莱因福奥文章历史记录：2018年7月27日收到2018年12月4日修订2019年1月14日接受在线预订2019年1月26日保留字：运输问题初始基本可行解最优解总机会成本矩阵A B S T R A C T运输问题（Transportation Problem，TP）是将产品从产地运送到目的地的成本规划问题，提出了初始基本可行解（Initial Basic Feasible Solution，IBFS）来寻求最优解。IBFS是达到最佳结果的重要因素以往的相关方法并不总是能取得令人满意的效果。为此，提出了一种新的确定IBFS的方法-总机会成本矩阵-目标是实现与最佳解决方案相似或更接近的总成本。为获得IBFS，高度考虑了初始矩阵的TOCM用31个数值TOCM-MT被证明有24个数值例子具有相似的值和7个数值例子具有更接近最优解的值实验结果表明，TOCM-MT比VAM、JHM和TDM 1获得©2019 Elsevier B.V.制作和托管代表开罗计算机和信息学院大学这是一篇CC BY-NC-ND许可证下的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。1. 介绍运输问题（TP）是在满足需求和供给约束的条件下，以最小的总成本将某些产品从源头运输到目的地的问题[1]。TP的目标是实现最小的总成本作为最优解。它最早是由希区柯克[2]提出的，也是线性编程问题之一[1，3].它可以应用于现实世界中的问题，如人员分配[4]，任务分配[5]，流水车间调度问题[6，7]和车辆路线[8，9]。在获得TP的最优解时有两个步骤。第一步是找到初始基本可行解（IBFS），*通讯作者。电子邮件地址：bamaliah@gmail.com（B. Amaliah），chastine@if.its.ac.id（C.gmail.com（E. Suryani）。开罗大学计算机和信息系负责同行审查。制作和主办：Elsevier第二个是从IBFS[10]中找到最优解。有必要从IBFS出发来解决运输问题[1，3，4，10]。IBFS是求最优解的一个基本解，因此它的求解是非常重要和有意义的。IBFS的结果可以与最优解的值相似或更接近。IBFS的较好结果可以减少获得最优解的迭代次数[1]。本研究的重点是寻找IBFS，以获得最小的总成本的运输问题。许多研究人员已经完成了许多与IBFS相关的研究，其中三个著名的方法是西北角方法（NCM），最小成本方法（LCM）和Vogel一些研究人 员 开 发 了 一 些 基 于LCM 的IBFS 方 法 ， 如Juman 和 Hoque[1] ，Babu[12]，Juman和Hoque[13]，Babu[14]，Dhurai[15]，Kousalya和Malarvizhi[16]，Ahmed等人[17，18]，Desh- mukh[19]。Juman和Hoque[1]提出了Juman Hoque方法（JHM）来获得IBFS。它不同于其他的，因为它开始于一个不可行的解决方案，并导致一个有效的IBFS。实验表明，JHM使18个运输问题中的16个总费用最小。Ahmed等人[17]提出了间接分配方法（IAM）来获得运输问题的IBFS。它可以应用于平衡和不平衡运输问题。他们[18]开发了分配https://doi.org/10.1016/j.eij.2019.01.0021110-8665/©2019制作和主办由Elsevier B. V.代表开罗大学计算机和信息学院这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。可在ScienceDirect上获得目录列表埃及信息学杂志杂志主页：www.sciencedirect.com132B. Amaliah等人/Egyptian Informatics Journal 20（2019）131XXP我的天. ; ijj表 法 （ ATM ） 从 最 小 奇 费 用 开 始 求 IBFS. 这 是 一 个 类 似 于Deshmukh[19]。VAM是最著名的初始基本可行解[3]。它已经被研究了很长一段时间 ， 并 由 一 些 研 究 人 员 如 Hosseini[3] ， Soomro 等 人 [20 ， 21] ，Rashid[22]，Hakim[23]进行了修改。Goyal[24]，Das et al.[25，26]阿扎德和侯赛因[27]，Alkubaisi[28]，Seethalakshmy和Srinivasan[29]。Hosseini[3]提出了总差异方法1（TDM 1），以获得IBFS对于TP。VAM计算所有行和列的惩罚，而TDM1仅计算行的惩罚。另一个区别是如何计算罚款。TDM1的惩罚比VAM更完整。这是因为VAM惩罚是两个最小成本之差，而TDM1惩罚是最小成本与其他成本之差的总和。Azad和Hossain[27]考虑了平均行和列惩罚。Alkubaisi[28]使用中值成本来找到惩罚值。Seethalakshmy和Srinivasan[29]提供了另一种计算惩罚值的方法。行惩罚是两个最高成本之间的差异，列惩罚是最大和最小成本之间的差。Soomro等人。[21]开发了改进的Vogel总机会成本矩阵（TOCM）由Kirca和Satir[30]提出。该算法通过对原TP矩阵的行、列机会成本矩阵进行加法运算，将原TP矩阵转化为初始矩阵。行/列机会成本矩阵将其中的每个元素减去最小成本。Khan等人 [31] 提 出 了 TOCM-SUM 来 获 得 运 输 问 题 的 可 行 解 。 Dubey 和Shrivastara[32]使用TOCM来改善VAM。 Islam等人[33]提出了总机会成本表（TOCT）来寻找运输问题的基本可行解（BFS）。Khan等人 [34] 规 定 了 TOCM 每 个 单 元 格 的 分 布 指 标 。 Mathirajan 和Meenakshi[35]将TOCM和VAM结合起来，以获得运输问题的最小总成本。有关TP和各种技术的一些文献已经开发出来Maity和Roy[36]开发了一个数学模型来解决具有多选择需求的他们的研究[37]讨论了多目标运输问题（MOTP）的各种数学模型，如目标规划（GP），加权目标规划（WGP）和修正的多选择目标规划（RMOGP）。在此之后，他们开发了一种新的方法RMOGP和效用函数的MOTP。Roy和Maity[38]考虑了一种新的方法，在具有区间值的多选择环境中通过单个目标函数来最小化运输问题的成本和时间。 他们的研究[39]提出了两阶段多选择灰数多目标运输问题的目标选择效用函数。Ali和Mustapha[40]比较了运输问题的五种方法，以找到最好的一种。Roy等人[41]介绍了一种圆锥标量化方法，以获得一个对VAM、JHM和TDM1进行了检验，以寻找IBFS，但它们不能始终提供最优解。然后选择TDM 1，因为以下原因：最高惩罚（HP）是任意选择的，最大单元直接分配给最小成本单元。因此，并不总是能得到最佳解决方案。一些研究使用TOCM矩阵作为初始矩阵，产生了更好的IBFS。因此，本研究整合TOCM与修正的TDM 1，称为总机会成本矩阵-最小总和（TOCM-MT），以确定TP的IBFS。TOCM-MT相对于TDM 1的优势可表述如下：1. TOCM-MT使用TOCM作为初始矩阵，这是由于被选择为最小成本的机会更大，而TDM 1使用原始矩阵而没有任何机会2. TOCM-MT有选择HP的规则，而TDM 1在有多个HP具有相同值时任意选择HP因此，TOCM-MT有更高的机会获得最优解。3. TOCM-MT具有当最小成本等于零时将最大单元分配给最小成本小区的机制这样，就有更大的机会获得最小的成本。本文的其余部分组织如下：第2节和第3节提出了运输问题的数学公式和总机会成本矩阵。现有方法总结见第4节。第5节是TOCM-MT的描述，第6节是数值样本的说明。第7节中讨论了显示所提出的方法的性能的实验结果。 实验的结论和未来的研究在第8节中展示。2. 运输问题运输问题（TP）可以用图1[10，18]中的网络图和表1[17]中的公式表表示。网络图和公式表的目标是确定变量Xi，j的值，该值将使运输问题的总成本最小化，如等式10所示。（一）.以下符号用于数学公式[31]。m供应总数n需求总数Si供应iDj需求jCi，j从供给i到需求j的运输成本Xi，j从供给i和需求j使用该符号，目标TP可以公式化如下：解决多目标运输问题。 MaityMn等人[42]研究了目标函数具有模糊多选择目标的多目标运输问题最小值Z¼Cij Xij联系我们由于进行计算的困难性，一些受nj¼1影响X ij¼S i对于i 1; 2;. M研究人员使用C++程序lan实现了这些方法语言，Java和Matlab。Imam等人[43]Sen et al.[44]采用C++程序设计语言，建立了面向对象的模型来求解对于j1 2n，m× D1/1其中，对于所有i;j，ð2Þ交通问题。Juman和Hoque[1]用C++语言实现了JHM[45]第四十五章：你是我的女人一个运输问题是平衡的，如果总供给等于总需求，如方程所示（三）、西北地区，最小成本，VAM，修正分销模型也是Java和NetBeans的垫脚石Khan等人[46个]在Matlab中实现了12种方法XSi¼XDj31/1j1B. Amaliah等人/Egyptian Informatics Journal 20（2019）131133×表3TOCM矩阵。D1D2D3D4供应S19425007S2912210809S3530922218需求58714Fig. 1. 运输问题的网络图。表1运输问题的列式表。需求1需求2需求n供应1C 11C 12.. .C 1 nS 1X11X 12X 1n供应2C 21C 22.. .C2 nS2X21X 22X 2n.... ........供应mC m1C m2.. .C mnS mXm1Xm 2XmnD1 D2 Dn3. 总机会成本矩阵总机会成本矩阵（TOCM）由Kirca和Satir[30]提出。它是通过增加行和列的机会，将矩阵运输问题从原始矩阵转化为初始矩阵。表2是原始运输问题的矩阵。行机会减去行中每个元素的最小成本。列机会减去列中每个元素的最小成本。TOCM是行和列机会的总和，如表3所示。4. 找到IBFS初始基本可行解（IBFS）是运输问题（TP）的初始解，被称为TP的起始解。在某些情况下，IBFS会得到最优解。本节将讨论三种现有的方法来找到IBFS第一种方法是VogelVAM的步骤可以描述如下：步骤1构建表2原始运输问题矩阵。S3 40 8 70 20 18要求5 8 7 14运输问题矩阵如果总供给不等于总需求，则添加虚拟行或列。步骤2找出每一行和每一列的惩罚。惩罚是两个最小成本之间的差异。步骤3选择最高的笔- alty.第四步选择最便宜的。第5步分配最大可能的单位。第6步调整供应和需求，然后划掉满足的行或列。第七步重新计算笔数，不考虑划掉的行和列。第8步重复第3-7步，直到所有行和列都满足要求。第9步最后计算总成本运输问题。总成本运输问题是成本和分配单位的乘积。第二种方法是Juman和Hoque方法（JHM）。JHMJHM的步骤可以描述如下：步骤1构造初始运输问题矩阵。步骤2对于每一列，确定成本最低的单元格，然后在那里分配需求。步骤3检查每一行的行和是否小于或等于供应量。如果是，请转到第9步。 4.如果有几个未满足的行，确定第二最小和最小单位成本之间的差异，确定其中最小的，以及转到步骤5。如果只有一个未满足的行，请转到步骤7。步骤5对于每个未满足的行，检查另一个未满足行中没有第二个最小单位成本的单元格。当找到这样的行时，检查前一行并转到步骤7。第6步选择任意两个未满足的行。对于每一个，找出第二小和最小单位成本之间的差异。步骤7考虑在步骤5（或步骤4或步骤6）中识别的未满足行，将最大量的过量供应从最小成本单元转移到下一个最小成本单元，并且继续该转移直到不存在过量供应。第8步划掉已满足的行，然后转到第3步。第9步停止，当前的解决方案是IBFS。第三种方法是总差异法1（TDM1）。TDM1仅计算行的惩罚[3]。TDM 1的步骤可以具体描述如下：步骤1构造运输问题矩阵。如果总供给不等于总需求，则添加虚拟行或列。步骤2找出每一行的惩罚。罚款是最低成本和其他成本之间的总差额。第三步选择最高的惩罚。第四步选择最便宜的。第5步分配最大可能的单位。第6步调整供应和需求，然后划掉满足的行或列。第7步重新计算惩罚，不考虑划掉的行和列。第8步重复第3-7步，直到所有行和列都满足要求。第9步最后计算总成本运输问题。总成本运输问题是成本和分配单位的乘积。5. 总机会成本矩阵总机会成本矩阵-最小总和（TOCM-MT）是TOCM和修改的TDM 1的组合。TOCM-MT的步骤可描述如下：步骤1：构建原始运输问题（TP）矩阵mn，成本为Cij，供应Si;i=1. m和要求Dj;j= 1.. n.如果总供给不等于总需求，则添加虚拟行或列D1D2D3D4供应S1193050107S2703040609134B. Amaliah等人/Egyptian Informatics Journal 20（2019）131XXXXXX.¼步骤2：从原始TP中构造一个行机会矩阵，找到每一行的最小成本，然后减去具有最小成本的行中的每个成本步骤3：从原始TP中构造列机会矩阵，通过找到每列的最小成本，然后减去具有最小成本的列中的每个第4步：构建TOCM，其中的条目是行和列机会矩阵的总和第五步：求出每一行的罚分Pi。惩罚Pi是最小成本LCi与行中的其他成本之间的总差，如等式1所示。（4）和（5）。LC i½minC ij;j1：：n4nPi½Cij-LCi½50j1第6步：选择最高惩罚（HP），如等式所示。（六）、如果出现平局（即HP相等），请使用以下平局决胜器：给定的顺序：（i）选择具有最小Cij的HP。(ii)如果对于（i）中的一个配合，选择具有最大总成本TCi的惩罚，如等式（1）中所（七）、（iii）在（ii）项中的并列情况下，选择惩罚，Xi，j的最大分配。表4TOCM-MT和TDM 1的比较。步骤步骤描述TOCM-MTTDM11构建原始TP是的是的2构建行机会矩阵是的没有3构建列机会矩阵是的没有4构建TOCM是的没有5求每一行是的是的6选择最高惩罚的规则是的没有7选择成本是的是的8检查LC值是的没有9分配最大可能单位Xij是的是的10调节供求是的是的11重新计算刑罚是的是的12重复步骤6是的是的13计算TCTP是的是的步骤12：重复步骤6-11，直到所有行和列都满足要求。步骤13：最后，通过将TOCM-MT与惩罚和原始运输问题组合来计算总成本运输问题（TCTP），如等式（11）所示。MnHP最大值：1000000;i：：m1000000nTCi¼Cij 70j1第7步：从最高惩罚中选择最低成本（LC）。在平局的情况下（即相等的LC），选择具有最大分配X i，j的LC。步骤8：检查LC的值如果LC不等于零，则转到步骤9，否则如果LC等于零，则从第一HP（HP1）或第二HP（HP2）中选择HP通过比较HP1中的每个成本单元格和HP2中的每个成本单元格选择HP。C1j是HP1的成本，C2j是HP2的成本.如果HP 1中的成本大于HP 2中的成本，则GV 1 j的值为1，如果HP 1中的成本小于HP 2中的成本，则GV 1 j的值为0。如果HP1中的成本小于HP2中的成本，则GV2j的值为1;如果HP1中的成本大于HP2中的成本，则GV 2 j的值为0。TotalGV1j是GV1j之和，如等式（1）所示。并且TotalGV2j是如等式（8）中所示的GV2j（九）、如果TotalGV1j大于TotalGV2j，则HP为HP1，如果TotalGV1j小于TotalGV2j，则HP为HP2，如等式（1）所示（十）、n公司简介C ij X ij11联系我们TOCM-MT和TDM 1之间存在三个差异第一种是TOCM-MT使用TOCM矩阵，而TDM 1使用原始矩阵。第二个是TOCM-MT具有选择HP的规则第三种是TOCM-MT在分配最大单元Xij之前检查最小成本的值，而TDM 1直接将最大单元Xij分配给最小成本。TOCM-MT和TDM 1的比较如表4所示。6. 计算实验本研究使用三十一个数值例子来说明所提出的方法TOCM-MT。从期刊中选取25个算例，随机生成6个算例Deshmukh[19]的以下示例用于说明所提出的方法。例如，一家公司有3个供应工厂，分别生产7辆、9辆和18辆汽车。公司供应给四个买家，他们的需求分别是5，8，7，14辆汽车。每辆汽车的运输成本见表5。GV1j哪里GV2j简体中文1如果C1jC2j;j<$1; 2;：：n<0，如果C1jPC2j;j=1;2;：：nnð8Þ目标是找出以最小的总成本将汽车从工厂转移到买家的时间表第一步：构建一个原始的运输问题（TP），如表5所示。步骤2：从原始TP构建行机会矩阵;找到每行的最小成本，然后减去具有最小成本的行中的每个成本，例如。行1的最小成本是10，则总计GV2j¼GV 2j29j1哪里用10减去单元格中的每个成本。步骤3：从原始TP中构建列机会矩阵;找到每列的最小成本，然后减去每列HPHP 1，如果1jPHP2如果GV1

下载后可阅读完整内容，剩余1页未读，立即下载