物流配送车辆调度问题毕业设计

1、兰 州 商 学 院本科生毕业论文（设计）论文（设计）题目： 物流配送车辆调度问题 学 院、 系： 信息工程学院 数学系 专 业 (方 向)： 信息与计算科学专业 年 级、 班： 2008级信息与计算科学班 学 生 姓 名： 陈海燕 指 导 教 师： 王国兴 _年 月 日声 明本人郑重声明：所呈交的毕业论文（设计）是本人在导师的指导下取得的成果。对本论文（设计）的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。因本毕业论文（设计）引起的法律结果完全由本人承担。本毕业论文（设计）成果归兰州商学院所有。 特此声明毕业论文（设计）作者签名： 年 月 日物流配送车辆调度问题摘 要随着经济全球化和

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 influen

5、ce 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 enterprise

6、 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 based

8、 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 proble

9、m, 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致 谢33物流配送车辆调度问题一、引言当前，现代物流已被公认为是企业在降低物质消耗、提高劳动生产率以外创造利润的第三个重要源泉，也是企业降低生产经营成本，提高产品市场竞争力的重要途径，据专家测算，现代物流成本约占企业经营成本的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 sched

15、uling problem，即车辆调度问题)，该问题于1959年由dantzig和ramse提出后4 ：很快便引起运筹学、应用数学、组合数学、图论与网络分析、物流科学、计算机应用等学科的专家以及运输计划制定者的极大重视，并一直是运筹学与组合优化领域的前沿与热点问题。vrp与vsp是根据问题的空间特性和时间特性的相对重要性来划分的，一般认为当不考虑时间要求，仅根据空间位置安排线路的称为routing，根据时间要求安排线路的称为scheduling，同时考虑空间位置和时间要求的称为routing和scheduling混合问题，也有不区分两者的，若有具体约束则加上定语，例如将有时间要求的车辆调度问题

16、称为vehicle routing problem with time windows。在现实应用中，由于scheduling涉及的内容和关键技术比routing宽泛，因此绝大多数研究者的主要研究兴趣集中在scheduling问题上，且主要对车辆调度问题(vehicle scheduling problem简称vsp)开展广泛的研究。在现实生产和生活中1，邮政投递问题、飞机、铁路车辆、水运船舶及公共汽车的调度问题、电力调度问题、管道铺设问题、计算机网络拓扑设计问题都可以抽象为物流配送车辆调度问题。因此，将物流配送车辆调度问题作为研究对象具有一定的理论和现实意义。二、物流配送业务概述（一）物流配

17、送概述配送的概念有多种表述。日本工业标准表述，将货物从物流结点送交收货人。日本1991年版物流手册的表述:生产厂到配送中心之间的物品空间移动叫“运输”，从配送中心到顾客之间的物品空间移动叫“配送”。美国物流管理供应链过程一体化表述:实物配送这一领域涉及将制成品交给顾客的运输。实物配送过程，可以使顾客服务的时间和空间的需求成为营销的一个整体组成部分我国现代物流学表述:配送是以现代送货形式实现资源最终配置的经济活动；按用户订货要求，在配送中心或其他物流结点进行的货物配备并以最合理方式送交用户。一般认为物流配送是指物流过程的中转型送货(也称为二次输送、支线输送、终端输送)。也就是在产品用户集中区域，

18、按用户的订货要求和时间计划，在物流中心配货并将配好的货物采用汽车巡回运送的方式交收货人的小范围、近距离、小批量、多品种、为用户服务的运输3。配送不是单纯的运输或送货，而是运输与其它活动的组成，除了各种“运”、“送”活动外，还要从事大量的集货、分货、配货、配装等工作，是配与送的结合。对于配送的深入认识，应当掌握以下几个要点:(1)配送的资源配置作用配送是“最终配置”，因而是接近顾客的配置。对于现代企业而言，“接近顾客”是至关重要的。美国兰德公司对“幸福”杂志所列的五百家大公司进行一项调查表明“经营战略和接近顾客至关重要”，所以接近顾客的配送，自然取得了它在现代经济中的地位。(2)配送的实质是送货

