（管理科学与工程专业论文）带模糊时间窗的多车型车辆调度问题研究.pdf

r e s e a r c ho nh e t e r o g e n e o u sf i x e df l e e tv e h i c l er o u t i n gp r o b l e m w i t hf u z z yt i m ew i n d o w s b y m a oc h a o b e ( z h e j i a n go c e a nu n i v e r s i t y ) 2 0 0 7 at h e s i ss u b m i t t e di np a r t i a ls a t i s f a c t i o no ft h e r e q u i r e m e n t sf o rt h ed e g r e eo f m a s t e ro fm a n a g e m e n t m a n a g e m e n ts c i e n c ea n de n g i n e e r i n g i nt h e g r a d u a t es c h o o l o f h u n a nu n i v e r s i t y s u p e r v i s o r p r o f e s s o rd e n ga i m i n n o v e m b e r , 2 0 0 9 54m 7 93m7，iii1y 湖南大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所 取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任 何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡 献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的 法律后果由本人承担。 作者签名：磊歹纽日期：叫年，月乡日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意 学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文 被查阅和借阅。本人授权湖南大学可以将本学位论文的全部或部分内容编 入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇 编本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密由 ( 请在以上相应方框内打“”) 作者签名：磊握 导师签名：娜表氏 日期：叫年 日期：矽绛 1 1 月，弓日 f ，月，多日 随着全球经济一 遍目标和战略行为， 手段，在强调降低成本的同时，客户服务水平在物流配送中也越来越重要。然而， 物流服务水平与物流成本之间存在效益悖反，权衡物流服务水平与物流成本是物 流企业一项重要的战略性工作。 基于以上分析，本文综合考虑配送成本和客户服务水平，提出了带模糊时间 窗的多车型的车辆调度问题。 首先，在综述带时间窗的车辆调度问题、多车型车辆调度问题以及模糊信息 车辆调度问题等相关研究的基础上，分析了标准车辆的调度问题及其数学模型构 成要素、扩展标准、扩展问题和求解算法。 其次，引入配送服务水平模糊隶属度函数，建立了带模糊时间窗的以总配送 成本为最小和客户满意度最高的双目标多车型车辆调度模型。 再次，在设计产生初始可行解算法的基础上，采取基于概率选择的四种算子 邻域操作增进模拟退火法的搜索解空间的能力，由此产生的改进模拟退火算法对 模型求解。算法分两阶段对模型求解：第一阶段，将服务水平控制在某个水平以 上，获得对应的可接受时间窗，第二阶段求得更高服务水平的优化解。 最后，通过求解设计的算例说明了该方法的可行性，并以益阳城区烟草配送 路线多车型车辆调度优化为例验证了该模型的实用性。算例结果还显示，通过控 制车辆服务时间和出发时间，适当控制降低少数客户服务水平，可以有效降低配 送成本且总体服务水平影响不大。 关键词：车辆调度；模糊时间窗；多车型；改进模拟退火算法 i i 硕十学位论文 a b s t r a c t w i t ht h ea d v a n c eo fg l o b a le c o n o m i ci n t e g r a t i o n ，g l o b a lm a n u f a c t u r i n g ，g l o b a l p u r c h a s i n ga n dg l o b a lm a r k e t i n gh a v eb e c o m eac o m m o no b j e c t i v ea n ds t r a t e g i c b e h a v i o ro ft h ee n t e r p r i s e s ，a n dt h ei m p o r t a n c eo fl o g i s t i c si si n c r e a s i n g l ys i g n i f i c a n t t oi m p r o v ec o m p e t i t i v ea d v a n t a g e ，l o g i s t i c se n t e r p r i s e sp a ym o r ea n dm o r ea t t e n t i o n t oc u s t o m e rs e r v i c el e v e l si nl o g i s t i c sd i s t r i b u t i o nw h i l ee m p h a s i z i n gr e d u c i n gt h e c o s t b e c a u s eo ft h ep a r a d o xb e t w e e nt h es e r v i c el e v e la n dt h ec o s ti nl o g i s t i c s ， t r a d e o f fb e t w e e nt h es e r v i c el e v e la n dt h ec o s th a sb e e na ni m p o r t a n ts t r a t e g i cw o r ki n l o g i s t i c se n t e r p r i s e b a s e do nt h ea b o v ea n a l y s i s ，t h ev e h i c l er o u t i n gp r o b l e mw i t ha f u z z yt i m ew i n d o wc o n s i d e r i n gb o t ht h ed i s t r i b u t i o n c o s ta n ds e r v i c el e v e lw a s r e s e a r c h e d f i r s t l y ，o nt h eb a s i so fr e v i e w i n gt h er e l e v a n ts t u d i e so f v e h i c l er o u t i n gp r o b l e m w i t hat i m ew i n d o w ，m u l t iv e h i c l er o u t i n gp r o b l e m ，a sw e l la sv e h i c l er o u t i n gp r o b l e m o ff u z z yi n f o r m a t i o n ，t h i sp a p e ra n a l y s i st h es t a n d a r dv e h i c l er o u t i n gp r o b l e ma n di t s m a t h e m a t i c a lm o d e l ，a sw e l la st h ec o n s t i t u e n te l e m e n t so ft h ep r o b l e m ，e x p a n s i o n s t a n d a r d ，e x p a n s i o np r o b l e ma n dt h ea l g o r i t h m s e c o n d l y ，b yi n t r o d u c i n gf u z z ym e m b e r s h i pf u n c t i o no f t h ed e l i v e r ys e r v i c el e v e l ， ab i o b je c t i v eh e t e r o g e n e o u sf i x e df l e e tv e h i c l es c h e d u l i n gm o d e lw i t hf u z z yt i m e w i n d o ww a se s t a b l i s h e d ，w h i c hw a st a k i n gt h es m a l l e s tt o t a ld i s t r i b u t i o nc o s t sa n dt h e h i g h e s tc u s t o m e rs a t i s f a c t i o na st h eg o a l t h i r d l y ，b a s e do nt h ea l g o r i t h md e s i g no fg e n e r a t i n ga ni n i t i a lf e a s i b l es o l u t i o n ， a d o p t i n gt h en e i g h b o r h o o do p e r a t i o n s o ft h ef o u ro p e r a t o r sb a s e do np r o b a b i l i t y s e l e c t i o nt oe n h a n c et h es e a r c h i n gs o l u t i o ns p a c ea b i l i t yo fs i m u l a t e da n n e a l i n g a l g o r i t h m at w o p h a s ea l g o r i t h mw a sp r o p o s e df o rs o l v i n gt h em o d e l ：a tt h ef i r s t s t a g e ，c o n t r o l l i n g t h es e r v i c el e v e lo v e rac e r t a i nl e v e lt og e tt h ec o r r e s p o n d i n g a c c e p t a b l et i m ew i n d o w ，t h es e c o n dp h a s ei st og e to p t i m a ls o l u t i o n o ft h eh i g h e r s e r v i c el e v e l a tl a s t ，t h i sp a p e ri l l u s t r a t e st h ef e a s i b i l i t yo ft h em e t h o db ys o l v i n gt h ed e s i g n e x a m p l e s ，a n dt a k i n g t h eh e t e r o g e n e o u sf i x e df l e e tv e h i c l er o u t i n go p t i m i z i n g p r o b l e mo ft h ey i y a n gt o b a c c od i s t r i b u t i o n l i n e sa sa ne x a m p l et ov a l i d a t et h e u s e f u l n e s so ft h em o d e l t h es i m u l a t i o nr e s u l t sa l s os h o wt h a td i s t r i b u t i o nc o s t sc a n e f f e c t i v e l yb er e d u c e d a n d i th a sl i t t l ee f f e c to nt h eo v e r a l ls e r v i c el e v e l sb y c o n t r o l l i n gt h ev e h i c l es e r v i c et i m ea n dd e p a r t u r et i m e ，a n da p p r o p r i a t l yr e d u c i n g t h e i i i i v 硕+ 学位论文 目录 学位论文原创性声明和学位论文版权使用授权书i 摘要i i a b s t r a c t i i i 插图索引一v i i 附表索引v i i i 第1 章绪论1 1 1 研究背景及意义一l 1 2 国内外相关研究综述与不足3 1 3 研究内容和思路一9 1 3 1 研究内容9 1 3 2 研究思路与技术路线1 0 第2 章车辆调度问题理论基础1 2 2 1 标准车辆调度问题及其数学模型1 2 2 1 1 标准车辆调度问题1 2 2 1 2 标准车辆调度问题的数学模型1 3 2 2 车辆调度问题的扩展1 4 2 2 1 车辆调度问题的构成要素1 4 2 2 2 车辆调度问题的扩展标准1 6 2 2 3 车辆调度问题的扩展问题1 8 2 3 车辆调度问题的求解算法2 0 2 3 1 经典启发式算法2 0 2 3 2 现代启发式算法2 1 第3 章带模糊时间窗的多车型车辆调度模型与求解2 6 3 1 问题提出与模型构建2 6 3 1 1 带模糊时间窗的多车型车辆调度问题2 6 3 1 2 模型的构建2 7 3 2 算法选择2 9 3 2 1 模拟退火算法原理2 9 3 2 2 模拟退火算法的改进3 0 3 3 求解算法设计3 2 3 3 1 求解思路与算法流程3 2 3 3 2 初始解产生3 5 v v i 硕士学位论文 插图索引 图1 1 技术路线图 图2 1 服务水平模糊隶属函数图 图3 1 改进模拟退火算法流程图 图3 2 初始解产生算法 图3 32 o p t 算子示意图 图3 4r e l o c a t e 算子示意图 图3 5s w a p 算子示意图 图3 62 - o p t * 算子示意图 图3 7 服务水平优化邻域操作示意图 图4 1 益阳市烟草配送客户分区图一 v h 表1 1 表1 2 表2 1 表4 2 表4 1 表4 3 表4 4 表4 5 表4 6 表4 7 表4 8 表4 9 表4 1 0 表4 1 1 表4 1 2 v i i i 硕十学位论文 1 1 研究背景及意义 第1 章绪论 随着经济的不断发展，全球经济一体化的推进，在世界范围内进行资源配置 已成为现实。2 0 世纪后期，通讯产业和信息革命的发展迅速，经济全球化趋势加 快，全球采购和全球营销成为企业普遍目标和战略行为。在这种向物流索取利润 的浪潮推动下，世界物流业自9 0 年代以来连续保持2 0 一3 0 的高速增长，物流 的重要性日益显著。现代物流覆盖了原材料、产成品从起点至终点及相关信息有 效流动的全过程。它将运输、仓储、装卸、加工、整理、配送、信息等方面有机 结合，形成完整的供应链，为用户提供多功能、一体化的综合性服务。它把整个 社会看作一个物流运行系统，它用信息系统来整合对客户、经销商、运输商、生 产商、物流公司和供应商之间的管理，让物的流动具有最佳的目的性和经济性， 消除整个价值链上的浪费，让每个参与者都能受益，从而提高整个社会的资源利 用水平，提高整个社会的竞争力，抵消市场经济条件下盲目竞争和调节滞后的制 度性缺陷。因此，物流管理被视作是继管理革命、成本控制革命之后的第三次利 润革命。 早在2 0 世纪中期，西方发达国家就已开始通过降低单位g d p 中的运输和物 流成本来提高利润。物流业越发达，物流成本就越低，物流总成本在g d p 中的比 例就会越低，这个国家的制造业就会显著地降低成本并提高客户的满意程度。相 关数据显示，在美国等发达国家物流成本约占g d p 的l o 左右，中等发达国家( 如 韩国) 的比重在1 5 左右。根据国家发革委、国家统计局和中国物流与采购联合会 共同发布的( ( 2 0 0 8 年全国物流运行情况通报显示，2 0 0 8 年我国社会物流总费用 为5 4 5 4 2 亿元，社会物流总费用与g d p 比率为1 8 1 。从社会物流总费用的构成 看，运输费用为2 8 6 6 9 亿元，占社会物流总费用的比重为5 2 6 【lj 。这些数据说 明了两个问题： 第一，我国物流业的整体水平还较落后，物流成本过高，影响了国民经济的 发展，增加了企业运营成本，进而降低了企业的市场竞争能力。目前，中国己成 为全球第三大贸易国，钢、铁、铜全球消费量第一，原油进口量全球第二，是许 多世界制造业产品、整机、零配件的最大生产基地，物流量在国际物流中占有重 要位置，如果加上国内物流量，则总物流量在世界上数一数二。然而，当前中国 物流业的发展水平同这一地位并不相称。除了内资制造业的扩张，跨国公司也纷 纷把其制造业部分移向中国，中国制造业产出的增长位居世界前列，完全有可能 成为2 l 世纪世界制造业的基地。但过高的交易成本使得我国企业的总成本并不 低。这就需要中介服务特别是物流服务来帮助降低交易成本。对于我国，降低1 带模糊时间窗的多车型车辆调度模型研究 的物流成本，相当于增加了3 0 0 0 多亿的经济效益。因此通过优化物流系统来提高 物流管理水平和效率，降低物流成本，是我国经济发展的迫切需求。 第二，运输费用占据了全社会物流总费用的一半以上。这说明，加强对运输 费用的控制，对降低物流成本有重要意义。配送是物流中的一个重要的、直接与 客户相连的环节，其一般定义为：将货物从物流结点送到客户需求点的过程。配 送是在集配货的基础上，按客户在种类、品种搭配、数量、时间等方面的要求所 进行的运送，是“配”和“送”的有机结合形式。有效率的配送系统期望在距离最短、 时间最少、成本最小的目标之下，规划最合适的配送路线，在需求量上、被配送 时间上满足不同地理位置的客户需求。配送的核心问题是车辆调度问题( v e h i c l e s c h e d u l i n gp r o b l e m s ，简称v s p ) ，其作为智能物流运输系统中的重要内容，在现 代物流中占有很重要的位置【z j 。 作为物流企业提高竞争优势的重要手段，在强调降低成本的同时，客户服务 水平在物流配送中也越来越重要。然而，物流服务水平与物流成本之间存在效益 悖反，权衡物流服务水平与物流成本是物流企业一项重要的战略性工作。 从文献查阅来看，一般的车辆调度问题中，均假设为客户点进行配送服务的 车辆是同质的( h o m o g e n e o u s ) ，即车辆具有相同的装载能力、相同的固定费用、具 有相同的最大行驶距离约束等，并且通常假设车辆数无限。然而在实际的配送管 理中，配送公司所拥有的车队( f l e e t ) - - 般是由一组异质或者异型( h e t e r o g e n e o u s ) 的 车辆组成，这些车辆具有不同装载能力、不同的单位旅行费用，使用车辆具有不 同固定成本，由于受资金约束，配送公司拥有的各种类型的车辆的数目也是有限 的。上述问题构成了本文要研究的车辆调度问题：具有固定车辆数的异型车辆路 径问题( h e t e r o g e n e o u sf i x e df l e e tv e h i c l es c h e d u l i n gp r o b l e m ，h f f v s p ) 。 与标准车辆路径问题相比，h f f v s p 是更接近配送管理实际的问题，在湖南 大学交通运输与物流研究所承担的湖南益阳烟草配送车辆的优化调度项目中，配 送车辆就拥有五十铃、依维柯等不同的车型。因此，h f f v s p 是比v s p 更实用的 模型。尽管h f f v s p 应用更广泛，但是文献中对这类问题的研究相对较少。 另一方面，目前v s p 问题主要集中在配送成本的降低、求解算法的改进、约 束条件的变换以及客户信息的不确定性等讨论上，但很少综合考虑配送成本与服 务水平对配送路径进行优化研究。事实上，降低服务成本和提高服务水平是物流 管理中的两个最重要的问题。所谓服务水平，在物流配送中可以表现为客户的满 意度。通常情况下，实际配送数量是否满足客户需求量、实际到达的时间是否为 客户所期望的时间等因素决定了客户的满意度。如报刊亭希望当天的报纸在早上 【7 ：0 0 ，7 ：3 0 之间送到，酒店希望酒水在中午 1 0 ：3 0 ，1 l ：0 0 】之间送到等等；如果货物 能按订单准时足量送到每个客户，则客户满意度最高。值得注意的是，如果没在 客户预定的时间内送到，客户满意度会下降，但并不意味着会失去这个客户，每 硕士学位论文 个客户有个相对可接受的迟到或者早到的时间范围，例如，报纸在6 ：5 5 或7 ：3 5 服务客户并不会很大的影响到报刊亭的销售量，因此，该客户虽然满意度下降， 但是仍为比较满意的，也就是说，并不会因为这5 分钟造成该客户流失。针对上 述现象，本文从系统出发，提出了考虑整体客户服务水平和整体成本的双目标带 模糊时间窗的h f f v s p 问题( h e t e r o g e n e o u sf i x e df l e e tv e h i c l es c h e d u l i n gp r o b l e m w i t hf u z z yt i m ew i n d o w s ) ，简称为h f f v s p f t w 。 该模型和算法将为物流企业处理非j i t 业务时，提供一种权衡服务成本与服 务水平进行多车型车辆调度的方法，具有重要实际意义。 1 2 国内外相关研究综述与不足 李军、郭耀煌在物流配送车辆优化调度理论与方法【3 l 书中将v r p 定义 为，对一系列发货点和( 或) 收货点，组成适当的行车路径，使车辆有序地通过它 们，在满足一定约束条件的情况下，达到一定的目标。在许多场合，人们也将v r p 称为v s p ( v e h i c l es c h e d u l i n gp r o b l e m s ) ，但是严格地讲，这两类问题是有区别的， 通常v r p 是指与空间有关的路径安排问题，而v s p 是指与时间有关的车辆配置 问题。本文遵照大多数人的习惯，对两类问题不做严格区分，仍统称为v s p 问题。 车辆调度问题的研究历史要回溯到d a n t z i g 和r a m s e r 及c l a r k 和w r i g h t 的研 究工作。d a n t z i g 和r a m s e r 在其1 9 5 9 年发表在( m a n a g e m e n ts c i e n c e ) ) 上的文章 ( ( t h et r u c kd i s p a t c h i n gp r o b l e m ) ) 中首次研究了汽油配送卡车的最优车辆路线问 题，并提出了基于线性规划的求解过程【4 】。作为对d a n t z i g 和r a m s e r 求解算法的 改进，c l a r k e 和w r i g h t 于1 9 6 4 年提出了一个有效的贪婪启发式算法【5 1 。自上述 两篇关于车辆调度问题的论文发表以来，运筹学学者们对于不同类型的车辆调度 问题提出了许多不同的数学模型，并提出了许多获得问题最优解或次优解的算法。 其研究结果在运输系统、物流配送系统、快递收发系统中都已得到广泛应用。车 辆调度问题是交通运输和物流配送领域的一个核心问题，现在对该问题的研究仍 然相当活跃。v s p 与旅行商问题、背包问题密切相关，它的可行解是多个满足背 包限制的t s p ( t r a v e l i n gs a l e s m a np r o b l e m ) 回路。通常情况下，v s p 均要求一个客 户只能由一辆车提供服务，若一个客户可以有多辆车提供服务则为分离配送 v s p ( s p l i td e l i v e r yv s p , s d v s p ) 。 带时间窗的车辆路径问题，是带约束条件v s p 中比较常见的一种类型，要求 车辆在没有违反容量和时间窗约束条件下，服务所有用户，求解最小费用的车辆 路径( 或最少的车辆数) 。它包括硬时间窗( v s p t w ) 和软时间窗( v s p s t w ) 两种情 况。v r p t w 问题已经被证明是n p h a r d 问题，s a v e l s b e r gm w p ( 1 9 8 5 ) 指出，对 于固定车辆数的v s p t w ，甚至找到可行解都很困难【6 】。l e n s t r a 等( 1 9 8 1 ) 指出所有 v s p t w 为n p 完全问题，求解v s p t w 主要是采用现代启发式方法1 7 j 。s o l o m o n 带模糊时间窗的多车型车辆调度模型研究 m m ( 1 9 8 7 ) 提出了一种解决带时间窗的车辆调度问题的算法【8 】。d e s r o c h e r s 等 ( 1 9 8 8 ) 通过将v s p t w 构建为带时间约束的网络流问题，采用拉格朗日松弛法， 解决服务所有用户的最少车辆数量问题【9 j 。t h a n g i a h 等( 1 9 9 1 ) 是最早采用g a 解决 v s p t w 【l 引。d e s r o c h e r s 等( 1 9 9 2 ) 禾1 j 用分枝定界法和动态规划法，解决车辆数不受 限制的v s p t w t l l 】。h o n g 等( 1 9 9 9 ) 基于启发式方法，采用并行插入方法对用户分 组，采用序列线性目标规划法构建路径，在车辆行驶总距离和用户等待总时间两 个目标函数最小的条件下，求解带时间窗的最优车辆数量问题【1 2 1 。l i u 等( 1 9 9 9 ) 基于一个考虑路径和节点新的邻域结构，采用并行算法，解决v s p t w 1 3 】。n a n r y 等( 2 0 0 0 ) 基于反应式t s ，设计了一个分层搜索法，在3 个邻域间动态的搜索，解 决带时间窗的送载v r p t l 4 】。i o a n n o u 等( 2 0 0 3 ) 采用最近邻法，在车辆数不受限制 的情况下，解决v s p s t w t ”】。h o 等( 2 0 0 4 ) 采用t s 解决带时间窗的货物可分割 v r p 1 6 j 。国内方面郎茂祥( 2 0 0 5 ) 等用禁忌搜索算法、遗传算法和蚁群算法对带时 间窗的车辆路径问题进行了研究，并取得了良好的效果【1 7 j 。邓爱民( 2 0 0 8 ) 等在带 软时间窗的集配货一体化v r p 改进模拟退火算法优化研究一文中，采用改进的 模拟退火算法获得了带软时间窗集配货一体化v r p 问题的更优解【l 引。 与他们不同的是，l a u 等( 2 0 0 3 ) 研究了带时间窗的有限v s p t l 9 】。基于禁忌算 法( t s ) ，作者设计了保留表( h o l d i n gl i s t ) 和层次成本结构( h i e r a r c h i c a lc o s t s t r u c t u r e ) 方法，保留表中存放未构成路径的用户，通过在保留表和已建路径间， 采用交换和插入用户的方法，改进路径。同时，由于所要解决的问题具有两个目 标，最大化车辆服务的用户数量和最小化总行程距离，因此，采用层次成本结构 作为评价体系，根据t s 插入和交换操作中的性能指标的改变，将客户进行等级 分类，按照优先级对用户进行操作。根据所查到的资料，到目前为止，除l a u 的 文献外，其余均为研究车辆数不受限制或将车辆数视为需要决策的变量。但对于 车辆数受限制的路径问题，通常在实际中更普遍。 在h f f v r p 中，问题变得相对复杂，由于车辆数的限制以及车辆类型的限制， 算法对产生的路线重新指派( r e a s s i g n m e n t ) 车辆。 文献中运筹学研究人员对于h f f v r p 研究较少。t a i l l a r d ( 1 9 9 9 ) 首次提出了一 种列产生( c o l u m ng e n e r a t i o n ) 启发式算法【2 们。算法首先针对每一种类型的车辆k ， 用基于禁忌搜索算法的a m p 算法来求解一般的v r p 问题，得到相应的路线为 坂，则算法将得到一个的总的组合u 心( 缈= 1 ，2 ，k ) 为车辆类型集) 。算法 然后凡通过求解一个集分割问题来从u 帆中选择最优的路线组合作为h f f v r p 七e 舻 的解。其中作者用c p l e x 软件来求解集分割问题。t a r a n t i l i s 等( 2 0 0 3 ) 提出了求解 h f f v r p 的基于列表的阈值接受启发式算法，阈值接受启发式算法属于确定性退 硕士学位论文 火算法【2 1 1 。其使用下列算子来产生邻居解：路线内和路线间2 - o p t 、路线内和路 线间1 1 e x c h a n g e 算法、路线内和路线间1 - 0 e x c h a n g e 算法。t a r a n t i l i s 等( 2 0 0 4 ) 又利用另外一种阈值接受启发式算法求解h f f v r p ，即带回溯阈值启发式算法， 与t a r a n t i l i s ( 2 0 0 3 ) 阈值接受启发式算法不同的是：算法中通过增加阈值允许算法 回溯到以前搜索过的解，以增强算法多样化搜索的能力【2 z 。 在日常生活和工作中，人们经常会遇到一些不能确切地预计其后果，但是能 够知道其后果出现规律的随机事件，在v r p 中也经常会出现这种事件。在构造车 辆路径之前，与问题有关的某些信息并不完全知晓，仅能根据历史资料或市场调 查获得某些信息的统计规律，也就是v r p 中的某些要素是随机的。由于这类问题 有着广泛的应用背景，并且其求解方法和解的特征与确定性v r p 有很大区别，所 以近些年来引起人们的广泛关注。 g e n d r e a u ( 1 9 9 6 ) 等将s v r p 分为以下6 种类型：随机客户的t s p ( t s pw i t h s t o c h a s t i cc u s t o m e r s ，简称t s p s c ) ，随机旅行时间的t s p ( t s pw i t hs t o c h a s t i c t r a v e l i n gt i m e s ，简称t s p s t ) ，随机旅行时间的m t s p ( m t s pw i t hs t o c h a s t i c t r a v e l i n gt i m e ，简称m t s p s t ) ，随机需求量的v r p ( v r pw i t hs t o c h a s t i cd e m a n d s ， 简称v r p s d ) ，随机客户的v r p ( v r pw i t hs t o c h a s t i cc u s t o m e r s ，简称v r p s c ) ， 随机客户随机需求的v r p ( v r pw i t hs t o c h a s t i cc u s t o m e r sa n dd e m a n d s ，简称 v r p s c d ) t 2 3 1 。 在车辆路径问题中，由于人类认识事物的模糊性，许多因素可能具有一定的 模糊特征，例如，估计从一个节点到另一个节点大约须费时2 0 分钟等。在主观估 计旅行时间时，没有人会宣称将费时1 7 分钟。这种旅行时间的估计不是客观测量 的结果，它是随决策者不同而会相应变化的主观估计。旅行时间通常被看作随机 变量对待，在这种情况下，需要对旅行时间进行测度并建立特定的概率密度函数。 但在许多情况下，决策者需要根据其经验获知绝对旅行时间进行主观估计，将旅 行时间表述成诸如“短”、“长”、“大约x x 分钟”等模糊语言。因此，研究模糊信 息条件下的车辆路径问题具有重要的现实意义。但是，但目前为止，对这个问题 的研究还很少，相关文献也只有寥寥数篇，下面就把这些文献做一个简单介绍。 p e r i n c h e r r y 和k i c u c h i l 研究了模糊环境下的转载转乘问题【2 4 1 。所谓转载问题 就是在存在中间节点可存储货物满足今后需求的网络中，在供应点和需求点之间 优化货物和服务的优化配置。输入信息是需求、供给、运输成本和转运点的存储 成本。在多数现实生活问题中，这些信息多以估计形式给出，不是很精确。 p e r i n c h e r r y 和k i c u c h i 引入了模糊线性规划原则处理模糊输入信息条件下的转运 问题。他们假设可获得的供应量和需求量是模糊的，而各位置间的旅行时间以及 相关费用是精确信息。p e r i n c h e r r y 和k i c u c h i 认为模糊转运问题的目标不总是费 用最小化，而是以“合理的费用”，安排运输。此处，“合理的费用”用模糊集表示。 带模糊时间窗的多车型车辆调度模型研究 在题为“f u z z ys e tt h e o r ya p p r o a c ht ot h ev e h i c l er o u t i n gp r o b l e mw h e nd e m a n d a tn o d e si su n c e r t a i n ”( 1 9 9 6 ) 的文献中，t e o d o r o v i c 和p a v k o v i c 研究了单车场情况 下，具有模糊客户需求的车辆路径问题【2 5 1 。t e o d o r o v i c 和p a v k o v i c 假设各节点的 需求只是大概知道，并用三角模糊数表示这样的需求。而其他有关信息，如车场 位置、各个待服务的节点位置以及车辆的运载能力等都是己知的。目的是设计一 系列最小化总费用的车辆路径。 t e o d o r o v i c 和p a v k o v i c 运用g i l e t t 和m i l l e r 提出的s w e e p i n g 算法【2 6 1 ，首先 任意选择一个种子点( s e e dp o i n t ) ，按其他各点与原点连线与种子点与原点连线的 夹角从小到大( 顺时针方向) 的顺序逐步加入当前车辆路径，直至某点由于违反约 束( 如时间约束，车辆运载能力约束等) 不能再加入。此时，以该点作为种子点， 重复以上过程，形成一新的路径，直至所有节点都分配完毕。随着客户的加入， 车辆剩余能力逐步减小，在确定条件下，很容易确定车辆剩余能力以及车辆能否 继续服务下一节点。但在模糊信息条件下，在安排路径时，车辆剩余能力和下一 节点需求都是模糊的，有些情况下，车辆能否满足下一节点需求并不确切知道， 那么，此时的车辆路径该如何安排? t e o d o r o v i c 和p a v k o v i e 通过引入决策者偏好 这一模糊表述，运用模糊推理算法，解决了这一问题。t e o d o r o v i c 和p a v k o v i c 提 出了两种模糊推理算法。在算法1 中，作者仅仅考虑了车辆剩余能力因素；而在 算法2 中，作者同时考虑了车辆剩余能力和下一节点需求量两个方面的因素。 随着模糊集的推广，国内对模糊车辆路径问题的研究也活跃起来，张建勇， 李军( 2 0 0 6 ) 对具有模糊旅行时间的v r p 问题进行了研究，文献对具有模糊旅行时 间的v r p 问题进行简单描述的基础上，构建了相应的数学模型，并通过将模糊逻 辑、模糊控制方法与遗传算法进行有效结合，提出了求解该问题的一种混合遗传 算法【2 。朱晓锋，蔡延光( 2 0 0 8 ) 对带时间窗的模糊需求多类型车辆路径问题的求解 算法进行了研究，对于表示节点模糊需求，文章采用了三角模糊数【2 引。最后作者采 用禁忌搜索算法解决了相关问题。张建勇，李军，郭耀煌( 2 0 0 8 ) 为有效解决动态 环境下考虑客户偏好的车辆路径优化问题，在对反映客户偏好的模糊预约时间以 及具有模糊预约时间的动态车辆路径问题进行简单描述的基础上，给出了该问题 的求解思路，即当新客户出现时，在保证车辆运载能力和配送时间的可行性的前 提下，由最佳车辆在最合适的时间为该新客户服务【2 引。基于此思路，设计了由前 后双向可推的推一碰过程确定最佳配送时间的插入启发式算法。在该算法中，通 过对客户的配送时间的前推或后推，确定能使所有客户的综合满意度达到最大的 配送时间调整方案。最后，文章指出更复杂的动态模糊车辆路径问题可能具有模糊 旅行时间、模糊客户需求时间、模糊费用系数等多重模糊性。进一步的研究可从 这些方面入手，寻找解决这些问题的启发式或亚启发式算法。 从对模糊信息车辆路径问题的研究看来，利用模糊理论解决一系列的车辆路 硕上学位论文 径问题一方面能推动车辆路径问题不确定性的研究，另一方面能解决实际配送中 的遇到问题，具有理论与实践双重意义。 由于车辆路径问题研究非常活跃，阶段性成果也非常的多，将近年来国内外 与本文相关的研究文献进行了总结，见表2 1 ，表2 2 。 表1 1 国外与本文相关研究文献表 带模糊时间窗的多车型车辆调度模型研究 表1 2 国内与本文相关研究文献表 8 硕士学位论文 ( 续表) 从文献列表中可以看出，由于车辆调度问题本身就是个复杂的问题，因此大 多数的研究是针对某一种情形来进行研究的。而实际生活中往往是多种约束并存， 如何将其他们的研究整合在一起，并且找到较优的算法求解是未来车辆调度问题 研究的热点和难点。另一方面，虽然近年来模糊理论被用到车辆调度问题中，但 事实上并没有完全发挥出模糊理论的优点，模糊理论适用于对主观因素的评价分 类，因此，一方面要充分考虑车辆调度问题的决策者的模糊判断能力，另一方面， 当今社会越来越强调优秀的服务水平，解决车辆路径问题时也要站在客户的角度 出发去探讨如何提高车辆调度问题中的客户满意度等问题。 1 3 研究内容和思路 1 3 1 研究内容 由于v r p 也要由人参与决策，在决策过程中难免会受到人类认识事物的模糊 性影响，所以模糊v r p 也应该是v r p 中的一个重要研究方向，然而目前对模糊 v r p 的研究只有寥寥数项。 本文的研究是在紧跟国际学术前沿基础上，从引入模糊时间窗入手，利用模 糊隶属度函数刻画由时间引起的客户满意度的变化，基于物流服务成本与服务水 平的背反定律讨论车辆路径问题的优化，对于实际配送中存在的多车型问题，提 出了考虑不同车型具有不同容量，不同的出行费用及旅行费用的多车型车辆路径 模型。具体研究内容是： 第1 章是绪论部分，主要介绍了论文的选题背景及其意义，对带时间窗的车 辆调度问题，多车型车辆调度问题以及模糊信息车辆调度问题的相关研究进行了 综述，并介绍了论文的主要研究内容、思路与研究方法。 第2 章介绍车辆路径问题及其扩展问题，对本文所研究的带模糊时间窗的多 车型车辆调度问题给出明确的定义。讨论并确定模糊隶属度函数的选取。 带模糊时间窗的多车型车辆调度模型研究 第3 章对本文研究的问题做一系列的合理假设，介绍相关的符号后提出带模 糊时间窗的多车型车辆路径问题模型，并对模型进行解释。 第4 章设计求解模型的算法。比较求解v r p t w 问题的相关算法，介绍本文 采用的模拟退火算法，设计模型求解的算法流程图，讨论核心步骤的实现。构造 具有一定规模的算例，通过编写相关程序，对算例进行求解。通过对不同满意度 下的配送成本的讨论，以益阳烟草配送项目为支撑，体现本模型的实用性以及算 法的可行性和优越性。 最后，对全文的研究进行总结，提出结论，对研究的不足之处进行展望