北大仓物流配送路径优化的研究

哈尔滨工业大学工学硕士学位论文-PAGEII--PAGEVI-（工程硕士）北大仓物流配送路径优化的研究THERESEAＲＣＨOFBＥIDACＡＮGLOGISTICSDISＴＲＩBUTIＯＮＲＯＵＴEＳOＰTＩMIZATＩOＮ２０0８年３月国内图书分类号：国际图书分类号:工程硕士学位论文北大仓物流配送路径优化的研究ClａｓｓiｆｉｅｄIndeｘ：Ｕ．D.C。:ＤiｓserｔａtiｏｎｆｏrthｅMasterDegreeiｎＥnｇiｎeeｒｉngTHERESEＡＲＣHＯＦＢＥIDＡCANGLOGIＳTIＣSDISTＲＩBUTＩONＲOUTESＯPTIMＩZAＴＩＯN摘要物流配送路径优化问题一直是国内外学者普遍探索的重要课题。传统的物流配送难以满足实效性要求，本文主要解决物流配送路径优化问题。本文的研究就是围绕物流配送路径优化问题展开的,指出了路径优化方面存在的问题，提出本文所要解决问题方案。酒类产品配送呈现小批量、多频次、及时性等特点,配送路径更加复杂。本文立足于对物流配送路径优化问题的研究,指出该问题属于典型的VRPＴW问题,结合时间窗约束和配送车辆容量限制约束构造了时间惩罚函数和容量限制惩罚函数,建立了该问题的数学模型。分析了遗传算法的重要控制参数,描述遗传算法的基本步骤和基本操作流程，通过引入刘海交叉法，构造了一种具有较强全局搜索能力的引申刘海交叉法，改进了原有的标准遗传算法,利用MAＴLAB编制了相应的计算程序，实现问题的迅速求解。结合北大仓啤酒有限公司的物流配送业务，用实例验证了改进遗传算法在求解此类问题时的可行性及优越性，验证了该计算程序的准确性及通用性。本文的创新点之一就是将顾客满意度函数和惩罚函数作为首要的约束条件体现在模型当中,在模型选优的过程中直接作用，从而将配送中心以往不能量化的信誉损失间接的予以量化,这在很大程度上强化了配送中心的长远利益，也提高了顾客服务水平，即准时化、高效率化等;创新点之二就是在模型的求解过程中对遗传算法的应用,为了便于求解模型，将遗传算法做了改进，应用MＡTLAB，使之更适应于本文的研究。关键词物流配送；路径优化；遗传算法；车辆调度AｂｓｔrａctTheoptimｉzａtｉonofｄｉｓtriｂutｉoｎｒoutｅsｈａsｂeｅnaniｍpoｒtanｔｒeseａrchpｒojectａtｈomｅａｎｄabroad．Tｈetraditｉonａllogisticｄistribｕtｉonｃan'ｔｓolvetheprｏblemｏfstｒicttimelｉｎｅsｓ，ｔheｔhｅｓｉｓmainｌyfocuｓedontｈeoｐtimizａtｉｏｎofeｄistributionrｏuｔinｅｓ。Ｔｈｉsｔhesｉsreｓearchｉsceｎtersonｔhｅlogｉｓｔｉｃｄistｒibuｔiｏnrouｔesoptiｍizatｉoｎｑｕestioｎtolａｕｎch，haｄｐoｉntｅdouｔｔｈｅwａyoｐｔｉmizatioｎaｓpeｃｔexistsｔｈｅｑuｅｓtiｏn，propｏｓedtｈisａrtｉcleneedｓtｏsｏｌｖetｈeqｕestiｏnplan.Thewｉｎeｓｐｒｏductａllocaｔｉonpｒeseｎtscharacｔerｉsticｓandｓｏonsmａｌlbaｔcｈ,mｕｌtｉ—fｒeｑｕeｎｃiｅｓ，timeliｎｅsｓ,tｈeｒｏuｔeｓisｍoｒeｃｏmpｌex.Thｉｓarｔｉclebaｓesｏｎtｏthｅlｏgisticdｉstrｉbutionｒoutesopｔiｍiｚaｔｉｏnqｕesｔｉonrｅsearｃｈ.ｉtiｓｐoiｎｔedｏutthatthepｒobｌemisattribｕｔabｌeｔｏtyｐiｃａｌVＲＰＴＷ．Comｂｉningwiｔhthereｓtrｉcｔionsｏftｉmewiｎdowsａnｄｄｉstrｉbuｔｉonｖｅｈｉclecaｐabilityｌｉmit，tｈeｔｉmepenalｔｙｆuncｔionandcａｐabiliｔyｌimitpenaltｙfunctioｎwerecoｎstruｃtｅｄａnｄtｈｅｃorresｐｏndiｎgｍathｅmａｔicａlmｏdelwasestａbｌｉsｈed。Thｅｉmporｔantｃontｒｏｌpａｒamｅｔeｒsofｇeｎeｔicａlｇｏritｈｌnｗｅreａnaｌyzedaｎdthebasicstepsanｄoperationprｏcｅsswｅｒedeｓｃribedinｔheｔhesｉs。ＡnextｅndｉngLｉuhaicrossｏvｅrmeｔｈoｄｗｉthsｔronｇglobａlｓearｅhinｇａbiliｔywasconsｔructeｄbyinｔrｏducingＬiuhaｉcroｓｓｏｖerｍethod，whiｃhaｍeliｏratestｈｅoriginａlｓｔａndardｇeneticａlgorｉtｈｍ．Andtｈｅsolｖｉｎgｓtｒatｅgyfoｒtheoptimiｚａtionofdiｓtrｉbuｔionroｕｔesofgoodsｗasｂroughｔforward.Tｈecalculａtiｏnｐｒocｅssｃanbeｒｅaｌiｚedqｕｉckｌｙｂｙthecaｌｃuｌaｔion

proｃedurｅ

bｙ

MATLAB。Tｈe

fｅaｓibilｉｔｙ

aｎｄ

ｓｕｐeriｏrity

oｆ

aｍeliorａteｄgenｅｔicａlgoｒithｍａppｌieｄinsｕｃhprｏｂlｅmswerecollatedｂyｂｅidaｃａngbｅerｌimiｔｅdｃomｐａny'sloｇisｔicdiｓtributiｏnsｅrvｉce，aｎdｔheａccuｒacyandcuｒｒeｎｃyofthecａlculａtionpｒogrａmwerｅｐrｏｖｅd。Oｎeofthisarticleiｎnovationistaｋｅｓｔhecusｔoｍｅrdegreeoｆsatiｓｆactｉoｎfｕnｃtionthｅmｏstimpｏrｔantconsｔｒainｔstomanifestiｎｔhｅｍｉddlｅofｔhｅmｏdｅl,iｎtｈemodelcｈoｏseｓinthesｕperｉorpｒoｃessthedirectaｃtion，wiｌｌtｈuｓalｌｏｃatｅａｎｄｄiｓpａtｃhtheceｎterforｍeｒlynotｔｏbeabｌetheｑｕaｎtifｉcatｉonprｅsｔigｅｔoｌoseｉndireｃｔlｙgiｖeｓthｅqｕａnｔiｆｉcation,thisｓtrｅnｇthenｅdthｅallｏｃａｔioｎcｅnｔerlonｇ—ｔeｒmｂeneｆｉtsｔoagｒｅaｔeｘｔｅｎｔ,ａlsoraｉsedthｅcuｓtomerｓｅrｖｉｃelevｅl，ｎａmelyａcｃurａｔｅcurｒeｎｔevents，highefficiencyandsoｏn；Secondｉｎnｏｖaｔｉonaｒｅｉｎtheｍoｄelsｏlｕtｉonｐroｃesstotheｇeneticaｌｇorithｍａpｐliｃａtiｏn，foreａseofthesoｌｕtionmodel，thegｅneticalgｏrithmwillhａvｅｍａdetｈeｉmprｏveｍeｎt，appliesＭATLＡＢ，causesitｔoａdapｔｉnthｉsａrｔiｃleｒeseａｒｃh.Ｔhisarｔｉcｌｅresｅaｒｃｈisaｃcordiｎgtothｅactｕａｌneｅｄｃonstrucｔionmodｅl,notonlycoｎsiｄｅredfｒomenteｒpｒｉseownｅcｏnｏmicagｅｎｔ,morｅovｅralｓｏｆrｏmthecuｓｔomｅｒｔoｔheservｉｃeｒequest＇sangleembaｒkinｇcoｎsideｒaｔｉonqueｓｔｉon，ｄeteｒmｉnｅstｈebesｔrouteｓ。Ｋeyｗord:

Logistｉcs

Diｓtributiｏn,

Optimizatｉon

ｏf

roｕting,

Geｎeｔｉc

Ａlgorithmｓ，VehiclｅsdisｐａtchPAGEII---PAGEVIII-目录ＴOC＼ｏ＂1－3"\h＼z\uHYPERLIＮKAbstrａctﻩPＡＧEREF＿Toc１9３７７458３＼hVHYPＥRＬINＫ＼l"＿Tｏｃ1９3７7４584＂第1章绪论ﻩPAＧERＥＦ＿Toｃ19377４5８4＼h10ＨYPEＲLＩNＫ\l”_Toc193７７４５85"1.1课题背景 ＰＡGＥRＥF＿Toc193７7458５\h１０HYPEＲLINＫ＼ｌ”_Ｔｏc193774５86"1。2研究意义ﻩPAGEREＦ＿Ｔoc１９３７74586\h11HＹPＥRLINK\l"＿Ｔoc１937745８7"１.3研究现状 PAGＥREＦ_Tｏc１９37７４587\ｈ12ＨYPEＲＬIＮK＼ｌ"_Toｃ193774５88"1。３.1国内、外物流发展状况ﻩPＡGEＲEF_Tｏｃ19377４5８8\ｈ12HYPEＲLＩＮK\l＂_Toｃ１9377458９"1．3．2国内、外物流配送路径优化研究现状ﻩPＡＧＥRＥF＿Tｏｃ1937７４５８9＼ｈ14ＨＹPＥRＬINK２。3.2各种优化方法比较分析ﻩＰAGEREＦ_Toc1９3７7４５98\h２５HＹＰEＲLＩNK＼l"_Toc19377459９"２。3.３优化方法的选择ﻩPＡGＥREF_Toc１9３77４5９9\h2６ＨYPERLINK\ｌ"＿Toc193７７46０0＂2．4遗传算法的概述 ９37７４60０\h２6ＨYＰERLＩNK\ｌ”_Toｃ1９３7746０１"2．4.1遗传算法的发展历程ﻩPAGEREF_Toｃ19３77４60１\h27HYＰＥＲLINＫ＼ｌ"＿Tｏc193７74602＂2．4.2遗传算法的特点与应用 ＰＡＧEREF＿Toｃ19３774６０2\h28HYPERLINＫ＼ｌ"_Ｔoc193774603＂２。４．3遗传算法求解一般步骤ﻩPＡＧＥREＦ_Toc1937７4603\ｈ２８ＨＹPERＬＩNK\ｌ"＿Ｔｏｃ193７７４６０4"2.４.4遗传算法求解一般流程 ＰＡＧEＲEＦ_Toc19３7７４604\h2９HYPEＲLINＫ\l"_Toｃ1９３７74605＂２．5遗传算法的重要参数 ＰAGＥRＥＦ_Tｏc1937７4605\h302。５．1遗传空间 ＰAGEREF_Ｔｏc19３7７4606\h30ＨYＰＥRＬINＫ＼ｌ＂＿Ｔoc193774607＂2.5。2编码ﻩＰAGEREF_Toｃ19３7746０7\h30HＹＰＥＲＬＩＮK＼ｌ”＿Ｔoc19377４608"2．5.３染色体 ＰAGＥRＥＦ_Toｃ19３7７４６０8\ｈ30HYPＥＲLIＮK\l＂＿Toc1937７４６0９"2.5.4种群和种群规模 PAＧEREF_Toc19377460９＼h３0HＹＰERＬＩNＫ\l”＿Toｃ1９３７7４61０”２．5。５遗传算子ﻩＰAGERＥF_Toc19377４6１0\h31ＨYＰＥRLＩNＫ＼l"_Tｏc1937７4611＂2．5。6适应度和适应度函数ﻩPＡＧＥREＦ_Toｃ193774６１1＼ｈ３2HＹＰEＲLINＫ\l”＿Tｏｃ1９3７７４612"2．5．7进化代数ﻩＰAGEＲEF_Tｏc１９３７７４612\ｈ32HＹPERLＩNK\l”_Toｃ１９3７７4613"2.６本章小结 ＰAGEＲEF_Toc193７74６1３＼h3２HYＰEＲＬIＮK\l＂_Toc1937７4614＂第3章北大仓啤酒有限公司的物流业务描述ﻩPAＧEREF_Ｔｏc１９3７746１4\h3３HＹＰＥRLＩＮＫ\l”＿Tｏc１9３７7４６15＂3.1北大仓啤酒有限公司物流的构成ﻩPＡGＥREF_Toc19３7７4615\h33ＨYPERLINK\l”_Toc１93774616＂3．1。１物流的三个主要环节ﻩPAGEREＦ_Tｏc1９37７4６16\h33HYPERLIＮＫ＼ｌ”＿Ｔoc１９３７74６１7"3。１．2物流的成本构成ﻩPAGERＥF_Tｏc１9３774617\ｈ33ＨYPＥRLINK＼l＂_Toc19377461８＂３．2北大仓啤酒有限公司物流的流程ﻩPAGＥRＥF＿Toc19３７74618\ｈ34HYPERＬIＮK＼l”＿Ｔoc1９3７746１９＂3。2。1物流采购ﻩＰAGEＲEF_Toc１９3７7461９\h34HYＰＥRLＩNＫ\l＂_Toc1937746２0＂3.2．２物流加工 PAＧERＥF_Ｔoc1９377４６20＼ｈ35ＨＹＰERLINK＼l"_Ｔoｃ19３774６21"3.２.3物流配送ﻩＰＡGEＲEF＿Toc1937７４621＼h3５HYPERLINK＼ｌ"_Ｔｏc193７74６22"３．3北大仓物流配送存在的问题ﻩPAGＥREF_Tｏc１９3７74６22＼h３6HYＰEＲLINK＼l"＿Ｔoc１９３７74６2３”3。4北大仓物流配送流程的优化ﻩＰAGＥＲEF_Toc19３774623＼h3６HＹPERLINＫ＼ｌ＂＿Toc１937746２4”3．5本章小结ﻩＰAGERＥF_Tｏc1937７4624\ｈ37HＹPERＬINK＼ｌ”＿Toｃ１93774６25＂第4章北大仓啤酒有限公司物流配送优化原型设计ﻩPAGERＥＦ_Toc１937７４６25\h３8HYPＥＲLＩNK4。1．1北大仓物流配送的拓扑结构ﻩ１９37７４62７＼h３8HYＰERLINK\ｌ”_Toｃ193７7４62８"4.1。2北大仓物流配送优化的设计思路ﻩPAＧERＥＦ＿Tｏｃ1937７４628\h38ＨＹPEＲLＩＮK\l＂_Ｔｏc1９3７746２9"４。２数学描述ﻩＰＡGEREF_Toｃ19３77４６２９\ｈ39ＨＹPERLＩNＫ＼ｌ”_Toｃ１９3774６３0"4．2。１北大仓物流配送路径优化问题的数学描述 PAＧEREＦ_Toc19３77４６３０\h39ＨYＰERＬINK＼l"_Tｏc1９3７746３1＂4。２.2时间窗约束的数学描述ﻩPAＧERＥF_Ｔoc19377463１＼ｈ40HYPＥＲLINK\l”_Tｏc193７７4６32"4．3数学建模 PAＧERＥF＿Toｃ１９37７４6３2\h4１HYＰERＬINK\l＂＿Ｔoｃ19377４６３３＂4．3.1构造惩罚函数ﻩPＡＧEREF＿Toc19３7７４633\h4１HYＰERLINＫ\l”_Toc19377４634"4.3.2建立数学模型ﻩPＡGERＥＦ_Toｃ193７７4６3４\h42ＨYPERLINＫ\ｌ"_Toｃ１９３77463５"４.４算法设计ﻩＰAGEＲＥＦ＿Ｔoｃ１9３7７４635\h４４HYＰＥRLＩNＫ\ｌ"_Ｔoc１93７７4６36"4。4。1构造染色体ﻩPAGEＲEF_Toｃ１93７７46３6\h44HＹPＥRLINK＼ｌ”_Tｏc１9377463７”4．４。２种群初始化ﻩPＡＧEREF_Toc1９３774６３7＼h44HＹPERLＩNＫ\l＂_Toc19３77４638＂4。4.３性能评价 ＰAGERＥF＿Ｔoc１9377４6３８\h４4ＨYＰERLＩNＫ4。4。4自然选择 PAGＥRＥＦ_Toc１93774639\ｈ４5HYPERLINＫ\l＂_Tｏｃ１93774６４0”４．4．５染色体交叉ﻩPAGＥＲEＦ_Toc１93７７4640\ｈ４6HＹＰERLＩNＫ４．４。7结果输出ﻩPＡＧEREＦ_Toc１937746４2\h49HYPＥRＬＩNK4．5.1主要代码ﻩPAＧEＲＥF＿Toc193774６44\h49HYPＥRＬINＫ＼l＂＿Tｏc1９3７7４645”4．5．２运行步骤ﻩＰAＧEＲEF_Ｔoc１9３774６45\h5１HＹＰEＲLIＮK5．1北大仓物流配送路径优化问题的提出ﻩPＡGERＥＦ_Tｏc19３7７4648＼h5３HYPERLＩＮK\l＂_Toc19３77４649”5。２北大仓物流配送路径优化问题的求解过程ﻩPAＧＥREF_Toc193７７4649\ｈ5４HYＰERＬINK５。３．1核对配送过程 PAGERＥF_Tｏｃ19３774６5４\h58HYPERLIＮＫ\l”＿Tｏc1９3774655”５。3．2验证求解结果ﻩPAGEＲＥＦ＿Toc193774655\h５９ＨYＰＥＲＬINＫ\l”_Toc193７７46５6”5．４本章小结ﻩPAGEREF_Toｃ１９3７７4６56\h61HＹＰＥＲＬＩNＫ\ｌ”_Toc193７7４6５７”结论ﻩＰAＧERＥＦ_Tｏc19３7７４６５7\ｈ63ＨＹPERLINＫ＼l＂_Toc193７746５8”参考文献ﻩPAGＥRＥF_Toc193７74658\ｈ6５HYPERLINK\l”_Toc19377４659"附录：改进遗传算法的程序清单ﻩPＡGＥREF_Toc１93７７4６5９\h６８HＹPEＲLINＫ＼l"_Tｏc１93７7４660"哈尔滨工业大学硕士学位论文原创性声明ﻩＰAGＥＲEF＿Toｃ1937746６0\h75ＨＹPＥRLＩＮＫ\l"_Ｔoc1937７46６1＂哈尔滨工业大学硕士学位论文使用授权书 PＡGEREＦ_Toc19３７74661\ｈ7５HYPＥＲLINK\ｌ＂＿Toc１937７４66２"哈尔滨工业大学硕士学位涉密论文管理ﻩＰＡＧEREF＿Ｔoｃ１937７4662\h75HYＰERLＩＮK\l"_Toｃ19３７7４663”致谢 ＰAＧERＥF_Ｔoc19３77４６63\ｈ7６第1章绪论近年来,物流业在我国得到了快速的发展,成为经济发展的重要动力，综观国内外的发展状况,物流的价值将会在各个领域得到进一步体现。最初的物流配送（ＰｈysicalDｉsｔriｂuｔiｏｎ）的概念［1,2],是美国学者克拉克在二十世纪初提出的。传统意义的物流,是指发生在商品流通领域中的在一定劳动组织条件下凭借载体从供应方到需求方的商品实体定向移动.之后在二站期间,围绕战争供应问题，形成了“后勤”（Lｏｇisｔics)理论,将战时物资生产、采购、运输、补给等活动作为一个整体进行统一部署，以求战略物资补给的费用更低,速度更快,服务更好。后来，“Loｇｉsticｓ"一词在企业中被广泛应用。随着经济社会的不断发展,现代物流已逐渐从传统的单一销售服务，发展成为以现代科技、管理和信息技术为支柱的综合物流系统。1９84年，美国物流管理协会正式将物流概念改为Lｏgiｓtiｃs，并将物流定义为“为了符合顾客的需求,将原材料、半成品、完成品以及相关的信息从发生地向消费地流动的过程,以及为使保管能有效、低成本的进行而从事的计划、实施和控制行为"［３］.相对于传统物流而言，现代物流的特征是在传统物流的基础上，运用先进的计算机电子技术和先进的网络信息技术,以及诸如供应链管理等先进的管理方法,综合组织物流中的各环节，把制造、运输、销售等环节统一起来管理,使物流资源得到最有效的利用,以平衡物流的服务优势和服务成本，以期使用户得到最大的满足,实现服务增值.1.１课题背景本文的研究主要以齐齐哈尔北大仓集团有限公司的物流配送业务为背景.北大仓集团有限公司是黑龙江省大中型骨干企业之一，是齐齐哈尔市十大重点企业集团之一和地方财政主要支柱之一，是以生产A级绿色食品“北大仓”牌白酒和“明月岛”牌啤酒为主导产品的跨行业、跨地区、融工业、商业、房地产开发业务等多种行业为一体的综合性发展的企业集团。北大仓集团啤酒有限公司是集研发、生产、销售为一体的中型专业生产啤酒公司.公司目前下辖甘南分厂、富裕分厂两大生产基地及齐齐哈尔七区九县十六个销售营业部，各销售部负责辖区销售点的产品配送，已经形成一个生产基地—-销售营业部——客户点的三级配送网络。为了能够实现快速配送,北大仓集团啤酒有限公司拥有几十辆载重不同的车辆,负责基地到销售部的销售、调拨、运输任务。销售部也管辖一定数量的车辆,负责完成客户网点的配送任务。公司下设物流部门,管理物流配送中的各个环节。物流部门设置了专职的调拨中心，负责每天基地→基地和基地→销售部之间的货物调拨.那么如何将车辆有效的使用并决定其最经济的行驶路线图，在最短的时间内把产品送到顾客的手中,提高顾客的满意度，将是物流部门的工作重点。显然配送服务的要求将越来越高,为了实现配送成本的降低，必须对配送过程进行合理规划。这就涉及到时间、财务、环境及服务质量四方面的因素,首先从时间上要考虑准时性、快速响应；财务上要考虑运输涉及的各种开支（员工薪酬、消耗等);环境上要尽可能减少不必要的行驶，避免交通拥挤、空气以及噪音污染;最后从服务质量上，要求满足顾客要求，达到顾客满意度最大化.这些都可以通过改进运输方式、线路规划等来改善。目前，物流配送活动中的配送运输路径确定问题，成为近二十多年来车辆路径问题的重点研究对象和应用领域。在配送运输中，由于配送用户多，城市交通路线又复杂,如何组成最佳路线，如何使配装和配送路线有效搭配等,是配送运输的特点，也是难度较大的工作。于是采用科学的、合理的方法来确定配送线路，成为提高物流配送车辆效益、实现物流配送科学化的重要途径,也是配送活动中非常重要的一项工作。可见,物流配送业务的重点是如何将车辆有效的使用并决定其最经济的行车路线,使得货物能以最少的成本在最短时间内送到顾客的手中，国外将此类问题称为车辆优化调度问题（VehiｃleＲouｔinｇＰroｂlｅｍ),简称VＲP问题。随着消费者需求的多样化发展，对于该问题的分类向多元化,如送货时间要求的日趋严格引出了有时间窗的车辆优化问题(VehicｌｅRoutｉｎgＰｒoblemｗｉthTimeＷindows)，简称VＲPTW等。本课题针对北大仓啤酒有限公司产品配送过程中现实存在的到货期限过长、影响集团信誉等问题,提出采用即时配送方式;在标准遗传算法的基础上引入刘海交叉法,构造出一种改进遗传算法，用于求解北大仓啤酒有限公司产品配送的路线优化问题;编制相应的MＡTLAB计算程序，实现该问题的迅速求解;通过具体北大仓啤酒有限公司配送数据,验证利用这种改进遗传算法在求解该问题时的可行性及优越性。以此拓宽遗传算法的应用范围,便于在更多领域内发挥其优越性；将严格要求配送时效性的北大仓啤酒有限公司产品从普通货物中分离出来，单独考虑其配送的最佳方式,从行业的角度更新物流配送的划分方式，使物流配送理念植根于具体的货物品类中,为其它品类货物的配送起到抛砖引玉作用.１．２研究意义本论文以北大仓啤酒有限公司提供的啤酒配送数据为依据，对配送路径问题进行数学分析，通过适用性较强的遗传算法解决车辆的配送线路的生成问题。主要解决配送优化中可能存在的以下问题:1、解决时间限制问题。通常情况下，客户对车辆到达时间有限制的，主要有硬时间窗、软时间窗和软硬相结合的混合时间窗，而在实际的物流配送中，混合时间窗的相对多一些，配送车辆如果能在最佳时段内将货物送到客户，则客户满意度最大,否则客户的满意度降低。随着服务质量要求的提高，客户对其要求也越来越严格,时间限制成为首要的约束条件。２、目标性。对配送中心而言，以往只是一味的按照某一目标，在主要以时间为约束的条件下确定方案，产生很多不良效果，如不满足准时送货的目标、会令顾客不满意等，因此有人通过建立多目标函数来优化方案，通过综合各个约束条件,尤其是多目标之间的协调性,从中选出相对较优的方案,相应的在计算方面较单一目标计算的复杂度难些。但是本文通过引入顾客满意度这一约束变量,使配送中心可以在单一目标下，满足准时送货的要求来进行决策,将多个目标综合到总配送费用最小的目标中,从而避免了多个冲突目标之间协调性把握不准确的问题,降低了计算的难易程度，这将是本论文的一个突出的创新点。3、实效性。在实际选优过程中，顾客对服务的满意程度往往是各不相同，如对服务时间要求不同，相应的满意程度也不同.因此就要求我们在满足配送费用最小化的同时,还要充分考虑顾客的最大满意程度。本论文对物流配送企业实现计算机配送路径优化、降低成本和提高物流经营管理水平、更快的响应、最终能显著的增加企业的竞争力具有重要的参考价值。应该说,在实践当中具有较强的理论意义和实践价值。1．3研究现状物流业在国民经济和地区经济中发挥着带动和支持整个国民经济的作用.当前,在信息技术的支持下，发达国家的现代物流已经成为国民经济发展的重要支柱产业、提高经济效益的重要源泉、产业升级和企业重组的关键推动力、以及区域创新和经济发展支撑环境的关键因素之一。物流业在国民经济和地区经济中发挥着带动和支持整个国民经济的作用。物流业实际的发展情况也证明了其在一国国民经济中的重要地位.根据《国际统计年鉴200５》[4］提供的资料测算，200５年各国物流业增加值占ＧDP的比重,美国为２2.7２％,日本为21。1５％,法国和意大利分别为20。3３％和24。87％。物流业也是国家和地区财政收入的主要来源。200５年１月至９月，我国社会物流总值为35.6万亿元，同比增长25．1％；物流业增加值为6８７8亿元，同比增长14.7％，占服务业全部增加值的比例从上年的１９。５％提高到21．3%;物流相关行业固定资产投资633４亿元，同比增长２8。２%，略高于全国平均投资增长水平,成为财政收入的重要来源。物流业的发展能创造众多的就业岗位，对社会的发展和稳定具有重要作用。2００0年各国批发零售业与货运业从业人员占第三产业就业人口的比重，美国为３5.29%，日本为４5。５4%，加拿大为４1．３5％，德国为3５．１４％,意大利为３9．6６％。西方发达国家,流通产业就业人数己经超过一、二产业，成为吸纳劳动力最多的部门。我国关于批发零售业与货运业从业人员占第三产业就业人口的比重虽然没有准确的统计，但物流产业的快速发展,带动经济发展与就业需求已经成为实现和谐社会的重要途径.1．3。1国内、外物流发展状况从总体上看,我国的现代物流还处于发展的初期阶段［5]，从物流企业的性质上来看，现有的物流企业大致可分为以下几类：１、中央直属的专业性物流企业，即专营生产资料的物资储运总公司和外运公司。像中石化、中铁运输、烟草行业等,物流主要针对系统内部，商流与物流从形式上是分离的，受行业行政控制.这些专业物流企业一般有资金优势,但是由于缺乏市场竞争压力,无论是现在物流的意识和现代技术的应用都存在较大差距，效率和成本问题比较突出。２、地方专业性物流企业,即地方商业系统的储运公司及粮食仓储系统，完全受当地行政领导.这些物流企业的发展现状与当地政府有密切关系，一些沿海发达城市，在一些外资企业带来的先进管理思想和技术的影响下，物流的现代化程度相对较高。一些地区建立了“物流园区”，吸引物流人才和技术，第三方物流得到蓬勃发展.3、兼营性物流企业，即集物流与商流为一体的物流企业，比重大,且数量正在不断增多。由于规模和资金方面的差异,造成良莠不齐的局面，大部分顶多只能说是运输公司,普遍处于传统物流的阶段。从物流业总体水平来看，与国外发达国家相比差距还很大[6]。以物流成本为例，西方发达国家由于经济运行的节奏加快,量流动资本处于沉淀状态的份额极小，周转速度普遍较快，从而可以为企业带来巨大的增值空间,物流总成本占GDＰ的比重，美日等国家物流成本占GDP的比重不断在降低。据统计,美国的这一比重20０0年为１０.2%,20０1年为9。５%，20０2年为8．７％；日本的比重也基本维持在９％左右.2００４年我国物流总费用相当于GDP（现价）的２1.３％。2005年１月至９月,同比增长13。6％；社会物流总费用占GＤＰ的比例20．９％。造成成本巨大差异的背后，是我们人才的制约、管理的粗放等差距，先进的管理思想和技术没有普及，说明我国的物流业尚处于传统物流阶段.对于国内物流企业来说,基础信息化仍然是当前需求的主要内容，据2006年有关调查，72%的企业仍把办公自动化建设列为未下一年的重点,86.１％的企业有将上MＲＰ２的意愿，6０%的企业把ERP列为下一阶段建设的重点。这表明在相当长的时期内，需求的特点仍是在规范流程中实现信息的采集、传输、存储、共享,建立决策、控制依赖于信息、数据的机制，与真正的应用还有距离.其在近几年“物流热"的影响下，在国内关于物流的研究还是有一些。如关于库存与运输问题，有随机库存—运输联合优化问题研究[50]，从宏观上给出了库存－运输联合优化问题的定义、特点和分类,同时指出了己有研究中存在的不足和一些潜在的研究领域，这些都有利于对此类问题的研究的进一步深入和扩展。还有，关于算法问题,有基于遗传算法的物流配送网络优化[5１］[５2][５3]，分析了物流配送网络优化模型的各个关键组成部分，包括优化目标，决策变量和约束条件，分析了如何利用和设计合适的遗传算法来解决物流配送网络的优化问题等.国外的物流发展起步早,经验成熟,尤其是信息化管理程度高，对我国物流发展有很大的借鉴意义。1、物流电子商务蓬勃发展。２004年电子商务市场规模超过1０00０亿美元,电子物流将是21世纪物流发展的大趋势.2、规模效应显著体现.规模的扩大通过企业合并，企业间的合作与联盟,大型的物流企业和物流经济区不断增加。美国的物流模式为物流中央化，该模式强调“整体化的物流管理系统”,物流管理包括分配计划、运输、仓储、市场研究、为用户服务五个过程。3、物流服务的增值效果明显。建立QR、EＣR和ＪIＴ系统[５4］。ＱＲ（QｕiｃkReｓponse)，即快速反应.８0年代,在美国以低价销售为特征的沃尔玛，K—MARK等平价商场大行其道,主要原因是物流信息及渠道的畅通。专业服务的介入，使在生产商看来非常繁琐耗时的信息处理工作变得十分简单。EＣR（EｆficｉentCustｏmeｒResponｓｅ)，即高效客户信息反应系统,源于１９92年FMI（美国食品营销协会）发表的一份报告。其原因是传统商店的经费高于会员制全销俱乐部等新商业形式,比如，超级市场的经费率为２１．８％，而会员制的全销俱乐部只有7。5％,平价药店为16％。其仓库商品的周转次数每年达20次左右，若利用客户信息反馈这种有效手段，可增加到2４次。ＪIT(juｓｔintｉme)，即及时制造系统,可从零售商店很快地得到销售反馈信息，组织生产，达到零库存的目标,物流配送不仅实现了内部的信息网络化，而且增加了配送货物的跟踪信息,从而大大提高了物流企业的服务水平，降低了成本，增强了竞争力。4、第三方物流发展迅速［５5]。第三方物流服务公司大都是传统的“类物流”业为起点而发展起来的，如仓储业、运输业、空运、海运、货运代理和企业内的物流部等，他们根据顾客的不同需要，通过提供各具特色的服务取得成功.５、用新的科学技术改造物流装备和提高管理水平。信息化—采用无线互联网技术，卫星定位技术（GPS），地理信息系统（GＩS），射频标识技术（ＲF）等.自动化—导引小车（AGＶ)技术,搬运机器人（RｏｂotSyｓｔem）技术等。智能化-电子识别和电子跟踪技术，智能运输系统（ＩTS）。集成化-信息化、机械化、自动化、智能化于一体。信息技术在流通领域的广泛应用，极大地提高了发达国家流通的效率和竞争力。例如，沃尔玛将信息技术广泛运用于分销系统和存货管理，曾投入七亿美元建立了一个卫星交互式通讯系统,并在每一台货物运输车辆上都安装卫星移动计算机系统，可以实现世界范围内500０多家门店的单店管理，有110家配送中心，８5％以上的商品自己配送。沃尔玛公司凭借先进的信息、补货系统，可将一件商品从出厂到摆上货架的时间平均控制在５-7天,而一般公司需３0天。信息技术是沃尔玛领先于其对手的核心竞争力之一。物流的发展与现代信息技术是息息相关的，信息化是现代物流的灵魂，现代信息技术推动了传统物流的发展。可以看出,西方先进发达国家物流现代化的途径就是信息化，通过信息化建设加大地缩短了服务响应时间，提高了物流的效率,从而达到降低成本的目标，建立了企业核心竞争力。我国物流业最需要借鉴西方发达国家的经验就是从微观应用层面，推广使用现代物流的管理和技术，实现可持续的发展道路。１．3.２国内、外物流配送路径优化研究现状自从Dantinｇ和Ramseｒ于1959年首先提出车辆路径问题(ＶRP)及相应的数学规划模型和求解算法以来，由于其应用的广泛性和经济上的重大价值,一直受到国内外学者的广泛关注.在经典VRＰ的基础上，配送车辆路径问题在学术研究和实际应用上产生了许多不同的延伸和变化型态，包括带能力约束的车辆路径问题(CａPａcitａｔedvｅhｉdeＲoutｉｎｇProblｅms，ＣVRP)、带时间窗的车辆路径问题（ＶehｉcleRoutｉngＰrｏbleｍswithTimeWindoｗs，ＶRPTW)、追求最佳服务时间的车辆路径问题（VｅhｉdeRoｕtｉｎｇＰroｂｌemｓwithDefiｎedＴｉme，VRＰDＴ）、多车种车辆路径问题(ＦｌeetSｉｚeaｎｄmixＶehicleRoｕtｉngＰrobｌems,FSVRＰ)、车辆多次使用的车辆路径问题（ＶehiｃlｅRouｔｉnｇProbleｍsｗithMultipleUseｏfＶｅｈicｌe，VＲPＭ）、随机需求车辆路径问题（VeｈicleRoutingProbｌemｗｉtｈStoｃhａsｔｉcDemanｄ,VRPＳD)、动态车辆路径问题(DｙnamcVehicｌeRoｕtiｎgＰｒoblems,DＶRP)、考虑收集的车辆路径问题（VｅhｉclｅRoｕtinｇPrｏbleｍｓwiｔｈBaｃｋｈaｕls，VRＰB）、满载/非满载VRＰ、双向ＶRＰ等［５８].本文对当前国内外不同的VRP研究进行综合,详细介绍有时间窗的物流配送路径优化问题的国内外研究现状。有时间窗的VRP(VRPＴＷ)是对经典ＶＲP加上时间窗限制(即加上客户要求访问的时间窗口),可以看作是经典VRＰ的一个特殊类。１98５年,Ｓavelｓbｅrｇh证明了VRPTW是一个NP(Voｎ-linｅaｒＰｒｏbｌem，非线性规划)疑难问题，很难求得问题的最优解。目前，国内外专家和学者对其求解主要集中在启发式算法上，求得问题的近似最优解（可行解）.1964年，由Ｃlａｒk和Wｒｉｇht提出Ｃｌａrke-Wright算法（成本节约法）以后,Golden，Nelｓoｎ，Ｐaeｓｓenｓ等人通过使用适当的数据结构,降低了它的复杂度。C—W法随后成为许多专家和学者针对VRPTW的研究基础［59].1９68年，Ｒao等人在BalinsｋｉVRP集分割的基础上引入了列生成方法进行求解。这种算法本质上是最短路径算法，同时结合了分枝定界算法。Ｄeｓrochｅr曾用它求解有１0０个客户的VRPTW.1981年，Fｉsｈe等人针对带能力约束、时间窗以及无停留时间的ＶRＰ,提出了三下标车辆流方程。基于Bendｅrs的分解方法，他们提出了一种启发式算法,保证在有限的步骤内找到优化解.Ｆishe等人用它计算了有了０-１99个客户的VＲP.Martelｌｏ和Desｒocｈｅrs则分别提出了相应的改进算法。19９１年Thａngｉaｈ和1９9３年Ｊoｅy分别用遗传算法求解VRPTW，但是都存在“早熟收敛"的问题[６０］［６1］.199４年，P.waｒk等人提出了重复匹配的方法，该算法在其模型里同时考虑了时间约束和能力约束，因此适用于这类具有强约束ＶRP［6２］.重复匹配算法也可求解较大规模的问题（１９９个客户)。在我国，一些专家和学者也开始尝试ＶＲＰTW的研究。１998年,李大卫等人对适用TＳP的最近距离搜索启发式算法进行修正，构造出评价函数,并据此提出一个求解VＲPTＷ的启发式算法。２０00年，谢秉磊等人将货运量约束和时间窗约束转化为目标约束，设计了基于自然数编码的可同时处理软、硬时间窗约束的遗传算法，实验分析获得了较好的结果[63].20０1年，周贤伟和李光远根据车辆装载ＧＰＳ设备的特性,建立了货物运输VRPＴW的数学模型，并设计了求解的遗传算法[64]。20０2年,张丽萍等人通过引入新颖交叉算子,构造了一种改进遗传算法.该算法摆脱了对群体多样性的要求,不存在传统遗传算法常见的“早熟收敛”问题,可用于解决VＲPTW［５7］.２０03年，宋厚冰和蔡远利针对VRPTＷ，在标准遗传算法的基础上，将分组信息与每一个染色体结合，并辅以补交换局部搜索技术，构造了一种改进遗传算法，使得求解结果更接近最优解［5６]。同年,宾松和符卓通过引用一种新的编码方法及交叉和变异概率的自适应机制，构造了改进遗传算法来求解带软时间窗的VRＰTW［55］。2００4年，刘小兰等人为了克服原有大规模邻域搜索算法不能有效求解时间窗较宽的ＶRＰ的缺陷,介绍了VＲPTW的通用数学模型。通过分析各主要变量之间的关系，构造了一种简单、快速的确定性初始算法，并通过引入“短路径优先策略”,构造了改进的大规模邻域搜索算法，该策略也可嵌入到求解时间窗比较窄的ＶＲＰ中,达到加速搜索的目的［４9］。1。4本论文的研究目的随着经济全球化和信息技术的迅速发展，企业依靠降低物质消耗和提高劳动生产率来提升竞争优势的空间越来越小，被誉为“第三利润源泉”的现代物流正在世界范围内广泛兴起。完善的物流将起到减少人力,减少企业内部运作环节，提高生产效率,降低成本，增强竞争力的作用。在整个配送环节中,车辆配送路线的合理优化,对于整个物流速度、成本、效益影响至关重要.目前，北大仓物流有限公司产品配送路径的选择主要是依靠劳动者的经验手工制定的。随着企业规模的不断壮大，销售营业部的数量和客户间的路径也日益增多，安排配送路径的复杂度越来越高。手工配送不但耗时费力，在配送路径的合理性上，也很难满足企业的业务需求。为了进一步提高企业的物流配送效率、降低物流成本，最大限度地提升北大仓物流有限公司的配送能力和市场竞争力,根据具体的齐齐哈尔北大仓啤酒有限公司的实际业务应用背景，提出了利用改进的遗传算法来解决路径优化问题,应用ＭＡTLＡB,尽可能缩短配送时间或配送距离，达到客户时效性的要求,从而在降低配送成本的同时改善顾客服务的水平，是本文的研究工作目的。１。5本论文的主要工作和框架结构作者阅读大量文献后，对车辆路径问题按照涉及到的实际配送路径规划中的不同约束条件进行分析和总结。在此基础上提出了本文研究的车辆路径问题,即在不违背车辆容量、最大路径、时间等约束条件的前提下,合理规划配送时的车辆路径安排，以尽可能小的成本满足客户对货物和服务时间区间的要求,用改进遗传算法优化车辆路径问题，解决车辆调度任务。应用改进的遗传算法对模型求解的最佳路径,优化配送路径，是本论文的核心部分。针对本文要解决的问题,构建以配送费用最小为目标的配送路径优化模型,把顾客满意度引入模型中，作为一个重要的约束条件来处理，通过模型的构建，来解决实际当中可能遇到的问题，进而优化问题。在求解过程中,通过改进,将遗传算法的逻辑思维应用到的MAＴLＡB编程当中，得到最合理的配送方案，避免了多目标的计算复杂性,同时达到了多目标的效果.本论文的主要工作如下：(１）针对北大仓物流有限公司产品配送过程中现实存在的到货时间过长、货损严重等问题,提出构建北大仓物流有限公司产品配送路线优化问题的数学模型。(2)在原有刘海交叉法的基础上,构造一种引申的刘海交叉法，并提出相应的改进遗传算法。(３)应用这种改进遗传算法，求解北大仓物流有限公司产品配送路线优化中的实际问题。（４）编制相应的MAＴＬAB计算程序，实现北大仓物流有限公司产品配送路线优化问题的迅速求解.(5)通过具体实例,验证应用这种改进遗传算法求解北大仓物流有限公司产品配送路线优化问题的有效性及优越性.本论文各章节的主要内容如下：第一章：本章介绍了本课题研究的背景,分析了北大仓物流配送路线优化研究的重要性，描述了物流配送的发展状况，阐述VＲPTW问题的国内外研究现状，并对本文的主要工作及研究内容做出了简要的概括.第二章：主要介绍物流配送路径优化需要应用的主要技术和理论，阐述选择理由.介绍了物流配送车辆路径问题、各种优化方法的介绍、比较分析;结合北大仓啤酒有限公司物流配送实际,分析了算法选择的理由,介绍了遗传算法的概况、特点、重要参数以及遗传算法的求解步骤和流程。第三章:简要描述北大仓啤酒有限公司物流的基本情况,分析及各环节存在的现状和存在的问题。将北大仓啤酒有限公司的物流分为物流采购、物流加工、物流配送三个主要环节,分析北大仓物流配送环节普遍存在较多的问题。第四章:根据北大仓啤酒有限公司的实际业务情况，讨了北大仓物流配送路线优化问题,首先针对该问题的主要内容以及时间窗约束给出了数学描述,构造了车辆容量惩罚函数和时间惩罚函数，建立了该问题的数学模型;针对遗传算法固有的控制参数选择困难及早熟收敛等缺陷，在标准遗传算法基础上引入适用于旅行商问题的刘海交叉法，构造出一种引申的刘海交叉法，提出了相应的改进遗传算法；编制了MATLAＢ计算程序，实现了北大仓物流配送路线优化问题的迅速求解。.第五章:通过把改进的遗传算法应用到北大仓物流配送路径优化问题中，验证改进的遗传算法。结合北大仓物流配送路线优化问题的具体实际，阐述了该问题的求解过程；借助MATLＡB计算程序,实现了最优配送路线的搜索过程；根据时间窗约束及容量限制约束对所求结果进行了核对;利用标准遗传算法在同等条件下重新求解了该问题；在两个求解结果的比较过程中,验证了本文所提出的改进遗传算法在求解该问题时的优越性,证实了为求解该问题所编制ＭＡTＬＡB7。0程序的通用性和迅速性。第六章：结论。通过对全文内容的归纳和总结,得出了本研究的主要结论,指出了北大仓物流配送路径优化问题的进一步研究方向.１。6本章小结通过本章节的研究,进一步明确了选题的背景、目的与意义，通过国内外的物流以及VＲP研究现状介绍,确定了本文的研究目的和研究内容。可以看出，现代物流的发展,必须对物流配送路径进行优化,实现低成本、高效率、高品质的物流配送服务.第2章物流配送路径优化研究的相关理论本章主要对物流配送优化的相关技术和理论进行介绍，解决北大仓啤酒有限公司物流配送路径的优化问题。2.1物流配送路径优化概述根据物流长期发展所形成的通用经验,发现物流配送的一个重要目标就是要在满足客户要求的前提下，投入尽量少的配送成本(主要是各种运输线路上的损耗）.在网络化的今天,由于信息流通便捷，各部门协同工作的能力越来越强，实现诸如“整合运输”、“最低库存”、“快速反应”的客观条件越来越充实；因此，如何充分利用现有条件，达到物流配送的最小成本消耗己经成为一个备受关注的问题。特别是“整合运输"等一系列新的货物运输概念的提出,更使得原来的单线的，仓库→单个客户→仓库的配送模式被完全推翻，取而代之的是每个运输单位运输不同的货物到不同的客户手中;而不是像往常那样，每个配送单位分配单名客户,把货物运到客户手中就立即返回,造成路程上的大量浪费。物流配送问题可以描述为:如何选择最优配送路径，使得投入的运输成本最低,又能满足客户的时间要求.实际上，由于客户数目的巨大，这一问题的可行解数目非常巨大，甚至不可能用类似于枚举法的方法在能够接受的时间范围内得到最优解或者较优解，因此该问题己经成为一个公认的物流难题。２．2物流配送路径优化目标物流配送路径合理与否直接影响着物流运输的成本和效益，因此,采用科学的合理的方法确定配送路线,是物流配送过程中非常重要的一项操作。确定配送路线可以采取各种数学方法和在数学方法基础上发展和演变出来的经验方法.无论采取何种优化方法，首先要明确物流配送路径的优化目标,目标的选择根据配送的具体要求、配送中心的水平、实力及客观条件而定，一般有以下几种：1、效益最高：在选择以效益为目标时,通常以企业当前的效益为主要考虑因素，同时兼顾长远的效益。效益是企业整体经营活动的综合体现，可以用利润来表示，因此，可以在计算时以利润数值最大化为目标值。但由于效益是企业经营的总体反映，在拟定数学模型时，很难与配送路线之间建立函数关系,所以一般很少采用这一目标。2、成本最低:成本计算比较困难,但和以效益为目标相比有所简化。成本和配送路线之间有密切关系，且在成本对最终效益起决定作用的情况下,采用以成本最低为目标实际上等于选择了以效益为目标，比较可行实用.３、路程最短：如果成本和路程相关性较强,则可以选择路程最短为目标，这样可以避免许多不易计算的因素.但需要注意的是，有时候路程最短并不意味着成本最低，如果道路条件、道路收费等因素影响了成本，这时单以最短路程为最优解则不合适了。4、单位运输量最大：单位运输量是指单位距离内所运送的货物总重量。单位运输量在长途运输中常作为选择目标。5、准时性最高:准时性是配送中重要的服务指标，以准时性为目标确定配送路线就是要将各客户的时间要求和到达各客户点的先后顺序进行协调安排，这样有时难以顾及成本问题,甚至需要牺牲成本来满足准时性要求。6、运力利用最合理:在运力非常紧张、运力与成本或效益有一定相关的情况下，为了节约运力、充分运用现有运力，而不需外租或新购车辆，也可以运力安排为目标，确定配送路线。针对不同的物流配送问题，要根据具体情况选择优化目标。本文研究的物流配送问题根据北大仓啤酒有限公司自身物流的特点，将优化目标设定为:路程短、准时性高、运力利用合理。2.3物流配送的路径优化方法的选择国外将物流运输车辆调度问题归结为VRＰ（VｅhiｃleRoｕtingＰrｏblem，即车辆路径问题)[24][25］、ＶSＰ（ＶehiｃlｅScheduｌｉngProｂｌeｍ,即车辆调度问题）和MTSP（MｕlｔｉｐleTraveｌｉｎgＳaleｓmanPrｏｂｌem，即多路旅行商问题)。该问题于1959年由Ｄanｔzｉg和Ramsｅｒ提出后［2６］，很快便引起运筹学、应用数学、组合数学、图论与网络分析、物流科学、计算机应用等学科的专家以及运输计划制定者的极大重视,并一直是运筹学与组合优化领域的前沿与热点问题。在现实生产和生活中，邮政投递问题、飞机、铁路车辆、水运船舶及公共汽车的调度问题、电力调度问题、管道铺设问题、计算机网络拓扑设计问题等都可以抽象为物流运输车辆调度问题。本文所研究的物流配送车辆路径问题的求解方法对解决上述问题也是有效的。可见,本文将物流配送车辆路径问题作为研究对象，具有一定的理论和现实意义。经典的物流配送路径优化问题（即经典ＶＲP）可描述如下:有多个货物需求点（或称顾客）,已知每个需求点的需求量及位置，至多用m辆汽车从配送中心（或中心仓库)送货,每辆汽车载重量一定，安排汽车路线,要求每条路线不超过车辆载重量和每个需求点的需求必须且只能由一辆车来满足,目标是使运距最短或者运输费用最少。早在１９62年Bａlinsｋi等人首先提出VRＰ的集分割，直接考虑可行解集合，在此基础上进行优化，建立了最简单的VRP模型[7].1９８1年，Eiｌon等人提出将动态规划法用于固定车辆数的VＲＰ，通过递归方法求解[８］。１９7４年,Ｗrｅn，Giｌleｔｔ等人提出Sｗｅeｐ算法（扫描法）[9]。１９81年,Chriｓtofidｅs等人提出了k度中心树和相关算法，对固定车辆数m的M-ＴSP进行度中心树松弛［１0］.后来,Ｍ．Ｌ。Fｉsｈe对这种方法做了进一步改进可求解有１３4个客户的ＶＲP[11]。１99１年，Ｇｅndreａu等人将禁忌搜索方法应用于VRP［12]。它是针对VRＰ比较好的启发式算法,可以成功地应用于许多经典的ＶＲＰ.其后Ｅ。Tａｉｌｌａrd等人通过按角度和路径重心对原问题的空间进行分割，结合禁忌搜索和模拟退火对子问题求解，实现了对问题求解的并行化［１3]。1９96年，J.Ｌａwrｅｎｃe将遗传算法用于ＶRP的研究，并可有效求解带时间窗限制的VRＰ［14］。鉴于传统的遗传算法是个大范围、粗粒度的寻优算法，Bａrｎier将其与约束满足问题(CＳP)的技术相结合,通过遗传算法来处理CSP参数的子域，从而减小搜索空间，降低CSP问题目标函数和遗传算法约束的复杂度。由于有时间窗约束的路径优化问题一直被众人作为核心内容研究，围绕其进行扩展研究，因此适应求解有时间窗限制的路径优化的方法自然也适合其他扩展问题的求解.本章将回顾国内外学者对求解该类问题时的相关方法，作为本文求解算法的基础。２。3．1物流配送路径优化的方法随着信息技术的不断进步，企业运营节奏的加快,有关的研究方法也随之进步。可以说问题由简单到复杂,研究方法则由精确解法发展到传统启发式算法，再到现代启发式算法，下面就路径优化的研究方法进行综述.1、物流配送路径优化问题的精确算法[27］(1）动态规划法（ＤｙnaｍiｃProｇｒamｍing）。动态规划法被用到求解物流配送路径优化问题是Ｅilon等人在1９71年提出的。Kｏlｅn等在198７年第一个将动态规划法用到带时间窗限制的路径优化问题上.该算法解题的基本思路是将一个n阶段的决策问题转化为依次求解ｎ个具有递推关系的单阶段的决策问题，从而简化计算过程［３2]。因其复杂性在于各阶段决策之间的相互联系,而且计算时间与计算机内存空间均随变量的增加而呈指数增加，所以虽然此方法可求得最优解,但仅适用于较小规模的寻优问题。（2)分枝定界法（Bｒancｈａndｂｏund）。此方法是一种隐枚举法或部分枚举法，它不是一种有效算法,是枚举法基础上的改进，是求解整数规划的较好方法［32］。Koleｎ曾利用此方法求解有时间窗约束的车辆巡回问题,其实验的节点数范围为6～１５.当节点数为６时，计算机演算所花费的时间大约１分钟（计算机机型为VAＸ11/７8５）,当节点数扩大至12时,计算机有内存不足的现象产生,所以分枝定界法比较适用于求解小型整数规划问题。Held和Ｋarp指出分枝定界法的求解效率与界限设定的宽度有极大的关系。(3)切平面法(Cｕttiｎgplanｅs）。此方法与分枝界限法类似,也是在求解与整数规划相对应的线性规划上，不断地增加新的约束,也就是另外加入线性约束条件，以切掉对应于非整数规划的所有可行解的集合,以使问题可达到整数线性规划求解的形式，从而获得最优解。求解时间过长，不适用于大规模问题。2、物流配送路径优化问题的传统启发式算法[２8］［２9］［30］传统的启发式算法在求解路径优化问题时通常是从初始解出发，以邻域搜索的方式实现解的改进，并在较短的时间内获得一个可以接受的解.下面详细介绍几种最常用的传统启发式算法.（1)节约算法（ＳａvingMｅｔhod）.节约算法最早由Claｒke等于1964年提出该方法并用于求解车辆巡回问题.其思想在于按节约值（较短路径与原路径之差)从大到小排序,在车辆的容量限制下,依序将对应的两个顾客点排入路径中,直到所有的顾客都被插入路径为止[33］。Solomｏｎ于１983年将此方法用于求解有时间窗约束的车辆巡回问题,关键在于当节约值较大的两客户点被排入路径时，除需考虑车辆容量限制外，更需要考虑到时间窗的限制,也就是时间窗上界较早者，应优先被配送，并检验其时间可行性.而两节点间的节约值的计算公式如下：(2—1）其中：ｄ（i，o）代表客户i至配送中心的距离，d（i，j）则代表客户ｉ至客户j的距离。计算两节点i与ｊ间的节约值s(ｉ，ｊ）时，应先计算原路径中各往返路径的总和s（ｉ,j），再以之与较短路径的总路径和相比较；两节点的原路径与较短路径如图2—1所示.此方法的优点是可提高车辆的利用率.didjｄｉｄｊdｄ0原路径较短路径图2-1路径优化前后Ｃhａrｔ2—1Ａｒoｕndｗａｙoｐｔimｉzaｔion(2）邻接算法(Nｅaｒeｓt－Ｎeigｈbｏr）。邻接算法是Ｓolmon于198３年所提出的求解带时间窗限制的方法,它是一种序列构造路线法[35］。算法从一条只含一个配送点的路线出发（通常取这个点为—“距离"配送中心最近的点）。在未分配点中筛选出可加入点(所谓可加入点,是指一个未分配点,将它作为一条路线的终点仍然保持路线的可行性），并从可加入点中选取一个点作为当前路线的终点，使得路线的成本最小。如此不断对路线进行扩充，直到路线不存在可加入点为止。这时，如果所有点均已分配，则算法结束;否则，生成一条新的初始路线，重复前面的路线扩充程序。需要指出,对距离加上双引号是为了说明这样的距离未必指实际的距离，而是关于距离和时间等因素的函数.（3）插入算法。它原本是Mｏlｅ和Jａmeson于１9７６年所提出，用于求解VRＰ问题的方法，其结合邻接算法与节约算法的观念，依序将顾客点插入路径中以构建配送路线。Sｏｌomoｎ于198３年将此方法应用于求解ＶRPTW问题,因为时间因素加入，而使原问题的顾客的等待时间缩短。它的流程与邻接算法相似,也是从初始路线出发，序列构造路线。并在不存在可行插入时新增一条初始路线。插入算法的关键是选择最合适的未分配点在路线中进行最佳位置的插入。（４）扫除算法。扫除算法最早由Gillett和Mｉｌler在19７4年提出,是一种“先分组后路线”(cluｓｔeｒ—ｆirｓtｒｏｕｔe—second）的算法[３6］.1987年，将其推广应用于ＶRPTＷ问题的路线构造.所谓分组，即指分派给每辆车一组点.一种简单的分组方法是将以车站为原点的坐标平面划分为多个扇形区域，并初步将每个扇形区域的点分派给一辆车.而所谓的“路线”，是指在每个区域内,采用扫除法选择未分配点，然后应用插入算法扩充路线。如果在进行了一次“分组—路线”的路线构造后，还存在未分配点,则再进入“分组—路线"程序。如此反复，直到所有点均已分配为止。３、物流配送路径优化问题的现代启发式算法相对于传统启发式算法，现代启发式算法不要求在每次迭代中均沿目标值下降方向，而允许在算法中适当接受目标值有所上升甚至不可行的解,其目的是能够跳出局部搜索邻域。下面，对应用于

VRＰTW的现代启发式算法进行综述:（１）禁忌搜索算法（ＴＡBＵSＥARCＨ，TS)。禁忌搜索算法最早由Gｌｏver在19８6年提出，是局部搜索算法的扩展。该算法通过利用一个禁忌表记录已经到达过的局部最优点,并在后面的搜索中,根据某种限制循环的规则和禁忌表中记录的信息在当前搜索邻域中取一个合适的解［３3］。典型的禁忌是禁止在最近的次迭代中选取某些边，以控制在最近的t次迭代中不会出现同样的解。有时，根据某种事先设定的规则，选用某个禁忌对象可能会使搜索邻域更快地接近全局最优点，这种规则被称为特赦规（ＡspｉｒatiｏnCｒitｅｒia）.１９９4年,Gａrcｉａ等首先将禁忌算法应用于VRPTW问题[３７］。为了减少搜索的计算量，有专家提出了一些限定邻域的方法。另一方面,为了加速搜索进程，可采用平行计算技术。较多算法都以车辆数最少为优化的第一目标。在禁忌搜索中,通过一些变化（diｖersificatｉｏn）与强化（ｉntｅｎsｉｆicatiｏn）规则来引导搜索将显著提高其搜索效率。1995年，Roｃhat和Tａｉllaｒd定义了所谓的“适应性记忆信息”（adaptiｖｅmemorｙ）,即在搜索过程中,将最好的解所包含的一些路线保存下来所汇集而成的路线信息.其目的是通过对适应性记忆信息中所有路线进行筛选与组合后，为禁忌搜索提供一个新的起始解。之后,在199７年,Ｔaｉllard应用这种思想求解带软时间窗的问题.为了避免低效率的循环或过度限制搜索邻域,Ｃｈｉａｎｇ和Ｒusseｌl对禁忌表长度实施动态控制,即当同样的解重复次数较多时增加禁忌表的长度,而当搜索不到可行解时减少禁忌表长度。（2)遗传算法(GeneticAｌgｏrithｍ,GA）。遗传算法最早是由Ｈｏlland在1975年提出,并首先被DeJong用来解决复杂问题[3７］。由于遗传算法是借用适者生存规律进行局部搜索改进的一类算法,最优化问题的求解过程是从众多解中选出最优解，而生物进化的适者生存规律使得最具有生存能力的染色体以最大可能生存。二者的共同点使得遗传算法可以在优化问题中得以应用。该算法通过染色体的配对和变异过程实现种群的进化,每一次进化则对应解的一次迭代.当迭代次数达到最大次数限制或群体中的个体无显著差异时，迭代终止.１991年，Thaｎgiah首先将遗传算法用于求解VRPTW问题。该文将遗传算法用于点的分组。其中，每一种分组方案被编码为一个染色体，适应性函数值定义为根据相应的分组方案所构造的路线总成本，而交配则指通过随机选取染色体的两个位串（即两个组)进行的点的互换，最后以小概率事件改变其中某些位的值来实现变异。１999年，Hｏmｂeｒgｅr和Gehriｎg提出了应用遗传算法求解ＶRPＴＷ问题的进化策略。具体地,将所谓的策略参数与解向量一同编码，并通过重组和变异来实现进化。对于VRPTW问题，策略参数包括某种局部搜索方法的使用频率，以及在车辆数和总路长这两个目标之间交替改进的一个二进制参数.同年,Geｈring和Hombｅrgｅr采用一种协同自治的方式在车辆数优化方法与总路长优化方法之间建立一种协作关系。具体地，算法应用遗传算法最小化车辆数量,应用禁忌搜索算法最小化总路长,并通过制定解的更新规则建立这两个优化方法之间的协作关系。可见遗传算法在路径优化问题上的应用性很广，而且有一定的延伸性，值得做进一步改进，使算法更合理.（3)模拟退火算法(ＳiｍｕｌatedAnneaｌｉng,A）。1９96年,Ｃｈiａnｇ和Rusｓｅｌl提出带时间窗的配送路径问题的模拟退火算法。模拟退火算法实际上是一种随机松弛技巧，它模拟了退火过程.在搜索的初始阶段,算法跳向远点,随着时间的延伸或“降温"，跳跃幅度逐渐减小，最终转向局部搜索下降方法。200０年,Ｔan等基于2－iｎｔeｒｃｈangｅ法和单调降的降温表提出一种快速模拟退火算法.当到达最低温度后,通过参考初始温度和到达最好解时的温度设置一个新的温度,然后重新启动模拟退火搜索过程。20０1年,Ｌｉ等在应用插入算法和扫除算法初始化路线后,将邻域搜索方法与模拟退火程序相结合实现路线改进。(4)蚁群算法（ＡntColｏnyOｐtimｉzation，ＡCO).蚁群算法模拟了蚁群搜索食物的行为。在寻找食物时，蚂蚁会在它所经过的路径通过排放一种外激素(在算法中称为信息素）做出标记，排放的量则根据路径长度和食物的等级决定。这些外激素为其它蚂蚁提供信息，并吸引他们前去搬运食物.对于ＶＲPTW问题，每一条边（i,j)对应两个值,即吸引力认η１1和信息素τ１1。通常,η11表示两点间距离的倒数,在整个求解过程中是一个固定量,而τ１1则表示在搜索过程中选择一条边的价值,它在迭代过程中是一个需要不断调整的量。在路线的构造过程中，将根据η11和τ11确定的概率分布随机选取下一点对路线进行扩充,而信息素则根据边的选用情况进行局部和全局性的更新.具体地,局部性更新是在蚂蚁选用一条边之后,即刻对这条边的信息素τ1１下调,以减少这条边再次被选取的概率,从而提高解的多样性；全局性更新则是针对当前所获得的最好解，对其某种邻域内的边的信息素τ11上调,以增加这些边被选取的概率。1999年,Gambａrｄellａ应用蚁群算法对ＶRPTＷ进行路线改进。算法中,首先构造两组相互协作的人工蚁群,其中第一个蚁群用于最小化车辆数,第二个蚁群用于最小化总路长，并以共用解的方式建立协作关系。上述优化方法都曾解决过不同难易程度的配送路径优化问题，是根据实际发展需要而发展起来的，总结如图２—２所示.从框架结构图中可以看出：VRＰ求解是由简单到复杂,而求解方法则由精确到合理,适用性由小规模到大规模，可见其发展是随着实际需要发展的,有一定的必然性，在优化方法的选择上自然也需要改进和发展.VRP求解方法VRP求解方法最优化算法传统启发式算法现代启发式算法动态规划法分枝定界法切平面法节约算法邻接算法扫除算法禁忌搜索法遗传算法模拟退火法蚁群酸法图2—2物流配送路径优化方法框架图Ｃhart２—2Lｏｇｉsticdisｔｒｉbutionｗayoｐtｉmｉｚａtiｏｎmｅｔhｏdframechaｒt2。３．２各种优化方法比较分析综上所述,各种优化方法在一定时期、一定情况下都有其各自的优点，都有解决某一类问题的优越性，但随着发展的需要,对优化方法要求也越来越高，下面对各种方法进行比较分析，通过表格的形式来展现各自的特点，如表2。1所示。通过表格的分析比较，可以看出各种方法的特点,物流配送路径优化问题的精确算法有一个共同的特点就是可以求得最优解，但由于它引入了严格的数学方法,所以用它们求解中小规模的VＲP时在精度上优于其他算法.而VRＰ即又是NＰ难题，精确算法无法避免指数爆炸,所以不适应现在的复杂的路径优化问题，尤其是对多配送点的大型配送服务，相对求得最优解比较费时费力,且难以实现。而传统的启发式算法比精确算法相对好些,但仍不太适用于现在实际遇到的问题，和现代启发式算法相比,有些不足,但可以将传统的与现代启发式算法结合使用,通常可以在有限时间里找到满意的次优解或可行解，这是精确算法难以达到的,因此现代启发式算法方便适用，能解决实际当中所遇到各种复杂问题。表2－１各种优化方法的比较分析类别基本方法优点缺点产生时间适用性物流配送路径优化问题的精确算法动态规划法可以求最优解计算时间长且占用内存量随变量的增加成指数倍增长１9７１年适用于规模较小的问题分枝定界法求得最优解计算时间长且内存使用常有不足现象发生用于解组合优化的小型问题切平面法可以求得最优解计算时间长且所需内存大适用于解小规模问题物流配送路径优化问题的传统启式算法发节约算法提高车辆利用率，可以解决大规模问题解是较优的可行解,不一定是最优解１964年可以解决大规模问题邻接算法考虑邻近节点成本问题排序时有局限性１983年适用节点少的插入算法结合节约法和最邻近法、等待时间缩短速度慢、解非最优1976年适用于小规模问题扫除算法穿插插入法，将二者有机结合扫描每一个点，速度慢１974年适用于小规模问题物流配送路径优化问题的现代启发式算法禁忌搜索算法可以通过规则提高搜索效率可能搜索到局部最优解198６年适用于带软时间窗的VＲP问题遗传算法具有鲁棒性且全局搜索能力强,所需时间少可能会有早熟收敛现象1975年适用于复杂优化问题模拟退