19、配送的主要经济活动，尤其是接近顾客的经济活动是送货。(3)配送是现代送货现代两个字表述了和旧式送货的区别。其区别主要在于:)一般送货可以是一种偶然的行为，而配送却是一种体制行为，是市场经济的一种体制形式。)一般送货是完全被动的服务行为，而配送则是有一定组织形式的计划行为。)配送依靠现代生产力，依靠科技进步支撑，实现对用户的送货服务。(4)配送是“配”和“送”有机结合的形式配送利用有效的分拣、配货等理货工作，使送货达到一定的规模，以利用规模优势取得较低的送货成本。如果不进行分拣、配货，有一件运一件，需要一点送一点，这就会加大送货成本。所以，追求整个配送的优势，分拣、配货等工作是必不可少的。(5)

20、配送是市场经济产物配送是在市场经济条件下，在“供大于求”的买方市场环境中所派生的一种形式。 在买方市场环境下，用户具有选择权，而卖方需要通过有效的服务来售出自己的产品，争夺一块份额，这就形成了有提供者、有需求者的理想市场环境，使配送得以发展。(6)配送以用户的要求为出发点“按用户的订货要求”明确了用户的主导地位。配送是从用户利益出发，按用户要求进行的一种活动，因此，在观念上必须明确“用户第一”、“质量第一”。配送企业的地位是服务地位而不是主导地位，不能从本企业利益出发，而应从用户利益出发，在满足用户利益基础上取得本企业的利益。更重要的是，不能利用配送损伤或控制用户，不能利用配送作为部门分割、行

21、业分割、割据市场的手段。 (7)以最“合理的方式”的提法是基于这样一种考虑:过分强调“按用户要求”是不妥的，受用户本身的局限，要求有时候存在不合理性，在这种情况下会损失自我或双方的利益。对于配送而言，应当在时间、速度、服务水平、成本、数量等多方面寻求最优，实现 “双赢”的原则。（二）物流配送产生的原因配送作为先进的物流形式，它的产生以及推广并不是偶然的，而是随着现代商业经营环境和经营形式的变化而出现的。这些变化主要体现在:1、消费者消费行为的变化随着人们生活水平的提高，20世纪90年代以来，人们对生活的追求已逐渐从原来的温饱型、数量型转向小康型，对生活质量的要求越来越高。伴随着这种生活观念的变

22、化，在经济社会向国际化、信息化急剧转变的基础上，消费者价值观趋于多元化和多样化，喜欢购买具有差别化的商品。这种消费行为变化对企业的生产和经营产生了深远的影响，使生产和销售企业在适应消费者消费行为变化的过程中，开始强化物流管理，通过少批量、多品种、快速化、柔性化的生产和经营来满足消费者的需求。2、生产商生产策略的转变在传统消费模式中，当新产品被厂家研制、开发出来后，通过各种各样的媒体、特别是电视广告等促销手段的运用和商业推广，其一般能唤起全国规模的需求，这种营销模式背后隐含的是消费者具有“与他人一致”的消费意识。与这种消费者相对应，零售业以百货业和综合超市为中心，通过大量购进、大量陈列廉价的商品

23、来推动销售额的增长。但是随着消费个性化、多样化的发展，原来那种商品在一部分人中开始流行后，大家争相购买的情况会越来越少，而且流行商品的生命周期也越来越短。在这种状况下，厂家要准确预测特定商品的流行程度十分困难。此外，基本生活品在全社会普及之后，商品在质量上的稍微改进或价格的稍微降低都不能大量激发消费者的购买欲望，因而能开发出具有爆发性需求规模的革新产品也会越来越困难。 正因为如此，如今很多厂商都在积极开展多品种战略，即将原来的产品加以改良，附加各种机能，形成产品间微妙的差异，积极开展多品种生产战略。3、零售商向连锁经营发展的趋势在传统的流通模式下，商品从制造商生产出来后，经由层层的批发商再到零

24、售商，最后到达消费者手上，批发商在此扮演着整个通路的枢纽作用。随着消费形态的改变，整个市场成为消费者导向，这种趋势迫使企业改变传统的经营方式，建立新的竞争策略，许多制造商为了将自己生产的产品直接输往末端市场，纷纷构建自有的通路体系，这使得超级市场、便利点、连锁店一时之间快速成长。伴随着连锁经营的兴起，配送服务的重要性越来越为人们所关注。4、无在库经营的倾向零售业中与消费个性化、多样化以及厂商多品种生产相对应，无论在既存的零售业态百货店和超市中，还是新型的24小时店等新业态中，经营的商品品种数越来越多。但是，与此同时，由于政策、环境、房地产价格等原因，店铺的规模和仓库规模不可能无限扩大，特别是在

