基于遗传算法的边防连队运输保障车辆调度问题研究.pdf

《基于遗传算法的边防连队运输保障车辆调度问题研究.pdf》由会员分享，可在线阅读，更多相关《基于遗传算法的边防连队运输保障车辆调度问题研究.pdf（71页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、国防科学技术大学硕士学位论文基于遗传算法的边防连队运输保障车辆调度问题研究姓名：赵崇远申请学位级别：硕士专业：项目管理指导教师：凌云翔20080501国防科学技术大学研究生院工程硕士学位论文摘要配送是将物资送达用户的重要物流环节。在物流活动的各项成本中，配送成本占了相当高的比例。配送车辆调度的合理与否对配送速度、成本、效益影响很大，特别是多用户配送车辆调度的确定更为复杂。采用科学、合理的方法来进行配送车辆调度，是物流配送中非常重要的一项活动。因此，车辆调度问题(V e h i c l eR o u t i n gP r o b l e m 简记V R P)成为众多学者竟相研究的热点领域。本文以

2、现代物流的基本理论和方法为基石，紧密结合当前我军所正在进行的后勤体制改革，以全面提升边防部队后勤快速保障能力这个中心目标展开研究。全篇在结构上共分为六章，其中前五章是论文的主要内容，第六章是对研究的总结与展望。第一，回顾物流研究领域的有关研究进展情况和当前所取得的研究成果，引入物流、军事物流等基本概念，并就其特点与功能进行阐释。对本研究的基本思路、方法、内容与目标做了必要的介绍。第二，介绍了遗传算法的基本思想、基本原理、基本特征以及遗传算法的解题步骤，另外还介绍了图与网络的基本知识，为后面的遗传算法对边防部队后勤车辆优化调度问题进行研究求解打下理论基础。第三，根据边防连队配置地域分散，道路网复

3、杂，地形多变，从而导致需求点较多且分布不均匀的特点，部队的军用物资需求是随着任务的进一步发展随机发生的，这些因素直接影响到配送物资车辆使用安排，本文建立了适于进行多需求点配送的多源点车辆配送问题模型及含有时间窗口的数学模型，并将之分解为分群主问题和巡回子问题两个求解过程。首先探讨时间窗的特性及其对模型建立与求解的影响，然后建立针对含时间约束的车辆配送问题的模型，以遗传算法进行求解。最后则以两个案例具体说明本文提出的遗传算法，并对算法性能效果进行分析评价。主题词：物流配送遗传算法边防连队车辆调度问题第i 页国防科学技术大学研究生院工程硕士学位论文A B S T R A C TD i s t r

4、i b u t i o ni Sa no p e r a t i o nl i n k i n gW i t hc o n s u m e rd i r e c t l y，a n dt a k e sa c c o u n tf o rc o n s i d e r a b l ep r o p o r t i o ni nv a r i a b l ec o s t si nl o g i s t i c s T h ep l a n n i n go fv e h i c l er o u t i n gi nd i s t r i b u t i o nw i l lt a k eg

5、r e a te f f e c to nt h ee f f i c i e n c y，c o s ta n db e n e f i t，e s p e c i a l l yi nd i s t r i b u t i n gf o rm u l t ic o n s u m e r s S o，v e h i c l er o u t i n gp r o b l e mh a db e c o m ef o c u so fm a n ys c h o l a r st os t u d y U n d e rh i g ht e c hc o n d i t i o n s，m

6、o d e ml o c a lW a rh a sb e c o m em o r ea n dm o r ec o m p l e x T h ec o u r s ea n dt h er e s u l to ft h eW a rh a sb e e nm o s t l yd e p e n do nt h em a t e r i a le n s u r e T h ea r t i c l ec o n s i s t so fs i xc h a p t e r s，a m o n gw h i c h，t h ef o r m e rf i v ec h a p t e

7、r sa r eb o d yp a r ta n dt h es i x t hi st h eo u t l o o ka n ds u m m a r y F i r s t，al o o ka tt h ep r o g r e s sh i s t o r ya n dt h em o d e ma c h i e v e m e n t si nt h er e s e a r c h；i n t r o d u c t i o no ft h eb a s i cc o n c e p t ss u c ha sl o g i s t i c sa n dm i l i t a

