运输工程课程设计题目货运车辆运行路线的优化院(部) XXXXXXXXXXXX专业物流工程班级物流XX学生姓名XXXX学号XXXXXX课程设计任务书题目货运车辆运行路线的优化院(部) XXXXXXXXXXXXX专业物流工程班级物流XXX学生姓名XXX学号XXXXXXX年XX 月XX 日至XX 月XX 日共X 周指导教师XXXXXX 年XX 月X 日摘要物流配送中的车辆路线优化方法和系统，是实现快速、准确和低成本物流配送的重要手段和途径，是现代物流系统必不可少的重要部分。

车辆运行路线问题在现实生活中有着广泛应用，也是现代物流配送系统中的重要环节，因此，论文的选题有着重要的理论意义和应用前景。

现有的数学方法在解决此问题时还根不完善，缺乏科学的理论作指导,这些问题的解决，往往需要用启发式方法作出决策和判断，追求运输系统总体最优、总费用最低、总效益最大的最优解。

本文首先介绍货运车辆调度问题的分类,根据问题的不同性质将货运车辆优化调度分为满载和非满载调度,有时间要求和无时间要求的调度等多种类型。

然后,详细介绍求解货运车辆优化调度问题常用的启发式算法的原理、模型和求解过程。

本文所论述的方法对于实际的货运车辆调度问题具有指导意义。

关键词：物流配送，启发式算法，运输车辆，优化方法1我国物流配送的发展分析1.1我国物流配送发展现状长期以来，由于受计划经济的影响，我国物流社会化程度低，物流管理体制混乱，机构多元化, 导致社会化大生产、专业化流通的集约化经营优势难以发挥，规模经营、规模效益难以实现，设施利用率低，布局不合理，重复建设，资金浪费严重。

由于利益冲突及信息不通畅等原因，造成余缺物资不能及时调配，大量物资滞留在流通领域，造成资金沉淀，发生大量库存费用。

另外，我国物流企业与物流组织的总体水平低，设备陈旧，损失率大、效率低，运输能力严重不足，形成了“瓶颈”，制约了物流的发展，物流配送明显滞后。

商流与物流分割，严重影响了商品经营和规模效益。

实践证明，市场经济需要更高程度的组织化、规模化和系统化，迫切需要尽快加强建设具有信息功能的物流配送中心。

随着电子商务的日益普及，中国的物流配送业一定会按照新型物流配送中心的方向发展。

据国家有关部门预测，未来10年全国还计划兴建100个物流中心，以及7个主要交易中心，由此看来，物流业在我国的发展前景将是十分广阔的。

2001年3月，国家经贸委、铁道部、交通部、信息产业部、外经贸部和民航总局六部委局联合印发了《关于加快我国现代物流发展的若干意见》。

国家计委、国家经贸委联合发布的《当前国家重点鼓励发展的产业、产品和技术目录》中，已把发展物流配送中心列为重点鼓励发展的项目。

在中国政府大力发展现代物流业的宏观政策引导下，各地纷纷出台了自己的物流发展规划，把发展现代物流列入了重要议事日程。

1.2我国物流配送存在的问题(1)对物流配送缺乏正确和充足的认识。

20世纪80年代初，我国就引进物流配送的概念，经过二十多年的经济发展，越来越多的人对物流配送有了全面的了解和认识，但在相当多的企业中，其领导人的观念还停留在成本中心、利润中心上，没有把物流配送放到服务中心、战略中心的高度。

(2)物流配送人才短缺。

国外物流配送的教育和培训系统非常发达，很多大学和学院开设物流管理专业，部分院校设置研究生物流课程，并在社会上全面开展物流配送的职业教育。

许多国家的物流从业人员必须接受职业教育，获得从业资格后，才能从事物流配送方面的工作。

相比较而言，我国在物流配送方面的教育还非常落后，在高等院校中开设物流专业和课程的仅有10所左右，占中国全部高等院校的1％，研究生层次教育才刚刚起步，职业教育更是贫乏。