25、大都市中，由于人口密度大、地价高昂、消费更新快、环境规制严格等原因，更加限制了仓储点和仓储空间的扩大，在这种情况下，只有提高店内管理效率，通过加快商品周转来抵消仓储空间不足等问题。如今，在国际上，大型零售业的方针均已从原来通过开设新店寻求外延型发展，转向充实内部管理和投资，积极探索内涵型发展。除此之外，推动无在库经营的原因是，由于消费行为的多样化、个性化发展，商品品牌、品种、式样的急剧增多，使零售商对顾客实际需求的预测十分困难。在这种状况下，库存越大，零售企业承担的资金占用和滞销风险也越大，因此为了加速资金周转和降低风险，零售企业必须尽可能地压缩库存，实现实时销售。具体看，现代零售业的管理重点

26、是：)实行“单品管理”，迅速制定经营中的“畅销品”与“滞销品”，以此为基础确定定货商品的种类和数量。)实行“无在库经营”，在有限的空间里陈列更多的商品，降低销售风险，极力抑制各类商品的在库量，彻底实现在库管理和在库成本的削减。（三）物流配送的流程1、物流配送的主要操作(1)备货配送的准备工作和基础工作。备货工作包括筹集货源、订货、采购、集货、进货及有关的质量检查、结算、交接等。配送的优势之一就是可以集中若干用户的需求进行一定规模的备货。备货是决定配送成败的初期工作，如果备货成本太高，会大大降低配送的效益。(2)储存配送中的储存有储备及暂存两种形态:)储备 配送储备是按一定时期的配送经营要求，形

27、成的对配送的资源保证。这种类型的储备数量较大，储备结构也较完善，视货源及到货情况，可以有计划地确定周转储备及保险储备结构及数量。配送的储备保证有时在配送中心附近单独设库解决。)暂存另一种储存形态是暂存，是具体执行配送时，按分拣配货要求在理货场地所做的少量储存准备。由于总体储存效益取决于储存总量，所以这部分暂存数量只会对工作方便与否造成影响，而不会影响储存的总效益，因而在数量上控制并不严格。还有另一种形式的暂存，即是分拣、配货之后，形成的发送货载的暂存，这个暂存主要是调节配货与送货的节奏，暂存时间不长。(3) 分拣及配货这是配送不同于其他物流形式的有特点的功能要素，也是配送成败的一项重要支持性工

28、作。分拣及配货是完善送货、支持送货的准备性工作，是不同配送企业在送货时进行竞争和提高自身经济效益的必然延伸，所以，也可以说是送货向高级形式发展的必然要求。有了分拣及配货，就会大大提高送货服务水平，所以，分拣及配货是决定配送系统水平的关键要素。(4)配装在单个用户配送数量不能达到车辆的有效载运负荷时，就存在如何集中不同用户的配送货物，进行搭配装载以充分利用运能、运力的问题，这就需要配装。和一般送货不同之处在于，通过配装可以大大提高送货水平及降低送货成本，所以配装也是配送系统中有现代特点的功能要素，是现代配送不同于传统送货的重要区别之处。(5)配送运输配送运输属于运输中的末端运输、支线运输，和一般

29、运输形态主要区别在于:配送运输是较短距离、较小规模、频度较高的运输形式，一般使用汽车和其他小型车辆做运输工具。与干线运输的另一个区别是，配送运输路线选择问题是一般干线运输所没有的，干线运输的干线是惟一的运输线，而配送运输由于配送用户多，一般城市交通路线又较复杂，如何组成最佳路线，如何使配装和路线有效搭配等，是配送运输的特点，也是难度较大的工作。(6)送达服务 配好的货运输到用户还不算配送工作的完结，这是因为送达货和用户接货往往还会出现不协调，使配送前功尽弃。因此，要圆满地实现运到交货的移交，并有效地、方便地处理相关手续并完成结算，还应讲究卸货地点、卸货方式等。送达服务也是配送独具的特殊性。 (

30、7)配送加工在配送中，配送加工这一功能要素不具有普遍性，但是往往是有重要作用的功能要素。主要原因是通过配送加工，可以大大提高用户的满意程度并提高被配送货物的附加价值。配送加工是流通加工的一种，但配送加工有它不同于一般流通加工的特点，即配送加工一般只取决于特殊用户要求，其加工的目的较为单一。(8)回程在执行完配送的使命之后，车辆需要回程，在一般情况下，回程车辆往往是空驶，这是降低配送效益、提高配送成本的因素之一。在规划配送路线时，回程路线应当尽量缩短；在进行稳定的、计划配送时，回程车辆可将包装物、废弃物、残次品运回集中处理，或者将用户的产品运回配送中心，作为配送中心的资源，向其他用户进行配送。2

