1、 经济管理学院华东交通大学经济管理学年论文评阅书姓名 学号 专业 学年论文题目 指导教师评语：指导教师签字：年 月 日成绩学年论文题目I摘 要物流运输问题是当今研究的热点问题，随着运输交通工具的多样化，交通网络的复杂化，物流运输路线的选择就是组合优化中的一个 NP 难题。物流运输路线的选择是否合理直接影响着运输企业配送的速度、企业成本和企业效益。本文主要分析了运输线路选择与安排问题的具体特征，选用了现有的一个简单的两阶段的 VRP 网络模型来抽象描述，相比其它网络模型，它更加清楚明确，同时能把车辆调度从路线安排问题中剥离出来。接着在对比了现有三类路线选择算法的优缺点的情况下，考虑到遗传算法在全
2、局收敛性上的优势，故采用它来建立该问题求解模型。并且为了改进其全局收敛性，针对其中的交叉与变异操作的概率进行了自适应调整，以防止其过早收敛。最后本文通过使用 MVC设计模式，将遗传算法封装到系统 Controller 层中，实现了遗传算法在物流运输系统中的应用与实现。关键字：遗传算法；VRP 问题；网络模型；路线选择；MVC黑体，小四号*该节为罗马数页码Times New Roman，四号黑体，三号，段前段后 0.5 行，1.5 倍行距宋体，小四号，行距为固定值 20 磅*开始分节华东交通大学学年论文- II -ABSTRACTXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
3、XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
4、XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX。Key words: Genetic Algorithm; VRP Problem; Network Model; Route Choice; MVCTimes New Roman，三号，加粗段前段后 0.5 行，1.5 倍行距段前段后 0.5 行，1.5 倍行距Times New Roman，小四号，行距为固定值 20 磅Times New Roman，小四号，加粗学年论文题目- III -目录1 引言 .11.1 物流运输的作用及重要性 .11.2 问题的提出 .1
5、2 物流运输系统框架设计 .12.1 物流运输业务流程 .12.1.1 运输线路选择问题描述 .2参考文献 .4致谢 .5黑体，小二号，1.5 倍行距一级：黑体，四号二级：宋体，小四号三级：楷体，小四号行距为固定值 20 磅学年论文题目- 1 -1 引言本章主要是对现代物流进行概述，指出运输在物流活动中的作用及重要性和路径选择现状，阐明了物流网络优化的重要意义。1.1 物流运输的作用及重要性从我国目前的经济发展来看，由于市场经济的深入，单纯依赖商流赚取利润的机会愈来愈少，企业逐渐将目光转向素有“第三利润源泉 ”之称的物流，纷纷投资建设不同类型的流通中心、物流中心或者配送中心，想以此成为新的经济
6、增长点。物流作为目前飞速发展的行业已经在企业经营过程中占有举足轻重的位置。据了解，在国内物流费用已占到生产成本的 40之多 1，显然它已成为了企业发展过程中必须有效控制的一个瓶颈因素之一 2。作为物流成本中一项，运输成本与其它成本不同的是，它隐藏着一些游离于财务审计监督之外的成本。它是由于运输主体的行为而有意或者无意造成的具有一定隐蔽性的将来成本和转移成本。这个成本往往是由一些不合理的物流运输所造成的 1。因此，现代企业迫切的需要做好运输决策与运输线路的安排，从而控制运输成本，提高自身在同行业市场上的竞争力。1.2 问题的提出目前国内很多企业在物流管理方面纷纷实现了电子化、信息化，而且很多 E
7、RP 软件都将物流运输管理作为一个重要功能模块。但大多数软件都将物流运输功能集中在库存管理上，而对于车辆调度的处理则相对较少，对于行车路线的选择问题更是涉及得不多。而且很多企业的实际做法是：在货物发出后采取的运输方针依然是司机说了算，凭经验进行路线的选择。这往往造成许多不合理运输现象，即违反物资运输的客观规律，不考虑物资流通的总体效益，缺乏科学的方法，孤立地处理物资运输问题，从而造成的不合理的运输现象。其中包括：对流运输(相向运输)、过远运输、迂回运输、重复运输、倒流运输、运输工具的使用效益低下、运输方式以及货物流量的分配不合理。所以通过在物流管理方面引入包含科学的路线选择功能的管理软件，对于
8、解决以上不合理运输问题具有以下几点重要意义：节约运输费用，降低物流成本；缩短流通时间，加快物资流通速度；节省运力和能源。那么应该构建一个怎样的运输网络优化模型？基于构建出来的模型，应该设计一个怎样的算法进行求解？以及如何将这样的一个算法应用到物流运输路线选择系统中来？本文通过参阅已有的国内外的文献，针对现有的物流运输网络模型，比较现有的运输路线选择算法，设计了一个通过使用改进的遗传算法来解决路线选择问题的物流运输系统，来帮助企业做好运输决策。一级标题：宋体，小四号，加粗，2 倍行距二级标题：宋体，小四号，加粗，1.5 倍行距正文：宋体，小四号，行距为固定值 20 磅*开始分节*该节为阿拉伯数页
9、码Times New Roman，四号华东交通大学学年论文- 2 -2 物流运输系统框架设计2.1 物流运输业务流程本文主要考虑一家第三方物流公司，其业务包括货运代理业务、快递业务以及车务代理业务，另外还有一些支持性业务包括：存储中心业务、汽车货运等，其业务遍及华中、华东经济较发达的城市。2.1.1 运输线路选择问题描述运输线路选择与安排中的主要内容即是做好线路选择与车辆时间安排，这类问题我们通常把其归结为车辆路径问题(Vehicle Routing Problem，简称为 VRP)。VRP 问题是一个著名的组合优化问题，它是最早由 Dantzig 和 Ramser 于 1959 年提出的一种
10、车辆路线问题。该问题可以这样描述，假设已知客户网络中的客户数量、客户所在的位置、客户需求和配送车辆的最大负荷，要求在满足约束的前提下为给定的中心仓库设计车辆路径，使运输成本最小。具体参见图 1所示。图 1 XXXXXXXX表 1 XXXXXXXXXXXXX XXX XXX XXX XXX所以物流配送或运输系统的基本结构其实是一个复杂的网络。这个运输网络，由许多像仓库、配送中心、零售商等通过物理点通过一些概念性的线段连接在一起构成。而整个网络的作用则是依靠大量的车辆在网络中各点运送货物来完成的物流运输服务。在这个服务过程中，基本的运营问题是在已知的客户地点、需求的运输量情况下解决车辆行驶路线和行
11、程安排问题。启发式算法一般将问题分解为若干个子问题，将这些子问题依次采用启发式方法或精确方法来加以解决，各子问题之间存在相互依赖的关系。采用多阶段分解步骤可使复杂的问题简单化，避免产生局部最小化的结果。像构造启发式算法通常就是从初始解出三级标题：楷体，小四号，加粗，1.5 倍行距图标题：宋体，五号，加粗段前段后 0.3 行，单倍行距表标题：宋体，五号，加粗段前段后 0.3 行，单倍行距学年论文题目- 3 -发，以邻域搜索的方式实现解的改进，并在较短的时间内获得一个可以接受的解。比较典型的就是节约算法、最邻近法、最近插入法、扫描法等等。但构造启发式算法在求解结果可能产生不理想或不合理的结果，有些只能导出满意解，而不能最优。后来Christofides、Mingozzi 、 Toth 于 1979 年提出了两阶段启发式算法，以改进构造算法求解的不足。两阶段启发式算法常常采用交互式优化的技术，把人的主观能动作用加入到VRP 问题的求解过程中，以优化结果。华东交通大学学年论文- 4 -参考文献 XXX, XXX, XXX. XXXXXXXXXXM. XX:XXXXXX, 1999.2 XXX, XXX. XXXXXXXXXXXXXXXXXX J. XXXXXX, 2005,36(7):82-92.宋体，五号，行距为固定值20 磅宋体，小四号，加粗，1.5倍行距，段前段后 0.5 行
