《物流配送车辆调度问题毕业设计》由会员分享，可在线阅读，更多相关《物流配送车辆调度问题毕业设计（38页珍藏版）》请在金锄头文库上搜索。
1、兰 州 商 学 院本科生毕业论文（设计）论文（设计）题目： 物流配送车辆调度问题 学 院、 系： 信息工程学院 数学系 专 业 (方 向)： 信息与计算科学专业 年 级、 班： 2008级信息与计算科学班 学 生 姓 名： 陈海燕 指 导 教 师： 王国兴 _年 月 日2声 明本人郑重声明：所呈交的毕业论文（设计）是本人在导师的指导下取得的成果。对本论文（设计）的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。因本毕业论文（设计）引起的法律结果完全由本人承担。本毕业论文（设计）成果归兰州商学院所有。 特此声明毕业论文（设计）作者签名： 年 月 日物流配送车辆调度问题摘 要随着经济全球化
2、和网络信息技术发展步伐的加快，现代物流作为一个新的经济增长点引起了全社会广泛的关注。作为客户服务的直接手段，物流配送无疑是现代物流管理中的重要环节，配送线路的合理与否对配送速度、运营成本及经济效益影响很大。采用科学合理的方法确定配送路线，是物流配送活动中非常重要的工作，对提高企业服务质量，增强企业的竞争力具有重要的意义。车辆优化调度问题(Vehicle Scheduling Problem简称VSP)是物流配送中的最为核心的内容，它是一个典型的NP难题，涉及到运筹学、应用数学，组合优化、图论与网络分析、计算机软件、计算机应用、物流科学、运输管理等众多学科领域。VSP是运筹学与组合优化领域的前沿
3、与研究热点问题，对它的研究为组合优化理论与方法的发展有着积极的推动作用。本文在已有数学模型的基础上，提出了适合制造企业实际需求的物流配送车辆调度问题模型的目标函数和约束条件，建立了无时限的纯装或纯卸的非满载车辆调度问题模型。在解决问题的过程中，对经典的节约算法进行适当的修正，结合Dijkstra单源最短路径算法，求得满足实际需求的可行解。关键词 物流配送 车辆优化调度问题 节约算法 Dijkstra算法 ABSTRACTAlong with the economic globalization and the network information technique stepping up,
4、 the modern logistics catches the whole social attention extensively as a new economy growth point. Being the direct means of the customer service, the model logistics is the important tache in the modern logistics undoubtedly, whether the distribution route is reasonable or not, it has great influe
5、nce on distribution rate, transport cost and economic benefit. It is a very important work in the logistics distribution activity to constitute the distribution route by scientific and reasonable methods. It is significant meaning to raise the enterprise service quantity and strengthen the enterpris
6、e competition. The vehicle scheduling problem is the very core of the content in the logistics scopes, it is a typical NP-hard problem, involving in many research subjects such as operations research, applied mathematics, combinatorial optimization, transportation network analysis, computer software
7、, computer applications, logistics science management, etc. VSP becomes advanced and hot spots in the field of operations research and combinatorial optimization research, researches for VSP can promote actively the development of the theory and method of combinatorial optimization.The research base
8、d on the mathematics model, the target function and subject condition for logistics vehicle scheduling problem model is presented which adapt to the actual request of manufacturing. The non-full loaded pure pickup or pure delivery without time windows model is builded. In the course of solving probl
9、em, the C-W saving methods is modified properly and combines with the Dijkstra single-source shortest path algorithm, which the feasible result for the actual requests is analysied.Key words Logistics Distrubution, Vehicle Scheduling Problem, C-W Savings Methods, Dijkstra Methods目 录一、引言1二、物流配送业务概述3（
10、一）物流配送概述3（二）物流配送产生的原因61、消费者消费行为的变化62、生产商生产策略的转变63、零售商向连锁经营发展的趋势74、无在库经营的倾向7（三）物流配送的流程81、物流配送的主要操作82、物流配送的一般流程11三、物流车辆调度现状12（一）物流车辆调度模式12（二）物流车辆调度存在问题分析14四、基本问题17（一）图的基本概念17（二）最短路问题18（三）旅行商问题191、问题概述192、TSP的数学模型19五、物流配送车辆优化调度模型及求解算法21（一）物流配送车辆优化调度问题的提出21（二）Dijkstra单源最短路径算法原理及实现流程211、Dijkstra单源最短路径算法的
11、基本原理212、Dijkstra单源最短路径算法实现流程22（三）无时限的纯装或纯卸非满载VSP实现241、节约算法基本原理242、节约算法实现流程253、应用举例27六、总结30参考文献32致 谢3333物流配送车辆调度问题一、引言当前，现代物流已被公认为是企业在降低物质消耗、提高劳动生产率以外创造利润的第三个重要源泉，也是企业降低生产经营成本，提高产品市场竞争力的重要途径，据专家测算，现代物流成本约占企业经营成本的30-50%，当一个有效的物流系统与企业主要商业系统集成之后，可使仓储量降低50%，准时交货率提高40%，营业收入增加10%以上1。在经济发达国家和一些经济水平较高的发展中国家，
12、现代物流水平己成为影响企业竞争力的关键因素1,2 。与发达国家相比，我国的物流产业效率较低1。根据全国第三产业普查资料，我国交通运输、仓储、代理和批发等行业的成本费用之和占国民生产总值的比重为15%左右，如果考虑其它相关流通环节的费用和流通过程中的物流损失，则全社会物流费用支出约占国民生产总值的20%以上，而美国的全社会物流费用支出仅占其国民生产总值的10%左右。另据有关资料，目前我国一般工业品从产品出厂经过装卸、储存、运输等各个物流环节到消费者手中的流通费用约占商品价格的50%左右；而新鲜水果、易变质食品、某些化工产品的流通费用有的高达商品售价的70-80%；我国汽车零配件的生产中，其加工装
13、配时间仅占2%，而98%的时间是原材料、零配件的储存、装卸和搬运时间。在各种产品的生产和流通环节中还有大量原材料、零部件和产品的“库存”3。这些费用和时间上的消耗以及大量存在的库存正是潜在的实施物流管理的领域，为物流的发展留下了巨大的空间。在这种形势下，研究如何通过实施科学的物流管理，以提高物流效率、降低物流成本、提高服务质量是十分必要的。物流配送是现代化物流中的一个重要环节，它是指按客户(包括零售商、用户等)的订货要求(包括货物种类、数量和时间等方面的要求)，在物流中心(也称物流基地、物流据点，包括配送中心、仓库、车站、港口等)进行分货、配货工作，并将配好的货物及时送交收货人的物流活动。物流
14、配送过程主要包括以下作业环节：从生产工厂进货或运达并集结的集货作业；根据各个客户的不同需求，在物流中心将所需要的货物挑选出来的分货和配货作业；考虑配送货物的重量和体积，充分利用车辆的载重和容积的货物配装作业；合理确定车辆配送路线并及时送货的作业。可见，物流配送是一种集集货、分货、配货、配装、送货等多种功能为一体的物资流通方式。在物流配送业务中，存在许多优化决策的问题，车辆优化调度问题涉及面较广，需要考虑的因素较多，本文将着重研究物流配送车辆调度的一般问题。国外将物流配送车辆调度问题归结为VRP ( Vehicle Routing Problem，即车辆路径问题)和VSP (Vehicle Sc
15、heduling Problem，即车辆调度问题)，该问题于1959年由Dantzig和Ramse提出后4 ：很快便引起运筹学、应用数学、组合数学、图论与网络分析、物流科学、计算机应用等学科的专家以及运输计划制定者的极大重视，并一直是运筹学与组合优化领域的前沿与热点问题。VRP与VSP是根据问题的空间特性和时间特性的相对重要性来划分的，一般认为当不考虑时间要求，仅根据空间位置安排线路的称为Routing，根据时间要求安排线路的称为Scheduling，同时考虑空间位置和时间要求的称为Routing和Scheduling混合问题，也有不区分两者的，若有具体约束则加上定语，例如将有时间要求的车辆调度问题称为Vehicle Routing Problem with