31、、物流配送的一般流程不同的配送对象有不同的配送流程，但一般来说，物流配送的流程可用图1表示： 订货协议/货物运到验货 退货代理协议理货 废弃物的处理订单履行 暂存包装、疏通、加工 验货/拣选上货架 配货发货区暂存发货发货图1物流配送的一般流程三、物流车辆调度现状（一）物流车辆调度模式物流车辆调度过程是整个物流过程中重要的步骤，在降低运输成本上有着关键的作用。但是目前，我国货物运输车辆调度方法比较落后，多采用传统的人工方法编制调度方案。目前仍然被大多数公司采用的车辆调度模式，是一种基于传统设备和调度员、驾驶员经验的调度模式，并且由于很多物流企业的一部分车辆的所有权不属于物流企业，这一部分车辆的所

32、有权属于车主，车主带车加入物流企业，完成所分配的任务并且按照所完成的任务数量来得到收入，车主与物流企业并不属于从属的关系，加大了管理的难度。所以，调度决策者只对驾驶员分配和安排调度任务，对路径的选择很多情况下都由司机凭经验做出选择。这种调度模式的基本过程如下:(1)集货过程:集货有专门负责的车辆来完成，由于在集货过程中，货物主要来自物流点周围，所以根据货物来自于不同区域把为物流企业集货服务的车辆分为不同的组别，比如某公司把该公司专门负责集货的车辆分为4个组，分别负责来自周边4个市区的货物的集结任务。当顾客向该物流公司提出运输需求时，调度管理人员便电话通知相应的车主，之后车主便去完成相应的任务。

33、(2)联系收获人:对于一部分货物，货主会在提出运输需求的同时提出该货物的目的地和到达目的地的准确时间。对于另一部分货物而言，物流公司调度管理人员就会及时与收货人进行联系，确认交货的时间和地点。在服务过程中出现问题时，最重要的就是要及时与顾客及时沟通，协商解决。(3)货物的存放:货物被送到公司所属的仓库后，根据货物的去向和出货的先后顺序存放于仓库中。把未知出货去向和时间的货物放于仓库的其他角落。(4)送货过程:物流公司把专门用来负责送货的车辆分为两种，第一种为长途送货车辆;第二种为市内配送车辆。第一类车辆由于运输距离远、载重吨位大、购买费用高，所以这一部分车辆大多属于公司的固定资产;第二类车辆负

34、责武汉市内的货物配送，这一部分车辆大多不属于物流公司。在第二类车辆中，物流公司又把它们分为4个组，分别负责来自周边4个地区的货物的配送任务。当的有送货任务时，调度管理人员会电话通知车主，车主开车到仓库后装货，然后把货物按要求送到其收货人指定地点卸货，收货人检查货物的完整性后签字确认完成运输任务。从上述所说的物流车辆调度过程，我们可以知道，这些物流企业中的车辆调度其实只分配了运输任务，对行驶路径没有做规定。那么对路径的选择很多情况下都由驾驶员凭经验做出选择，驾驶员选择所走路径时考虑最多的几个因素如下:)运行费用因素:包括燃油费与过路费，所选择路径满足运行费用最小。)时间因素:在顾客规定的时间内把

35、货物送达口但是我国的物流需求大多属于低端的物流需求，很多情况下，顾客对时间的要求并不是那么严格。)路况条件因素:选择比较适合自己的道路或者是路况条件较好的路径但是每个驾驶员都有自己的价值取向，这个影响因素的随机性比较大。)货物种类因素:对不同的货物，可能会选择出不同的路径。比如，对于易碎品，司机可能会选择路况条件好的路径;对于贵重品，则会选择即安全又快捷的路径，使得贵重物品最先卸载。)目的地的距离因素:一般情况都是先送距离较近，然后再送距离远的货物。（二）物流车辆调度存在问题分析上节所描述的基于经验的车辆调度模式，基于传统设备和调度员、驾驶员经验。例如，某物流公司经理对该企业的物流车辆地调度总

