（机械制造及其自动化专业论文）物流配送动态需求车辆调度模型及其混合qea研究.pdf

。1 l gu n i v e r s i t yo ft e c h lgyng ur o v e r s | c h n o l o 妤 o fd o c t o r m o d e la n dh y b r i dq e af o r l o g i s t i c sd i s t r i b u t i o nv e h i c l e r o u t i n gp r o b l e m w i t hd y n a m i cd e m a n d c a n d i d a t e ：z h a n gj i n g l i n g a d v i s o r ：p r o f z ha oy a n w e i c o l l e g eo fm e c h a n i c a le n g i n e e r i n g z h e j i a n gu n i v e r s i t yo ft e c h n o l o g y m a y 2 0 1 0 浙江工业大学 学位论文原创性声明 本人郑重声明：所提交的学位论文是本人在导师的指导下，独立进行 研究工作所取得的研究成果。除文中已经加以标注引用的内容外，本论文 不包含其他个人或集体已经发表或撰写过的研究成果，也不含为获得浙 江工业大学或其它教育机构的学位证书而使用过的材料。对本文的研究作 出重要贡献的个人和集体，均已在文中以明确方式标明。本人承担本声明 的法律责任。 作者签名： 乏贬戛凇 日期：bf 6 年6 月e t 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学f 移论文( i 勺规定，同意 学校保留并向圜家有关部门或机构送交论文的复e r j l - t ：g 电子版，允许论文 被查阅和借阅。本人授权浙江工业大学可以将本学位论文的全部或部分内 容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存 和汇编本学位论文。 本学位论文属于 l 、保密口，在年解密后适用本授权书。 2 、不保密瓯 ( 请在以上相应方框内打“”) 作者签名：弓臣戛砍 导师签 e - _ - i 期：加一年6 月7n 日期：加晦否月日 1 。一 下项目资助 国家自然科学基金项目 ( n 0 6 0 9 7 0 0 2 1 ) ： 面向物流配送的动态车辆调度模型和混合量子进化算法 浙江省重大科技攻关项目 ( n o ：2 0 0 3 c 1 1 0 3 3 ) ： 第三方物流智能信息协作平台的研究及其应用示范 1 = 业大学博士学位论文 辆调度模型及其混合q e a 研究 摘要 现代物流业的飞速发展为车辆路径问题( v e h i c l er o u t i n gp r o b l e m ，v r p ) 的研究提供 了广泛的现实背景，同时通信和信息处理技术以及计算机硬件技术的飞速发展，能够快速 获取和处理实时信息，为动态车辆调度问题的研究创造了条件。随着对v r p 研究的深入， 以往静态v l 冲的模型和算法仅能处理预先确定的信息，难以满足现实中处理各种动态信息 的需求，有必要研究包含动态信息的v r p ，建立符合物流配送实际的动态车辆路径问题 ( d y n a m i cv e h i c l er o u t i n gp r o b l e m ，d v r p ) 的模型和算法。d v r p 己成为现阶段车辆路 径问题研究的热点，通过对车辆路径进行实时动态调度，有助于提高企业物流配送服务水 平，增强企业竞争力，具有较强的现实意义；同时对该问题的研究还能丰富和充实物流科 学、运筹学及组合优化等研究领域，还具有较强的理论意义。 本文在国家自然科学基金项目“面向物流配送的动态车辆调度模型和混合量子进化算 法( n o 6 0 9 7 0 0 2 1 ) ”的资助下，针对物流配送动态需求车辆调度中的几类典型问题，在分 析其理论和实践背景的基础上，建立了多车型开放式、基于沿途补货的多配送中心、具有 模糊预约时问窗的多目标以及具有随机信息的动态需求v r p 模型；研究了混合量子进化算 法对上述模型的求解。本文的主要工作和成果如下： 1 首先阐述了课题的研究背景及意义，给出了动态车辆路径问题的定义和分类，分 析了动态需求车辆路径问题的构成要素，在对国内外大量文献总结提炼的基础上，从模型 和求解方法两方面深入分析其研究现状，针对目前研究中存在的问题以及我国物流配送车 辆调度的特点，提出了论文的主要研究内容和组织结构。 2 分析了已有研究关于每种车型车辆数目固定的多车型v r p 的不足，引入虚拟配送 中心，建立了动态需求多车型开放式v r p 的两阶段数学规划模型；制定了相应的“预优化 路线的制定十实时动态优化调度”两阶段求解策略；提出混合2 - o p t 量子进化算法进行求 解，引入2 - o p t 局部优化方法来优化子路径能减少客户序列的交叉从而提高了算法的收敛 速度；设计了一种将常用的基于整数的编码引入到量子比特的编码方法，从而解决了车辆 分析， 需求车辆路径问题的有效性， 性， 则来控制车辆补货的解码方法；提出了自适应免疫量子进化算法进行求解，引入免疫算子 进行线路内和线路间再优化，从关于问题的先验知识中提取疫苗，有效的加快了算法的收 敛速度，提高解的质量，同时为适应动态调度对算法有较高实时性的要求，在疫苗接种的 过程中设计了一种随个体适应度大小而变化的自适应选择概率，从而减少了算法的运行时 间；最后，对实例进行了仿真测试，分析了疫苗接种方式以及沿途补货策略对结果的影响， 并与最邻近插入法进行了比较，实验结果表明沿途补货策略适应于动态需求车辆路径问 题，所提的算法能有效能满足调度的实时性要求。 4 提出了一种更符合实际情况的模糊预约时间窗，通过该模糊预约时间窗来表示客 户满意度，该模糊预约时间窗可区别对待提前客户和延期客户的满意度，弥补了已有研究 同等看待的不足。将最大化的客户满意度和最小化的运行成本作为目标，建立了多目标动 态需求车辆路径问题的模型；提出自适应网格多目标量子进化算法进行求解，在算法中设 计了一种自适应网格保持解集多样性的方法，每一代中网格的数量不固定，而是根据当前 代非劣最优解集的分布情况自适应调整，采用擂台赛法则构造非支配解集；最后通过实验 分析对比，分析了算法参数对于结果的影响，选择适合问题的参数对标准测试实例进行了 实验仿真，结果表明了模型的正确性和所提算法求解多目标动态问题的有效性。 5 分析了l a r sm h 的动态随机需求v r p 模型，该模型将表示顾客数量的随机变量设 为确定值，并假设在某时刻t 随机需求的信息变为已知，从而随机数变为确定值。针对其 模型的不足，本章研究在时刻t 客户是否有需求能确定，但需求量服从参数为力泊松分布 的动态随机问题，并在l a r sm h 建立的模型的基础上考虑多配送中心，开放式的特点，建 立了动态随机问题的基于补偿策略的两阶段随机规划模型；设计的自适应免疫量子进化算 法有效加快算法的收敛速度，提高解的质量；最后，对实例进行测试仿真，分析了参数a 取 不同值时的优化结果，并与基本量子进化算法和最邻近插入法进行了比较，实验结果表明 该方法能有效的求解动态随机需求v r p 。 6 在上述理论工作研究的基础上，搭建了动态需求车辆调度仿真平台。该平台有效 集成上述各章动态需求v r p 的模型以及所提的混合量子进化算法，验证所提方法的可行 度的 混合 浙江工业大学博士学位论文 a b s t r a c t t h e r a p i dd e v e l o p m e n to fm o d e ml o g i s t i c so f f e r saw i d er a n g eo fr e a l i s t i cb a c k g r o u n df o r t h ev e h i c l er o u t i n gp r o b l e m ( v r p ) m e a n w h i l e ，t h er a p i dd e v e l o p m e n to fc o m m u n i c a t i o n s ， i n f o r m a t i o nt e c h n o l o g ya n dc o m p u t e rh a r d w a r ec o u l do b t a i na n d p r o c e s sr e a l t i m ei n f o r m a t i o n q u i c k l y , p r o v i d i n gc o n d i t i o n sf o rt h es t u d yo fd y n a m i cv e h i c l es c h e d u l i n gp r o b l e m a l o n gw i t h t h es t u d yo fv e h i c l er o u t i n gp r o b l e m ，t h em o d e la n da l g o r i t h mo fs t a t i cv e h i c l er o u t i n g p r o b l e m c o u l do n l yp r o c e s st h ed e f m i t ei n f o r m a t i o n ，w h i c hc o u l dn o ts a t i s f yt h ed e m a n do fd y n a m i c i n f o r m a t i o np r o c e s si nr e a l i t y s oi t i sn e c e s s a r yt os t u d yt h ed y n a m i cv e h i c l er o u t i n g p r o b l e m a n de s t a b l i s hm o d e l sa n da l g o r i t h m d y n a m i cv e h i c l er o u t i n gp r o b l e mh a sb e c o m et h eh o t s p o t e n t e r p r i s e sc o u l di m p r o v et h ec u s t o m e rs e r v i c el e v e ld u r i n gl o g i s t i cd i s t r i b u t i o nb a s i n g0 1 1 r e a l t i m ed y n a m i cs c h e d u l i n go fv e h i c l er o u t i n ga n de n h a n c et h ec o m p e t i t i v e n e s s ，w h i c hh a sa s t r o n gp r a c t i c a ls i g n i f i c a n c e m e a n w h i l e ，t h es t u d yo ft h i sp r o b l e mc a na l s oe n r i c ht h el o g i s t i c s 、 o p e r a t i o n sr e s e a r c ha n dt h ec o m b i n a t o r i a lo p t i m i z a t i o n ，w h i c ha l s oh a sas t r o n gt h e o r e t i c a l s i g n i f i c a n c e t h i sp a p e ri nt h en a t i o n a ln a t u r a ls c i e n c ef o u n d a t i o no f m o d e la n dh y b r i dq e af o r d y n a m i cv e h i c e lr o u t i n gp r o b l e mo r i e n t e do nl o g i s t i c sd i s t r i b u t i o n ，s t u d i e ss e v e r a lt y p i c a l p r o b l e m si nl o g i s t i c sd i s t r i b u t i o nv e h i c l er o u t i n gp r o b l e mw i t hd y n a m i cd e m a n d s ，a n a l y z i n gt h e t h e o r ya n dt h eb a c k g r o u n do fp r a c t i c e ，a n dp r o p o s e sf o u rm o d e l so fd y n a m i cd e m a n dv r p ： o p e nh e t e r o g e n e o u s f l e e tv r p , m u l t i d e p o tv r p , m u l t i o b j e c t i v ev r p w i t hf u z zt i m ew i n d o w s ， a n ds t o c h a s t i c 艘a n dr e s e a r c hh y b r i dq e af o rt h ep r o b l e m s t h em a i nr e s e a r c hw o r ka n d a c h i e v e m e n ta sf o l l o w s ： 1 f i r s to fa l li te x p o u n d st h eb a c k g r o u n da n ds i g n i f i c a n c eo fr e s e a r c ht o p i c ，d e f i n i n ga n d c l a s s i f y i n gt h ed y n a m i cv e h i c l er o u t i n gp r o b l e m , a n a l y z i n gt h ec o m p o n e n t so fd y n a m i cv e h i c l e v 2 o nt h eb a s i so fe x i s t i n gr e s e a r c hc o n c e r n i n gh e t e r o g e n e o u sf l e e ts t a t i cv e h i c l er o u t i n g p r o b l e mw i t ht h ef i x e dn u m b e ro fe a c ht y p eo fv e h i c l e ，av i r t u a ld i s t r i b u t i o nc e n t e ri si n t r o d u c e d ， a n dt h et w op h a s em a t h e m a t i c a lp r o g r a m m i n gm o d e lo fd y n a m i co p e nh e t e r o g e n e o u sf l e e tv r p i se s t a b l i s h e d ac o r r e s p o n d i n g ”f o r m u l a t i o no ft h eb e f o r e h a n dr o u t i n go p t i m i z a t i o n + r e a l t i m e o p t i m i z a t i o no fd y n a m i cs c h e d u l i n g ”t w op h a s e ss o l u t i o ns t r a t e g yi sf o r m u l a t e d ah y b r i d2 - o p t q e a i sp r e s e n t e dt os o l v et h ep r o b l e m ，o p t i m i z a t i o nb yi n t r o d u c i n go f2 一o p tl o c a lo p t i m i z a t i o n m e t h o dc o u l dr e d u c et h ec r o s so fc u s t o m e rs e q u e n c ew h i c hi m p r o v i n gt h ec o n v e r g e n c es p e e do f a l g o r i t h m ac o d i n gm e t h o d i sd e s i g n e d ，w h i c hi n t r o d u c e sac o m m o nc o d eo nt h eb a s i so fi n t e g e r c o d et oq u a n t u mb i t ss o l v i n gt h ec o n t r a d i c t i o nt h a tc a n n o tb es o l v e db yq u a n t u me v o l u t i o n a r y a l g o r i t h m f i n a l l y , s i m u l a t i n ga n da n a l y z i n gb a s e do nt h es t a n d a r dt e s tp r o b l e m sa n dc o m p a r i n g t h er e s u l t so ft h ew a yo fi n s e r t i n gt h en e i g h b o r s e x p e r i m e n t a lr e s u l t ss h o wt h a tt h ea c c u r a c yo f t h em o d e la n dt h ea l g o r i t h mf o rt h ev e h i c l er o u t i n gp r o b l e mo ft h ed y n a m i cd e m a n da n dh y b r i d 2 - o p tq u a n t u me v o l u t i o n a r ya l g o r i t h m sc a nm e e tt h er e q u i r e m e n to fr e a l - t i m es c h e d u l i n g 3 b a s e do nt h es t a t i cm o d e lo fr e p l e n i s h m e n ta l o n gr o u t e s ，t h ec u s t o m e r s d y n a m i cd e m a n d i si n t r o d u c e da n dad y n a m i cd e m a n dm u l t i - d e p o tv r pw i t hs t r a t e g yo fr e p l e n i s h m e n ta l o n gr o u t e i s p r o p o s e d ad e c o d em e t h o d i sd e s i g n e dt oc o n t r o lt h ev e h i c l er e p l e n i s h m e n t a na d a p t i m m u n eq e ai sp r o p o s e df o rt h ep r o b l e m ，i n t r u d i n gi m m u n eo p e r a t o rt oo p t i m i z es u b - r o u t e ， e x t r a c t i n gv a c c i n ef r o mt h ep r i o r ik n o w l e d g e ，a c c e l e r a t i n gt h ec o n v e r g e n c eo ft h ea l g o r i t h m ， i m p r o v i n gt h eq u a l i t yo fs o l u t i o n a n di no r d e rt oa d a p tt h eh i g hr e q u i r e m e n to fr e a l t i m e d y n a m i cs c h e d u l i n ga l g o r i t h m d u r i n gt h ep r o c e s so f v a c c i n ea na d a p t i v es e l e c t i o np r o b a b i l i t yi s d e s i g n e d , w h i c h c h a n g e dw i t ht h es i z eo f i n d i v i d u a lf i t n e s s f i n a l l y , m a k eas i m u l a t i o nt e s tt ot h e e x a m p l ea n da n a l y z et h ew a y o fv a c c i n a t i o n sa n dt h ei n f l u e n c eo fr e p l e n i s h m e n ta l o n gr o u t e s a n dc o m p a r i n gw i t ht h en e i g h b o r i n gi n s e r t i o nm e t h o d ，e x p e r i m e n tr e s u l t ss h o wt h a tt h es t r a t e g y t oa d a p tt oa l o n gt h er e p l e n i s h m e n td y n a m i cv e h i c l er o u t i n gp r o b l e m ，t h ep r o p o s e da l g o r i t h m c a l le f f e c t i v e l ys a t i s f yt h er e q u i r e m e n to fr e a l t i m es c h e d u l i n gp r o b l e m a n da n a l y s i so fe x p e r i m e n t ，a n a l y s e st h ei n f l u e n c eo fp a r a m e t e r st ot h er e s u l t s ，c h o o s e p a r a m e t e r sw h i c hi s s u i t a b l et ot h ep r o b l e mo fs t a n d a r dt e s t ，s i m u l m i o nr e s u l t ss h o wt h e a c c u r a c yo ft h em o d e la n dt h ee f f e c t i v e n e s so fm g o r i t h r nf o rs o l v i ngo fm u l t i o b j e c t i v ed y n a m i c p r o b l e m s 5 a n a l y z e dl a r sm hm o d e li nw h i c ht h er a n d o m n u m b e ro fc u s t o m e r si sm a d ed e t e r m i n e d v a l u e ，a n dh y p o t h e s i z et h a ta tt h em o m e n ttr a n d o md e m a n di n f o r m a t i o nb e c o m ek n o w n i nt h i s c h a p t e rr e s e a r c hi nt i m etc u s t o m e rd e m a n dc a nb ei d e n t i f i e dw h e t h e rt h e r e ，b u tt h ed e m a n di sa r a n d o mv a r i a b l eo fp o i s s o nd i s t r i b u t i o n b a s e do nm o d e lo fm hl a r s ，c o n s i d e r i n gt h e m u l t i - d e p o ta n do p e nc h a r a c t e r i s t i c s ，t w op h a s es t o c h a s t i cp r o g r a m m i n gr e s o u r c em o d e l sa r e e s t a b l i s h e d a na d a p t i v ei n l n l u n ee v o l u t i o n a r ya l g o r i t h mi sd e s i g n e df o rt h ep r o b l e m f i n a l l y , s i m u l a t i o ne x a m p l e si st e s t e d , a n a l y s e st h eo p t i m i z a t i o nr e s u l t so fd i f f e r e n tv a l u e so ft h e p a r a m e t e r s 兄，a n dc o m p a r e dw i t hb a s i cq u a n t u me v o l u t i o n a r ya l g o r i t h ma n dt h en e i g h b o r i n g i n s e r t i o nm e t h o d , e x p e r i m e n t a lr e s u l t ss h o wt h a tt h i sm e t h o dc a ne f f e c t i v e l ys o l v et h er a n d o m d e m a n do fd y n a m i cv e h i c l er o u t i n gp r o b l e m 6 o nt h eb a s i so fa b o v et h e o r yr e s e a r c hw o r k ，as i m u l a t i o np l a t f o r mo fd y n a m i cd e m a n d v e h i c l er o u t i n gp r o b l e mi sm a d e t h i sp l a t f o r mi n t e g r a t e st h eh y b r i dq u a n t u me v o l m i o n a r y a l g o r i t h mo fd y n a m i cd e m a n dv e h i c l er o u t i n gp r o b l e mf r o me v e r yc h a p t e ra b o v e ，w h i c hv e r i f i e s t h ef e a s i b i l i t yo ft h ep r o p o s e dm e t h o d a n dc o m b i n et h i sa l g o r i t h ml i b r a r yt og i sp l a t f o r m , w h i c hp r o c e s sd y n a m i ci n f o r m a t i o n s h o wt h es c h e d u l i n gr e s u l t so fd y n a m i cd e m a n dv e h i c l e r o u t i n gp r o b l e mo ng i sp l a t f o r m , e m b e di n t ow e bt h a tc o u l db er e v e a l e dt h r o u g hb r o w s e r 7 c o n c l u s i o na n dp r o s p e c t s u m m a r i z et h em a i nr e s e a r c hw o r ko ft h ew h o l ep a p e ra n d p r o s p e c tt h ef u r t h e rr e s e a r c hw o r ko fv e h i c l er o u t i n gp r o b l e m k e yw o r d s ：l o g i s t i c sd i s t r i b u t i o n ， f l e e tv e h i c l e ，m u l t i d e p o t ，m u l t i 一0 博十学位论文 瓦 d i 瓦 c ：f u 伊 n d 车辆的载重 客户的需求 发车的固定费用 客户间的运行成本 车辆在客户间的运输量 虚拟配送中心数量 新派车数量 最小化 。 目标函数 种群规模 问题规模 量子染色体 量子旋转门 旋转角大小 迭代次数 算法复杂度 用符号 礞，卵 车辆路径问题的决策变量 a 选择概率 适应度函数 时间窗 时间窗 到达客户f 的时间 客户f 到的运行时间 等待时间 在客户处的服务时间 客户的满意度 最优解集 构造集 非支配解集 p 支配q 第f 代每一维网格的数量 随机数 泊松分布参数 ，舱 厶 包 9 钐 - 二 ， ，l，l 冗 e 勺 w 岛 以 ， 吆 日 丁 皿 z 尸 甜 g 玎 协 卜 詹， 甄 q m p 矿 m 力 浙江工业大学博士学位论文 2 2 1 问题的描述2 4 2 2 2 数学模型的建立- 一2 5 2 2 3 多车型分配策略- 2 7 - 2 3 动态需求多车型v r p 的混合q e a 求解2 8 2 3 1 量子进化算法的原理与研究进展2 8 2 3 2 问题的求解策略3 2 2 3 3 混合量子进化算法求解动态需求多车型v r p 3 3 2 3 4 混合量子进化算法的计算复杂性分析3 6 2 3 5 量子进化算法收敛性证明- 3 7 2 4 实验结果与分析3 8 2 4 1 算例一3 8 2 4 2 标准实例测试一4 0 2 4 3 算法的比较分析- 4 3 - 2 5 本章小结一4 3 - 第3 章动态需求多配送中，t l , v r p 模型及其q e a 优化 - 4 5 3 1 弓l 言4 5 3 2 动态需求多配送中心冲数学规划模型- 4 6 3 2 1沿途补货策略4 6 3 2 2 数学规划模型4 7 3 3 动态需求多配送中心冲的自适应免疫q e a 求解5 1 3 3 1自适应免疫量子进化算法51 3 3 2 自适应免疫量子进化算法复杂度分析5 4 3 4 实验结果与分析5 4 - 3 4 1 实例测试5 4 3 4 2 优化性能实验及分析5 8 3 4 3 疫苗接种方式分析6 2 3 4 4 沿途补货策略分析6 3 3 4 5 算法的比较分析6 3 浙江工业大学博士学位论文 3 5 本章小结 第4 章多目标动态需求v r p 模型及其多目标q e a 优化 4 1 引言。 4 2 基于客户满意度的多目标动态需求冲的数学规划模型6 6 - 4 2 1 时间窗- 6 6 4 2 2 模糊时间窗6 6 4 2 3 数学规划模型6 7 - 4 3 多目标量子进化算法求解7 1 - 4 3 1 多目标优化问题7 l - 4 3 2 多目标量子进化算法设计- 7 3 4 3 3 算法复杂度分析7 7 - 4 4 实验分析7 7 4 4 1 实验数据7 7 4 4 2 算法参数讨论7 8 4 4 3 算例测试7 8 4 4 4 算法比较分析8 2 4 5 本章小结8 3 第5 章动态随机需求v r p 模型及其q e a 优化 5 1 引言8 5 5 2 动态随机需求嫂的基于补偿策略的随机规划模型8 6 5 2 1问题描述8 6 5 2 2 预优化调度阶段模型8 8 5 2 3 实时优化调度阶段模型9 0 5 3 动态随机需求v i 冲求解9 2 5 4 实验结果与分析，9 2 5 4 1实例测试9 2 5 4 2 优化性能实验及分析9 6 5 4 3 算法的比较分析9 9 5 5 本章小结1 0 0 第6 章动态需求车辆调度仿真平台 6 1 弓l 言1 0 1 6 2 仿真平台的框架1 0 1 6 2 1 仿真环境101 6 2 2 总体框架1 0 2 6 3 仿真平台各功能的实现1 0 4 6 3 1 实验仿真半台一1 0 4 6 3 2 实例应用1 0 7 6 4 本章小结1 1 2 第7 章结论与展望。 7 1 结论11 3 7 2 展望1 1 4 参考文献 致谢 攻读博士学位期间参加科研项目和取得成果。 。1 1 7 - 1 2 7 - 1 2 9 息处理等 “第三利 润源泉 的物流对经济活动的影响日益明显，越来越得到了人们的重视，成为当前“最重 要的竞争领域”。近年来，世界现代物流业呈稳步增长态势，欧洲、美国、日本成为当前 全球范围内的重要物流基地。中国物流行业起步较晚，随着国民经济的飞速发展，物流业 的市场需求持续扩大。进入2 1 世纪以来，在国家继续加强和改善宏观调控政策的影响下， 中国物流行业保持较快增长速度，物流体系不断完善，行业运行日益成熟和规范。 物流配送是物流系统中的核心功能，是直接与消费者相关联的一个重要环节，配送功 能完成的质量好坏及其达到的服务水平，会直接影响到客户对整个物流服务的满意程度。 物流术语【2 】中对配送的定义为：在经济合理区域范围内，根据用户要求对物品进行拣 选、加工、包装、分割、组配等作业并按时送达指定地点的物流活动。配送的核心部分是 配送车辆的集货、货物分拣及送货过程，而车辆配送路径的合理优化，对于整个物流运输 速度、成本、效益影响至关重要。根据中国仓储协会对1 4 6 个企业的调查显示，用于运输 的费用占整个物流费用的比例分别为：在生产企业原料物流中占5 8 ，在生产企业成品物 流中占7 3 ，在商业物流中占5 2 。 作为物流配送系统中关键的一环，物流配送车辆路径问题( 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 3 】于1 9 5 9 年首先提出 的，近五十年来，一直受到运筹学、物流科学、计算机应用等学科的专家极大重视，成为 运筹学与组合优化领域的前沿与研究热点问题，各国学者对其理论和应用进行了大量的研 究工作，取得了许多研究成果，使v r p 的研究成为“最近半个世纪运筹学领域是成功的研 究之一【4 】。 目前绝大多数关于v r p 的研究一般假定在路径规划之前，所有的信息如顾客的地理位 置、顾客的请求服务时间、顾客请求的服务量、现场的服务时间、旅行时间等都是已知的， 并且这些信息均与时间无关，不随时间推移而变化。在这样的假定下，安排的路径也是相 对固定的，这类v r p 被称为静态v r p 。但是，客观世界存在着大量的不确定性，反映在 浙江工业大学博十学位论文 v r p 中，主要有不确定的顾客需求、不确定的顾客需求时间、线路制定者决策的主观偏好 性、交通拥挤、车辆故障等。这些不确定信息随着时间的推移出现，需要动态改变车辆的 运行路线，对已安排好的车辆路径进行及时调整。这时，静态v r p 的理论和方法不再具有 处理这些问题的能力，需要研究一整套新的求解动态车辆路径问题( d y n a m i cv e h i c l e r o u t i n gp r o b l e m ，d v r p ) 的理论和方法。由此可见，动态v r p 更贴近实际生产和生活