[计算机软件及应用]物流配送系统中货物装载及 线路选择问题优化.doc

石家庄铁道大学毕业设计 物流配送系统中货物装载及线路选择问题优化The Logistics Distribution System Loading Goods and Route Choice Optimization Problem2013届 信息科学与技术 学院专 业 计算机科学与技术学 号 学生姓名 指导教师 完成日期 2013年5月30日毕业设计任务书题 目物流配送系统中货物装载及线路选择问题优化学生姓名学号班级信0801-1专业计算机科学与技术承担指导任务单位信息科学与技术学院导师姓名导师职称一、主要内容本系统以物流配送系统为背景，对货物装车等子集和问题，以及路线选择算法等问题进行分析、研究，开发简易的实现物流公司货物装载、运输路径选择等问题的原型系统，要求本学生完成如下主要功能：1. 分析影响物流公司货运的主要因素。2. 理解并研究子集和问题原理。3. 理解与子集和问题相关的各算法及原理，并将其应用于实际问题。4. 理解与最短路径选择及货物装载问题相关的各算法及原理，并将其与物流公司实际问题 相联系。 5. 实现物流公司货物装载及短路径选择系统的开发。二、基本要求及主要技术指标运行环境及开发工具：Visual Studio 2010。设计要求：1.完成各功能模块理论分析及设计。2.编码实现上述功能模块。3.分析最短路径与货物选择问题原理并掌握相关算法。4.进行严格的系统测试和系统联调，并提供完整的软件说明书。三 、应收集的资料及参考文献1 .C#标准教程。2 .物流配送问题相关文档。四、进度计划第1周第6周：毕业实习、系统调研、查阅资料；第7周第9周：系统分析、系统设计；熟悉开发环境及工具；第10周第14周：系统开发(编程及调试)；第15周第16周：整理资料，撰写论文，准备答辩。教研室主任签字时间年 月 日目 录第1章 绪论11.1本课题研究的背景及重要意义11.2国内外现状和发展11.3研究本课题的过程31.3.1研究本课题意义31.3.2采用的方法31.3.3系统完成的主要功能41.3.4论文的主要结构4第2章 开发技术及开发环境52.1 开发工具介绍52.1.1 Visual Studio 2010简介52.1.2 Visual Studio 2010的扩展52.2 关键技术62.2.1 ASP.NET6第3章 系统需求分析83.1系统目标83.2用户类和特征83.3运行环境83.4系统的可行性分析83.5系统的使用流程9第4章 系统概要设计104.1系统概念设计104.2系统结构设计104.2.1 系统功能结构104.3系统功能模块设计114.3.1 货物装载模块114.4.2 路径选择模块12第5章 系统详细设计135.1货物装载模块设计135.1.1遗传算法设计135.1.2贪心算法设计145.1.3穷举算法设计155.3.4动态规划算法设计165.3.5迪杰斯特拉算法设计185.4关闭系统19第6章 系统实现及测试分析206.1系统实现206.1.1遗传算法实现206.1.2 贪心算法实现246.1.3 穷举算法实现286.1.4 动态规划代码实现306.1.5 迪杰斯特拉算法实现326.2测试目的346.3测试过程356.3.1货物装载之手动输入测试356.2.2货物装载之文件输入测试36第7章 总结37参考文献38致 谢39附录A:外文翻译资料40附录B:系统使用说明书49石家庄铁道大学毕业设计论文第1章 绪论 随着我国经济的快速发展，交通运输网络和物流体系的日益完善，物流量也大幅度增加。因此，高效、快捷的运输便成为物流公司竞相追逐的发展方向。本章着重介绍本课题的研究背景和重要意义，分析当今物流配送方面国内外发展情况，并简述自己对本课题的研究过程，给出本论文结构图。1.1本课题研究的背景及重要意义随着我国交通运输网络和物流市场体系的不断完善，商品经济的发展日益加快，物流量也大幅度增加，货物运输中多频度、小批量、多品种、高价值的货物越来越多，消费者对运输企业的物流服务质量和水平提出了更高的要求。为了满足日益提高的客户服务的要求，在货物配送计划的指导下，合理组织货物配送和选择最优配送路径对提高运输效益和物流效率都是非常重要的，同时对我国将来实现物流现代化具有一定的促进作用1。物流装载中的配送，表面上看起来传统而简单，实质上是电子商务活动过程中做起来最难、最花力气、最费金钱的一块。物流成本过高、物流配送效率低下、配送服务质量差，严重影响着企业的快速发展。物流装载中的配送是完成企业电子商务完整交易过程的一个非常重要的环节，它是实现整个交易过程的最终保证8。可以说，一个企业没有真正意义的物流配送，便没有真正意义的电子商务。对于一个企业来说，电子商务是信息传送的保证，而物流配送是实物执行的保证。在当前的企业中，由于物流配送的发展与电子商务的需求存在着很大的差距，从而使电子商务活动犹如背着一块枷锁在网络上跳舞，怎么也不能潇洒自如。因此，深入分析电子商务物流配送的影响和作用，把握电子商务配送的现状及发展方向，探寻促进电子商务配送发展的解决方案，以理论指导实践，是摆在我们面前的重要课题，也是我们分析物流装载中的配送问题的目的9。1.2国内外现状和发展20世纪80年代末，许多发达国家真正认识到了配送的重要性。这种态度认识的极大转变，给企业创造出更多盈利机会。在观念发生变化的同时，配送方式和手段也有很大发展10。(1)配送共同化的进展。为满足用户配送要求，出现了配送企业车辆利用率低，不同配送企业之间交错运输，交通紧张，事故频繁等许多方面不合理现象。但近年来的发展，上升到从更大范围考虑配送合理化，致力于推行整个城市所有企业的共同配送。(2)配送计划化的进展。一改往日完全按顾客要求办事，而并不是按客户的合理要求办事的局面。制定合理计划是高水平计划配送的一大进展。计划有效的促进了配送合理化。由于可采用减少收费，也受到用户的欢迎。(3)配送区域的扩大。关国己经开展了洲际配送，日本不少配送是在全国范围或更大区域范围进行的，如日本东京的三味株式会社的全国性配送系统，日本Arica配送系统、日本资生堂配送系统等都是全国性的配送系统。(4)直达配送的进展。不经过物流基地中转，在足够批量且不增加用户库存情况下，配送在“直达”领域中找到了优势。(5)计算机管理配送的发展。随着规模的扩大和计算机的微型化，计算机管理配送取得很大进展，这个进展突出表现在以下三个方面：信息传递与处理，建立了EDI系统。计算机辅助决策，如辅助进货决策，辅助配货决策，辅助选址决策等，美国IBM公司率先建立了配送车辆计划和配送路线的计算机软件。计算机与其他自动化装置的操作控制，如无人搬运车，配送中心的自动分拣系统等。(6)配送作业的进展。配送劳动手段作为支撑配送的生产力要素，是进展很大的领域。到20世纪80年代，发达国家配送己经普遍采用了计算机系统、自动搬运系统、大规模分拣、光电识别、条形码等。发达国家的配送已经发展到一个较高水平，己经成为一种稳定的经济形态，在资源的末端配置方面，已成了一种普遍的方式。但是纵观其在配送这一方面的研究，在有关多车型多包装配载配装问题的研究上仍然少有问津。我国自加入WTO后，很多领域相继对外开放，更多的跨国企业将进入我国参与市场竞争；我国的物流配送也出现了一些新的变化和趋向11。(1)专业化趋向。企业内部物流交由专业物流公司经营，这必然导致第三方物流比重的增大。(2)规模化、集团化趋向。国内的中小型物流企业，有一部分将利用拥有国内网络及设施、人力资源成本低等本土优势，与国外大型物流企业建立战略合作伙伴关系：一部分将可能被大型物流公司收购、兼并；还有的将进行战略性重组和改造，向综合物流发展，为大型跨国物流企业配套，成为供应链的重要组成部分。(3)多元化趋向。我国物流市场今后将呈现出一个国有、集体、个体、中资、外资等各种所有制物流企业相互依存、同台竞争、相互促进的局面。(4)国际化趋向。由于世界制造业和OEHL中心在向我国转移，以及经济一体化进程的加快，未来我国与世界各国之间的物资、原材料、零部件与制成品的进出口运输，无论是数量还是质量都会发生很大变化。为适应这一变化，要求我国必须在物流技术、装备、标准、管理、人才方面与世界对接。因此，我国物流配送在国际化方而将会发展很快。(5)传统运输与仓储企业加快向第三方物流转变。由于国外物流企业纷纷来到中国，再加之香港、台湾地区的中小企业进入内地，给国内的传统运输与仓储企业造成很大压力。因此，将会有更多的传统运输与仓储企业加快向第三方物流转变。(6)物流配送信息化建设步伐加快。现代物流以信息技术为支撑，没有信息化就没有现代物流的发展。目前国内外的一些大型物流企业，都在规划建立自己的配送中心，改善物流配送信息服务技术，以提高企业的物流配送能力12。我国配送的发展应该说还处于很不成熟的状态，需要深刻分析，研究解决的办法。我国对配送理论有一定研究，应用研究十分缺乏。基于多车型多包装的货物配载配装问题更是很少有问津，尽管有一些关于配装或配载方面的研究，也大多是关于集装箱配载的算法，应用到实际问题当中并不多见。1.3研究本课题的过程1.3.1研究本课题意义我国自加入WTO后，很多领域相继对外开放，更多的跨国企业将进入我国参与市场竞争。传统物流配送将逐步融入市场经济体系和经济全球化过程，为中国物流改革发展提供了难得的机遇，同时也使之面临十分严峻的挑战13。物流配送是物流系统中的一个重要环节，是物流结点运送达收货人的过程。满足货运要求的前提下，如何选择货物装车以及物流运输线路是非常重要的，货物装载和路径选择优化的目的在于保证运输安全的前提下，是配送线路和运输时间最优14。1.3.2采用的方法以配送中心为服务对象，针对一定的货物配送中心如何选择路径优化运输；以及当货车体积一定时，如何配装包装规格不同的货物才能使得车辆的载重利用率达到最大15，这就是本论文所要研究的主要问题。问题的提出采用的是理论与实际相结合的方法，现有的解决相关问题的算法主要有迪杰斯特拉算法、近似算法、贪心算法、动态规划算法、穷举算法等等。在设计本系统的过程中，重点研究各算法的原理与实现，从而计算相应结果。通过将给定的货车容量、物品数量、各物品重量及体积的输入，可求出装入货车的最大重量及哪些物品可进行装入，并输出执行时间；通过输入各路径之间的权值，可得出货车选择走那条路径及最短路径值。1.3.3系统完成的主要功能根据物流实际情况的需要，设计的详细功能包括：(1)数据的输入：货车容量、物品数量、各物品重量，各物品体积，路径之间权值以及查询地点等；(2)假设货物重量不大，进行装入货车物品重量的计算；(3)物品选择的计算；(4)运算时间的计算；(5)最短路径及最短路径值。1.3.4论文的主要结构论文结构绪论开发技术及开发环境系统需求分析系统概要设计系统详细设计系统实现与测试分析附录部分 理论基础 附录 主要设计模块图1-1 论文结构图第2章 开发技术及开发环境 本物流配送系统中货物装载及线路选择问题的优化设计是运用C#语言编写的，运用开发工具Visual Studio 2010，以ASP.NET为开发平台，为用户提供清晰、使用简单的界面及运算系统。2.1 开发工具介绍2.1.1 Visual Studio 2010简介Visual Studio 2010是微软公司推出的开发环境，是目前最流行的Windows平台应用程序开发环境。Visual Studio 2010版本在2010年4月12日出台，它的集成开发环境的界面，在老的版本上被重新设计和组织。Visual Studio 2010的框架版本是NET Framework 4.0，它全面支持开发面向Win 7操作系统的的应用程序。Microsoft Visual Studio 开发系统是一套开发工具，旨在帮助软件开发人员因对复杂的挑战并创建创新的解决方案。Visual Studio 的目的是改进开发流程，帮助人们更轻松的实现突破、获得更令人满意的结果。Visual Studio 2010 中的新功能和增强功能可帮助程序员发挥创造力。使用多监视器支持功能自定义工作区。创建丰富的 Web 应用程序。使用 IntelliTrace 消除了可怕的“无法重现”问题。通过精确的多目标定位功能开发各种版本的 .NET Framework 程序。2.1.2 Visual Studio 2010的扩展Visual Studio 如何改进开发流程：提高工作效率。Visual Studio 提供的工具不断提供更好的方法，帮助软件开发人员完成更多有意义的工作，避免将时间和精力浪费在重复和意义不大的工作上。从单一集成开发环境 (IDE) 中的高效代码编辑器、IntelliSense、向导和多种编码语言，到 Microsoft Visual Studio,Team System 中的高端应用程序生命周期管理 (ALM) 产品。Visual Studio 的新版本不断推出创新工具，帮助开发人员专注于解决问题，而不是将时间浪费在繁琐的细节上。集成。使用 Visual Studio，软件开发人员会受益于包含工具、服务器和服务的集成产品体验。Visual Studio 各产品不仅能够相互良好协作，而且可以很好地与其他 Microsoft 软件(如 Microsoft 服务器产品和 Microsoft Office system)一起使用。全面。Visual Studio 提供的工具适用于软件开发的所有阶段(开发、测试、部署、集成和管理)和所有开发人员(从新手到经验丰富的专家)。Visual Studio 的设计还支持各种类型设备上的开发，包括 PC、服务器、Web 和移动设备。可靠。Visual Studio 经过严格的设计和测试，能够提供良好的一致性、可靠性、安全性、互操作性和兼容性。Visual Studio 实现了安全功能、可伸缩性和互操作性的完美组合。Visual Studio 不断推出前瞻性功能，但其设计也尽可能确保向后兼容性。2.2 关键技术2.2.1 ASP.NET ASP是Active Server Page的缩写，意为“动态服务器页面”。ASP是微软公司开发的代替CGI脚本程序的一种应用,它可以与数据库和其它程序进行交互，是一种简单、方便的编程工具。ASP的网页文件的格式是.asp，现在常用于各种动态网站中。ASP是一种服务器端脚本编写环境，可以用来创建和运行动态网页或WEB应用程序。ASP网页可以包含HTML标记、普通文本、脚本命令以及COM组件等。利用ASP可以向网页中添加交互式内容(如在线表单)，也可以创建使用HTML网页作为用户界面的WEB应用程序。 与HTML相比，ASP网页具有以下特点：(1)利用ASP可以实现突破静态网页的一些功能限制，实现动态网页技术；(2)ASP文件是包含在HTML代码所组成的文件中的，易于修改和测试；(3)服务器上的ASP解释程序会在服务器端执行ASP程序，并将结果以HTML格式传送到客户端浏览器上，因此使用各种浏览器都可以正常浏览ASP所产生的网页。 (4)ASP提供了一些内置对象，使用这些对象可以使服务器端脚本功能更强。例如可以从web浏览器中获取用户通过HTML表单提交的信息，并在脚本中对这些信息进行处理，然后向WEB浏览器发送信息。 (5)ASP可以使用服务器端ActiveX组件来执行各种各样的任务，例如存取数据库、发送Email或访问文件系统等。 (6)由于服务器是将ASP程序执行的结果以HTML格式传回客户端浏览器，因此使用者不会看到ASP所编写的原始程序代码，可防止ASP程序代码被窃取。 (7)方便连接ACCESS与SQL数据库. (8)开发需要有丰富的经验,否则会留出漏洞,让黑客利用进行注入攻击.ASP也不仅仅局限于与HTML结合制作WEB网站，而且还可以与XHTML和WML语言结合制作WAP手机网站。但是其原理也是一样的。ASP.NET 是下一代的 ASP，但是不能把 ASP.NET 称为 ASP 的升级版本。ASP.NET 是全新的服务器端 ASP 脚本。它从桌面开发中向网页引入了“窗体”的概念。 ASP.NET使用.NET Framework构建，运行于实时环境中，提供了一个类似于JAVA的虚拟机。通过使用已经开发好的数目众多的类库，可以大大加快开发的时间。它是统一的 Web 开发平台，用来提供开发人员生成企业级 Web 应用程序所需的服务。ASP.NET 的语法在很大程度上与 ASP 兼容，同时它还提供一种新的编程模型和结构，用于生成更安全、可伸缩和稳定的应用程序。它功能强大，有更好的适应性、安全性、可以用不同的程序语言进行开发，使用多种数据库主要包括MSSQL，ACCESS等这些常用数据库。多处理器的支持，可以大大提高执行速度，ASP做不到这一点。另一个，ASP和ASP.NET可以共用一个IIS组件，不会受互相干扰。要追求完美，追求最新技术或有更高需求的客户，用ASP.NET来开发应用系统就很不错。在未来的10年中，ASP.NET应该会在各种网络开发应用中发挥积极，主要的作用。微软是希望通过.NET技术把原来分散在Internet上的各种服务有机的组合起来。不论你什么时候，在什么地方，使用什么设备上网，也不论你使用什么操作系统，使用什么语言开发，你都可以通过.NET技术找到自己想要的服务。第3章 系统需求分析本章主要介绍系统的需求分析，帮助对本系统的性能及要实现的功能有一个深刻明确的分析，明确系统设计目标，分析系统的使用用户群体及特征，明确设计方向，判定了系统的真实可行性，并设计了简单的程序流程图，为系统概要设计做下坚实的铺垫。3.1系统目标本系统是一个可以帮助物流快递公司计算如何选择货物进行装车，并计算装入货车总重量的系统，将最终结果在下方输出；还可以选择最优货车运输路径并计算最优路径的系统，最终指定位置输出供物流公司参考。本系统设计目标为：研究开发帮助物流公司快捷进行选货装车，计算装入货车重量，并求出最优运输路径及距离的系统。3.2用户类和特征本系统的设计主要是帮助物流公司人员便捷的工作，并提供一些关键的参数。用户使用群体可能并不掌握系统设计的专业知识，因此要求此运算系统要使用简单快捷、方便操作。而非本物流公司工作人员使用本系统时，可能觉得对自己用处并不大。3.3运行环境本系统所要求的运行环境：硬件平台： 处理器：双核处理器 内存：2.00GB软件平台： 操作系统：Windows 7服务器： .NET版本：.NET 4.0以上3.4系统的可行性分析本系统的实现是可行的，第一：有专业理论知识的支持。要实现本系统，首先要理解各算法的原理，然后进行各种计算。其中算法大都是我们书本上学过的，我们很容易从书本上找到。第二:在软件实现方面是可以实现的，在.NET环境下运用C#编程语言进行实现，在图书馆有许多C#编程语言方面的书，方便学习实现。综上两方面考虑，本系统是可以实现的。3.5系统的使用流程系统总体流程：用户通过本系统主界面进入系统后，点击选择自己接下来要进行的计算方向：货物装载或路径选择；当用户进入功能页面后，可以输入相应的数据信息，点击按钮触发执行后，数据将统一传入程序进行计算并给出最终正确的计算结果供用户参考使用。当用户使用完系统后，可以点击系统界面上的关闭按钮，即可退出本页返回上一页。用户输入数据系统判断输入是否正确，若正确则传入程序计算程序处理数据，并给出最终运算结果图3-1 系统的整体设计思路第4章 系统概要设计本章在前一章需求分析的基础上，开始着手系统的概要设计，主要介绍系统相关概念设计及系统结构设计，并给出系统结构图；分析系统的主要功能模块设计并给出相应的功能模块流程图。4.1系统概念设计在系统中对所需要触发及输入的部分进行分析，得出系统的基本概念信息如下所示：货物装载：位于主页面的按钮，点击可触发弹出货物装载页面。路径选择：位于主页面的按钮，点击可触发弹出路径选择页面。手动输入：位于货物装载页面的按钮，点击可触发弹出手动输入页面。文件读入：位于货物装载页面的按钮，点击可触发弹出文件读入页面。货车容量：位于货物装载页面，需要用户输入货车的固定容积。物品数量：位于货物装载页面，需要用户输入物品的数量。物品重量：位于货物装载页面，需要用户输入各物品的重量，中间用空格隔开。物品体积：位于货物装载页面，需要用户输入各物品的体积，中间用空格隔开。读取：位于文件读入页面，要求用户选择要读入的事先编辑好的数据文件。权值输入：位于路径选择页面，要求用户手动输入各路径之间的权值。结点查询：位于路径选择页面，要求用户在下拉菜单中手动选择要查询结点名称4.2系统结构设计4.2.1 系统功能结构根据系统分析的结果，按照结构化的系统设计方法，画出本物流系统结构图下图所示：物流系统路径选择货物装载贪心算法计算动态算法计算迪杰斯特拉算法计算穷举算法计算遗传算法计算图4-1 物流系统结构图4.3系统功能模块设计4.3.1 货物装载模块 开始 接收关键字传入算法进行运算并显示结果结束通过StringToFloat函数修改关键字格式关键字个数需键入空格货物装载模块流程图如图所示： 开始k=1 k>2图4-2 货物装载模块流程图手动输入模块：用户可以通过手动输入货车容量、物品数量、各物品重量及体积，在选择下拉框内选择算法，按确定键触发，计算运行结果，将最终结果输出，可以帮助工作人员高效的工作。文件读入模块：将货车总体积大小，各货物重量及体积事先输入到一个txt文件中，运用系统选择文件读入，点击运行按钮触发运行，将最终选择装入结果及装入总体积在下方输出，帮助工作人员高效的工作。4.4.2 路径选择模块路径选择模块如图所示：开始接收路径权值传入算法进行运算，并显示结果结束接收起始点名称图4-3 路径选择模块流程图路径选择模块首先默认总地点数为5，地点名称分别为：A，B，C，D，E，要求用户输入各路径之间的权值，并在下拉菜单中选择要查询的起始及终点地点名称，点击查询按钮，触发程序执行，在下框中输出选择的最短路径，并计算最短路径值同时输出。第5章 系统详细设计 本章在前一章系统概要设计的基础上，进一步设计实现系统的详细功能。文中给出了系统主要计算模块的界面图，以及算法的接口图，帮助用户理解程序构成。5.1货物装载模块设计5.1.1遗传算法设计是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。其主要特点是直接对结构对象进行操作，具有内在的隐并行性和更好的全局寻优能力。其运行界面如下5-1所示：图5-1 遗传算法运行界面系统的接口结构图如图5-2所示：货物装载页面货车容量遗传算法物品体积物品重量 接口1：s 接口2：dataWeight 接口3：dataVolumn 接口4：遗传算法图5-2 遗传算法系统接口图接口1：通过事先编辑好的数据文件读入货车容量。接口2：通过事先编辑好的数据文件读入物品重量。接口3：通过事先编辑好的数据文件读入物品体积。接口4：遗传算法传入计算。5.1.2贪心算法设计贪心算法没有固定的算法框架，算法设计的关键是贪心策略的选择。必须注意的是，贪心算法不是对所有问题都能得到整体最优解，选择的贪心策略必须具备无后效性，即某个状态以后的过程不会影响以前的状态，只与当前状态有关。因为用贪心算法只能通过解局部最优解的策略来达到全局最优解，因此，一定要注意判断问题是否适合采用贪心算法策略，找到的解是否一定是问题的最优解。贪心算法运行界面如下5-3所示：图5-3 贪心算法运行界面贪心算法的接口图如图5-4所示：货物装载页面货车容量算法选择物品重量物品数量物品体积 接口1：tw 接口2：n 接口3：w 接口4：v 接口5：贪心算法图5-4 贪心算法接口图接口1：通过Textbox1将背包容量值tw传给贪心算法程序。接口2：通过Textbox2将物品数量值n传给贪心算法程序。接口3：通过Textbox3将物品重量值w 传给贪心算法程序。接口4：通过Textbox4将物品体积值v 传给贪心算法程序。接口5：通过ComboBox选择贪心算法并开始运行。5.1.3穷举算法设计穷举是最简单、最基础，也是通常被认为最有效的算法。但是，穷举拥有很多优点，它在算法中占有一席之地。首先，穷举具有准确性，只要时间足够，正确的穷举可以得出的结论是绝对正确的；其次，穷举拥有全面性，因为它是对所有方案的全面搜索，所以，它能够得出所有的解。采用穷举算法的基本思路：(1)确定穷举对象、穷举范围和判定条件；(2)一一列举可能的解，验证是否是问题的解。穷举算法运行界面如下5-5所示：图5-5穷举算法运行界面穷举算法的接口图如图5-6所示：货物装载页面货车容量算法选择物品重量物品数量物品体积 接口1：tw 接口2：n 接口3：w 接口4：v 接口5：穷举算法图5-6 穷举算法的接口图接口1：通过Textbox1将背包容量值tw传给穷举算法程序。接口2：通过Textbox2将物品数量值n传给穷举算法程序。接口3：通过Textbox3将物品重量值w 传给穷举算法程序。接口4：通过Textbox4将物品体积值v 传给穷举算法程序。接口5：通过ComboBox选择穷举算法并开始运行。5.3.4动态规划算法设计基本思想与分治法类似，也是将待求解的问题分解为若干个子问题（阶段），按顺序求解子阶段，前一子问题的解，为后一子问题的求解提供了有用的信息。在求解任一子问题时，列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解。依次解决各子问题，最后一个子问题就是初始问题的解。由于动态规划解决的问题多数有重叠子问题这个特点，为减少重复计算，对每一个子问题只解一次，将其不同阶段的不同状态保存在一个二维数组中。与分治法最大的差别是：适合于用动态规划法求解的问题，经分解后得到的子问题往往不是互相独立的（即下一个子阶段的求解是建立在上一个子阶段的解的基础上，进行进一步的求解）。动态规划算法运行界面如下5-7所示：图5-7 动态优化算法运行界面动态算法的接口图如图5-8所示：货物装载页面货车容量算法选择物品重量物品数量物品体积 接口1：tw 接口2：n 接口3：w 接口4：v 接口5：动态算法图5-8 动态算法的接口图接口1：通过Textbox1将背包容量值tw传给动态算法程序。接口2：通过Textbox2将物品数量值n传给动态算法程序。接口3：通过Textbox3将物品重量值w 传给动态算法程序。接口4：通过Textbox4将物品体积值v 传给动态算法程序。接口5：通过ComboBox选择动态规划算法并开始运行。5.3.5迪杰斯特拉算法设计迪杰斯特拉算法是典型的最短路径路由算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率低。它是很有代表性的最短路算法，在很多专业课程中都作为基本内容有详细的介绍。迪杰斯特拉算法运行界面如下5-9所示：图5-9 迪杰斯特拉算法运行界面该算法的接口图如图5-10所示：路径选择页面路径权值迪杰斯特拉算法终点名称起点名称 接口1：JZ 接口2：Qi 接口3：Zhong 接口4：迪杰斯特拉算法图5-10 迪杰斯特拉算法接口图接口1：将所有TextBox 内的值转化后传入数组JZ。接口2：将combobox1中数据传入Qi。接口3：将combobox1中数据传入Zhong。接口4：按钮触发迪杰斯特拉算法开始执行。5.4关闭系统在系统的各运算界面分别设有“关闭”按钮，方便用户办公完毕后随时退出系统。当用户点击关闭按钮时，服务器接收请求，判断出是关闭请求，则开始清空TextBox，是用户回到上一界面，若此界面是主页面，则将关闭整个系统。第6章 系统实现及测试分析本章在上一章详细设计的基础上，进一步给出算法具体实现的主要函数代码，并指明测试目的和一些步骤，供用户参考使用。6.1系统实现6.1.1遗传算法实现遗传算法的特点是直接对结构对象进行操作，不存在求导和函数连续性的限定；具有内在的隐并行性和更好的全局寻优能力；采用概率化的寻优方法和指导优化的搜索空间，自适应的调整搜索方向，不需要确定的规则。根据遗传算法的这些特点及本程序的自身要求，画出程序流程图如图6-1所示：确定实际问题参数集对参数集进行编码初始化群体评价群体遗传操作产生新一代群体结束满足停止规则图6-1 遗传算法流程图程序的主要函数实现代码如下： private void Variation() Random x = new Random(); Random y = new Random(); for (int i = 0; i < dataNum; i+) for (int j = 0; j < dataValue.Length; j+) double randomNum = Math.Sqrt(-2 * Math.Log(x.NextDouble() * Math.Cos(2 * Math.PI * y.NextDouble(); /当大于变异概率时，则对该位进行变异操作 if (randomNum > 1 - PVar) ai, j = !ai, j; /修正数据 ModifyData(); private void Cross() Random x = new Random(); for (int i = 0; i < dataNum; i += 2) if (x.NextDouble() > 1-PCross)/当大于杂交概率时两个样本杂交 /依次遍历每一位，根据均匀概率随即生成杂交掩码来杂交 for (int j = 0; j < dataValue.Length; j+) if (x.NextDouble() > 0.5)/i与i+1的第j位进行杂交 if (ai, j != ai + 1, j) ai, j = !ai, j; ai + 1, j = !ai + 1, j; ModifyData(); private void SelectSub() double elv = new doubledataNum; / 确保这一代中的最好个体进入下一代 CopyParent(index, 0); /计算这一代中各个体的适应值 for (int i = 0; i < dataNum; i+)