36、结为:实事求是，能用为主。由于没有一套规范的、完整的、科学的理论进行指导，当出现突发情况，正常的秩序较容易被打破，现场调度就可能出现问题。比如某辆车在中途出现故障，但是一时也找不到其他空闲车辆;一旦正常的秩序被打乱，那么就会影响到物流企业的经营效益和该企业在顾客心中的信心。这种状况也很难跟上现代化发展的步伐。这种基于经验的传统调度模式存在着以下一些问题:(1)我国物流实际与理论研究差距很大，限制了充分发挥物流车辆调度的功能和优势。当今大部分物流企业管理者都认为，现在整个物流运输市场现状为粗放服务，缺乏高标准的物流需求，所以对物流车辆调度的要求也不高。例如顾客大部分时候对时间的要求弹性很大，物流

37、企业有充分的时间来完成顾客的需求服务，所以时间因素很多时候并不是物流企业首要考虑的问题，而考虑最多的是经济因素。(2)物流企业的规模大都偏小，这导致很多为物流企业服务的车辆的所有权不属于物流企业，而是属于驾驶员的私人财产，这在很大程度上制约了物流企业对车辆和驾驶员的管理，最终导致整个物流车辆调度的效率不高。因为物流企业对驾驶员的管理一般基于任务管理，即根据驾驶员每天完成的任务，物流企业给他相对应于任务的报酬，但是驾驶员在服务过程中物流企业却没有能力去进行管理。(3)任务分配和路线选择相互脱离，这在整个物流调度过程中，就不能达到整体的最优，并且服务的质量也大大降低。在上节所分析的现行的车辆调度过

38、程，不论是集货过程还是送货过程，物流企业的调度管理员只对驾驶员分配和安排任务，具体的路径选择由驾驶员根据自己的偏好进行选择，这就可能会导致一系列不良的后果。首先，任务分配和路径选择的相互分离，物流成本不可能尽可能的降低；其次，车辆等其他资源不可能充分利用，导致资源的闲置和浪费；最后，由于具体路径选择有驾驶员选择，具有很强的主观性、随机性，服务质量的标准没有统一的认识，服务质量也参差不齐。(4)集货过程与送货过程相互脱离，这导致物流企业运作成本增加，并且物流企业对所掌握的资源利用率降低。在理论学习中，混合任务运输将大大提高车辆的利用率，降低物流成本和企业运作成本。但是在实际工作中，由于每次分配给

39、每个司机的任务一般都在5个以上，等司机完成这些任务后，时间己经不应许司机再去完成其他的运输任务。(5)物流企业所掌握的运输资源规格不一，但在调度过程中没有特别考虑这个问题。服务于城市集货和城市配送工作的车辆来自社会，车型五花八门，每辆车的新旧程度、载重吨位、单位油耗等参数都不尽相同，但是在具体的车辆调度过程中，很少考虑到那种车型更适合于什么货物、什么路线的运输。(6)物流企业在车辆调度工作上的资金投入有限，限制了车辆调度工作所需要的设备的更新。物流企业属于资金密集型企业，其投资资金大多用于车场的建设、车辆的购买、仓库的建设等大规模资金投资的基础项目建设，这也导致现行的调度模式还是基于电话、传统

40、仓库、人力搬运设备的等传统设备，车辆调度工作效率的提升空间便受到了限制。(7)物流企业信息化水平较低，物流企业的信息技术水平较低，是车辆调度发展的巨大障碍。由于我国物流企业总体上信息化起步较晚，信息化程度较低，对企业信息化存在着许多分歧，不少物流企业还处在电话联系、手工操作、人工装卸的低级阶段，并且信息化建设的难度也比较大。例如，在某物流企业中，把本来安装在负责该公司长途货运的大型车辆上的gps系统全部拆了，理论上很好的系统，但是在实际工作中，顾客不愿付出多余的代价来了解货物的实时信息。(8)一些融入当今先进的数字移动通信技术、计算机实时信息处理技术、全球卫星定位系统(gps)、地理信息系统(

41、gis)、数据库处理技术于一体的比较先进的车辆调度系统己经开始运用在120救护车调度、城市出租车调度等。但是在货物运输领域的运用还比较少见。(9)物流车辆调度观念的落后并且缺乏相应的人才。在调研过程中，大多数物流企业中的车辆调度工作人员的文化水平不高并且没有接受过专业的学习和培训。比如，在运输过程中，一味的追求成本最小化，就会出现一些不应出现的情形，超载运输是最常见的一种，运输安全受到比较大的威胁。从总体上来看，我国的物流车辆调度还处于发展的处级阶段，建立完善的交通车辆调度系统和科学的交通车辆调度方案，对于我们的物流产业及其与相关行业的发展，都有着非常重要的意义。四、基本问题（一）图的基本概念