(3)物流配送效率低，物流装备标准化程度低。

目前，我国大多数物流配送企业是在传统的企业机制上发展起来的，物流服务内容还停留在仓储、运输层面上，能够提供综合性服务的物流配送企业还很少。

同时运输、仓储的现代化水平比较低，物流配送中心建设发展比较缓慢，专业化操作水平不高，导致了物流配送效率低下。

此外，我国物流部门条块分割、自成体系，使得物流配送环节中各种运输方式之间装备标准不统一，增加了物流配送的无效作业环节，使物流配送速度降低、物流配送成本升高。

(4)缺乏有效线路优化方法。

目前，我国的交通运输设施布局很不合理，车辆运行路线存在严重的不足与资源浪费，主要的运输通道经常出现供需矛盾，从而影响了物流配送的效率；物流网点没有统一的布局，物流企业分布过于分散，无法实现资源的有效配置；物流设施装备普遍较差，不能适应现代物流的发展。

并且由于我国的物流信息管理和技术手段比较落后，无法建立公共的物流信息交流平台，对物流配送过程中各个环节进行统一管理和调度，实现高效的物流配送。

本文主要从优化线路方法方面出发，摒弃人们的利用经验的方法，结合运用启发式算法，从科学的角度出发，最大限度的节约成本，提高配送效率。

2运输车辆调度规划问题分类货运车辆优化调度问题可根据不同性质具体分为以下几类：按运输任务分为纯装问题、纯卸问题以及装卸混合问题。

按照车辆载货问题分为满载和非满载问题，满载问题是指货运量多余一辆车的容量，完成所有任务需要多辆运输车辆，根据是否返回车场划分为车辆开放问题和车辆封闭问题，车辆开放问题是指车辆不返回其出发地，车辆封闭问题是指车辆必须返回其出发车场。

按照优化的目标可分为单目标优化问题和多目标优化问题；按照有无休息时间要求可分为有时间休息的调度和无时间休息的调度问题。

2.1车辆类型的选择运输车辆的选择，主要是指根据货物的种类、特点及批量合理选择车辆类型及载量大小。

合理选择运输车辆，可以完好、准时、无误地完成任务，降低运输费用。

合理选择运输车辆是提高车辆运输生产率、降低运输成本的有效途径之一。

车辆的选择应保证运输费用最少这一基本要求。

其主要影响因素包括：货物的类型、特性与批量；装卸工作方法；道路与气候条件：货物运送速度；运输工作的劳动、动力及材料消耗量等。

车辆类型的选择，主要是指对通用车辆和专用车辆的选择。

根据货物的特性、包装物的类型和形状采用相应的专用车辆，如拦板式货车、罐式汽车、厢式车、冷藏车、平板车、水泥车及轴式挂车等，不但可以保证货物完好无损，改善劳动条件，提高行车安全，还可降低运输成本。

采用具有气动式卸货机构的水泥车与通用车相比，可以减少水泥损失和运输费用30％左右；采用面粉专用车与通用车相比，袋装面粉运输费用可降低1倍左右。

对于载重量相同的通用车与专用车相比，因专用车上增加了若干附属设备，使得其有效载重量有所降低，这样造成了车辆运输生产率下降。

显然，采用专用车辆缩短装卸时间，使其生产率提高是有一定条件的。

如何确定选择通用车辆还是专用车辆，通常可采取比较其生产率或成本的方法．即计算等值运距。

2.2车辆载重量的选择确定车辆最佳载重量的主要影响因素就是货物批量。

货物批量大，选择最高载重量车辆(道路法规允许范围内)运输是合理的，但装卸生产率应与之相适应。

货物批量有限，车辆的载重量必须与其相适应。

否则运输成本将增加。

在汇集式路线组织运输时，如遇特殊情况，也可选用较大载重量车辆。

