打孔机生产效能的提高

第一问：5、模型的建立与求解5.1问题一的模型建立与求解根据题目要求，给出单钻头作业的最优作业线路（包括道具转换方案）、行进时间和作业成本。为此，建立作业总成本模型：W=𝑊𝑑+𝑊𝑥即作业总成本=刀具转换成本+行进成本。在考虑总作业成本的计算时，分两种情况进行考虑：（1）首先确定孔型的顺序并求出各个孔型的最短行进路线和距离，再根据孔型确定刀具的转换顺序，最后依次按照打孔，求出总作业成本。（2）首先确定刀具的转换顺序，再根据刀具确定所需打孔的孔型，并在这一类孔型中确定最短路径和距离，最后依次打孔，求出总作业成本。比较上述两种方案，不难发现在第一种方案中，每一种孔型都需要确定一种最优路线。根据题目要求，除了A孔型和B孔型之外，其余孔型都需要两种或三种刀具进行打孔。随之，刀具的转换成本就会重复增加，并且多刀具孔型的行进路线也会重复增加。因为若要打完一个孔型之后再打下一个孔型，每个孔型所需是每一种刀具都要走完一遍这个孔型所对应的最短路线，直接导致无谓的累加刀具转换成本和行进成本。相反，在第二种方案中，根据刀具选择孔型的集合区域，即可使没个集合区域的最短路径直走一遍，若使得大局的转换次数最少，即可得到最优的作业总成本。5.1.1刀具转换顺序的确定根据题意，某种钻头上面装有8种刀具a，b，c，…,h，依次排列呈圆环状，而且8种刀具的顺序固定，不能调换。图1：某种钻头上8种刀具的分布情况在加工作业时，一种刀具使用完毕后，可以转换使用另一种刀具。相邻两刀具的转换时间是18s，例如，由刀具a转换到刀具b所用的时间是18s，其他情况以此类推。作业时，可以采用顺时针旋转的方式转换刀具，例如，从刀具a转换到刀具b；也可以采用逆时针的方式转换刀具，例如，从刀具a转换到刀具h。将任一刀具转换至其它刀具处，所需时间是相应转换时间的累加，例如，从刀具a转换到刀具c，所需的时间是36s（采用顺时针方式）。为了简化问题，假定钻头的行进速度是相同的，刀具在行进过程中可以同时进行刀具转换，但相应费用不减。不同的刀具加工不同的孔型，有的孔型只需一种刀具来完成，如孔型A只用到刀具a。有的孔型需要多种刀具及规定的加工次序来完成，如孔型C需要刀具bcdefghaa和刀具c，且加工次序为a，c。表1列出了10种孔型所需加工刀具及加工次序（标*者表示该孔型对刀具加工次序没有限制）。表1：10种孔型所需加工刀具及加工次序孔型ABCDEFGHIJ所需刀具aba,cd,e*c,fg,h*d,g,fhe,cf,c一块线路板上的过孔全部加工完成后，再制作另一线路板。但在同一线路板上的过孔不要求加工完毕一个孔，再加工另一个孔，即对于须用两种或两种以上刀具加工的过孔，只要保证所需刀具加工次序正确即可。根据题目所给的10种孔型所需加工刀及其加工次序，从a刀具穷举至h刀具，得到以各类刀具作为起始点的行进方案。其中，在每一个刀具的排序过程中，使转换距离尽量小，并保证各类孔型的打孔顺序正确。具体方案见下表：表2方案1方案2方案3方案4方案5方案6方案7方案8abcdefghbcdefghacdefghabdefghaccefghabcdfghabcdeghabcdefhabcdefgfccfgfgfcfgfgfccc25.2元25.2元23.1元21元23.1元29.4元25.2元23.1元有上表可知，方案4的刀具转换成本最低，转换次数也最少，故确定方案4为最优方案。表1十个孔的散点图5.1.2基于遗传算法的TSP模型在考虑行进路线的最优解时，考虑到确定了刀具的转换顺序，所以按照刀具确定的集合区域寻找最短路径。表3刀具类型defghabcF孔型区域D,GD,IJF,GF,HA,CBC,I,J,EG,E同时可以发现，将各类刀具所对应的孔型区域做为一个整体以寻找最优路线，不但可以缩短行进距离，避免重复行进，而且可以减少刀具转换的次数，即减小了成本。由此得出结论，算出8个孔型区域的最短路线距离累加求和，即可求得总的最优行进成本。计算各个孔型区域的最优路径，其实就是解决大数据量的TSP问题。遗传算法具有很好的全局收敛性，解决TSP问题速度快，精度高，效果好。（1）遗传算法的基本原理遗传算法类似于自然进化，通过作用于染色体上的基因寻找好的染色体来求解问题。与自然界相似，遗传算法对求解问题的本身一无所知，它所需要的仅是对算法所产生的每个染色体进行评价，并基于适应值来选择染色体，使适应性好的染色体有更多的繁殖机会。在遗传算法中，通过随机方式产生若干个所求解问题的数字编码，即染色体，形成初始群体；通过适应度函数给每个个体一个数值评价，淘汰低适应度的个体，选择高适应度的个体参加遗传操作，经过遗传操作后的个体集合形成下一代新的种群。对这个新种群进行下一轮进化。这就是遗传算法的基本原理。Step1：初始化群体;Step2：计算群体上每个个体的适应度值;Step3：按由个体适应度值所决定的某个规则选择将进入下一代的个体;Step4：按概率PX进行交叉操作;Step5：按概率PM进行突变操作;Step6：没有满足某种停止条件，则转Step2，否则进入Step7。Step7：输出种群中适应度值最优的染色体作为问题的满意解或最优解。程序的停止条件最简单的有如下二种：完成了预先给定的进化代数则停止；种群中的最优个体在连续若干代没有改进或平均适应度在连续若干代基本没有改进时停止。根据遗传算法思想可以画出如右图所示的简单遗传算法框图：开始初始化种群交叉操作选择操作计算适应度值变异操作输出适合度值最优的个体结束停止条件图2简单遗传算法框图（2）遗传算法的选择算子选择即从当前群体中选择适应值高的个体以生成交配池的过程。遗传算法中最常用的选择方式是轮盘赌（RouletteWheel）选择方式,也称比例选择或复制。在该方法中,各个个体被选择的概率和其适应度值成比例。设群体规模大小为N，个体i的适应度值为𝐹𝑖,则这个个体被选择的概率为:𝑃𝑠𝑖=𝑓𝑖/∑𝑓𝑖𝑁𝑖=1显然,个体适应度越大,其被选择的概率越高,反之亦然。遗传算法另一种常用的选择方式是锦标赛选择方式,其基本思想是将上一代群体中的个体和本次遗传操作产生的所有新个体放到一起按适值从大到小的顺序排队,然后取排在前面的N个（N为群体规模)个体组成新一代群体。这种策略一方面通过对群体中个体适值的变换,使群体中的个体在遗传迭代的整个过程中都能保持良好的多样性,既保证了算法具有较快的收敛速度,又能防止算法收敛于局部最优解；另一方面能使上一代的最优个体一定会被选择到下一代,即这种选择策略隐含了最优保持操作,保证了算法的全局收敛性。由于选择概率比较容易控制,所以适用于动态调整选择概率,根据进化效果适时改变群体选择压力。即轮盘赌选择方式、联赛选择方式和父子竞争选择方式,前一种选择方式在引入了最优保持操作后能保证算法的全局收敛性,但收敛速度较慢；后2种选择方式不能保证算法的全局收敛性,很可能收敛于局部最优解,但有较快的收敛速度。因此,适当选择遗传算法的选择方式对提高算法的计算。5.1.3模型的求解在求解各个孔型区域的最短路线时，为方便计算忽略上一个区域的最后一个点与下一个渔区的第一个点的距离，利用遗传算法求解问题，得到结果如下：表1A孔最短路径走势图表2A孔的遗传分析图5.1.4节省法改进模型克拉克（Clarke）与怀特（Wright）于1964年提出该方法以求解车辆巡回问题，其思想在于按节省值（较短路径与原路径之差）由大至小排序，在车辆容量限制下，依序将对应的两顾客点排入路径中，直至所有顾客都被排入路径为止。该方法的实质要求就是节省路线成本。Solomon于1983年将此法应用于求解时间窗约束的车辆巡回问题，关键在于当节省值较大的两顾客点被排入路径时，除需考虑车辆容量限制外，更需要考虑到时间窗的限制，也就是时间窗上界较早者，应优先被配送，并检验其时间可行性，此方法的优点是提高车辆的利用率，而两节点间的节省值的计算公式与意义如下所示：s(i,j)=d(i,0)+d(0,j)−d(i,j)其中d（i，0）代表顾客i至场站的距离，d（i，j）则代表顾客i至j的距离。计算两节点i与j间的节省值s（i，j）时，应先计算原路径中各往返路径的总和，再以之与较短路的总路径和相比较；两节点的原路径与较短路，如下图所示：ijo较长路径ijo较短路径图3节省法的步骤：Step1：先以一部货车负责一个客户，几个货车就负责几位客户为条件，对于其路线的成本作其个别的运算，计算其个别成本。Step2：将其路线组合后计算总成本后，将路线互相掉换。Step3：通过上面二步，再进行一次运算，并统计所以的组合可能及结果，看其最低的成本路线是何解。改进节省法模型以服务每一个节点为起始解，根据三角不等式两边之和大于第三边之性质，其起始状况为每服务一个顾客后便回场站，而后计算路线间合并节省量，将节省量以降序排序而依次合并路线，直到最后5.1.5模型求解将题目所给的数据按照1到2142依次编号，运用c++进行节省法模型的求解，得到：（其余见附录）（1）d刀具a.最短路径1848-1921-1843-1745-1792-1911-1775-1910-1758-1915-1776-1908-1759-1912-1777-1909-1760-1836-1761-1753-1797-1850-1762-1728-1798-1722-1763-1736-1799-1726-1764-1720-1800-1724-1765-1730-1801-1732-1766-1749-1802-1747-1767-1733-1785-1737-1768-1738-1803-1919-1804-1852-1769-1854-1805-1855-1770-1856-1806-1857-1771-2061-1900-2060-1902-2064-1904-1883-1826-1885-1827-1887-1861-1889-1863-1891-1905-1893-1865-1895-1866-1897-1876-2072-1906-2068-1879-2069-1907-2073-1882-1846-1838-1844-1840-1847-1839-1845-1837-2075-1881-2071-1880-2074-1878-2070-1877-1898-1829-1896-1875-1894-1828-1892-1864-1890-1862-1888-1860-1886-1859-1884-1903-2062-1901-2066-1899-2063-1750-1874-1808-1830-1790-1831-1773-1833-1791-1834-1774-1922-1841-1923-1751-1924-2079-1925-2078-1927-2077-1929-1917-1832-1918-1930-2076-1928-1739-2067-1743-2065-1825-1873-1772-1872-1789-1871-1807-1858-1824-1870-1788-1869-1823-1868-1787-1867-1822-1853-1786-1851-1821-1920-1820-1734-1784-1748-1819-1731-1783-1729-1818-1723-1782-1719-1817-1725-1781-1735-1816-1721-1780-1727-1815-1849-1779-1752-1814-