8、r yl o g i s t i c s；f u r t h e re l a b o r a t i o no nt h e i rf e a t u r e sa n df u n c t i o n s；a n dt h ei n t r o d u c t i o no ft h eb a s i ct h i n k i n g，a p p r o a c h，m a i np o i n t sa n do b j e c t i v e s S e c o n d l y，t h ei n t r o d u c t i o no ft h eb a c k g r o u n

9、do fg e n e t i ca l g o r i t h m，b a s i cp r i n c i p l e s，b a s i cf e a t u r e sa n di t ss t e p st os o l u t i o n；a n dt h ei n t r o d u c t i o no fb a s i ck n o w l e d g ei nd r a w i n ga n dn e t w o r k i n g，w h i c hl a y st h ef o u n d a t i o nf o rt h er e s e a r c hi nt h

10、 er o l eo fg e n e t i ca l g o r i t h mi nt h er a t i o n a l i z a t i o no fr o u t i n gf r o n t i e rd e f e n s e T h i r d，r e g a r d i n gt h es o l u t i o nm e t h o d，t h eg e n e t i ca l g o r i t h mi su s e dh e r e，w h i c hh a ss t r o n g e rh o l i s t i cs e a r c h i n gc a

11、 p a c i t y N u m e r o u sa n du n e v e n-s p r e a dd e s t i n a t i o n sc a u s e db yw i d es p r e a do ff r o n t i e rt r o o p s，c o m p l e x i t yo fr o u t e sa n dt e r r a i n s，t o g e t h e r 谢t l li r r e g u l a r i t yo ft h en e e d si nm i l i t a r ys u p p l i e sc a u s e

12、db yt h ei r r e g u l a r i t yo ft h ea s s i g n m e n t st ot h ef r o n t i e rt r o o p s d i r e c t l ya f f e c tt h er o u t i n g Am o d u l ew i t ht i m ew i n d o w sp e r i m e t e r sf o rr o u t i n gv e h i c l e sf r o mm u l t is o u r c e st om u l t id e s t i n a t i o n si se

13、 s t a b l i s h e di nt h i sa r t i c l ea n di sc o m p o s e do ft w os o l u t i o np r o c e s s g r o u pm a i np r o b l e m sa n dr e v o l v i n gs u b-p r o b l e m s T h ef e a t u r e so ft i m ew i n d o w sa n di t se f f e c to nt h es e t u pa n ds o l u t i o no ft h em o d u l ea

14、r ef i r s td i s c u s s e db yu s i n gg e n e t i ca l g o r i t h m，t h e nt h em o d u l ef o rt h er o u t i n gr e s t r i c t e db yt h et i m ew i n d o w si ss e tu pw i t hg e n e t i ca l g o r i t h m F i n a l l yt h eg e n e t i ca l g o r i t h ma n di t sp e r f o r m a n c ea r ee

15、x p l a i n e da n da n a l y z e db yu s i n gt w oe x a m p l e s K e yW o r d s-D i s t r i b u t i o nG e n e t i cA l g o r i t h mB o r d e rD e f e n s eR e g i m e n tV e h i c l eR o u t i n gP r o b l e m(V R P)第i i 页国防科学技术大学研究生院_ T 程硕士学位论文表目录表1 1 车辆路径优化问题分类一览表6表1 2 各种算法的比较8表4 1 分群结果一4 3表5

16、 1 各连队需求量表4 8表5 2 各连队之间的距离表。4 8表5 3 任务特征及要求表5 0表5 4 团到各连及各连队之间的距离5 0表5 5 演算结果5 1第1 I I 页国防科学技术大学研究生院工程硕士学位论文图目录图2 1 传统保障模式流程示意图1 3图2 2 现代军事物流配送流程示意图。1 3图2 3 遗传算法基本流程图。18图2 4 支路示意图21图3 1 算法流程图2 8图3 2 终端物流配送体系2 9图4 1 硬时间窗惩罚函数3 2图4 2 软时间窗惩罚函数3 3图4 3 混合型时间窗惩罚函数3 3图4 4V R P T W 问题的结构3 4图4 5 惩罚函数3 7图4 6 分

17、解主问题与巡回子问题间的关系图4 1图4 7 算法流程图4 3图4 8 染色体与分群结果对照4 4图5 1 运算结果4 9图5 2 算法性能对照表51第1 V 页独创性声明本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得的研究成果尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它教育机构的学位或证书而使用过的材料与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意学位论文题目基王遣笾箕洼的边区莲区重捡堡隍主牺溷度闻塑盈盔学位论文作者签名：j 亟名立L日期：切寥年多月3日学位论文

