（交通运输规划与管理专业论文）基于聚类分析和遗传算法的带时间窗车辆路径问题研究.pdf

福建农林大学2 0 0 9 届硕士学位论文 基于聚类分析和遗传算法的带时间窗车辆路径问题研究 摘要：车辆路径问题( v r p ) 是物流配送过程中的关键问题之一，随着物流配送 行业竞争日益激烈和客户对物流配送时效性要求越来越高，对v r p 的研究，尤其 是对带时间窗车辆路径问题( 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 w s ， v r p t w ) 的研究，不仅可以帮助运输企业提高服务水平，为顾客提供快捷、准 时、安全、舒适的服务，解决发展电子商务中速递这一“瓶颈”约束，而且有助 于企业节约运输成本，改善车辆利用效率，缩短生产周期，加速资金周转，实现 资源的合理配置，汲取“第三利润源泉”的财富，因此更加具有实际意义。 本文在认真分析国内外v r p 研究现状的基础上，对带时间窗车辆路径问题进 行深入分析，考虑道路拥挤程度对配送的影响，引入交通工程学中的道路阻抗系 数，进而建立了带时间窗车辆路径问题的的数学模型。针对大规模车辆路径问题 的特点，应用两阶段启发式算法求解，首先应用k - m e a n s 聚类分析对配送网点进 行配送区域划分，将大规模的v r p 简化成小规模的v r p ，降低计算量，提高求 解速度；其次结合使用遗传算法，应用一种新颖的染色体编码和交叉方式，改进 了传统的遗传算法，使求解过程大大简化，从而为快速、有效地优化带时间窗车 辆路径问题创造了有利条件。通过m a t l a b 编程，有效地实现了对路径的自动 寻优。并通过实例，进一步将运算结果与其他优化算法进行比较，证明了本文提 出的改进遗传算法在处理路径优化问题上具有明显的优势，在所用配送车数量最 小的前提下，可得到一个相对最短的行驶路线，实现总运行成本最低的目的。 关键词：车辆路径问题遗传算法聚类分析 时间窗 中图分类号：u l1 6 2文献识别码：a 基于聚类分析和遗传算法的带时间窗车辆路径问题研究 r e a r c ho nt h ev 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 w s b a s e do nc l u s t e ra n a l y s i sa n dg e n e t i ca l g o r i t h m a b s t r a c t ：v e h i c l er o u t i n gp r o b l e m ( v r p ) i so n eo ft h ek e yp r o c e s s e so fl o g i s t i c s d i s t r i b u t i o n a sc o m p e t i t i o n sa m o n gl o g i s t i c sd i s t r i b u t i o ni n d u s t r ya r eg e t t i n gm o r e a n df i e r c e ra n dc u s t o m e r s r e q u i r e m e n t sf o rat i m e e f f e c t i v el o g i s t i c sd i s t r i b u t i o na r e b e c o m i n gm o r ea n dm o r ei n t e n s e ，s t u d i e so nv r p ，e s p e c i a l l yv e h i c l er o u t i n g p r o b l e mw i t ht i m ew i n d o w s ( v r p t w ) ，a r ep r a c t i c a l l y s i g n i f i c a n to ne v e r ya s p e c to f l o g i s t i c sd i s t r i b u t i o ni n d u s t r y t r a n s p o r t a t i o nc o m p a n i e sc a ni m p r o v et h e i rs e r v i c e s b yp r o v i d i n gt h e i rc u s t o m e r s 埘t hf a s t ，p u n c t u a l ，s a f ea n dc o m f o r t a b l es e r v i c e s ，t h e i r t r a n s p o r t a t i o nc o s t sc a nb ec u td o w nb yi m p r o v i n gv e h i c l e su t i l i z a t i o n b e s i d e s ，f a s t s p e e d ，a sa ”b o t t l e n e c k ”t ot h ed e v e l o p m e n to fe - c o m m e r c e ，i sl a r g e l ys o l v e d p r o d u c t i o nc y c l e sa r es h o r t e n e da n dc a p i t a lt u r n o v e ri sa c c e l e r a t e d ，t h e r e f o r e ，r a t i o n a l a l l o c a t i o n so fr e s o u r c e sc a nb er e a l i z e da n df o r t u n e sf r o m ”t h et h i r dp r o f i ts o u r c e ”c a n a sw e l lb em a d e u n d e ras e r i o u sa n a l y s i so nt h er e s e a r c h e ds t a t u so fv r pb o t hi nc h i n aa n d a b r o a d ，v r p t ww a sp a r t i c u l a r l ya n a l y z e di nd e p t h c o n s i d e r i n gt h ei m p a c t sf r o m r o a d sc o n g e s t i o no nt h ed i s t r i b u t i o n m a t h e m a t i c a lm o d e l so nv r p t ww e r eb u i l tw i t h t h ei n t r o d u c t i o no fr o a dr e s i s t a n c ec o e f f i c i e n t t w o p h a s eh e u r i s t i ca l g o r i t h mw a s a p p l i e dt os o l v et h em o d e l sa c c o r d i n gt ot h ec h a r a c t e r i s t i c so fl a r g e - s c a l ev r p f i r s t l y ， l a r g e - s c a l ev l 冲w a ss i m p l i f i e di n t o s m a l l s c a l ev f u pb yu s i n gk - m e a n sc l u s t e r a n a l y s i st od i v i d et h ed i s t r i b u t i o nn e t w o r ki no r d e rt or e d u c ec o m p u t a t i o nw h i l e i m p r o v et h ec o m p u t i n gs p e e d ；s e c o n d l y ，a ni m p r o v e dg e n e t i ca l g o r i t h m ，w h o s e c h r o m o s o m ec o d i n ga n dc r o s s w a y sw e r ec h a n g e dt oab e t t e rp a t t e r n ，w a sa d o p t e dt o g r e a t l ys i m p l i f yt h es o l u t i o np r o c e s sa n dc r e a t ea d v a n t a g e st oq u i c k l ya n de f f e c t i v e l y o p t i m i z ev r p t w f i n a l l y ，a na u t o m a t i co p t i m i z a t i o n o nd e l i v e r yr o u t e sw a s e f f e c t i v e l yw o r k e do u tt h r o u g ht h ei m p l e m e n t a t i o no fmat l a bp r o g r a m m i n g c o m p a r i s o n so fc o m p u t e dr e s u l t sw i t ho t h e ri m p r o v e dg e n e t i ca l g o r i t h mw e r ec a r r i e d o u tu n d e ras t u d yc a s et of u r t h e ri n d i c a t et h a tt h ei m p r o v e dg e n e t i ca l g o r i t h mi nt h i s p a p e rh a v ec o n s i d e r a b l ea d v a n t a g e so ns o l v i n gv r p t w a n do nt h ep r e m i s eo f l i 福建农林大学2 0 0 9 届硕士学位论文 m i n i m i z a t i o nu s e dv e h i c l e s ，ar e l a t i v e l ys h o r t e s tr o u t ec a nb ew o r k e do u t ，t h u s e n s u r i n gt h el o w e s tt o t a lo p e r a t i n gc o s t s k e yw o r d s ：v e h i c l er o u t i n gp r o b l e m ；g e n e t i ca l g o r i t h m ；c l u s t e ra n a l y s i s ；t i m e w i n d o w s c l cn u m b e r ：u 11 6 2d o c u m e n tc o d e ：a 1 1 i 独创性声明 本人声明，所呈交的学位( 毕业) 论文，是本人在指导教师的指导下独立完成的研究 成果，并且是自己撰写的。尽我所知，除了文中作了标注和致谢中已作了答谢的地方外， 论文中不包含其他人发表或撰写过的研究成果。与我一同对本研究做出贡献的同志，都在 论文中作了明确的说明并表示了谢意，如被查有侵犯他人知识产权的行为，由本人承担应 有的责任。 学位c 论文作者亲笔躲科 如矽。乡哆 论文使用授权的说明 本人完全了解福建农林大学有关保留、使用学位( 毕业) 论文的规定，即学校有权送交 论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部分内容，可以采用 影印、缩印或其他复制手段保存论文。 保密，在年后解密可适用本授权书。 口 不保密，本论文属于不保密。 口 学位( 毕业) 论文作者亲笔签名 指剥币亲笔签名：；苏汐诹 唧显嗍蹿。夕i 日凝：抛9 6 1 f 福建农林大学2 0 0 9 届硕士学位论文 1 绪论 1 1 研究背景 随着我国经济的高速增长，当前物流活动呈现出前所未有的频繁，2 0 0 8 年 l 9 月份，全国货物运输量较上年同期增长1 3 7 ，货物周转量较上年增长 1 6 1 。7 、8 、9 三个月的增速不仅没有下降，而且增幅持续上升，增幅分别为 1 5 6 、1 5 7 、1 6 1 ，预计2 0 0 9 年公路运输车辆市场依然稳定并将保持上升 态势【l 】。但是目前我国物流管理仍然比较落后，物流行业普遍面临着专业化程度 低、高耗低效等问题。另外，随着新世纪的到来，电子商务的蓬勃发展，市场竞 争进步加剧，企业要保有和争得市场，不仅要在产品的质量、功能上下功夫， 更重要的还是要在优质服务上下功夫。 据统计我国车辆的运输成本是欧洲或美国的3 倍，全国运输汽车的空驶率约 3 7 ，其中汽车物流企业车辆空驶率达3 9 ，存在着回程空驶、资源浪费、运输 成本高等问题【2 】。可见，减少运输费用是有效减少物流成本的重要方面。对于物 流中心和第三方物流企业的货物配送，运输车辆调度和线路优化是工作的重点， 正确合理的调度可以有效减少车辆的空驶率，实现合理路径运输，从而有效减少 运输成本，节约运输时间，提高经济效益。 车辆路径问题( v e h i c l er o u t i n gp r o b l e m ，缩写为v r p ) 【3 j 是物流配送过程中 的关键问题之一，该问题作为网络优化的基本问题之一而一直受到学者们的关 注。v r p 一般指对一系列的客户点，组织适当的行车路线，使车辆有序地通过 它们，在满足一定的约束条件( 如货物需求量、车辆容量限制和时间窗限制等) 下，达到一定的目标( 如运距最短、费用最少、车辆数尽量少和客户满意度最佳 等) 。v r p 的研究作为发展敏捷后勤的一个重要组成部分，是实现物流现代化的 基础和前提条件，不仅有助于改变我国物流管理落后的现状，也有助于解决城市 交通拥挤、能源短缺、大气污染等困扰人们的社会问题，实现效率、资源、环境 和价值观念各方面的内在统一，促进物流业的进步和社会经济的可持续发展。 随着社会经济的不断发展，人们对物流配送的实效性要求越来越高，对配送 时间提出了明确要求，一般都规定了一个希望被访问的时问窗，要求在此时间窗 内接受服务，这就产生了有时间窗的车辆路径问题( v e h i c l er o u t i n gp r o b l e mw i t h 基于聚类分析和遗传算法的带时间窗车辆路径问题研究 t i m ew i n d o w s ，缩写为v r p t w ) ，它是在v r p 的基础上增加了客户要求访问的 时间窗约束。这就对物流配送技术提出了新的挑战。随着物流配送行业竞争日益 激烈和客户对物流配送时效性要求越来越高，对v r p 的研究，尤其是对v r p t w 的研究，不仅可以帮助运输企业提高服务水平，为顾客提供快捷、准时、安全、 舒适的服务，解决发展电子商务中速递这一“瓶颈”约束，而且有助于企业节约 运输成本，改善车辆利用效率，缩短生产周期，加速资金周转，实现资源的合理 配置，汲取“第三利润源泉”的财富，因此更加具有实际意义。 1 2 国内外研究现状 车辆路径问题最早是由d a n t z i n g 和r a m s e r 于1 9 5 9 年提出的，一般定义为： 对一系列装货点和( 或) 卸货点，组织适当的行车路线，使车辆有序地通过它们， 在满足一定的约束条件下( 如货物需求量、发送量、交货时间、车辆容量限制、 行驶里程限制、时间限制等) 一卜，达到一定目标( 如路程最短、费用最少、时间 尽量少、使用车辆数尽量少等) 。由于其应用的广泛性和经济上的重大价值，一 直受到国内外学者的广泛关注。 在经典v r p 的基础上，车辆路径问题在学术研究和实际应用上产生了许多 不同的延伸和变化型态，包括旅行商问题( t r a v e ls a l e m a np r o b l e m ，t s p ) ( t s p 可看 作v r p 的一个特例，即当只包括一条路径，且没有能力约束) 、带能力约束的车 辆路径问题( c a p a c i t a t e dv e h i c l er o u t i n gp r o b l e m ，c v r p ) 、带时间窗的车辆路径 问题( 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 w s ，v r p t w ) 、追求最佳服务时间 的车辆路径问题( v e h i c l er o u t i n gp r o b l e mw i t hd e f i n e dt i m e ，v r p d t ) 、多车种 车辆路径问题( f l e e ts i z ea n dm i xv e h i c l er o u t i n gp r o b l e m ，f s v r p ) 、车辆多次使 用的车辆路径问题( v e h i c l er o u t i n gp r o b l e mw i t hm u l t i p l eu s eo f v e h i c l e ，v r p m ) 、 考虑收集的车辆路径问题( v e h i c l er o u t i n gp r o b l e mw i t hb a c k h a u l s ，v r p b ) 、随机 需求车辆路径问题( v e h i c l er o u t i n gp r o b l e mw i t hs t o c h a s t i cd e m a n d ，v r p s d ) 、 动态车辆路径问题( d y n a m cv e h i c l er o u t i n gp r o b l e m ，d v r p ) 、满载非满载v r p 、 双向v r p 等4 】。车辆路径问题的求解方法主要足精确算法( 如分枝定界法、切 平面法、动态规划法) 和启发式算法( 详见图1 1 ) 。 2 福建农林大学2 0 0 9 届硕士学位论文 生 辆 路 径 问 题 的 求 解 方 法 图l - l车辆路径问题的求解方法 f i g u r e l 1 t h es o l u t i o nm e t h o do f v e h i c l er o u t i n gp r o b l e m 1 2 1 国外研究现状 经典v r p 可描述如下：有多个货物需求点( 或称顾客) ，已知每个需求点的 需求量及位置，至多用m 辆汽车从配送中心( 或中心仓库) 送货，每辆汽车载 重量一定，安排汽车路线，要求每条路线不超过车辆载重量和每个需求点的需求 3 蓟 叟 舭 搬 法 翩 裣 法法索火络 法 近 法 法 类 弼 算 算 搜 退 网 间 内 断rlil 法 样 觯 法 法 施 觥 就 黜 法 黜 舫 黻 黻 一 一 一 捌 一 蝴 撇 鼾 眺 赫 瑚 r。厂llj 1 0 0 ) ，交通网络复杂 的车辆线路优化问题，现有算法存在一些问题：精确算法求解大规模的v r p 显 然是不现实的，因为该算法引入严格的数学方法，因而无法避开指数爆炸问题， 从而使该类算法只能有效求解中小规模的v r p ，且精确算法的计算量一般随问 题规模的增大呈指数增长，在实际中应用范围很有限；遗传算法、禁忌搜索算法、 模拟退火算法、蚁群算法、粒子群算法等亚启发式及其混合算法则因问题规模增 大时，劣解增多而大大降低了解的搜索效率，无法实现搜索时间和解的性能两者 之间的平衡。 1 3 研究意义 车辆路径问题的求解方法一般分为精确算法和启发式算法。精确算法指可求 出其最优解的算法，但对车辆路径问题来说，精确算法很难在合理的时间内得出 最优解，其原因在于车辆路径问题是一类n p h a r d ( n o n - d e t e r m i n i s t i cp o l y n o m i a l ) 问题，这类问题一般具有大量的约束条件和变量，并且约束条件和变量的多少对 计算时问是非线性的，即随着约束条件和变量的增多，会产生指数爆炸现象。同 时，随着所考虑的约束条件的增多，除了要考虑成本的因素之外，还要考虑配送 时间和环境等方面的因素，这就使问题的建模和求解变得更加复杂。而遗传算法、 9 基于聚类分析和遗传算法的带时间窗车辆路径问题研究 禁忌搜索算法、模拟退火算法、蚁群算法、粒子群算法等亚启发式及其混合算法 则因问题规模增大时，劣解增多而大大降低了解的搜索效率，无法实现搜索时间 和解的性能两者之间的平衡。因此，为解决大规模的车辆路径问题，需要有一种 时间上耗费较少、求解性能较优的算法，来满足实际工作的需要。本文所指的大 规模足指客户数比较大，以客户数1 0 0 为界限的。 针对大规模车辆路径问题，本文提出应用聚类分析和遗传算法来求解大规模 车辆路径问题，通过聚类分析把大规模的车辆路径问题简化为小规模的车辆路径 问题，从而解决由于问题规模增大而引起解的搜索困难，然后对传统遗传算法进 行改进，提高算法的整体求解效率，从而为解决大规模车辆路径问题提供一种新 的思路和方法，为实际物流配送提供切实可行的线路优化手段，达到降低物流成 本，提高企业利润和客户满意度的目的，本研究具有重要的现实意义。 1 4 研究内容 本文收集了国内外学者专家对车辆路径问题的相关研究成果，对文献资料进 行整理、分类，作为数学模型建立的理论基础，提出应用两阶段法求解v r p ， 即第一阶段，采用k - m e a n s 聚类分析对配送网点进行区域划分，将大规模v r p 简化小规模v r p 来求解；第二阶段是对同类中的客户点进行线路规划，本文采 用全局搜索能力较强的遗传算法求解，并对遗传算法进行改进，然后用m a t l a b 实现本文提出的算法，并以s o l o m o n 的标准数据中c 1 0 1 系列数据进行数值实验， 得出用两阶段法具有更强的寻优性能。本论文的丰要研究内容如下： ( 1 ) 根据配送中心的条件、道路情况及客户的需求等实际情况，将车辆行 驶的总路程尽量少、车辆延误时间尽量少作为目标函数的主要考虑因素，建立带 时间窗车辆路径问题的数学模型。 ( 2 ) 针对标准遗传算法存在的问题，提出用遗传算法求解v r p 问题时的改 进策略，为下一步的研究做准备。 ( 3 ) 应用k - m e a n s 聚类分析对配送网点进行配送区域划分，设计更适合于 带时问窗车辆路径问题优化的改进型遗传算法，并通过实例进行验证。 1 0 福建农林大学2 0 0 9 届硕士学位论文 2 车辆路径问题的数学模型分析研究 车辆路径问题( v r p ) 是从旅行商问题( t s p ) 演化而来，旅行商问题是车 辆路径问题的一个特例，它只包括一条路径问题，且没有能力约束的。而有时间 窗车辆路径问题是在经典车辆路径问题基础上根据学术研究和实际应用延伸和 变化的一种型态，它们三者之间是一脉相承的、相互联系的。 2 1 旅行商问题( t s p ) 的数学模型 旅行商问题可以描述为：安排一条旅行线路，使得旅行商从起点出发，经过 每个城市一次，最终返回原地，而总的旅行距离最短，该问题的数学模型为【删： v = 0 ，1 ，刀) 点集，表示旅行商要经过的城市，其中0 表示起点； a = ( f ，歹) lf ，j = o ，1 ， ，f 弧集，表示旅行商可能经过的路段集合； c = kl ( f ，j ) e 彳) 费用集合，劬表示旅行商经过对应路段( i ，) 时的花费，如 时间、距离、行驶费用等。 求解t s p 即在加权图g = 【y ，a ，c 】中找到总费用最小的汉密尔顿( h a m i l t o n ) 回路。 定义变量柳= ，三若弧g 窑贝乒线路上 建立以下模型： m i n f = z z c 口勖 ( 2 一1 ) s 1 z x , j = 1 j = o ，l ，” ( 2 2 ) = lf = 0 ，l ，玎 ( 2 - 3 ) 勋s i s - iv s g 矿一 o ( 2 - 4 ) j ，e 3 勘( 0 ，1 )f = o ，1 ，刀；j = 0 ，l ，打 ( 2 5 ) 目标函数( 2 1 ) 使旅行商巡游费用最小；约束( 2 2 ) ，( 2 3 ) 保证每个城市 只被访问一次；约束( 2 - 4 ) 为支路消去约束，即消去构成不完整线路的解。 基于聚类分析和遗传算法的带时间窗车辆路径问题研究 2 2 经典车辆路径问题( 心) 的数学模型 经典车辆路径问题( v r p ) 可具体描述如下：设有一场站( d e p o t ) ，共有k 辆货车，车辆容量为q ，有 r 位顾客需要服务，每位顾客有其需求量9 ，车辆 从场站出发对客户进行配送服务最后返回场站，要求所有顾客都被服务，顾客需 求由一次配送完成，不能违反车辆容量的限制，目的是所有车辆行驶的总距离最 小。图一为v r p 示意图( 图中矩形表示场站，小圆圈表示需要服务的顾客，箭头 线表示车辆行驶路径) 。 图2 - 1车辆路径问题示意图 f i g u r e 2 1 t h es k e t c hm a po f v e h i c l er o u t i n gp r o b l e m 经典v r p 在满足以下约束条件情况下，求解m 辆车的总行驶成本最小： ( 1 ) 每条路径的起点和终点都是供货点； ( 2 ) 每个客户只应该被车辆服务一次； ( 3 ) 每条路径中的所有客户需求的总和不能超过车辆的载重量o 经典v r p 模型用数学语言可以描述为删： y k , ：c 前舭噤辄就( 圳，1 ，“= l ，2 ，问 2 1o 否则 u 刈，l ，m 拈l ，厶球j 矿c 车辆枞囊需驰崎= o ，l ，朋，2 ，“)孙2 1o否则； 【f ，j 刈，l 职拈l ，z ，k j 福建农林大学2 0 0 9 届硕士学位论文 以最小化系统运行费用为目标，建立如下车辆路径问题模型： m i n f = 白x 肛 ( 2 6 ) ， s j g ，y 村q ( 七= 1 , 2 9 o - , k ) ( 2 7 ) y - y 白= 1 ( i = 1 , 2 ，刀) ( 2 8 ) 膏 儿o = k ( 2 9 ) x 班= y 扫( ，= 1 , 2 ，) ( 2 1 0 ) y x 砸= y k , ( f = 1 , 2 ，刀) ( 2 1 1 ) ， x 壮 o ，l o ，j = o ，1 ，；k = 1 , 2 9 - , - 9 k ) ( 2 一1 2 ) y 打 0 ，1 ) ( f = o ，l ，一，；七= 1 , 2 ，k ) ( 2 1 3 ) 模型中，配送中心编号为0 ，客户点编号为l ，2 ， ，配送中心和客户点均点 f ( i = 0 ，1 ，2 ，拧) 表示。 目标函数( 2 6 ) 是使车队总的服务费用最低；约束( 2 7 ) 为车辆装载能力约 束，即每条配送线路j | i 的送货量不能超过车的最大载重量；约束( 2 8 ) 保证每个 客户都被服务；约束( 2 9 ) 保证车辆都从配送中心出发并返回到配送中心；约束 ( 2 1 0 ) 、( 2 1 1 ) 保证如果客户点i ，j 在车辆k 的行驶线路上，那么客户点i ，j 将由车辆k 服务。 2 3有时间窗车辆路径问题( 心t w ) 的数学模型 2 3 1 时间窗问题描述 时间窗是一个时问段【e t , ，三丁，】，是由客户要求的最早服务时间e 兀和最晚 服务时问r ，确定的一个服务时间区间。在v r p 的基础上给每个顾客加上服务 所允许的时间窗( t i m ew i n d o w s ) 约束，v r p 就扩展成了v r p t w 。 2 3 2 时间窗车辆路径问题的分类 由于时间窗车辆路径问题的复杂性，如果严格按照顾客设定的服务时问为其 服务，可能造成企业的配送成本增加。如果允许在某些客户点适当地延误，可能 使运输成本大为减少，即对该延误现象给予一定的惩罚。所以根据决策者在对客 1 3 基于聚类分析和遗传算法的带时间窗车辆路径问题研究 户满意和成本二者权衡时偏好的不同时，若按照客户满意度来分，时间窗还可以 分为硬时间窗( h a r dt i m ew i n d o w s ，简称h t w ) 和软时间窗( s o f tt i m ew i n d o w s ， 简称s t w ) 以及混合时间窗( m i x e dt i m ew i n d o w s ，简称m 丁w ) 三种情况。 ( 1 ) 硬时间窗( h a r dt i m ew i n d o w s ，简称h t w ) ：指配送车辆必须在规定 时间段内将配送货物送达到顾客手中，顾客拒绝接受在此时问段之外提供的服 务。如图2 2 为一惩罚函数( p e n a l t yf u n c t i o n ) ，当配送货物送达时间超过了规 定的时间段【e 兀，三7 f 】，其惩罚值p ( f ) 等于一个非常大的正值，以表示硬时间窗 的限制。 p ( ，) m 乃上正 图2 - 2 硬时i 司窗 f i g u r e 2 2 h a r dt i m ew i n d o w s 硬时间窗的车辆路径问题( v r p h t w ) 中，车辆可以在最早服务时间之前 到达客户所在地，但必须等待直至到了最早服务时间才能对客户提供服务；另外 车辆不能在最晚服务时间之后到达客户所在地。如在j u s t i n t i m e 牛产系统中， 送货车辆到达时问若迟于指定的最晚到达时问，会导致整个牛产线的延误和闲 置，造成时间成本的增加和效率的降低，因此这种情况下往往不允许违背时间窗 的约束。对于硬时间窗车辆路径问题来说，服务所有客户所需的车辆数目也是决 策变量，一般来说，所用车辆越少，对应的成本也越小，如何用最少的车辆在不 违背车辆容量及客户时间窗的约束的前提下，为所有客户提供服务，也是决策者 关心的一个问题。因此在对硬时间窗车辆路径问题建模时确定的目标函数往往是 多目标且多层次的，根据具体要求的不同，目标函数的层次也不尽相同。通常， 首先最小化服务所有客户所需的车辆数目，因为每多增加一辆车意味着多增加一 1 4 福建农林大学2 0 0 9 届硕士学位论文 条服务路线和一名司机，其成本会高很多，而且需要的车辆越多，车队的购置成 本也越高；其次，对于使用同样数目车辆的情况，最小化总的行驶路程或行驶时 间。 ( 2 ) 软时间窗( s o f tt i m ew i n d o w s ，简称s t w ) ：指配送车辆如果无法将 货物在特定的时段【e 兀，n 】内送到顾客手中，则必须按照违反时间的长短施以 一定的罚金或其它惩罚法则。图2 3 就是一种可能的惩罚函数。 p ( f ) e 乃上正 图2 3 软时i 司窗 f i g u r e 2 3 s o f tt i m ew i n d o w s 带软时间窗的车辆路径问题v r p s t w 相对带硬时间窗的车辆路径问题 v r p h t w 来说放松了对时问窗的约束，这是因为在实际情况中，由于道路交通 流量，车辆的行驶速度以及客户的需求时间等不确定因素导致货物无法在规定的 时间窗内送到，如果采用硬时问窗的约束进行优化，将导致成本非常高，甚至可 能无解。而v r p s t w 只要求车辆应尽可能在客户指定的时间窗内以最小的总成 本为所有客户提供服务，允许一定程度的延误现象。显然，v r p s t w 较v r p h t w 具有更好的通用性。在实际运输规划中，决策者往往需要在客户满意度和成本二 者之间权衡，偏好不同决定了可以允许延误的程度不同。在v r p s t w 中，车辆 如果在最早服务时间之前到达客户所在地，需等待直至到了最早服务时间后才能 提供服务；如果在最晚服务时间之后到达客户所在地，则可能导致客户满意度降 低，隐性成本的增加。因此应尽量避免延误现象的发生，如果发生，应加以惩罚， 惩罚的具体程度可由决策者设定。在对v r p s t w 建模时，表现为目标函数增加 了一项惩罚项，它具体体现在目标函数值( 对应服务成本) 的增加。 基于聚类分析和遗传算法的带时间窗车辆路径问题研究 混合时间窗( m i x e dt i m ew i n d o w s ，简称m t w ) ：在系统中有些顾客属于 硬时间窗，有些顾客属于软时间窗对同一顾客，又可能软、硬时间窗混合使用。 在实际的配送工作中，车辆如果能在最佳时间段【e 丁，三兀】内将货物送达到顾客 手中，则不处罚；若在图2 - 4 中的【口，e 兀】或 l t ，e l m 段内才送达，则顾客的满 意度降低，将处以一定的惩罚转化为惩罚函数，并且顾客不接受在上述两个时间 段以外的时间收货。 p ( ，) m 口 e 乃l 乃 e， 图2 - 4 混合时间窗 f i g u r e 2 4 m i x e dt i m ew i n d o w s 此外，如果时间窗按形式来分有单边和双边时间窗之分，所谓单边时间窗足 从双边时间窗中去掉了对最早服务时间的限制，客户不再要求车辆最早服务时 间，而只要求在某个时间点之前为客户提供服务。 目前研究最多的是带双边时问窗的车辆路径问题，即只有在客户指定的时问 窗口内为其提供服务。若车辆在客户指定的最早时问之前到达客户所在地，则需 要等待直到了客户要求的最早时间，才能对客户提供服务；此外，车辆必须在最 晚服务时间之前为客户提供服务，否则不可行。 2 3 3 有时间窗车辆路径问题的约束条件 随着社会经济的不断发展，人们对物流配送的实效性要求越来越高，研究带 时间窗车辆路径问题更加贴近实际，更具有实际意义，但带时间窗车辆路径问题 本身的复杂性和难度，本文所研究的带时间窗车辆路径问题是指单车场、单车型、 1 6 福建农林大学2 0 0 9 届硕士学位论文 非满载、纯装货或纯卸货的带软时间窗车辆路径问题( v l 擅t w ) 。在对v r p t w 建 模时，确定的目标函数往往是多目标且多层次的，根据具体要求的不同，目标函 数的层次也不尽相同，其需要实现的主要目标是准时到达与成本最低，也就是在 满足客户对送货时间要求和其他需求的基础上，合理安排车辆路线，使得车辆总 运行成本尽可能少。结合问题的实际背景，特作如下假设描述： ( 1 ) 车场在本问题中，仅存在单一的车场，且车场位置己经确定，车场拥 有足够数量的车辆，保证满足所有客户的需求。 ( 2 ) 车辆性质在本问题中，所有车辆必须从车场出发，经客户点装货( 或 卸货) 后，必须回到车场，这样有利于车场对车辆进行管理调度所有的车辆均拥 有相同的载重限制，不允许超载运行所有车辆的行驶速度均认为相同每辆车可以 服务多个客户，但每个客户的货物只由一辆车配送。 ( 3 ) 客户需求性质在本问题中，所有客户的位置均己知且固定，所有客户 的需求也已知，且需求小于车辆的载重限制，客户对被服务时间有限制，所有客 户的需求形式均相同，或全部为装货问题，或全部为卸货问题。 ( 4 ) 道路性质在本问题中，考虑道路的实际交通情况，并用交通的道路阻 抗来表示，且认为所有客户之间、客户与车场之间均存在可连通的道路，所有道 路构成的网络为无方向性对称网络，即d ( i ，) = d ( j ，f ) ，f ，_ ，为问题中的任意客 户或车场。 ( 5 ) 所需满足的限制条件在本问题中，必须满足的限制条件是：每条 路线上各客户的需求量之和不超过车辆的载重限制；每条配送路线的长度不超 过车辆一次配送的最大行驶距离限制；每个客户的需求必须满足，且对某个客 户点，车辆到达时间限制在某一时间段内( 软限制) ，如果此约束不满足，则引 入惩罚函数；车辆的行车路线的总耗时不超过一个事先定下的数值，以满足客 户对供货时间的要求。问题求解的目标合理安排车辆路线，在满足所有客户需求 且不违反限制的情况下，使得车辆总运行成本尽可能少。在本论文中，车辆总运 行成本用路线总长度来代表。 2 3 4 有时间窗车辆路径问题( v r p t w ) 的数学模型 在过去的一些研究中，所建立的v r p t w 模型大多基于网络图，此类模型具 有决策变量、约束条件和目标函数等表示复杂抽象、难以理解的缺点，不利于 基于聚类分析和遗传算法的带时间窗车辆路径问题研究 v r p t w 的优化求解。本文在李军、郎茂祥、张潜等6 脯2 】研究的基础上，充分考 虑问题的约束条件和优化目标，建立优化物流配送路径的数学模型： ( 1 ) 模型中用到的参数 q ，( i = 1 ，2 ，玎) ：表示第f 个客户的需求量； g ( k - l ，2 ，k ) ：表示第k 辆车的载重量； g ：表示所有客户的集合，g = l ，2 ，1 ) ； g 。= g u o ) ，其中 0 ) 代表配送中心； g 。：表示由车辆k 服务的客户的集合； d 。：表示第k 辆车的最大行驶距离； c ，：表示车辆从客户f 到客户，的所有运输成本； ”：表示需要服务的客户总数； t 口：表示车辆从客户f 到客户j 的行车时间； ，：表示车辆从配送中心到客户f 的行驶时间； 岛：表示车辆在客户i 处的服务时间； 硝：表示车辆k 的出发时间； 砖：表示车辆k 的要求返回时问； e t ，：表示任务i 允许的最早服务时问； l t ，：表示任务f 允许的最晚服务时间； m ：为一个非常大的正常数； i1 车辆从点i 行驶到点， y 。= 。 ，”10否则 l 点i 的任务由车辆k 完成 x l k2 10否则 “。：表示从客户f 到歹的距离或时间； a 口：表示从客户i 到j 的路况系数 福建农林大学2 0 0 9 届硕士学位论文 ( 2 ) v r p t w 数学模型 1 ) 软时间窗v r p 软时间窗v r p 指不能按要求时间到达客户处，则处以惩罚值。 以c ：表示车辆在客户处等待单位时间的机会成本，c 3 表示车辆在要求时间后 到达客户处单位时间所处以的罚值。 若车辆在乃之前到达客户处，则产生成本c ：( e t 厂f ，) ；若车辆在三兀之 后到达客户处_ ，则处以罚值c ，( t ，- l t j ) ，最终将软时间窗v r p 的目标函数表示 为： k 打 n h” m i n f = x c ”y o k 九p + c 2 x m a x ( e t ，- t ，) ，0 】+ c 3 x m a x ( t ，一r ，) ，0 】 ( 2 1 4 ) 芹= 1 i = 1i = f ，；lj = l s j 9 ，x 聩g ，v k k x y 驰2 x j k ，g 。，七k y 肼= x 店，v i g o ，k k x 庙= l ，i = 1 2 ，7 0 s x ，i 珂 p 口y 驰sd i x 睹= 胛 。kf m 其中i = 0 吉五严11 其中f ：1 ，2 2 刀 丁：+ 圣y , j k ( t + 岛) r ：，k k 厶+ 岛+ 矿一m ( 1 一y 城) t j , v i ，j g ，k k ， 0 ，1 其中，( 2 1 ) 的c ，表示点i 到点j 的运输成本，可用( 2 2 6 ) 表示 f c o t + c l p 一当江0 时 c , j = l c 啪。当i 0 m 1 9 ( 2 - 2 6 ) ” d 乃 砂 缈 d 动 制 0 0 o o 乏 乏 乏 乏 乏 乏 p 口 q q q q p q q q q 基于聚类分析和遗传算法的带时间窗车辆路径问题研究 其中，c 。表示调用第k 辆车的固定费用，c ，。表示第k 辆车运行单位距离或 单位时间的费用，材p 表示从客户i 到_ ，的运行时间或运行距离。i i 过( 2 2 6 ) 同时 满足了3 个目标：车辆数最少，运输距离最短，总成本最低。这是因为c ， 与c 。，c 。是同向增减的。 其中，( 2 1 ) 的a 。表示点i 到点这路段的路况系数，可用( 2 2 7 ) 表示 a 。= + a ( 嚣 卢 ： c 2 2 7 ， 其中，q y 表示点i 到点这路段上的交通量；c 驴表示点f 到点歹这路段的 实际通过能力，即单位时间内路段实际可通过的车辆数；口、p 表示阻滞系数， 在美国公路局交通流分配程序中，a 、j b 参数的取值分别为口= o 1 5 ，芦= 4 ，也 可由实际数据用回归分析求得【6 3 】。通过( 2 2 7 ) 可知，路况系数随着交通量的增 大而增大。此系数贴近实际，并可以与运行时间或运行距离相结合使用。 ( 2 1 5 ) 式保证每条路经上各客户的需求量之和不超过配送车辆的载重量； ( 2 1 6 ) ( 2 1 7 ( 2 1 8 ) 保证了每个客户点的需求只有一辆车来服务； ( 2 1 9 ) 式保证了第k 辆车服务的客户数不超过所有客户的总数 ； ( 2 2 0 ) 式保证了每辆车的运输总距离不超过允许的最大行使距离的限制； ( 2 2 1 ) 式保证所有客户点的需求均被满足； ( 2 2 2 ) 式保证了每辆车均从配送中心出发并且都回到配送中心； ( 2 2 3 ) 式保证了出发时间和返回时间均在规定的时间窗内； ( 2 - 2 4 ) 式保证了车辆的行车路线的总耗时不超过一个事先定下的数值，以 满足客户对供货时间的要求； ( 2 2 5 ) 式限制了x 聩和y 触口n , 台t j 量匕取0 或l ； 2 ) 硬时间窗v r p 硬时间窗v r p 指每项任务的时间约束必须满足，否则为不可行解。对上式 进行修改得到： m i n f 2 y c y 城a 盯+ m