42、在生产和日常生活中，人们常常用点和线画出的示意图来反映一些对象之间的关系。如一个地区的交通图是表明这个地区的一些城镇及这些城镇之间的道路沟通情况的示意图。这里所研究的图是反映实际生活中某些对象之间某种特定关系的一种工具。以点代表研究的对象，点和点的连线表示这两个对象之间的特定关系，与通常的几何图形或函数图像中的图是不同的。这里的点不是真正的几何点，它只是某种事物的一种抽象，连线也不是几何中的线段，而是代表某些事物之间的关系6，因此点与连线的画法具有随意性。则图可以表示为： =, 式中是点的集合，是边的集合。上面定义的图 区别于几何学中的图。在几何学中，图中点的位置、线的的长度和斜率等都十分重要

43、，而这里只关心图中有多少个点以及哪些点之间有线相连。有向图上的连线是有规定指向的，称作弧。弧的代号是( ,),表明方向是从点指向点。有向图是点与弧的集合，记作=,。上一段介绍的图是无向的。无向图中两个方向均可以通过，但有向图中只能沿着箭头方向通过。对于实际问题构成的图，不仅需要表明各元素之间的联系，还需要表明这些联系的强弱程度。这时，可给图中的反映联系的边赋一数值，称为权，来表明一定的含义，一般标在边上。赋权的图称为网络图。这里的权在不同的情况下具有不同的含义，它可以表示距离，也可以表示时间，甚至还可以表示费用。（二）最短路问题最短路问题是图论中的基本问题，许多实际问题都可以用它来解决，例如管

44、道的铺设、线路的安排、厂区的布局、设备更新等等。另外，诸如运价最小、运行时间最短、最可靠路等问题，都可以转化为最短路问题加以解决7。在运输网络的每一个对子之间的最小路径，称为最短路。最短路在物流运输、配送活动中的意义是不言而喻的，一般情况下，最短路的权重是以对之间的距离、车辆行驶时间、费用来表示。求解物流网络的最短路就是求出在每一对对子之间的最短运输距离、最短行驶时间以及最省的运输费用。由此可见，求解最短路意义是很重大的。dijkstra算法是目前公认的解决在权 0的情形下，此类问题的最好算法，在物流运输中，这一约束条件是完全能够满足的。（三）旅行商问题1、问题概述 旅行商问题(traveli

45、ng salesman problem，简称tsp)是运筹学、图论以及组合优化中的著名难题，由于其有广泛的应用背景，引起了人们的极大兴趣。tsp本身可以直接用于解决类似tsp的最优巡回线路等问题，其它例如交通车辆的巡回线路问题、民航机组人员的轮班安排问题、教师任课班级负荷分配问题、装配线进度问题、数控机床的运行问题以及生产系统传送带顺序问题等，都可以直接或间接引用 tsp的求解方法加以解决。tsp一般描述为:旅行商从驻地出发，经所要去的城市至少一次后返回原地，应如何安排其旅行线路，才能使总的旅行距离(或时间、费用等)最少。对于现实问题，由于限制条件的增加，tsp可衍生出许许多多相关的问题。2、

46、tsp的数学模型一般tsp指一个旅行商访问所有城市。这里设城市0为旅行商出发城市，需要访问的个城市编号为1,2,，为了便于说明问题，把旅行商问题构造成网络图以表示: 点集，表示旅行商需要经过的地点。 弧集，表示旅行商可能走过的线路段集合。 费用矩阵，表示旅行商经过对应弧段(,)所花的费用，如时间、距离、花费等7。求解tsp即要求在加权图中找到总费用最小的哈密尔顿(hamilton)回路，这里点0称为源点。所谓哈密尔顿(hamilton)回路即指从源点出发，经过每个顶点一次，且仅仅一次的回路8。定义变量如下:则得到以下数学模型: (4-1) (4-2) (4-3) (4-4) (4-5)其中，（