18、版权使用授权书本人完全了解国防科学技术大学有关保留、使用学位论文的规定本人授权国防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子文档，允许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文(保密学位论文在解密后适用本授权书)学位论文题目：基王鲎笾篡洼煎垫陵蓬丛重捡堡睦主舾迥廑闻题珏究学位论文作者签名：超级丝日期：z 彬留年多月Jo 日作者指导教师签名：1 金呈羟日期：2 科年月3 日国防科学技术大学研究生院T 程硕士学位论文第一章绪论1 1 课题的背景及目的、意义随着科学技术的发展和军队现代化水平的提高

19、，信息化战争已全面登上历史舞台。纵观美军近些年发动的几场信息化战争，其军队后勤保障模式发生了巨大变化，军事物流在其后勤保障中的地位和作用不断凸现。军事物流配送作为军事物流的核心功能，越来越引起各国军队的关注【l】。1 1 1 课题的背景本研究课题一基于遗传算法的边防连队运输保障车辆调度问题研究，顺应了现代战争的要求和科学技术发展的趋势，是我军现代化建设的必然要求，具有重要的意义和实际应用价值。军事物流配送保障通过加快物流速度，实现物资科学储备。现代高技术条件下的信息化战争，具有很强的联合性、机动性、透明度和突发性，作战部队的物资需求已从“少品种、大批量、少批次、长周期转变为“多品种、小批量、多

20、批次、短周期，1 2 1。而目前我军军事物资在生产、周转、储备的整个流程中，层层设库，逐级设库，后方储备更是要经过多级仓库的转运才能到达需求部队手中，后勤物资的保障效益低下，难以在现代战争复杂的环境中，快速、高效、准确地满足部队多样化、个性化的物资需求。在战场后勤保障中，物流速度与其产生的军事、经济效益成正比，即物流速度越快，军事、经济效益就越高。军事物流配送保障通过减少保障层次、超越中间保障环节，实行严格的物资储备动态调控，避免作战物资过多的存储和积压在各级仓库中，控制物资的储备规模，限制储备周期，加快物资周转，实现以最小的物资储备来满足作战部队的实际需求，最大限度地节约后勤资源，从而提高后

21、勤保障效益【3 J。军事物流配送保障通过实时传递需求信息，实现精确化保障【4】。在我军现行后勤物资保障模式下，仓库和运输部队作为具体的保障实体，承担上级赋予的物资收发和运输任务，对于部队需求信息的及时反馈和处理，及物资如何适时、适量、适地、高效、低成本地从起点“流”到最终用户(部队)手中，通常并不关心【5】。军事物流配送保障通过充分运用以信息技术为核心的现代高技术手段，精细而准确地筹划和运用各种后勤保障力量，在准确的时间地点为部队作战提供数量准确、第1 页国防科学技术大学研究生院T 程硕士学位论文质量合格的物资技术保障【6 J。这就要求我军后勤运用各种信息手段对后勤物资的生产、运输、储备和消耗

22、进行实时监控，根据战场的态势变化及时修订保障计划，灵活协调保障行动，变被动为主动，对部队实施适时、适地、适量的精确化保障【7 J。军事物流配送保障通过优化整合物流资源，实现体化保障。我军现行物资保障体制存在着“条块分割，各自为政 的弊端。军事物流各个环节“割裂，难以支撑整个战区的网络物流动作【8 J。作为后勤保障主体的联勤(分)部，军兵种后勤所属基地、仓库等，均以自身功能和效益最大化为目标，较少关注本环节外的事情，缺少一个权威性的物流管理机构对全区域内的整体物流运作进行协调与集成。军事物流配送保障通过对区域内的军地物流资源进行优化整合，整体筹划和运用，按照不同的保障任务，将现有相对独立的保障单

