（管理科学与工程专业论文）引入顾客满意度求解车辆优化调度问题.pdf

摘要 在经济全球化和信息化的浪潮中，现代的物流业已经从为社会提供传统的运 输服务，扩展到以现代科技、管理和信息技术为支柱的综合物流系统。随着信息 技术的发展，物流调度的优化问题已成为研究的一个热点问题。在过去4 0 年间， 以路线选择为背景的车辆优化调度问题得到了广泛的研究，取得丰富的研究成果。 在大力发展物流的同时，顾客满意度在物流配送中也起到越来越重要的作用， 顾客满意度已成为物流企业提高竞争优势的重要手段之一。显然传统的模型由于 侧重点的不同，已不能满足物流业的新近发展和需要。基于以上的分析，本文将 引入顾客满意度求解车辆优化调度问题。 论文的主要内容如下： 第1 章：本文首先叙述了课题研究的背景，然后从算法发展的角度，分析了 车辆路径问题的研究成果：最后说明了本课题的必要性及现实意义。 第2 章：旅行商问题一直被认为是车辆优化调度问题求解的基础。在本章， 作者侧重对于这一基本问题及其实现方式进行分析：通过分析旅行商问题的特点， 建立相应的数学模型，并利用反证法验证了模型的完备性。然后，从多角度介绍 遗传算法，结合模式理论，确定影响遗传算法的因素，并给出改进策略。最后， 提出基于改进遗传算法的问题求解过程，并通过比较分析及实例分析相结合的方 法，验证了算法的可行性。 第3 章；作者从理论角度对问题进行阐述：通过对车辆优化调度问题的分析， 指出针对v r p 的顾客满意度的含义，从而确定引入顾客满意度求解v r p 问题的实 质。然后结合当前的研究成果和实践经验，给出引入顾客满意度的车辆优化调度 问题求解策略。 第4 章：从模型分析和算法设计的角度，研究了与“车辆优化调度问题”相 关的3 个子问题：对于确定需求的v r p 问题，本文建立有时间窗的v r p 模型，并 采用两阶段法和改进的遗传算法编写实现算法，然后从运行时间、求解质量、稳 定性及扩展性等方面验证了算法的可行性；对于不可预测的不确定需求，本文建 立动态监控模型：根据客户的数量，采取不同的应对策略，然后通过渐进性分析， 证明了动态监控模型的可行性；对于需求转化问题，本文在g m ( 1 ，1 ) 预测模型 的基础上，增加了季节修改指数，建立改进的g m ( 1 ，1 ) 模型，并利用该模型尽 可能多地将不确定需求转化为确定需求。最后通过大量的数据分析，证明了模型 的有效性。 第5 章：本文提出了基于人机交互模型的问题实现方式，并给出了选择这种 方式的理由。然后在对系统进行简述的基础上，通过具体的实例，介绍了引入顾 客满意度的v r p 问题的实现过程。 最后，在结论部分，本文指出了论文的创新点、存在的不足及日后研究的方 向。 关键词：物流配送：需求分析；顾客满意度；甄阶段法；遗传算法；灰色理论； 先来先服务策略 a b s t r a c t w i t ht h eg l o b a l i z a t i o no ft h ee c o n o m y ，m o d e r nl o g i s t i c sh a se x p a n d e df r o m p r o v i d i n gt h es o c i e t yt r a d i t i o n a lt r a n s p o r t a t i o ns e r v i c et ot h ei n t e g r a t e dl o g i s t i cs y s t e m 、i mt h es u p p o r to f m o d e ms c i e n c e i n f o r m a t i o nt e c h n o l o g ya n dm a n a g e m e n t o v e rt h e p a s tf o u rd e c a d e s ，t h ep r o b l e mc o n c e r n i n gt h ed i s t r i b u t i o no fg o o d sb e t w e e nd e p o t sa n d f i n a lu s e r sh a v er e c e i v e de x t e n s i v ea r e n t i o na n dr e s e a r c h e sh a v em a d ee n o r m o u s p r o g r e s si nd e v e l o p i n gt h e o r y ，m o d e l sa n ds o l u t i o nm e t h o d sf o rt h e s ep r o b l e m s w i t ht h ed e v e l o p m e n to fl o g i s t i c s ，c u s t o m e r s s a t i s f a c t i o nh a sm o r ei m p o r t a n ti n t h ep r o c e s so fp h y s i c a ld i s t r i b u t i o na n di th a sb e c o m eo n eo ft h ei m p o r t a n tw a y st og e t t h ec o m p e t i t i v ea d v a n t a g e sa m o n gl o g i s t i c sb u s i n e s se n t e r p r i s e s o m er e c e n tl i t e r a t u r e s s e ta b o u tr e s e a r c ho nc u s t o m e r s s a t i s f a c t i o no b j e c t i v ef r o mt h es t a n d p o i n to fc u s t o m e r s b u tt h e yo n l yr e g a r dm e e t i n gc u s t o m e r s e x p e c t a t i o na sc o n s t r a i n t so ft h em o d e l si nt h e l i t e r a t u r e s ，w h i c hb e l o n gt ot h ec a t e g o r yo fas i n g l e o b j e c t i v ed e c i s i o n m a k i n g a n d m a n yd i s s a t i s f a c t o r yi t e m sf o rt h em o d e l sa w m ta m e l i o r a t i o na n d m o d i f i c a t i o n a b o v ea l l ，t h ep a p e rs t u d i e st h ev e h i c l em u t i n gp r o b l e mb a s e do nt h es a t i s f a c t i o n o f c u s t o m e r n 地m a i nc o n t e n t so f t l l i sd i s s e r t a t i o na r ea sf o l l o w i nc h a p t e rl ：1 1 1 ep a p e rr e v i e w st h eb a c k g r o u n da n dt h eb a s i cc o n c e p ti n c l u d i n g l o z i s t i e s ，m u t i n g s u b s e q u e n t l yb a s e do ns u m m a r i z i n gr e l e v a n tr e f e r e n c e s ，t h ep a p e r r e v i e w sd o m e s t i ca n df o r e i g nr e s e a r c h e so nt h ev e h i c l er o u t i n gp r o b l e m ，p o i n t so u t s h o r t c o m i n g so f r e s e a r c ho nt h i sp r o b l e ma n df m d ss o m ep o t e n t i a la r e a so f r e s e a r c h a t l a s t ，t h ep a p e re x p l a i n st h en e c e s s i t ya n dr e a l i s t i cs i g n i f i c a n c eo fs o l v i n gv r pb y i n t x o d u c i n gt h ei m p o r t a n c eo fd i s t r i b u t i o ni nt h ew h o l ep h y s i c a ll o g i s t i ca n dt h es t a t u s q u oi nt h eh o m ed i s t r i b u t i o ni n d u s t r y i nc h a p t e r2 ：t h et r a v e l i n gs a l e s m a np r o b l e m ( t s p li sap r o b l e mi nw h i c ha t r a v e l e rm u s tt r a v e r s eas e to fc o m p l e t e l yc o n n e c t e dc i t i e su s i n gt h em i n i m u ml e n g t h c y c l e t h i sp r o b l e mi sa tt h er o o to f t h e v e h i c l er o u t i n gp r o b l e mf v r p ) i nt h i sc h a p t e r ， f o r m a la n dm a t h e m a t i c a ld e f i n i t i o n s t o g e t h e rw i 也ab r i e fo v e r v i e wa b o u tg e n e t i c a l g o r i t h ma n dd e t a i l e dd e s c f i p t i o n o fs o l u t i o na p p r o a c h e s a ne x p e r i m e n ti sa l s o p e r f o r m e di no r d e rt oi m p r o v et h ee x i s t i n gh e u r i s t i c i nc h a p t e r3 ，t h ep a p e ra n a l y s e st h et h e o r e t i cp a r to ft h ew h o l ed i s s e r t a t i o n a tf i r s t , t h ep a p e rm a k e sf o r m a ld e f i n i t i o n sw i t ht h er e a l i s t i cv e h i c l er o u t i n gp r o b l e m ，t o g e t h e r w i t hd e t a i ld e s c r i p t i o n sa b o u tc u s t o m e r s s a t i s f a c t i o n t h e nt h ee s s e n t i a lm e a n i n g so f u l ec si l lm ev r pa r eg i v e n a c c o r d i n gt oi t , t h es o l v i n gs t m t e g ) rf o rt h ep r o b l e mi s g i v e n i nc h a p t e r4 ，t h ep a p e rs t u d i e st h ep r o b l e mf r o mt h ep o i n to fv i e wo fm o d e l sa n d a l g o r i t h m s t h ep a p e rs t u d i e st h r e es u b - p a r t sa c c o r d i n gt ot h er e a l i s t i cv r p ：f o rt h e d e t e n n i n i s t i cd e m a n d s ，t h i sr e s e a r c ha t t e m p t st of o r m u l a t eam a t h e m a t i c a lm o d e lf o rt h e v e h i c l er o u t i n gp r o b l e mw i t ht i m ew i n d o wa n d p r o p o s eat w o - p h a s ea l g o r i t h ma n d a n i m p r o v i n gg e n e t i ca l g o r i t h m ( g a ) t os o l v et h ep r o b l e m a n db ya n a l y z i n gt h e r u n n i n g - t i m e ，t h es o l v i n gq u a l i t y ，t h es t a b i l i t y ，t h ee x p a n s i b i l i t ya n dt h et r u l y e x p e r i m e n t s ，t h ep a p e rp r o v e st h ef e a s i b i l i t yo ft h ea p p r o a c h ；f o rt h es t o c h a s t i c d e m a n d s ，t h ed y n a m i cp r o g r a m m i n ga l g o r i t h mi sg i v e nb yt a k i n gt h ea l g o r i t h m si nt w o p a r t sa c c o r d i n gt ot h ed i f f e r e n ts c a l e so ft h ec u s t o m e r s t h e nt h em a t h e m a t i ca p p r o a c h i sg i v e nt oa p p r o v et h ef e a s i b i l i t yo ft h ed y n a m i cp r o g r a m m i n g b e c a u s es o m eo ft h e s t o c h a s t i cd e m a n d sc a n h et r a n s l a t e di n t ot h ed e t e r m i n i s t i cd e m a n d s ，t h ep a p e rb u i l d su p t h ei m l y r o v i n gg m ( 1 ，1 ) b a s e do nt h et r a d i t i o n a lg r e yt h e o r ya n ds e a s o n a li n d e xa n d r e g r e s s i o nm o d e lw h i c ha r ea p p r o v e db yd a t aa n a l y s i s i nc h a p t e r5 ：t h ep a p e rm k k e st h en e wa p p r o a c hi n t ot r u t hb ya n a l y z i n gt h et h r e e p a r t si n c l u d i n gt h er o u t i n gp a r t sa n dt h ef o r e c a s t i n gd e m a n d sa n dt h er e a l - t i m e c o n t r o l l i n g ，w h i c ha r ei n t e g r a t e db yt h eh u m a n - t o g e t h e ri n t e r a c t i o n m o d e f i n a l l y ，c h a p t e r6p r e s e n t ss u m m a r y ，c o n c l u s i o n sa n dr e c o m m e n d a t i o nf o rf u t u r e r e s e a r c hp r o s p e c t i v e 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 ；d e m a n d sa n a l y s i s ；c u s t o m e r s s a t i s f a c t i o n ； t w o - p h a s ea l g o r i t h m ；g e n e t i ca l g o r i t h m ；g r e yt h e o r y ；f i r s tc o m ef i r s ts e r v e d 1 1 研究背景 第1 章绪论 1 1 1 物流新的经济增长点 随着经济全球化趋势的加强，科学技术尤其是信息技术的发展突飞猛进，企 业生产资料的获取与产品营销范围日趋扩大，社会生产、物资流通、商品交易及 其管理方式正在并将继续发生深刻的变革。与此相适应，被普遍认为企业在降低 物质消耗、提高劳动生产率以外的“第三利润源”的现代物流业已在世界范围内 广泛兴起，目前正在成为全球经济发展的一个重要热点和新的经济增长点。 据有关统计，产品的直接成本约占总成本的1 0 ，产品的制造时间约占总时 间的5 ，所对应的9 0 的价值成本及9 5 的时间成本，主要是在储存、装卸、运 输、包装等物流作业过程中消耗掉的。所以发达国家经济学家们称现代物流为“未 被开垦的黑大陆”、“人力、资源之后的第三利润源泉”i l 心。 妊竿要攀鸵- 生产 t 流通 消费 广 为经营效率化而降低成本 f厂交通运输体系的整善 白商品市择的可靠性7 斗、 l 物流；商流l s耍一：三：的运通，对消费者重要岭l - ( 对地区重要性) 图1 1 物流的地位 f i g 1 1t h ep o s i t i o no f t h el o g i s t i c s 全球“物流”发展的七种趋势是：供应链管理，供应链全球化，虚拟企业， 电子商务，绿色物流，战略伙伴和新管理规则【3 】。如图1 1 所示，本文期望通过分 析物流与供应链管理之间的关系，以体现物流的地位 4 1 。 一一一劳r $ 争一一一一_ 一一一一暮b 法一一一- 集货配送干线运输支线还4 - - 输 末端运输 图1 2 配送的地位 f i g 1 2t h ep o s i t i o no f t h ed i s t r i b u t i o n 1 1 2 配送现代物流的核心组成 配送的实施一定是建立在供应链管理的基础上。显然通过分析配送对于供应 链系统的影响，我们可以确定现代配送的地位。 如图1 2 所示，随着存储环节要求日益趋向弱化，配送成为最重要的环节，直 接为用户服务。配送的核心部分是配送车辆的集货、货物配送及送货过程。而车 辆配送路线的合理优化，对于整个物流运输速度、成本、效益将产生至关重要的 影响。根据中国仓储协会对于1 4 6 个企业的调查显示，用于配送的费用占整个物 流费用的比例分别为：在生产企业原料物流中占5 8 、在生产企业成品物流中占 7 3 、在商业物流中占5 2 。所以进行配送系统优化，最主要是对配送优化，包括 集货线路优化、货物配送及送货线路优化。由此可以知道，现代配送对于供应链 系统的影响【5 】= ( 1 ) 配送是产品价值链的增值渠道； ( 2 ) 完善了整个的物流供应链管理系统； ( 3 ) 物流供应链上的所有成员形成一个利益共同体； ( 4 ) 供应链管理在现代市场经济中的作用。 图1 3 v r p 研究元素分析 f i g i 3t h ea n a l y s i so f t h ev r p sf a c t o r s 1 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 l f l g c r 予1 9 5 9 年 首次提出。作为物流系统优化中关键的一环，对于v r p 的研究得到了运筹学，组 合数学与网络分析、物流科学、计算机应用等学科的专家与运输计划指定者的极 大重视。各国学者对其理论和应用进行大量的研究工作，取得了数以千计的研究 成果，使v r p 研究成为“最近十年运筹学领域最成功的研究之一” 1 7 1 。 在过去的四十多年中，针对v r p 的研究已经取得了令人瞩目的成绩。利用e i 和s c i 数据库，以v e h i c l er o u t i n gp r o b l e m 和v e h i c l es c h e d u l i n gp r o b l e m 为主题词 检索，结果中将出现数千篇文献。为了能系统地、全面地理解v r p 的结构，如图 1 3 所示，本小节对构成该类问题的要素进行逐一分解嘲【9 l 【1 们。 1 2 1 基于确定条件的、，r p 早期对车辆优化调度问题的研究主要集中在确定信息基础上，它是对车队管 理问题的最简化，只考虑在某时段内如何组织车辆调配才能够满足己知客户的需 求，且使本时段的收益最大化。具体分为3 种基本的算法( 如图1 4 ) ：精确算法、 启发式算法和亚启发式算法【1 1 1 。 1 2 1 1 精确算法 精确算法通过严谨的数学模型或计算机数据结构规划，利用数学法则或数据 结构搜寻的方式，求得问题的解。由于两种方法都在所有可行解集合中寻找最优 解，所以求的解均为最优解。 随着变量的增加，车辆优化调度问题的解集合会有组合爆炸的现象，求解时 间也呈指数函数的趋势增长，不能在有限的时间给予决策者一个可行解，是这种 方法最大的缺点【1 2 l 。 1 2 1 2 启发式算法 由于糟确算法的求解效率较差，所以大部分的学者都致力于启发式算法的发 展。该方法在解题时可减少搜寻的次数，是一种容易且快速求解n p 难题的算法。 ( 1 ) 构造算法( c o n s t r u c t i v ea l g o r i t h m ) 构造算法，就是指根据一些准则，每一次将一个不在线路上的点增加进线路， 直到所有的点都被安排进线路为止。其中较为代表的研究成果如下【1 9 】： 1 9 8 6 年，s o l o m o n 应用先路线后分组的思想提出一种长回路启发式算法； 节约算法，最早由c l a r k e 等提出并用于求解v r p 问题； 合数学与网络分析、物流科学、计算机应用等学科的专家与运输计划指定者的极 大重视。各国学者对其理论和应用进行大燕的研究工作，取得了数以千计的研究 成果，使v r p 研究成为“最近十年运筹学领域最成功的研究之一”问【7 l 。 在过去的四十多年中，针对v r f 的研究已经取得了令人瞩目的成绩。利用e i 和s c i 数据库，以v e h i c l er o u t i n gp r o b l e m 和v e h i c l es c h e d u l i n gp r o b l e m 为主题词 检索，结果中将出现数千篇文献。为了能系统地、全面地理解v r p 的结构，如图 l 3 所示，本小节对构成该类问题的要素进行逐一分解i s l 9 ”l 。 1 21 基于确定条件的v r p 早期对车辆优化调度问题的研究主要集中在确定信息基础上，它是对车队管 理问题的最简化，只考虑在某时段内如何组织车辆调配才能够满足已知客户的需 求，且使本时段的收益最大化。具体分为3 种基本的算法( 如图1 4 ) ；精确算法、 启发式算法和亚启发式算法【l “。 1 2 1 1 精确算法 精确算法通过严谨的数学模型或计算机数据结构规划，利用数学法则或数据 结构搜寻的方式，求得问题的解。由于两种方法都在所有可行解集合中寻找最优 解，所以求的解均为最优解。 随着变量的增加，车辆优化调度问题的解集合会有组合爆炸的现象，求解时 间也呈指数函数的趋势增长，不能在有限的时间给予决策者一个可行解，是这种 方法最大的缺点。 1 2 1 2 启发式算法 由于糖确算法的求解效率较差，所以大部分的学者都致力于启发式算法的发 展。该方法在解题时可减少搜寻的次数，是一种容易且快速求解n p 难题的算法。 ( 1 ) 构造算法( c o n s t r u c t i v ea l g o r i t h m ) 构造算法，就是指根据一些准则，每一次将一个不在线路上的点增加进线路， 直到所有的点都被安排进线路为止。其中较为代表的研究成果如下1 1 埘： 1 9 8 6 年s o l o m o n 应用先路线后分组的思想提出一种长回路启发式算法； 节约算法，最早由c l a r k e 等提出并用于求解v r p 问题： 节约算法，最早由c l a r k e 等提出并用于求解v r p 问题； 图1 4 确定条件下的v r p 研究现状 f i g 1 4t h er e s e a r c h e sc o n c e r n i n gd e t e r m i n i s t i cv r p 邻接算法是一种序列构造路线法，算法从一条只含一个配送点的路线出发， 通常取这个距离车站最近的点； 插入算法的流程与邻接算法相似，也是从初始路线出发，序列构造路线， 并在不存在可行插入时。可以通过增加一条初始路线来解决； 扫除算法最早由o i l l e t t 和m i l l e r 在1 9 7 4 年提出，是一种先分组后路线的算 法。1 9 8 7 年，s o l o m o n 将其推广应用于v r p t w 闯题的路线构造。 以上五种算法是基础的算法，近期也有文献对这些算法做了一些改进： 1 9 8 8 年，v a nl a n d e g h e m 在节约值中增添了所谓的“弹性损失”； 1 9 9 3 年，p o t v i n 和r o u s s e a u 应用序列插入算法的结果估计路线的条数并确 定种子点集，然后选择后悔值最小的未分配点插入路线； 1 9 9 5 年，r u s s e l l 提出在路线构造时嵌入路线改进方法； 1 9 9 5 年，r u s s e l l 提出在路线构造时嵌入路线改进方法； 1 9 9 9 年，l i u 提出一种基于路线邻域的两阶段启发式算法。 ( 2 ) 两阶段法( t w op h a s ea l g o r i t h m ) 在构造算法求得的解的基础上再进一步改进，提出了两阶段法。第一阶段得到 一个可行解，第二阶段通过对点的调整，在始终保持解可行的情况下，力图向最 优目标靠近，每一步都产生另一个可行解来代替原来的解，使目标函数得以改进， 一直继续到不能改进目标函数为止。 其中较为代表的研究成果如下【2 0 1 ： 1 9 7 7 年，r u s s e l l 等首先在带时间窗的车辆路线问题中应用了k - o p t 算法； 1 9 8 6 年，b a k e r 和s c h a f f e r 首先将2 - o p t 和3 - o p t 推广应用到v r p t w 问题；1 9 9 5 年，p o t v i n 和r o u s s e a u 提出一种两条路线之间的边替换方法2 - o p t 法； 1 9 9 7 年，t a i l l a r d 等提出了一种命名为c r o s s - e x c h a n g e 的边替换方法； 1 9 7 6 年0 r 对t s p 问题提出了一种以他的名字命名的o r - o p t 方法：1 9 9 5 年， p o t v i n 和r o u s s e a u 将o r - o p t 方法推广应用到v t p t w 的路线改进，并结合使用其 他边替换法：1 9 9 8 年，v a nl a n d e g h e m 提出了类似的改进操作方法； 1 9 9 3 年，g l o v e r 提出一种连锁排挤算法； 1 9 9 3 年，t h o m p s o n 和p s a r a f i i s 提出一种循环k 转移方法，其中k 是给定 的整参数；1 9 9 7 年，d eb a c k e r 应用约束规划来表示v r p y w 的求解过程 1 2 1 3 亚启发式算法 亚启发式算法由于其全局搜索性，近年来在优化领域有着越来越广泛的应用。 亚启发式算法是从1 个初始解开始，通过对当前的解进行反复地局部扰乱以达到 较好的解它包括t a b us e a r c h ，s i m u l a t e da n n e a l i n g ，g e n e t i ca l g o r i t h r a 和n e u r a l n e t w o r k s 方法。 ( 1 ) 禁忌搜索：g e n d r e a u 等人最先将该方法应用于v r p 。其后，e 1 葡l l a r d 按角 度和路径重心对原问题的空间进行分割，再用禁忌搜索结合模拟退火对子问题求 解，实现了问题求解的并行化【2 l 】。 ( 2 ) 遗传算法：j l a w r e n c e 最先将该方法用7 ：v r p 的研究，并可有效求解带时 间窗口筮j v r p 2 2 。鉴于传统的遗传算法是个大范围、粗粒度的寻优算法。因此， b a r i e r 将它与约束满足问题( c s p ) 的技术相结合，通过遗传算法来处理c s p 参数 的子域，从而减小搜索空间，降低c s p 问题目标函数和遗传算法约束的复杂度。 张涛等人则是通过遗传算法来保证搜索的全局性，用3 o p t 算法来加强局部搜索能 力，得到针对v r p 的混合算法。这类算法目前已可以求解较大规模的问题( 1 9 9 个客户) 2 3 1 2 , q 。 ( 3 ) 模拟退火算法：该方法最早r o b u s t e 提出，其所定义的领域结构是基于 如下几种机制进行组合：将线路中的某部分倒置，将线路中的某部分移到同一线 路的另一位置，在两线路间对换顶点1 2 5 】【2 6 1 。其后，o s m a n 在其博士论文较全面地 构造了模拟退火过程。该算法的领域结构使用一个交换产生机制，并分别从这两 条线路中选出子客户，以满足某种规趔”1 。 ( 4 ) 蚁群算法：1 9 9 9 年，g a m b a r d e l l ae ta 1 应用蚁群算法对v r p t w 进行路线改 进。该算法首先构造两组相互协作的人工蚁群，其中第1 个蚁群用于最小化车辆数， 第2 个蚁群用于最小化总距离，然后以共用解的方式建立协作关系【2 3 1 。 1 2 2 基于随机条件下v r p 在日常生活和工作中，人们经常会遇到一些不能确切地预计其后果，但是能 够知道其后果出现规律的随机事件，在v r p 中也经常会出现这种事件。在构造车 辆路径之前，与问题有关的某些信息并不完全知浇，但能根据历史资料或市场调 查获得某些信息的统计规律，也就是v r p 中的某些要素是随机的。如图1 5 所示， 由于这类问题有着广泛的应用背景，并且其求解方法和解的特征与确定性v r p 有 很大区剐，所以近些年来引起人们的广泛关注f 2 9 1 。 jt ：。扭山了t 堆d 业韶i 旰举世f 豫il ，r 唧，- # 盐h _ 。一，_ 。，_ 。 基 一b e n s i m a s 结合p ，r s p ，心s c 给定了空间填充曲线，2 - 。p t 于 随 一l a p o r t e 求解顶点数最多为5 0 的问题，获得最优解 机 信 息 一 s t e w a f i 刍黾出了机会约束模型和两种补偿模型 下 生 辆 - q b e r t i s i m a 娃导出问题上下界、渐进性及理论特征 优 化 调 一 l a p o r t e 和g e l l d a u 提出了补偿模型的l 形算法 度 问 题 一 s e c o m a n d i 用r 。1 1 a m 算法改进了l 形算法 研 究 现 一 p a r k 和s o n g 修正了三种新的启发式算法 状 一 l 8 p o f t e 提出了机会约束模型，补偿模型且分枝割算法 图1 5 基于随机信息下v r p 的研究状况 f i g 1 5t h er e s e a r c h e sf o r t h es t o c h a s t i cv r p 1 2 3 基于模糊条件下v r p 近年来，有关某些参数既无确切数据又无统计规律可循的车辆调度问题的研究 开始出现，即模糊车辆调度问题( f u z z y v e h i c l es c h e d u l i n g o r r o u t i n g p r o b l e m ，简 称f v s p 或f v r p ) 。 目前对于这方面的研究比较少，下面介绍一下基本的参考文献； ( 1 ) t e o d o r o v i c 等人是最早着手研究这类问题的人。他以模糊数表示客户点的 需求信息，以倾向度为基础建立模糊判定规则，其核心是基于s w e e p 算法，并省 略y s w e e p 算法的第二阶段，即初始化子路径后对它们的优化过程【刈。 c 2 ) 祝崇俊、刘民、吴澄等人以模糊可能性分布，建立基于置信度的v r p 的 模型，并提出基于可能性分布的2 o p t 算法。该算法引入伪出发点，建立以置信度 为基础的判定规则，以遍历为终止条件，从而在全局层次上进行优化，同时避免 过多地扩大搜索空间。该算法已可解决较大规模的问题f 3 l 】。 1 2 4 动态分析 ： 图1 6 动态研究状况 f i g 1 6t h er e s e a r c h e sc o l c e l n l t t gd y n a m i cv r p 以上3 节主要从静态分析角度来研究v r p 问题，但是静态车队管理问题中所 存在的诸多不足为静态模型的应用与发展带来了极大的限制。动态车队管理问题 的研究弥补了静态问题的致命缺憾，把车队管理问题引入一个新的研究领域。 动态v r p 的研究在过去的1 4 一1 5 年里面逐渐兴起，各种专著和杂志上出现 了一批研究动态随机v r p 的论文，但是研究并不成熟。如图1 6 ，其发展状况1 3 2 1 。 1 3 研究意义 1 3 1 传统方法存在的局限性 尽管对于v r p 的研究在模型和算法上已经有了很多成果，但是由于v r p 问题 是典型的n p 难题，而且涉及的问题众多，很多重要的问题需要进一步研究，这主 要体现为； ( 1 ) v r p 阔题一直被理想化为许多建理上分布的实体在离散的网络流上的移 动，忽视了问题的空间性； ( 2 ) 随着“实体”及“实体间”的关系变得越来越复杂，出现了越来越多不确 定的因素。但传统研究往往假设其符合某种特殊的函数分布( 例如正态分布) ，建 立随机条件下运输模型，该模型具有极小的适用范围； ( 3 ) 不确定因素与确定因素同时存在于问题的求解过程中，显然孤立地研究它 们是没有任何意义的； ( 4 ) 对于模糊条件下的车辆优化调度问题的研究都是根据已有的模糊信息进行 车辆路径的预先安排，车辆按预先规定的路径行驶，而不根据实际运行中逐渐明 街、清楚的信息对车辆的运行路径进行实时、动态地调整。这样可能会造成运行 中的一些“不智”行为； ( 5 ) 顾客服务在物流中起到越来越重要的作用，顾客服务已成为物流企业提高 竞争优势的重要手段之一。 1 3 2 学术价值 车辆优化调度作为发展物流的一个重要组成部分，是实现物流现代化的基础 和前提条件，是产品与信息从原料到消费者之间的增值服务。实现真正意义上的 物流的成功运作需要车辆优化调度模型的支持。因此，研究车辆优化调度将对物 流学科群的建设与发展具有十分重要的意义： ( 1 ) 所要解决的问题具有相当的普遍性 物流系统中涉及的交易对象或实体可以是社会经济生活中的任何理性或非理 性个体，物流中涉及的供应项目可以是特定的产品、某种技术、某种服务等。物 流系统建设及其优化的理论、技术、方法与系统的发展与众多相关的发展水平相 关，没有止境，是一个永恒的课题。 ( 2 ) 有利于促进相关学科的发展 物流技术与系统的理论涉及系统论、协同论、信息经济学的有关理论与方法 以及管理科学与工程、信息技术与工程、计算机技术与工程等学科，是多专业、 多学科交叉融合的结果，是一个典型的边缘学科。物流技术与系统的研究、应用 与发展，可以促进相关学科的研究与发展。 ( 3 ) 不确定因素分析符合经济学理论发展要求 在任何一种经济系统中，都存在不确定性的影响。而每一种经济体制，都有 限制不确定性影响的某种功能。随着经济体制的深入，市场机制作用不断加大， 不确定性影响也越来越大，加强不确定性理论的研究，不仅符合我们经济发展实 践的需求，也符合我国经济理论的发展的需要。 1 3 。3 实际意义 车辆优化调度作为发展物流的一个重要组成部分，是实现物流现代化的基础 和前提条件。基于车辆优化调度问题的研究不仅有助于改变我国物流管理落后的 现状，也有助于解决城市交通拥挤、能源短缺、大气污染等阻扰人们的社会问题， 实现效率、资源、环境和价值观念各方面的内在统一，促进物流的进步和社会经 济的可持续发展。 同时，随着新世纪的到来，电子商务的蓬勃发展与中国加入w t o ，市场竞争 进一步加剧。企业要保有和争得市场，不仅要在产品的质量、功能上下功夫，更 重要的还是要在优质服务上下功夫。本文的研究成果，不仅可以帮助运输企业提 高服务水平，为顾客提供快捷、准时、安全、舒适的服务，解决发展电子商务中 “速递”这一瓶颈约束；而且还有助于企业节约运输成本，改善车辆利用效率， 缩短生产周期，加速资金周转，实现资源的合理配置，汲取“第三利润源泉”的 财富。 1 4 研究内容 本文的研究来源于国家自然基金资助项目( 7 0 5 4 0 0 0 5 ) “多维数据与空间数据 集成环境下数据挖掘模型的研究”和辽宁省科技厅资助项目“基于嵌入式技术的 船舶( 汽车) 监控导航与调度系统”。 0 目_ ，一一一1 b 图1 7 论文的结构图 f i g 1 7t h ef r a m e w o r ko f t h ep a p e r 如图1 7 ，本论文的研究：具体而言，本文首先结合当前形势，分析车辆优化 调度问题的研究现状，指出传统模型的局限性，确定了引入顾客满意度研究车辆 优化调度问题的意义。然后，通过分析旅行商问题和改进遗传算法，为车辆优化 调度问题的求解奠定了技术基础。在第三章，本文结合顾客满意度管理理念及车 辆优化调度问题实际，分析了针对于v r p 问题的顾客满意度的含义，确定了“具 体问题具体分析”的求解策略，为课题的研究奠定了理论基础。其后，针对于不 同的需求情况，本文采取了不同的求解策略。对于每一个求解策略，都从理论分 析和实际数据的角度加以证明。最后，本文提出了基于人机交互模式的问题实现 方式，并给出了具体的模块运行图。 2 1 旅行商问题 第2 章基本问题分析 2 1 1 问题描述 旅行商问题，可以简单地描述为：一个商人欲到挖个城市推销商品，每两个城 市i 到_ ，之间的距离为或，如何选择一条路径使得商人每个城市走一遍后回到起 点，而且所走的距离最短【划【3 朝。 用图论的术语来说，期望在赋权完全图上找一个权值最小的h a m i l t o n 圈。即： 假设有一个图g = ( v ，e ) ，其中v 是顶点集，e 是边集，设d = ( 巩) 是由顶点i 和顶 点，之间的距离所组成的距离矩阵，旅行商问题就是求出一条通过所有顶点且每个 顶点只通过一次的具有最短距离的回路。 旅行商问题t s p 是一个典型的组合优化问题，并且是一个n p 完全问题，其 可能h a m i l t o n 圈的数丑是顶点的数目拧的指数函数，所以一般很难精确地求出其 最优解。 2 1 2 数学分析 2 1 2 1 模型建立 严格的数学定义如下【3 6 】：图g = ( 矿，口) ，其中v = 1 ，2 ，3 ，h l 为顶点集，e 为边 集，各个顶点间消耗d = ( 噍) 。已知吒 _ 0 ，或= 一，问题要求g 的h a m i l t o n 回 路上的消耗达到最小值，并设： f 1边( f ，) 在h a m i l t o n 回路上 一1 0 其他 ( 2 1 ) 则t s p 的数学模型可写成如下整数规划形式： 舰z = 否勺勺 要求满足如下条件： ( 2 2 ) 行 善x