47、）; s为支路消去约束(sub-tour -breaking约束)，即削去构成不完整线路的解，如图2所示，两条支路均满足分配约束，但没有构成一条完整的线路，因此不是vsp问题的解。3 42 6 1 5图2 支路示意图五、物流配送车辆优化调度模型及求解算法（一）物流配送车辆优化调度问题的提出虽然物流配送具有多种类型和形式，但大部分物流配送形式中运输的特点是基本相同的，即将商品从配送中心按一定的要求发送到多个需求点。由于运输任务的性质和特点不同，道路条件及车辆类型不同，即使在相同收发货运点间完成同样任务时，采用的行驶路线方案也可能不同。而车辆按不同运行线路完成同样的运输工作时，其利用效果是不一样的

48、，有时甚至会有很大的差别。因此，在满足货运任务要求的前提下，如何选择最经济的运行路线，是一项重要的工作。所谓最经济的运行路线，就是在保证货物需求的前提下，运输时间或运输费用最省的路线。如何按时按量、经济高效地配送商品，在很大程度上取决于有效的车辆调度安排，调度方案的优化与否，对增加配送效率、减少总费用和提高服务水平具有重要的意义。约束条件和目标函数不同，对vsp描述和研究方法也不尽相同。本章中，根据系统的实际需求，考虑车辆装载量限制，研究无时限的纯装或纯卸的非满载vsp及单源最短路径问题，建立合理的数学模型，通过经典的节约算法进行修正与dijkstra单源最短路径算法分别求解问题。（二）dij

49、kstra单源最短路径算法原理及实现流程1、dijkstra单源最短路径算法的基本原理单源最短路径问题就是已知有向带权图(简称有向网)找出从某个源点到中其余各顶点的最短路径。dijkstra是一种按路径长度递增序产生各顶点最短路径的算法。其算法思想为:设为最短距离已确定的顶点集，一个顶点属于集合当且仅当从源到该顶点的最短路径长度已知；是最短距离尚未确定的顶点集。设为源点，为终点。)初始化初始化时，只有源点的最短距离是已知的，将源点的最短路径看作是己生成的源点到其自身的长度为0的路径。因此，中仅含有源点，为空。)重复以下工作，按路径长度递增次序产生各顶点最短路径在当前集中选择一个最短距离最小的顶

50、点来扩充集，以保证算法按路径长度递增的次序产生各顶点的最短路径。当集中仅剩下最短距离为的顶点，或者所有集中的顶点己扩充到集时，源点到所有顶点的最短路径就求出来了。 需要注意是:)从源点到某顶点的路径不存在，则可假设该顶点的最短路径是一条长度为无穷大的虚拟路径。)从源点到终点的最短路径简称为的最短路径；到的最短路径长度简称为的最短距离。2、dijkstra单源最短路径算法实现流程在本小节中，以图3为例，描述dijkstra单源最短路径算法的实现流程。0 10 100301 4 50 10 60 2 3 20图3 距离和最短路径示意图 第一步：初始化变量 表1初始化变量表变量名称初始值含义ss=0

51、,0为图3中的源点最短路径已确定的顶点集v-sv-s=1,2,3,4最短距离尚未确定的顶点集d表2中第一行d0,d4,表示顶点与原点之间没有连线已知原点到任意顶点的距离集合p表2中第一行p0,p4,-1表示顶点和原点之间没有连线算法实现过程当前产生的最短距离被哪个顶点改变 第二步：求解 若用表示图中两相邻点与的距离，若与不相邻，令，显然，用表示从点到点的最短距离，现要求从源点到其余各点的最短路，如下：) 中找出最短距离和相应的顶点，则此时有最短距离，将相应的顶点加入到集合中。)查看其余顶点是否与点有连接，若没有，维持集合,的和,的值不变；如果有，将与这两点之间的距离相加(点和点有相连，距离为)，和为，小于原来的距离，更新为,为，如表2中循环行所示： 表2 dijkstra算法生成最短路径过程循环sd0d1d2d3d4p0p1p2p3p4始化化001030100-10-10010,101060301