23、元与不同的作战单元进行组合，通过先进的野战机动后勤装备，实现后勤力量和作战力量的最佳结合，随时随地向作战部队提供高效的机动伴随保障，确保作战全时段、全方位、全过程不间断无缝隙的后勤供应保障p】。车辆调度管理工作是军队后勤保障的重要组成部分，而相应的对车辆优化调度的研究相对滞后，这方面的研究是我军的一个薄弱环节，迫切需要加强【l。从维持部队日常生活的衣、食、住、行，到提高部队战斗力的各种物资、油料、武器装备等，不仅需求量大，而且种类繁多。合理的调配有限的运输力量，才能及时充足地供应部队的需求。我军车辆调度管理滞后，基本上是基于分散管理，分散保障。具体表现在：整个军队物资需求量和实际运输车辆存储量

24、等信息难以获取和汇总，管理流通环节脱节。按现阶段的物资管理模式，部队作为一个作战单位，除了平时要组织训练、战时组织战斗之外，还要花费相当大的精力去组织物资保障，而且每一级单位都有自己的采购、运输、储存部门，再加上每一级都分成军需、后勤、营房、卫生等等，都是自己只负责自己的业务，这样不但机构重叠、成本高昂，而且效率低下【l。1 1 2 课题目的及意义军队车辆调度本身就是一项工作量大、涉及因素多、技术性强的工作。后勤部门在制定车辆调度计划时，必须考虑战场(或假想战场)环境，需要在作战背景下完成车辆、物资需求量统计、财务核算等大量的工作。因此，给车辆调度工作带来了一定难度。同时，随着信息、通讯手段的

25、提高，作战的供给需求变动大而且效率需求的水平提高，都给运输调度优化带来不小的困难。目前，军内配送车辆调度基本处于依靠人工经验调度阶段，无法适应现代军事配送数量大、种类繁的第2 页国防科学技术大学研究生院工程硕士学位论文特点，达不到统一调度的需要。只能缩小统一调度的范围，很难真正实现全局最优【1 2】。边防部队配置地域分散，道路网复杂，从而导致需求点较多且分布不均匀，因此制定调度方案单凭人工经验是难以做好的。尤其是现在高技术战争中，部队对配送的物资依赖性较强，对配送时效、质量要求较高。按照后勤保障有关规定，当日要求配送到的物资一定要配送到位。如何在保持高度准时、快速全配送要求下，降低成本是物流配

26、送面临的挑战。但如何制定优化调度方案，在满足车辆容量限制及时间限制条件下，使总运输距离或总运输时间最短并不容易。所以设计一定的配送调度模型和算法，并用计算机来实现意义重大。本课题则是为了解决如何在军队范围内实现物资的高速、高效、低成本流通的这样一个实际问题。课题紧密的结合了部队后勤发展方向，研究的对象是军事后勤保障中的车辆调度的流动规律，具有一定的理论价值，同时该研究对我军军队物资流通管理、车辆保障的现代化具有较强的应用价值，实践性较强。本研究课题针对边防部队车辆调度工作中存在的问题进行研究，找出问题的症结所在，进而找出军队车辆调度管理中优化调度的内在联系，找出解决的方法和途径，达到节约成本、

27、提高我军军事后勤保障能力目的。因此本研究课题从学术的角度来讲，将促进军事后勤保障物流中车辆调度问题的研究，从应用的角度来讲，提出的建议可以为决策机构参考，具有很大的理论和现实意义。论文在消化相关学科知识的基础上，进行了车辆优化调度的一系列理论问题汇总；其意义可概括为：本研究应用物流系统的设计理论初步设计了现代军事车辆优化调度模型，具有较强的操作性，有助于我军军事后勤部队物流系统高速有效运行。通过对实际车辆调度问题的掌握和数据积累，结合运筹学知识，本文提炼出车辆调度的数学模型，采用计算机求解出优化方案，然后再根据具体情况对方案进行修正，最终用于调配车辆，实现运力的合理利用，有效的节约资源，提高军

28、事后勤部门对部队的综合保障能力。本研究将军事物流思想和理论应用到边防部队车辆优化调度上，采用系统的观点和方法来处理车辆调度问题，推动了军队物流管理理论研究的发展。首先是保证军队物资物流的畅通，保障部队的供应。在此基础上，通过应用现代物流管理的思想和方法，降低军事物流的成本，全面提高军事物流的效率和效益，解决我军军队后勤保障观念和思想的一系列问题。长期以来，我军后勤保障领域由于地域上的隔离和部门之间的垄断，本位主义严重，物资流通管理部门没有整体观念，各自为政。本研究运用现代军事物流的思想、一体化的战略和建立军事物资中心配送的方法，对军队物资管理、流通的体制、思想、方法进行变革，达到适第3 页国防

