（机械设计及理论专业论文）配送线路划分与电子排单系统建模与算法研究.pdf

摘要 配送线路划分与电子排单系统建模与算法研究 摘要 目前物流配送中心的末端配送主要采取集中统一的送货方式，这种 配送模式必须综合考虑配送网点订货情况、物流配送中心规模、道路拥 挤度、道路整改等因素对配送效能的影响。本文从衡量配送线路实际工 作量大小的“广义工作量 指标入手，在地理信息系统( g e o g r a p h y i n f o r m a t i o ns y s t e m ，g i s ) 和企业网络数据库系统的支持下，以提高网点 客户满意度和降低配送成本为主要目标，进行物流配送中心末端配送线 路优化课题的研究工作。 研究工作主要包括配送线路广义工作量和送货经济距离概念的提出 和应用、配送线路的划分、单车线路优化和电子排单系统的可视化输出 等内容。 。 首先，本文提出了衡量配送线路工作量大小的“广义工作量的概 念。广义工作量是配送中心进行配送线路区域划分的一项重要经济指标， 它与送货经济距离s 、送货量d 、零售网点数量n 等因素相关，它要求 不同配送线路之间广义工作量大小基本均衡，以使所有线路车辆送货员 或驾驶员在其配送过程中更好地为客户提供满意的服务。在体现广义工 作量大小的影响因素中，客户订货量( 即配送中心送货量) 、送货经济距 离、单车线路的网点客户数量都是物流配送中心送货线路划分的重要因 素。送货经济距离是指在考虑路段长短、拥挤程度、车道数量、路面类 型等因素基础上，实现两点间配送时间最短的车辆行驶距离值。广义工 上海交通大学博上学位论文 作量概念的提出是进行配送线路划分的先决条件，也是求解配送成本与 网点客户服务水平之间均衡点的前提。 其次，在企业配送网络g i s 支持下，以广义工作量均衡和车辆容载 量为目标值，对所有配送网点进行配送线路的划分，把一个包含几千个 配送网点的难点问题，转化为有限个实际可控、可观测的子系统进行求 解。本文采用最邻近算法求得物流配送中心送货线路划分的初始解，然 后采用插入算法对线路划分初始解进行改进，在g i s 平台上的仿真结果 表明了改进后线路划分方案的合理性。为了使划分结果进一步符合物流 企业的实际应用，本文在常规最邻近算法的基础上，提出了二阶最邻近 算法的内涵，证明了该算法每次选择下一个新网点时，其与当前线路上 已有的两个次新网点所组成的网点子集都是聚集程度最高的，由此得到 的配送线路中的客户网点聚集程度，要高于常规一阶最邻近算法所得到 的线路，这为下一阶段的单车线路优化提供了较好的基础。 本文在配送线路划分的基础上，在g i s 平台上进行了单车配送线路 的优化调度，即综合考虑单车线路每次送货的网点数量、订货数量、道 路拥挤度等因素的变化，求解出每日每次每条送货车辆的行驶路线安排， 实现物流配送中心送货车辆的每日每次动态电子排单的可视化输出。 论文在对国内外单车线路优化问题大量调研的基础上，提出了自己 独特的、适合国内物流配送中心末端配送的单车线路求解方案t 先用最 节约插值法构建问题的初始可行解，生成初始解路径集合；然后采用混 合遗传算法的全局搜索策略优化最节约插值法得到的初始解，进而得到 一个相对满意的解。由于传统遗传算法全局搜索能力很强但局部搜索能 力不足，爬山算法则具有很强的局部搜索能力，是一种常用的寻找局部 最优解的方法，本文将二者相结合，以期取长补短，实践应用表明这种 h 摘要 策略可大大提高配送线路的优化性能。为了使每日每次单车配送线路更 加符合实际电子排单和道路交通状况，本文以杭州市某段景区为例，从 城市交通网络中道路路段间的地理关联关系入手，在最短路径算法 ( d 佻s t r a ) 基础上，考虑道路畅通度系数，探讨不同配送时间段道路畅通度 随机因素对单车线路配送效能的影响，分析结果使送货经济距离数据库 的建立和应用更加符合配送线路的实际运营状况。 上述研究以杭州市区卷烟配送网络为数据获取源和应用案例，分别 建立物流配送中心配送线路划分和单车线路优化两个阶段的系统模型， 采用多种算法( 或其混合) 进行求解。由于大规模配送网络车辆路线问 题是一个典型的n p 难点，随着网点数量的增加，系统计算的复杂度无论 在空间上还是在时间上都将成指数级增长，这对于规模较大的即时配送 调度问题的优化计算是难以接受的。据我们调研，物流配送企业对网点 客户订单的有效反应要求很高，节拍很短，有时甚至不允许电脑计算时 间过长，因此有必要进行本课题的系统建模与算法研究，解决物流配送 中心末端配送的复杂配送网络求解时间过长、计算工作量过高的现实问 题。 本文采用m a p l n f o 、v b 、s q l s e r v e r2 0 0 0 等开发技术将上述模型与 算法集成到企业配送网络g i s 环境下，完成物流配送中心末端配送系统 的设计与实现。通过与g i s 系统的集成，将线路划分结果与单车线路电 子排单结果，直观地输出在电子地图上，从而实现物流配送中心末端配 送车辆路线问题的可视化输出控制。研究成果在烟草、百货、医药、油 料等企业的物流配送中心末端集中配送领域，具有普适性和推广应用前 蔑 乐。 本文研究内容的创新性主要体现在以下几个方面：( 1 ) 在定义物流 i i i 上海交通大学博士学位论文 配送中心送货线路“广义工作量 和“送货经济距离”概念的基础上， 根据不同配送线路工作量均衡和送货经济距离最短的多目标决策问题求 解期望，采用改进后的二阶最邻近算法和插入法进行送货线路划分，从 而兼顾了配送成本降低与客户满意度提高两者之问的“二律背反 关系； ( 2 ) 单车线路优化应用了标准遗传算法与爬山算法相结合的混合遗传算 法，在其中的同化操作中，首次提出并应用能综合体现单车线路网点数n 、 送货量d 和总经济距离s 三个指标的个体适应度函数，作为判断单车线 路同化操作优劣的尺度标准；( 3 ) 根据道路拥挤度的随机变化，确定单 车配送线路任意两个网点间不同时间段的送货经济距离，及时调整配送 计划和配送路线，采用概率模型替代传统确定性模型；( 4 ) 研究成果已 应用于杭烟物流配送中心配送网络，取得了明显的应用效果，弥补了国 内车辆线路问题研究大多停留在理论层次的不足。 关键词：物流配送中心，末端配送，线路划分，单车线路，g i s ，模型与 算法 i v a b s t r a c t r e s e a r c ho nm o d e l sa n da l g o m t h m so f d i s t r i b u t i v e l i n ed i v i s i o na n ds i n g l e r o u t i n gp r ob l e m a b s t r a c t a tp r e s e n t ，t h ee n dd i s t r i b u t i o no fl o g i s t i c sa n dd i s t r i b u t i o nc e n t e rm a i n l y t a k e st h ec e n t r a l i z e da n du n i f i e dw a yt od e l i v e rg o o d s t h i sd e l i v e r ym o d e m u s tc o n s i d e rm a n yf a c t o r si n t e g r a l l y , s u c ha sc li e n td e m a n d s ，t h ew o r k i n g c a p a b i l i t y o fl o g i s t i c sa n dd i s t r i b u t i o nc e n t e r , r o a dh u s t l ed e g r e e ，s t r e e t c h a n g i n g ，e t c ，w h i c hi n f l u e n c eo nd i s t r i b u t i o ne f f i c i e n c y b e g i nw i t hu s i n gt h e g e n e r a l i z e dw o r k l o a d a st h em e a s u r eo fa c t u a lw o r k l o a do f o n ed i s t r i b u t i o n r o u t e ，t h et h e s i sf o c u s e so no p t i m i z i n gt h ee n dd i s t r i b u t i o n - l i n eo fl o g i s t i c s a n dd i s t r i b u t i o nc e n t e ru n d e rt h es u p p o f lo ft h eg i s ( g e o g r a p h yi n f o r m a t i o n s y s t e m ) a n de n t e r p r i s e sn e t w o r kd a t ab a s es y s t e m ，r e g a r d i n gt om e e tt h e d e m a n d so fc u s t o m e r sa n dr e d u c i n gt h ec o s to fd i s t r i b u t i o n t h es t u d yc a nb ed i v i d e di n t of o u rs t a g e s ：f i r s t ，t h e c o n c e p t s o f g e n e r a l i z e dw o r k l o a d o fs i n g l e d i s t r i b u t i o nl i n ea n dt h ee c o n o m i c a l d i s t a n c ea r ep u tf o r w a r da n da p p l i e d s e c o n d ，t h ed i s t r i b u t i v el i n e sa r e d i v i d e d t h i r d ，t h eo p t i m i z a t i o no fs i n g l er o u t i n gp r o b l e mi ss o l v e d f i n a l l y ， t h ev i s i b l eo u t p u t so fv a r i a b l ev e h i c l es c h e d u l e sa r eg i v e n t h ec o n c e p to f g e n e r a l i z e dw o r k l o a d t om e a s u r ew o r k l o a do fs i n g l e d i s t r i b u t i o nl i n ei sp u tf o r w a r di nt h i st h e s i s t h eg e n e r a l i z e dw o r k l o a di sa n i m p o r t a n te c o n o m i cc r i t e r i o nt ot h ed i s t r i b u t i o nr o u t ed i v i s i o no fd i s t r i b u t i o n c e n t e ri nad i s t r i c t g e n e r a l i z e dw o r k l o a d ( mo fas i n g l ed i s t r i b u t i o nl i n eh a s ab e a r i n go ne c o n o m i c a ld e l i v e r yd i s t a n c e ( s ) ，q u a n t i t yo fd e l i v e r y ( d ) a n d v 上海交通大学博士学位论文 q u a n t i t yo fc u s t o m e r s ( i td e m a n d st h eg e n e r a l i z e dw o r k l o a db e t w e e n d i f f e r e n td i s t r i b u t i o nr o u t e st ob ea p p r o x i m a t e l ye q u a l a n dm a k e sa l lv e h i c l e d e l i v e r st oo f f e rt h ec u s t o m e r sm o r es a t i s f i e ds e r v i c e o fa l lt h ef a c t o r so f g e n e r a l i z e dw o r k l o a d ，t h ec u s t o m e r so r d e rq u a n t i t y ( q u a n t i t yo fd e l i v e r y ) ， t h ee c o n o m i c a ld i s t a n c eo fd e l i v e r y ，t h eq u a n t i t yo fc u s t o m e r sa r ea l lc e r t a i n f a c t o r s e c o n o m i c a ld i s t a n c eo fd e l i v e r yi st h es h o r t e s tp h y s i c a ld i s t a n c eo f t w oc u s t o m e r s i ti st h ev a l u eo fv e h i c l ed e l i v e r si ns h o r t e s td i s t a n c ew h e n c o n c e r n i n gf a c t o r ss u c ha st h er o a dl e n g t h ，t h eh u s t l ed e g r e e ，t h ed r i v e w a y q u a n t i t y ，a n dt h et y p eo ft h er o a d t h ec o n c e p to fg e n e r a l i z e dw o r k l o a di st h e p r e c o n d i t i o no fd i s t r i b u t i v el i n ed i v i s i o na n dt h ep r e m i s et ob a l a n c eo ft h e l o g i s t i c sc o s ta n dc u s t o m e rs e r v i c e s e c o n d l y , u n d e rt h es u p p o r to fd i s t r i b u t i o nn e t w o r ka n di t sg i s ，a n d t a k i n ge q u i l i b r i u mo f g e n e r a l i z e dw o r k l o a d a n dt h el i m i t a t i o no fv e h i c l e s c a p a c i t ya s t h e t a r g e t s ，t h et h e o r e t i c a l l y u n s o l v a b l en pd i f f i c u l tq u e s t i o n w h i c hc o n t a i n st h o u s a n d so fd i s t r i b u t i o nn e t si st r a n s f o r m e dt ol i m i t e d s u b s y s t e m sw h i c ha r ec o n t r o l l a b l ea n dc a nb eo b s e r v e d i nt h i st h e s i s ，w eg e t t h ei n i t i a ls o l u t i o no fd i s t r i b u t i v el i n ed i v i s i o no fl o g i s t i c sa n dd i s t r i b u t i o n c e n t e rb yn e a r e s t - n e i g h b o rm e t h o d t h e ni m p r o v ei tb yi n s e r t i o na l g o r i t h m t h es i m u l a t i o nr e s u l t sb a s e do nt h eg i sh a v ep r o v e dt h er a t i o n a l i t yo ft h e i m p r o v e dd i s t r i b u t i o nr o u t e t om a k et h ed i s t r i b u t i o nr e s u l t sm o r es u i t a b l et o t h el o g i s t i c sc o m p a n y sp r a c t i c a la p p l i c a t i o n ，w ep u tf o r w a r dt h et h e o r e ma n d i t sc e r t i f i c a t i o no ft h es e c o n do r d e rn e a r e s t n e i g h b o rm e t h o dw h i c hi st h e i m p r o v e m e n t o fg e n e r a ln e a r e s t n e i g h b o rm e t h o d w h e nc h o o s ean e wc l i e n t ， t h es u b s e to ft h ec l i e n tf o r m e db yt w oa l r e a d ye x i s t i n gn e a r e s tn e wo n ei n c u r r e n tl i n eh a st h eh i g h e s tl e v e lo fa g g r e g a t i o n t h ec u s t o m e ra g g r e g a t i o n s l e v e lo fd i s t r i b u t i o nr o u t et h a tw eg o ti s h i g h e r t h a nt h a t b y t h e n e a r e s t n e i g h b o rm e t h o d ，a n dp r o v i d e sag o o df o u n d a t i o nf o rn e x ts t a g eo f t h eo p t i m i z a t i o no fs i n g l er o u t i n gp r o b l e m b a s e do nt h ed i s t r i b u t i v er o u t ed i v i s i o n ，t h eo p t i m i z a t i o no fs i n g l e v i a b s t r a c t r o u t i n gs c h e d u l i n gi sp e r f o r m e d t h eo p t i m i z a t i o ni n t e g r a l l yc o n s i d e r st h e d i f f e r e n c eo fc u s t o m e rq u a n t i t y , t h ed i f f e r e n c eo fc u s t o m e rd e m a n d s ，t h er o a d c o n g e s t i o n ，a n ds oo no fs i n g l ev e h i c l er o u t eo fe a c hd e l i v e r i tg e t st h e v e h i c l er o u t ea r r a n g e m e n ta n dt h ev i s i b l eo u t p u to fa l lv e h i c l es c h e d u l i n gi n t h el o g i s t i c sa n dd i s t r i b u t i o nc e n t e ri nr e a lt i m e i nt h i st h e s i s ，w eh a v ed o n eal o to fr e s e a r c h e so ns o l v i n gd y n a m i c n e t w o r km o d e lw h i c ha r et h eo p t i m i z a t i o np r o b l e m so fs i n g l e v e h i c l er o u t e ， a n dh a dc o m eu pw i t hau n i q u es o l u t i o no fs i n g l e v e h i c l ed i s t r i b u t i o nr o u t e ： f i r s t ，w eu s ei n s e r t i o na l g o r i t h mt ob u i l di n i t i a lf e a s i b l es o l u t i o n a n da n i n i t i a lp a t hs e ti sc r e a t e d ；t h e n ，w eu s et h eo v e r a l ls e a r c hs t r a t e g yo fh y b r i d g e n e t i ca l g o r i t h mt oo p t i m i z et h ei n i t i a ls o l u t i o n f i n a l l y , w eg e tas a t i s f i e d s o l u t i o nt h a ti so p t i m a lo rs u b - o p t i m a l i nt h et r a d i t i o n a lg e n e t i ca l g o r i t h m ， t h eg l o b a ls e a r c h c a p a b i l i t yi ss t r o n gb u tt h el o c a ls e a r c hc a p a b i l i t yi sn o t g o o de n o u g h h o w e v e r , t h eh i l l c l i m ba l g o r i t h mh a sas t r o n gl o c a ls e a r c h c a p a b i l i t yt h a ti sac o m m o ns e a r c ha l g o r i t h mf o ro p t i m i z a t i o np r o b l e m t h i s t h e s i sc o m b i n e sb o t ho ft h e mt ou t i l i z et h e a d v a n t a g e so fe a c ho n e t h e a p p l i c a t i o n s s h o wt h a tt h e s t r a t e g yc a ng r e a t l yi m p r o v et h eo p t i m i z a t i o n p e r f o r m a n c e o fd i s t r i b u t i o nr o u t e t om a k ee a c ht i m ea n d e v e r yd a y s s i n g l e - v e h i c l er o u t em o r ef i t t oa c t u a ls t a t u so fv i s i b l eo u t p u to f v e h i c l e s c h e d u l i n g ，t h eo p t i m i z i n gp a t ha l g o r i t h mb r o u g h tf o r w a r di nt h i st h e s i si s b a s e do nt h ea c t u a ls i t u a t i o no fd i s t r i b u t i o ns y s t e mi no n eo fs c e n i cs p o ti n h a n g z h o uc i t y f r o mt h ec i t y sr o a dt r a n s p o r tn e t w o r ki nt h eg e o g r a p h i c r e l e v a n c er e l a t i o n s h i p ，w ed i s c u s st h ea f f e c to fu n i m p e d e ds i t u a t i o no ft h e r o a d sa sr a n d o mf a c t o r so nt h ee f f e c t i v e n e s so fs i n g l e v e h i c l ed i s t r i b u t i o n r o u t eu s i n gt h es h o r t e s tp a t ha l g o r i t h m ( d i j k s t r a ) t h es i m u l a t i o nr e s u l t s d e m o n s t r a t et h ea c c u r a t e n e s so ft h em o d e la n dt h ei m p l e m e n t a t i o n t h er e s e a r c ho ft h et h e s i si sb a s e do nt h ei n f o r m a t i o na n da p p l i c a t i o nc a s e o ft o b a c c on e t w o r ki n h a n g z h o uc i t y b yi n v e s t i g a t i n g ，w ec r e a t e dt w o d i f f e r e n ts y s t e mm o d e l s o n ei sd i v i s i o no fd i s t r i b u t i o nr o u t eo fl o g i s t i c sa n d l d i s t r i b u t i o nc e n t e r a n dt h eo t h e ri s o p t i m i z a t i o no fs i n g l ev e h i c l er o u t e i t s o l v e st h ep r o b l e m sb yn e a r e s t n e i g h b o rm e t h o d s ( o n e t w oo r d e r ) ，i n s e r t i o n a l g o r i t h m ，h y b r i dg a , h i l l - c l i m ba l g o r i t h ma n ds oo n t h ep r o b l e mo ft h e v e h i c l er o u t eo fl a r g ed i s t r i b u t i o nn e t w o r ki sat y p i c a ln p p r o b l e m a l o n g w i t hi n c r e a s i n go ft h ec u s t o m e r sn u m b e r , t h e c o m p l e x i t ya n dt h ev o l u m eo f t h es y s t e mi n c r e a s e se x p o n e n t i a l l ye i t h e ri ns p a c eo ri nt i m e i ti sd i f f i c u l tt o a c c e p tf o ro p t i m i z a t i o no fl a r g e s c a l ed i s t r i b u t i o na n ds c h e d u l i n gp r o b l e m a c c o r d i n gt oo u ri n v e s t i g a t i o n ，d i s t r i b u t i o nc o m p a n i e sm u s tb ee f f i c i e n t l y r e s p o n s et o c l i e n to r d e r t h e ym u s tb er e a d yi nas h o r tt i m e s o m et i m e s e v e nt h ec o m p u t e r sc a l c u l a t i o nt i m ec a n tb et o ol o n g s oi ti s n e c e s s a r yi n t h et h e s i st or e s e a r c ho nm o d e l sa n da l g o r i t h m so fd i s t r i b u t i v el i n e d i v i s i o n a n ds i n g l er o u t i n gp r o b l e m ，a n dt ow o r ko u tt h ep r o b l e mt h a t c a l c u l a t i o n c o m p l e x i t yi st o oh i g h i no r d e rt oc o m p l e t et h ed e s i g na n di m p l e m e n t a t i o no ft h es y s t e m ，w e i n t e g r a t et h ea b o v em o d e l sa n da l g o r i t h m si n t ot h eg i s b a s e dd i s t r i b u t i o n n e t w o r k ，u s i n gm a p l n f o ，v b ，s q ls e r v e r2 0 0 0a n ds oo n t h r o u g ht h e i n t e g r a t i o n ，t h er e s u l t so fr o u t e d i v i s i o na n dt h ev i s i b l eo u t p u t so fv e h i c l e s c h e d u l i n gc a nb es e e nd i r e c t l yo nt h ee l e c t r o n i cm a p r e s e a r c hr e s u l t sh a v e g e n e r a ls u i t a b l e n e s si nt h ef i e l d so fc o n c e n t r a t i v e d e l i v e r y , s u c ha st h e l o g i s t i c s a n dd i s t r i b u t i o n e n t e r p r i s e s o f t o b a c c o ，g e n e r a lm e r c h a n d i s e ， m e d i c i n ea n do i la n ds oo n t h em a j o rw o r k sa n dc o n t r i b u t i o n so f t h i sd i s s e r t a t i o na r ea sf o l l o w s ：( 1 ) o nt h eb a s i so fd e f i n i n g “g e n e r a l i z e dw o r k l o a d a n d “e c o n o m i c a ld i s t a n c eo f d e l i v e r y ”，t h em o d i f i e ds e c o n do r d e rn e a r e s t n e i g h b o rm e t h o da n di n s e r t i o n a l g o r i t h ma r ep r o p o s e df o rs o l v i n gt h ep r o b l e mo fd i s t r i b u t i v el i n ed i v i s i o n ， w h i c hi sam u l t i o b j e c t i v ed e c i s i o n p r o b l e m a sar e s u l t ，t h ed e m a n d so f c u s t o m e r sa sw e l la st h ec o s to fd i s t r i b u t i o na r eb o t hg i v e na t t e n t i o n ( 2 ) a n h y b r i d o f g e n e t i ca l g o r i t h ma n dh i l l c l i m ba l g o r i t h mi s e m p l o y e df o r o p t i m i z i n gt h es i n g l e r o u t i n gs c h e d u l i n g af i t n e s sf u n c t i o n ( f ) w h i c h v i i i a b s t r a c t m e a s u r e st h en u m b e ro fc u s t o m e r s ( ，t h eq u a n t i t yo fd e l i v e r y ( d ) ，a n dt h e t o t a le c o n o m i c a ld i s t a n c e ( s ) i sp r e s e n t e d t h i sf i t n e s sf u n c t i o ns e r v e sa sa c r i t e r i ao ft h es i n g l er o u t i n gs c h e d u l i n g ( f = 1 0 0 0 木n 术d s ) ( 3 ) t h ee c o n o m i c a l d i s t a n c eo fa s i n g l er o u t i n gs c h e d u l i n gi n a g i v e nt i m e i sd e t e r m i n e d a c c o r d i n gt ot h es i t u a t i o no ft r a f f i cj a m a n dt h ed i s t r i b u t i o ns c h e d u l i n ga n d d i s t r i b u t i o nl i n ea r ea d j u s t e da c c o r d i n g l y f u r t h e rm o r e ，a p r o b a b i l i s t i cm o d e l i su s e di n s t e a do fad e t e r m i n i s t i co n e ( 4 ) t h er e s e a r c ho ft h et h e s i sh a sb e e n a p p l i e dt ot h et o b a c c on e t w o r ki nh a n g z h o uc i t yf i r s t l y t h ee f f e c t i v e n e s sa n d a p p l i c a b i l i t ya r ed e m o n s t r a t e d k e yw o r d s ：l o g i s t i c sa n dd i s t r i b u t i o n c e n t e r , t h e e n dd i s t r i b u t i o n ， d i s t r i b u t i v el i n e d i v i s i o n ，s i n g l e r o u t i n gp r o b l e m ，g e o g r a p h i c i n f o r m a t i o ns y s t e m ，m o d e la n da l g o r i t h m i x 符口说明 ( 按符号出现的顺序说明) w s d n c i j q x i j k y k i z f ( n ) ，g ( n ) t a ( n ) n p s ( i ，j ) d ( i ，j ) p 1 p 2 p 3 e v n v c 啦 符号说明 广义工作量( 无量纲) 送货经济距离( k m ) 送货量( 件) 网点数量( 个) 网点i 到网点j 的运输成本 任务i 的货运量 车辆容载量 网点i 到j 由车辆k 配送 网点i 由车辆k 配送 目标函数值 定义在正整数上的正实值函数 算法a 规模为n 的时间复杂度 非确定型的多项式算法 网点i 至网点j 的距离节约值 网点i 至网点i 的距离 行驶距离权值( 1 k m ) 送货量权值( 1 肿) 网点数权值( 1 个) 配送线路工作量预先设定值( 无量纲) 不同线路工作量允许误差 车辆的编号 总网点数目 总配送车辆数目 配送中心o 到网点i 的距离 上海交通大学博士学位论文 c i j d i d v 肌 a n 1 ，a n + 1 d i s ( a ，a n ) s 0 ) ，s ( 2 ) e lsl f p k n 0 c h l l 丫 q n 7 s p c p m g e n g e n h c p o p s i z e g r o u p s i z e 点i 到点j 的距离 网点i 的需求量 第v 辆车的最大车容量 第v 辆车的工作量 网点a 。的上游网点和下游网点 网点a 到网点a n 之间的最小送货经济距离 网点a n 的一阶经济距离和二阶经济距离 网点及物流配送中心之间道路的集合( 弧集) 集合s 中含图g 的顶点个数 个体适应度函数值 个体中所包含的染色体基因( 网点) 的数量 道路通行系数 车道的理论通行能力( 辆h ) 单向道路实际通行能力 饱和连续车流的平均车头时距 连续车流的车头间距( m ) 自行车影响修正系数 车道宽度影响修正系数 车道数修正系数 交叉口影响修正系数 交叉概率 变异概率 遗传算法迭代次数 执行爬山算子代数 染色体( 个体) 所含基因数( 网点数) 群体规模( 染色体个数) v 上海交通大学 学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立 进行研究工作所取得的成果。除文中已经注明引用的内容外，。本论 文不包含任何其他个人或集体已经发表或撰写过的作品成果。对本 文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。 本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名： 醐：1 砂月多日 上海交通大学 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同 意学校保留并向国家有关n i - j 或机构送交论文的复印件和电子版， 允许论文被查阅和借阅。本人授权上海交通大学可以将本学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印 或扫描等复制手段保存和汇编本学位论文。 保密口，在一年解密后适用本授权书。 本学位论文属于 不保密 ( 请在以匕方框内打“”) 醐硼r ；e l ， 饥 杪 二 沌 三 名 e 麟 佯 币 唧 眇 岫 獬岬 第一章绪论 第一章绪论 1 1 基于工作量均衡理论企业送货车辆路线问题的提出 1 1 1 物流配送企业末端配送面临的问题 随着经济全球化趋势的加强，现代信息技术、供应链管理技术的飞速发展，物流 作为一种实现经济高效运行、融合高新技术为一体的先进管理技术与组织方式，通过 计划、实施、控制与协调等手段对运输、仓储、装卸、包装、配送、流通加工、信息 各环节的系统