2.3环形式行驶路线的优选标准选择环形式行驶路线的原则是：当完成同样货运任务时，里程利用率β最高为最佳。

环形式行驶路线以运次为基本运输过程进行组织，并且在一条环形路线上包含有多个运次、多项货运任务。

其中，每个运次的重车路线由货运任务决定，所以重车方向是一定的，无从选择。

那么，只有合理组织该环形路线各个运次的衔接顺序，使总空车行程最短，才能使里程利用率β最高，才能获得最经济的行驶路线。

3启发式算法3.1汇集式路线定义定义：汇集式路线（一般情况下为封闭路线）是指车辆沿着分布于运行路线上各装卸作业点，依次完成相应的装卸作业，且每运次的货物装（卸）量均小于该车额定载质量，直到整个车辆装满（或卸空）后返回出发点的行驶路线。

汇集式行驶路线的优选原则是以每周转的总行程最短为最优。

当车辆采用汇集式行驶路线完成运输任务时，每次周转的货物周转量的大小与车辆沿路线上各货运点的绕行次序有关。

若绕行次序不同，即使完成同样货运任务其周转量也不一样。

在这种情况下，按总行程最短组织车辆进行运输最为经济。

3.2启发式算法启发式方法是从尚未安排的车辆、运输任务或行驶路径中按照构造算法进行选择，知道所有任务和车辆匀被调度为止。

够造的每一步，根据某个判别函数，把当前的线路构型和另外的构型进行比较并加以改进，以最小代价把一个不在当前构型上的需求对象插入进构型，最后得到一个较好的可行构型。

常见的构造算法有节约算法、最邻近法、最近插入法等。

启发式方法并不追求问题的最优解，而是强调问题的满意性，只要决策者认为所得到的解能够较好地满足要求就可以了。

可将此问题归为运筹学中的货郎担问题，应用启发式算法来进行近似求解，其基本思路是：当货运点多，总运量较大、需用运输车辆超过一辆时，选择汇集式行驶路线首先根据运输车辆每车次最高装载量定额，按就近调车的原则对货运点进行分组；然后按总行程最短的原则，采用启发式算法分别确定每车沿其本组货运点的绕行次序，以选定单车运行路线。

现以分送式路线选择为例，阐述其选择方法。

3.2.1首先确定计算所需数据所需数据包括：货运点的分布图或货运点间里程矩阵B ij ； 货运点收（卸）货量（q j ）； 单车最高装载量（q H ）。

其中，i 、j 为货运点序号，q j 、q H 的计算单位视货物情况而定（如可以是吨、件、桶、箱、瓶等）。

本设计中单位为吨。

3.2.2各货运点间里程（Bij ）和收货量（qj ）统计表某牛奶厂，拟采用一辆中型载重车（q=10吨）将鲜奶配送给6个固定的牛奶销售点，要求采用启发式法选择车辆绕行次序，目标是在完成任务的前提下，绕行的总里程最短。

表3.1各点之间的里程表表3.2各牛奶销售点的需求表3.2.3计算过程在此基础上可采用启发式算法按下面的程序进行计算：图3.1分送式路线选择总程序图A :确定货运点分组数d 为（公式3-1）经计算可得本方案中货运点分组数d 为1A: 计算货运点分组数dd>1?开始B: 单车货运点分组S:NkC: 选择单车货运点绕行次序S>1?D: 选取: S:∑=min LN结束否是否是式中∑qj——各收货点收获量之和（单位：t）；[ ]——取整函数的标记。

B :单车货运点分组：其程序为:1）确定单车行驶路线序号N（N=1，2，…n），即单车货运点分组组别序列，以依次确定单车行驶路线。

2) 选择第一个收货点。

以K表示收货点的序号，即选择K=1的收货点。

首先确定距发货点（j = 0）最远的收货点（j = r=6）为第一个收货点，即确定maxLoj 及车辆实际载质量q=qj =2吨,并将该点记为NK = N1，即第N组单车行驶路线上的第一个收货点。