29、科学技术大学研究生院丁程硕士学位论文应现代高技术战争对军队物资需求的要求。1 1 3 问题的提出目前，我军的大部分物流配送多是依赖人工经验并采用人工安排的方式，从而导致运输资源无法充分利用，运行成本过高，或者无法满足部队要求。因此，对物流配送优化问题进行研究，建立能即时定量反映运输车辆调度及路线安排系统，是提高保障能力和资源利用率的重要课题。边防团各连队的军需保障由团里的服务中心负责，根据各连队的需要，每周，团服务中心要对各连队进行两次保障，以便满足边防连队的日常所需。目前是由团服务中心首先到市场进行定点采购，而后采取经验式的车辆调度分配方法(受人员、车辆及安全因素等的影响，一般采用单车运输)

30、：1 对运输任务量大的单位，单独指定车辆负责；2 划分区域一般方法是将运输点按地理位置分成几个区域，当该区域的所需量超过车辆载重量时，将该区域剩余所需分配给临近区域；3 路线安排上，一般是按划分区域，以服务中心作为出发点，由远及近保障；4 如遇到特殊或突发问题再另行进行调整。面对保障连队个数多，分散广这一现实情况，如何选择最优配送路线，使得投入的运输成本最低，这一问题的可行解的数目非常巨大，甚至不可能用类似于枚举法的方法在能够接受的时间范围内得到最优解或者较优解，因此这种人工作业方式己难以实现即时配送车辆调度优化，因此迫切需要研究这一优化调度问题一车辆调度问题(v e h i c l er o

31、 u t i n gp r o b l e m V R P)可以定义为：运输车辆从一个或多个设施到多个地理上分散的客户点，优化设计一套车辆调度的方案，同时要满足一系列的约束条件。该问题的前提是团物资采购中心位置、连队点位置和道路情况己知。1 2V R P 问题研究现状1 2 1V R P 问题的一般描述及分类车辆调度问题(V e h i c l eR o u t i n gP r o b l e m，简称V R P)是由D a n t z i g 和R a m s e r于1 9 5 9 年提出来的。所谓V R P 问题，一般指的是：对一系列发货点和收货点，调用一定的车辆，组织适当的行车路线，

32、使车辆有序地访问它们，在满足特定的约束条件下(如：货物的需求量与发货量、交发货时间、车辆载重限制、行驶里程限制、行驶时间限制等)，力争实现一定的目标(如车辆行驶里程最短、运输总费用最低、车辆按一定时间到达、使用的车辆数最少等)。由于这一问题的理第4 页国防科学技术大学研究生院工程硕士学位论文论涉及多学科，而且很多实际问题的理论抽象都可归结为这一类问题，其应用前景非常广阔。所以，很快便引起物流科学、应用数学、图论与网络分析、运筹学、交通运输工程、管理科学与工程、计算机应用等学科的专家、工程技术人员和管理者的极大重视，自此，一直成为运筹学与组合优化领域的前沿与研究热点问题。为了便于描述和求解，可从

33、不同的角度，按不同的标准对V R P 问题划分如下(见表1 1)：1 2 1 1 满载和非满载车辆的优化调度问题当货物量小于车辆容量时，用一辆车执行任务就存在不满载运行情况，调度时可安排一辆车执行多项任务，即在一辆车上装载不同货主的货物。当然，这类问题有一个前提条件，即不同货主的货物允许混装。当货物量不小于车辆容量时，执行每项任务需要的车辆可能不只一辆，部分车辆需满载运行。这类问题可能有两种情况：一种是由一辆车往返多次运送，另一种是由多辆车分别运送。对于这类问题可以通过两个步骤将其转化为非满载车辆优化调度问题：第一步解决整车运输，这就是典型的最短路问题；第二步对于剩下不满一车的，按非满载车辆优

34、化调度问题加以解决。1 2 1 2 集货或送货和集送一体化的车辆优化调度问题所有任务全是集货点(装货点)或全是送货点(卸货点)，车辆空车从配送中心出发，去各货主处装满货后返回配送中心，或是车辆装满货物去各货主处卸货后返回配送中心，这种情况称为集货或送货的车辆调度安排。每一项货运任务都有自己的集货点和送货点，车辆从配送中心出发，去某一任务的集货地点装货后运至其送货地点卸货(即装卸混合)，完成所有任务后返回配送中心。这种情况称为集货和送货一体化的车辆调度安排问题。1 2 1 3 带有时间窗和不带时间窗的车辆优化调度问题如果到达任务点的时间是事先规定的，则称该问题是带时间窗要求的车辆优化调度问题；若

35、到达和离开时间没有规定，则称该问题就是一个直接的路线安排的问题。带时间窗的V R P 又可分为硬时间窗V R P 和软时间窗V R P。硬时间窗V R P指每项任务必须在要求的时间内完成，软时间窗V R P 指每项任务在一定的时间范围内完成，如果某项任务不能在要求的时间范围内完成，则给予一定的惩罚。1 2 1 4 单源点和多源点的车辆优化调度问题单源点车辆优化调度问题是指所有的车辆均从一个配送中心发出，完成各自的任务后都返回该配送中心。多源点车辆优化调度问题是指存在着多个配送中心，车辆可以从任何一个配送中心派出，完成任务后，车辆也可以返回其中的任何一个配送中心。随着供应链的集成一体化，多源点的

36、车辆优化调度问题将越来越多，第5 页国防科学技术大学研究生院T 程硕士学位论文越来越重要。对于这类问题可以通过一定的方法将其转化为单源点的车辆优化调度问题。表1 1 车辆路径优化问题分类一览表分类依据分类名称问题描述纯装(纯卸)问题车辆在所有任务点装货或卸货，即按任务目标区分集货或送货问题；每项任务有不同的装货点和卸货装卸混合问题点，即集货、送货一体化问题；满载问题货运量不小于车辆容量，完成一项按车辆载货状况区分任务需要不只一辆车；货运量小于车辆容量，一辆车可完非满载问题成多项任务；配送中心(车场)数单车场问题调度中心是唯一的；目区分多车场问题调度中心不是唯一的；单车型问题所有车辆类型和容量相

37、同；按车辆类型区分执行任务的各车辆的类型和容量不多车型问题完全相同；按车辆对车场的车辆开放问题车辆可以不返同其发车场；所属关系划分车辆封闭问题车辆必须返回其发车场；无时间窗车辆优化调度问题对运输没有时间要求；硬时间窗(H T W)是指任务必须在根据V R P 中各项硬时间窗车辆优化调度问题给定的时间范围内完成，否则得到任务是否有时间限制的解视为不可行解；来区分软时间窗(s T W)指如果任务不能软时间窗车辆优化调度问题在给定的时间范围内完成，则同时给予一定的经济惩罚：单目标优化是指某一项指标最优或按照优化的目标单目标优化问题较优划分多目标优化则是指同时要求多个指多目标优化问题标最优或较优；同种

38、货物优化调度多种货物优化调度问题是指运输货按照货物的种类物的种类多于一种，车辆调度时可要求划分多种货物优化调度能要考虑某些种类的货物不能同时装配运输的要求，如武器弹药等和军需食品等不能混装运输等按照有无休息时有休息时间的优化调度间划分无休息时间的优化调度第6 页国防科学技术大学研究生院工程硕士学位论文本文主要讨论的问题是单源点与多源点、带时间窗口的非满载送货车辆优化调度问题，对于多源点物流配送问题，本文将介绍将其转化为单源点物流配送问题的方法。1 2 2V R P 模型及求解方法概述1 2 2 1 模型对货运车辆调度问题可以构造为整数规划模型，也可以构造为图论及其他模型，各类模型之间存在着一定

39、的联系。从建立模型时的出发点考虑，大多数模型都可看成是下面三种模型的变形与组合：(a)车流为基础的模型；(b)物流为基础的模型；(c)覆盖模型。1 2 2 2 求解方法V R P 问题可归结为N P 难问题，其求解方法一般有如下几种：1 精确方法：是运用线性规划、整数规划、非线性规划等数学规划模型和方法来描述物流系统的数量关系，以便求得最优决策。由于物流系统庞大而复杂，建立和求解整个系统的优化模型一般比较困难，而且用计算机求解大型优化问题的时间和费用太大，因此优化模型常用于物流系统的局部优化，并结合其它方法求得物流系统的次优解。常用的精确方法有：分枝定界法、动态规划方法、网络流法、割平面法等。

40、2 模拟方法：模拟方法是利用数学公式、逻辑表达、图表、坐标等抽象概念来表示实际物流系统的内部状态和输入输出关系，以便通过计算机对模型进行试验，通过试验取得改善物流系统或设计新的物流系统所需要的信息。虽然模拟方法在模拟构造、程序调试、资料整理等方面的工作量大，但物流系统结构复杂，不确定情形多，所以模拟方法仍以其描述和求解问题的能力优势，成为复杂物流运输调度建模的主要方法。3 交互式优化法：是一种适用物流决策的通用方法，把人的经验结合到问题的求解过程中。主要思想是：有经验的决策者应具有确定和修改参数的能力，并根据知识直感，把主观的估计加到优化模型中去。这通常总是会增加模型最终实现并实际采用的可能性

41、。4 启发式方法：启发式方法是针对精确优化方法的不足，运用一些经验法则来降低优化模型的数学精确程度，并通过模仿人的跟踪校正过程求取物流系统的满意解。启发式方法能同时满足详细描绘问题和求解的需要，比优化方法更为实用；其缺点是难以知道什么时候好的启发式解已经被求得。因此，只有当优化方第7 页国防科学技术大学研究生院工程硕士学位论文法和模拟方法不必要或不实用时，才使用启发式方法。常用启发式算法有：构造算法、两阶段方法、不完全优化法、改进算法、遗传算法、神经网络法等等。各种算法间的比较见表1 2。表1 2 各种算法的比较求解方法解的精度算法收敛速度程序口J 仃性适用范围数学规划方法精确最优解慢较难简单

42、，确定型模拟方法较优解慢难复杂，不确定型交互式方法满意解快易较复杂，确定型启发式方法近似解较快易较复杂，确定型1 2 3V R P 问题的发展进程车辆调度问题是典型的带约束的组合优化问题，是N P 难问题，因其复杂性，至今尚未找到多项式算法，故多数研究者致力于其启发式算法。若将现实中的所有可能的约束条件和多种目标加入，不仅增加其复杂性，降低求解效率，而且可能根本无解。所以研究者常将现实应用中的常见问题抽象成模型，并根据各模型特点，设计相应的高效算法。V R P 作为运筹学领域中的一个重要分支，国外对这个问题进行了大量的研究，并己广泛应用于生产、生活的各个方面。我国在这一方面的研究还很少见到，多

43、数是半人工作业方式或是依据某单一目标用传统数学方法实现线路安排。而实际的车辆路线问题应考虑路长、路况、车况、时限等多种因素，是一个多目标的优化决策问题。用智能优化算法快速得到车辆路线方案，对于降低运输成本，提高工作效率起着关键作用。关于V R P 的研究和应用最初来自于公共服务行业，如学校接送学生的班车问题，银行运钞车路由问题，自动取款机、售货机和投币电话的现金、货物的投放和硬币回收等的路由问题，牛奶运送问题，垃圾收集问题以及公共设施维修问题等等。后来，随着电子商务和物流配送业的发展，V R P 对于各种连锁店、大型商场、邮政系统、快递公司、高速公路配货等，也有广泛的应用前景。目前，研究水平已

44、有很大发展，其理论成果除在汽车运输领域外，在水运、航空、通讯、电力、工业管理等领域也有一定的应用。而且，对于许多可转化为V R P 问题求解的组合优化问题也具有十分重要的意义，如飞机航线、智能交通、生产计划与控制等问题。据资料显示，美国利用计算机和最短路树算法、启发式算法解决货运汽车等问题，使汽车里程利用率提高了3-5，运输成本也有明显下降【l3 1。我国上海市运输公司十二场第六车队计算机和启发式算法调度货运车辆，使里程利用率提高了4 左右【l 引。英国早在1 9 5 9 年就开始研制车辆调度软件包，它所研制的计算机调度系统应用复杂的转移程序解决货运汽车作业计划中有多个装卸货点的最佳行车路线问

45、题，并可按照用户的具体要求，选择优化方案，因而与人工方法相比，可节省运输费用达1 5 以上，可第8 页国防科学技术大学研究生院工程硕士学位论文使车辆运行成本降低1 0【l5。迄今为止，国外对车辆调度理论和算法的研究成果颇丰，并且在计算机调度应用方面也取得了一定的成果。国内在这方面的研究大多停留在理论层面，实际应用系统的开发才刚刚起步。随着我国对物流业的不断重视，以及配送制的兴起，对货运车辆运输调度提出了经济性、准时性、灵活性的综合要求。虽然物流行业和理论界早在数年前就提出建立配送中心信息系统，但时至今日，仍没有较成熟可行的计算机车辆配送优化调度系统得以应用推广。原因是多方面的，一方面是企业对优

46、化调度认识不够，另一方面的原因是车辆调度数学模型本身与配送应用结合方面也存在问题，主要表现在：(1)配送方式下，用户对运输的要求高，调度约束条件多。而大多数算法只考虑了V R P 问题的某些约束，且设置了许多假设条件，因此限制了它们的应用范围。(2)实施配送运输的企业，业务模式常常会随用户的需求而不断变化，而许多计算机调度模型在设计时只注重针对某一种固定业务模式，算法单一，因此在应用中缺乏灵活性，无法很好地满足应用对计算机调度系统智能化地要求。鉴于以上原因，研究、开发实用性强的调度算法和货运车辆配送运输优化调度模型，并在此基础上开发出智能化的计算机车辆调度系统应用于实际问题中，具有重要的理论意

47、义和实践意义。1 3 本文研究的主要内容文章以现代物流的基本理论和方法为基石，紧密结合当前我军所正在进行的后勤体制改革，以全面提升后勤快速保障能力这个中心目标展开研究。本研究从解析现代物流的有关基本理论入手，引入军事物流的概念和思想，针对军事后勤保障中的车辆优化调度问题进行了深入的研究。第一章主要介绍课题的相关背景知识、任务以及研究意义。第二章主要介绍遗传算法的基础知识、基本原理和实现的一般步骤。介绍遗传算法的基本思想、基本原理、基本特征以及遗传算法的解题步骤，另外还介绍了图与网络的基本知识，为后面的遗传算法对军事后勤车辆优化调度问题进行研究求解打下基础。在求解方法上，本文采取全局搜索能力较强

48、的遗传算法。第三章根据边防部队配置地域分散，道路网复杂，从而导致需求点较多且分布不均匀的特点，建立适于进行多需求点配送的多源点车辆配送问题模型。前三节对单源点车辆优化调度问题进行分析并建立模型然后用遗传算法进行求解。第四节讨论将多源点问题转化为单源点问题进行求解。第四章针对有时间窗的车辆调度问题，建立了含有时间惩罚函数的数学模型，并将之分解为分群主问题和巡回子问题两个求解过程。在第一阶段，首先探讨时间窗的特性及其对模型建立与求解的影响。然后建立针对含时间约束的车辆配送第9 页国防科学技术大学研究生院工程硕士学1 1：)=论文问题的模型。第五章分别用两个案例说明用遗传算法解决边防连队车辆调度问题

49、的求解过程，及给部队带来的经济效益。第六章对本论文进行总结，并提出下一步研究的方向。第l O 页国防科学技术大学研究生院工程硕士学位论文第二章军事物流配送在军事后勤保障中应用的相关理论2 1 物流的概念、特点与功能2 1 1 物流概念的发展沿革物流作为“第三利润源泉，对世界经济活动的影响日益明显，也越来越引起人们的重视。它成为当前“最重要的竞争领域，对未来的市场竞争起着举足轻重的作用。物流学是5 0 年代发展起来的一门实践性很强的综合性交叉学科。它以物的动态流转过程为主要研究对象，揭示了物流活动(运输、储存、包装、装卸搬运、流通加工、物流信息等)的内在联系，使物流系统在经济活动中从潜隐状态显现

50、出来，成为独立的研究领域和学科范围。物流科学是管理工程与技术工程相结合的综合学科，应用了系统工程的科学成果，提高了物流系统的效率，从而更好地实现了物流的时间效益和空间效益。物流科学的产生和应用将给国民经济和企业的生产经营带来难以预料的经济效益，因此，引起了学术界和企业界的重视并给予高度评价，从而得到了迅速的发展和普及。物流的概念最早形成于美国，当初被称为P h y s i c a lD i s t r i b u t i o n(简称P D，即“实物分配”或“货物配送)。1 9 3 5 年，美国销售协会阐述了“实物分配”的概念：“实物分配是包含于销售之中的物质资料和服务在从生产场所到消费场所的