（管理科学与工程专业论文）正逆向物流一体化车辆路线问题研究.pdf

摘要 论文题目 正逆向物流一体化车辆路线问题研究 研究生姓名 李建 导师姓名 达庆利 授予单位 东南大学 小批量多批次配送已成为现代物流配送发展的一大趋势 而车辆路线问题是 其关键问题 目前配送通常将正向物流和逆向物流单独配送 这样会导致较高的 车辆空载率 为了节约资源 降低成本 本文将二者整合起来 研究正逆向物流 一体化车辆路线问题 分别从确定性 模糊性和动态三方面研究了该类问题的模 型和算法 论文的创新点主要体现在对车辆路线问题的拓展及相应有效算法的设 计 具体包括以下几个方面 1 租赁条件下的第三方物流多车型硬时间窗车辆路线问题研究 建立了以 车辆租赁费用和运行费用最小为目标的模型 并提出了结合模拟退火法的混合遗 传算法 该算法以优先满足最小费用车型的策略来分配多车型车辆 并采用客户 直接排列的方法以实现车辆数的变化 算例分析表明 该混合遗传算法具有较好 的搜索能力和求解稳定性 按最小费用分配车辆策略可为第三方物流企业车辆的 租赁决策提供重要依据 2 大规模同时集散货物路线问题的算法设计研究 首先应用分形理论中的 空间填充曲线法求解初始解 接着将当前解分解成几个独立的路线子集合 再用 新禁忌搜索算法求解每个路线子集合 最后将子集合求得的最好路线组成新的当 前解 其中新禁忌搜索算法集成了大量的邻域搜索方法 并采用了重起和扰动策 略 数据实验表明 该算法取得了新的最好解 为同时集散货物路线问题的求解 提供了新思路 3 业务繁忙环境下带时间窗的同时集散货物路线问题研究 以车辆数 运 输里程和完成运输任务总时间最小为目标建立了多目标模型 并提出了基于路线 集合划分的分解迭代算法以解决大规模问题 数据实验表明 该算法能有效解决 带时间窗的单向车辆路线问题和集散一体化的双向车辆路线问题 为物流配送提 供了有力的决策依据 4 配送车辆数和车辆工作时间有限的多车次同时集散货物路线问题研究 以车辆数和运输里程最小为目标建立了多目标模型 提出了允许不可行解的搜索 算法 该方法能同时解决路线安排和路线分配的问题 其中路线安排采用了4 种邻域搜索方法和重起策略 路线分配采用了初次分配和二次调整策略 算例分 析表明 该方法能有效地找到满意解 采用多车次安排路线比单车次安排路线更 加经济合理 5 逆向需求模糊的同时集散货物路线问题研究 建立了基于模糊置信度理 论的多目标模型 并提出了基于模拟的改进禁忌搜索算法来求解该模型 该算法 用模拟的方法计算路线失败值 在路线搜索中采用路线内部改善和路线间改善两 类邻域操作 而且采用了重起策略 算例表明 该算法优于传统的扫描算法 并 且正逆向物流整合与分别运输相比其运输费用显著减少 6 逆向需求动态出现的混合集散货物路线问题研究 该问题中逆向需求出 现的时刻 位置以及要求服务的时间和发货量事前是完全未知的 且具有时间窗 约束 将问题的求解过程分为静态和动态两阶段 每阶段分别用改进记录更新算 法求解 采用随机大邻域搜索法及重起和扰动策略来提高解的质量 并通过约束 邻域搜索范围和设计常量可行性检查两种策略来减少计算时间 数据实验表明 该算法是快速有效的 将动态出现的逆向需求实时整合到已有路线中 比单独安 排动态需求的配送更经济 关键词 车辆路线问题 同时集散 多车次 动态需求 模糊需求 亚启发 式算法 a b s t r a c t t o p i c as t u d yo nv e h i c l er o u t i n gp r o b l e m si n t e g r a t i n gr e v e r s el o g i s t i c s s t u d e n tn a m e l ij i a n s u p e r v i s e db y p r o f e s s o rd aq i n g l i s u b m i r e dt o s o u t h e a s tu n i v e r s i t y s m a l l q u a n t i t ya n dh i g l l 丘e q u e n c yd e l i v e r i e sh a v ei n c r e a s i n g l yb e c o m et h em a i n t r e n do fm o d e r nl o g i s t i c sa n dd i s t r i b u t i o n o fw h i c ht h ev e h i c l er o u t i n gp r o b l e mi st h e k e y m o s te x i s t i n gd i s t r i b u t i o n so f t e nt r e a tt h ef o r w a r dd i s t r i b u t i o na n dr e v e r s e d i s t r i b u t i o ni n d e p e n d e n t l y w h i c hr e s u l t si nal o wf u l ll o a d e dr a t i o i no r d e rt os a v e r e s o u r c e sa n dr e d u c ec o s t s t 1 1 e ya r ei n t e g r a t e di nt h er e s e a r c ho fv e h i c l er o u t i n g p r o b l e m si n t e g r a t i n gr e v e r s el o g i s t i c si nt h i sd i s s e r t a t i o n t h em o d e l sa n da l g o r i t h m s o fv e h i c l er o u t i n gp r o b l e m si n t e g r a t e dr e v e r s el o g i s t i c si nad e t e r m i n i s t i cc o n t e x t a f u z z yc o n t e x ta n dad y n a m i cc o n t e x ta r ei n v e s t i g a t e d r e s p e c t i v e l y t h em a i n c o n t r i b u t i o n so ft h i sd i s s e r t a t i o na r et oe x t e n dt h ev e h i c l er o u t i n gp r o b l e m sa n dt o d e s i g ne f f i c i e n ta l g o r i t h m sf o rt h e m 1 f r o mt h ep e r s p e c t i v eo ft h et h i r dp a r tl o g i s t i c s t p l s t u d yo nh e t e r o g e n e o u s v e h i c l er o u t i n gp r o b l e mw i t hh a r dt i m ew i n d o w su n d e rt h er e n t i nv e h i c l er o u t i n g p r o b l e mf o rt p l v e h i c l e sa r ec o m p o s e do fd i f f e r e n tt y p e so fv e h i c l e sa n da r eo r e n r e n t e df r o mo t h e rc o m p a n i e sw h e nt p li sf a c i n gt h ef l u c t u a t i o no fd e m a n d a i m e da t i t sc h a r a c t e r i s t i c s am a t h e m a t i c a lm o d e lw i t ht h eo b j e c t i v ef u n c t i o no fm i n i m i z i n g t h es u mo ft h er e n ta n dt r a n s p o r t a t i o nc o s t si sf o r m u l a t e da n dah y b r i dg e n e t i c a l g o r i t h mc o m b i n e dw i t hs i m u l a t e da n n e a l i n ga l g o r i t h mi sp r e s e n t e d t h i sa l g o r i t h m u s e sas t r a t e g yt h a tv e h i c l e sw i t ht h el e a s tc o s ta r ep r i o rt os e r v ec u s t o m e r st oa l l o c a t e t h eh e t e r o g e n e o u sv e h i c l e a n dt h es o l u t i o ni sd e n o t e db yam e t h o db a s e do n c u s t o m e r sa r r a n g e dd i r e c t l y a na p p l i c a t i o ne x a m p l es u g g e s t st h a th y b r i dg e n e t i c a l g o r i t h mc a no b t a i nb e r e ra n dm o r es t a b l es o l u t i o n s a n dt h es t r a t e g ya l l o c a t i n g h e t e r o g e n e o u sv e h i c l ec a ns u p p l yt h eb a s i sf o rt p lt om a k eal e a s e o r n o td e c i s i o n 2 s t u d yo na l g o r i t h mf o rl a r g e s c a l ev e h i c l er o u t i n gp r o b l e mw i t hs i m u l t a n e o u s d e l i v e r i e sa n dp i c k u p s v r p s d p f i r s t l y t h ei n i t i a ls o l u t i o ni so b t a i n e db ym e a n so f s p a c e f i l l i n gc u r v e si nt h ef r a c t a lt h e o r y t h e n t h ec u r r e n ts o l u t i o ni sd i v i d e di n t o s e v e r a ls u b s e t sw h i c ha r er e s p e c t i v e l ys o l v e db yt h en e wt a b us e a r c ha l g o r i t h mt h a t n l i n t e g r a t e sm a n yn e i g h b o r h o o ds e a r c hm e t h o d sa n da d o p t sr e s t a r ta n dp e r t u r b a t i o n s t r a t e g i e s f i n a l l y t h er e s u l t i n gr o u t e s a r em e r g e dt of o r man e wc u r r e n ts o l u t i o n c o m p u t a t i o n a lr e s u l t ss h o wt h a tt h en e wt a b us e a r c ha l g o r i t h mc a l li m p r o v es o m e b e s tk n o w ns o l u t i o n sa n ds u p p l yan e wm e t h o df o rs o l v i n gv r p s d p 3 s t u d yo nv e h i c l er o u t i n gp r o b l e mw i t hs i m u l t a n e o u sd e l i v e r i e sa n dp i c k u p s a n dt i m ew i n d o w s v r p s d p t w u n d e rt h ec i r c u m s t a n c e so fr a p i d l yi n c r e a s i n g c u s t o m e r s am u l t i o b j e c t i v em o d e li sd e v e l o p e dt od e t e r m i n eaf e a s i b l er o u t es c h e d u l e w h i c hm i n i m i z e st h en u m b e ro ft h ev e h i c l e s t r a v e l i n gd i s t a n c e sa n dt h es u mo f t r a v e l i n gt i m e s s e r v i n gt i m e sa n dw a i t i n gt i m e s d e c o m p o s i t i o na n di t e r a t i o n a l g o r i t h mb a s e do nr o u t es e tp a r t i t i o ni sp r o p o s e d c o m p u t a t i o n a lr e s u l t ss h o wt h a t t h i sa l g o r i t h mi se f f e c t i v et or e s o l v 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 so f b o t ho n e w a yd e l i v e r i e sa n ds i m u l t a n e o u sd e l i v e r i e sa n dp i c k u p s t h er e s e a r c ho ft h e v r p s d p t w p r o v i d e sar o b u s tt o o lf o rd i s t r i b u t i o nd e c i s i o n m a k i n g 4 s t u d yo nm u l t i t r i pv e h i c l er o u t i n gp r o b l e mw i t hs i m u l t a n e o u sd e l i v e r i e sa n d p i c k u p s m t v r p s d p t h el i m i t e dn u m b e ra n dw o r k i n g t i m eo ft h ev e h i c l e s am o r e p r a c t i c a lm u l t i o b j e c t i v em o d e lt o m i n i m i z et h en u m b e ro fv e h i c l e sa n dt r a v e l d i s t a n c e si sf o r m u l a t e d t h e nt h et a b us e a r c ha l g o r i t h ma l l o w i n gi n f e a s i b l es o l u t i o n s i sp r o p o s e d t h i sa l g o r i t h mc a ns i m u l t a n e o u s l ys o l v ep l a n n i n gr o u t e sa n da s s i g n i n g r o u t e st ov e h i c l e s i nw h i c hf o u rn e i g h b o r h o o ds e a r c hm e t h o d sa n dr e s t a r ts t r a t e g ya r e e m p l o y e df o rp l a n n i n gr o u t e sa n di nw h i c hi n i t i a lr o u t e sa s s i g n m e n ta n di m p r o v e d r o u t e sa s s i g n m e n ta r ea d o p t e df o ra s s i g n i n gr o u t e st ov e h i c l e s c o m p u t a t i o n a lr e s u l t s s h o wt h a tt h i sa l g o r i t h mi se f f e c t i v et oo b t a i nt h es a t i s f a c t o r ys o l u t i o n a n dt h a t m u l t i t r i pa r r a n g e m e n ti sm o r ee c o n o m i ca n dr e a s o n a b l et h a ns i n g l e t r i pa r r a n g e m e n t 5 s t u d yo nv e h i c l er o u t i n gp r o b l e mw i t hs i m u l t a n e o u sd e l i v e r i e sa n dp i c k u p s w i t hf u z z yr e v e r s ed e m a n d s t h ed e l i v e r i e so fe v e r yc l i e n ta su n c e r t a i np a r a m e t e r sa r e e x p r e s s e da st r i a n g u l a rf u z z yn u m b e r s am u l t i o b j e c t i v ef u z z yp r o g r a m m i n gm o d e l w i t hc r e d i b i l i t ym e a s u r et h e o r yi sc o n s t r u c t e d t h e nt h es i m u l a t i o n b a s e dt a b us e a r c h a l g o r i t h mc o m b i n i n gi n t e r r o u t ea n di n t r a r o u t en e i g h b o r h o o d sa n de m b e d d e dr e s t a r t s a r ed e s i g n e dt os o l v ei t c o m p u t a t i o n a lr e s u l t ss h o wt h a tt h et a b us e a r c ha l g o r i t h m d e v e l o p e di ss u p e r i o rt os w e e pa l g o r i t h ma n dt h a tc o m p a r e dw i t hh a n d l i n ge a c ho n s e p a r a t er o u t e s t h et r a n s p o r t a t i o nc o s t sc a nb er e d u c e dr e m a r k a b l y 6 s t u d yo nm i x e dv 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 sa n dd y n a m i c r e v e r s ed e m a n d s i nt h i sp r o b l e mt h ed i s p a t c h e r sd on o th a v ea n yd e t e r m i n i s t i co r i v p r o b a b i l i s t i ci n f o r m a t i o no nt h ea p p e a r i n gt i m e s e r v i n gt i m e l o c a t i o na n dd e m a n do f ar e v e r s ec u s t o m e ro r d e ru n t i li ta r r i v e s t h ep r o l e mi sd e v i d e di n t os t a t i ca n d d y n a m i cp h a s e sa n de a c hp h a s ei ss o l v e db yr e c o r d t o r e c o r dt r a v e la l g o r i t h m r e s p e c t i v e l y s t o c h a s t i cl a r g en e i g h b o u r h o o ds e a r c h r e s t a r s a n dp e r t u r b a t i o na r e a d o p t e d t o i m p r o v es o l u t i o n r e s t r i c t i n gn e i g h b o u r h o o ds e a r c ha n dd e s i g n i n g c o n s t a n tf e a s i b i l i t yc h e c ka l eu s e dt or e d u c ec o m p u t a t i o nt i m e s c o m p u t a t i o n a l r e s u l t ss h o wt h a tt h ei m p r o v e dr e c o r d t o r e c o r dt r a v e la l g o r i t h mi sq u i c ka n de f f i c i e n t a n dt h a ti n t e g r a t i n gd y n a m i cr e v e r s ec u s t o m e r st i m e l yi nt h ec u r r e n tr o u t e si sm o r e e c o n o m i c a lt h a ns o l ea r r a n g e m e n t k e y w o r d s v e h i c l er o u t i n gp r o b l e m s i m u l t a n e o u s d e l i v e r i e sa n d p i c k u p s m u l t i t r i p d y n a m i cd e m a n d f u z z yd e m a n d m e t a h e u r i s t i ca l g o r i t h m v 东南大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成果 尽我所知 除了文中特别加以标注和致谢的地方外 论文中不包含其他人已经发表或撰写过 的研究成果 也不包含为获得东南大学或其它教育机构的学位或证书而使用过的材料 与我 一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意 研究生签名 东南大学学位论文使用授权声明 东南大学 中国科学技术信息研究所 国家图书馆有权保留本人所送交学位论文的复印 件和电子文档 可以采用影印 缩印或其他复制手段保存论文 本人电子文档的内容和纸质 论文的内容相一致 除在保密期内的保密论文外 允许论文被查阅和借阅 可以公布 包括 以电子信息形式刊登 论文的全部内容或中 英文摘要等部分内容 论文的公布 包括以电 子信息形式刊登 授权东南大学研究生院办理 研究生签名 独导师签名 第 章绪论 1 1 问题的背景和意义 第一章绪论 随着我国市场经济的发展 作为 第三利润源泉 的物流对经济活动的影 响日益明显 越来越得到了人们的重视 成为当前 最重要的竞争领域 未来 的市场竞争中 物流将起到举足轻重的作用 2 0 0 8 年 全国社会物流总额达8 9 9 万亿元 比2 0 0 0 年增长4 2 倍 年均增长2 3 物流业实现增加值2 0 万亿元 比2 0 0 0 年增长1 9 倍 年均增长1 4 物流业增加值占全部服务业增加值的比 重为1 6 5 占g d p 的比重为6 6 物流费用占g d p 的比重为1 8 3 t 1 1 物流的基本功能包括运输 储存 装卸搬运 包装 流通加工 配送 信 息处理等七个方面 据统计 运输费用在整个物流费用中的比重一般为4 0 6 0 1 2 1 近年来 随着市场一体化进程逐步加快 网络经济的出现 商品经济快 速发展 经济要素流动规模和质量迅速提升 人们的生产生活方式发生了急剧 变革 公路小件快运市场呈现需求旺盛的态势 以批量小 价值高 时间紧 个性化为特征的小件货物运输日益增长 据2 0 0 8 年中国快运快递业研究咨询报 告显示 我国包括小件在内的快递市场规模高达5 0 0 亿元 未来1 0 年如果保持 现有的增长速度 市场总量将超过5 3 0 0 亿元 3 1 由于高新技术的发展 大量短 小轻薄 小批量多品种 高附加值高技术含量的工业产品也促进了小批量多批 次的运输发展 如何有效提高小批量多批次的运输效率 减少成本 正是车辆路线问题的 研究内容 在以往的配送中通常将正向物流和逆向物流分别加以考虑 往往会 导致较高的空载率 也会给客户带来不便 因为在许多实际情形中 客户有同 时送货和收货的需求 以下几个方面的发展也进一步促进了正逆向物流一体化 车辆路线问题的研究 1 逆向物流的发展 逆向物流是指在企业物流过程中 由于某些物品失去了 明显的使用价值 如加工过程中的边角料 消费后的产品 包装材料等 或消费 者期望产品所具有的某项功能失去了效用或已被淘汰 将作为废弃物抛弃 但在 这些物品中还存在可以再利用的潜在使用价值 企业为这部分物品设计一个回 收系统 使具有再利用价值的物品回到正规的企业物流活动中来 4 随着环境污 染的日益严重 一些国家 如德国 日本和美国 已经立法要求企业回收产品 的包装材料p j 我国也制定了电子产品回收的相关法规1 4 因此逆向物流备受关 东南大学博士学位论文 注 美国逆向物流委员会的调查表明 2 0 0 3 年的美国逆向物流成本达到4 0 0 亿 美元 从事再制造的企业在美国有7 3 0 0 0 家 年销售额超过5 3 0 亿美元 而在 我国 逆向物流还有较大的发展空间 矿产资源的总回收利用率为3 0 0 0 5 0 比世界平均水平低10 2 0 单位产品能耗为世界平均水平的2 3 倍 主要用 能产品单位能耗比世界先进水平高4 0 每年可综合利用的固体废弃物和可利 用的再生资源 没有利用其价值的高达5 0 0 多亿元 我国工业中产品能源 原 材料的消耗占企业生产成本的7 5 左右 若降低1 则可以取得1 0 0 多亿元的 效益1 6 i 2 人工智能 现代通讯和计算机网络技术的发展 人工智能的发展为复杂 问题的决策提供了有力的工具 现代通讯和计算网络技术的发展为车辆的实时 有效调度提供技术条件 3 汽车车厢设计的改进 为了适应物流配送的需要 车厢设计也发生了变 化 如多门设计为卸货和上货提供了方便 车辆路线问题除了在运输和物流配送中的实际应用外 由于其为n p h a r d 难题 求解该问题极具挑战性 因此引起了运筹学 应用数学 物流科学 交 通运输工程 管理科学与工程和计算机应用等学科的专家 工程技术人员和管 理者的极大兴趣 大量关于车辆路线问题的学术论文发表于交通运输 运筹学 管理科学 计算科学以及应用数学的顶级期刊上 比如 t r a n s p o r t a t i o ns c i e n c e l t r a n s p o r t a t i o nr e s e a r c h o p e r a t i o n sr e s e a r c h e u r o p e a nj o u m a lo f o p e r a t i o n a lr e s e a r c h j o u r n a lo f o p e r a t i o n a lr e s e a r c hs o c i e t y c o m p u t e r s o p e r a t i o n sr e s e a r c h m a n a g e m e n ts c i e n c e i n f o r m sj o u r n a lo nc o m p u t i n g 和 d i s c r e t e a p p l i e dm a t h e m a t i c s 等 因此 车辆路线问题的研究 成为 最 近半个世纪运筹学领域最成功的研究之一 7 综上所述 研究正逆向物流一体化车辆路线问题具有重要的理论和现实意 义 有助于丰富车辆路线 运输和运筹学等的研究内容 有助于节约能源 减 少污染 降低成本 1 2 研究思路与方法 1 2 1 研究思路 在归纳总结已有正逆向物流一体化车辆路线相关研究成果的基础上 深入 分析和把握相关领域的国内外研究现状和发展动向 分析了正逆向物流一体化 2 第一章绪论 车辆路线问题的特征 研究分类及研究动态 首先研究正逆向物流一体化车辆 路线问题的基础 单向车辆路线问题 主要以租赁条件下第三方多车型路线 问题为研究对象 分析其特点 设计基于遗传算法和模拟退火算法的混合算法 分析不同参数条件下对租赁车辆的决策影响 其次 研究正逆向物流一体化车 辆路线问题中不带时间窗的同时集散货物路线问题算法设计 再次研究其中带 时间窗和多车次约束下同时集散货物路线问题 根据其特点设计了相应的算法 然后 考虑逆向需求模糊条件下的同时集散货物路线问题 建立基于模糊置信 度理论的多目标模型 设计基于模拟的禁忌搜索算法设计 并分析相关参数的 影响 最后 研究逆向需求动态出现的混合集散货物路线问题 分析其特点 设计快速有效的算法 并比较安排动态客户策略的成本 1 2 2 研究方法 车辆路线问题的研究中 求解算法一般分为精确算法和非精确算法 启发 式算法 精确算法的求解规模较小 尤其是问题约束越复杂 精确求解就越困 难 为了提高其实用性 本文用非精确算法研究正逆向物流一体化车辆路线问 题 采用的方法包括禁忌搜索算法 遗传算法 模拟退火算法 分解迭代算法 模糊模拟和记录更新算法等 1 3 研究内容 论文内容主要包括三大部分 第一部分包括第一章和第二章 概述论文研究 的背景意义及相关文献研究现状 第二部分是论文的核心部分 包括第三章至 第八章 研究六类正逆向物流一体化车辆路线问题及其有效求解算法 第三部 分为第九章 是结论和展望 论文框架结构如图1 1 所示 具体内容如下 第一章为绪论 指出本文的选题背景 研究意义 研究的整体思路 主要研 究方法以及研究的主要内容 第二章为正逆向物流一体化车辆路线问题国内外相关文献综述 首先 回顾 国内外单向车辆路线问题的研究现状 接着 重点分析正逆向物流一体化车辆 路线问题的特征 研究分类和研究方法 然后总结单向车辆路线问题的发展趋 势及正逆向物流一体化车辆路线问题的研究不足 第三章研究第三方物流多车型硬时间窗路线问题 分析租赁条件下的第三方 物流多车型硬时间窗车辆路线问题的特点 建立以车辆租赁费用和运行费用最小 为目标的模型 并提出结合模拟退火法的混合遗传算法 通过数据计算验证算法 东南大学博士学位论文 的有效性 分析多车型容量对租赁车辆决策的影响 第四章研究大规模同时集散货物路线问题的算法设计 首先应用分形理论 中的空间填充曲线法求解初始解 接着将当前解分解成几个独立的路线子集合 再用新禁忌搜索法求解每个路线子集合 然后再将子集合求得的最好路线组成 新的当前解 其中新禁忌搜索算法集成了大量的邻域搜索方法 并采用了重起 和扰动策略 通过数据测试验证算法的有效性 论文研究的背景和意义 正逆向物流一体化车辆路线问置相关文献综述 结论与展望 图1 1 论文框架结构图 第五章研究业务繁忙环境下的带时间窗的同时集散货物路线问题 分析该 问题的多目标特征 以车辆数 运输里程和完成运输任务总时间最小为目标 4 第一章绪论 建立多目标模型 并提出分解迭代算法 通过单向车辆路线问题的测试数据验 证算法的有效性 并比较带时间窗的同时集散货物路线问题在不同权重目标下 的成本值 第六章研究配送车辆数和车辆工作时间有限的多次集散货物路线问题 以 车辆数和运输里程最小为目标建立基于集合划分的多目标模型 针对该问题包 括路线安排和路线分配两个子问题 提出允许不可行解的禁忌搜索算法 该方 法中路线安排采用4 种邻域搜索方法和重起策略 路线分配采用初次分配和二 次调整策略 通过算例验证该方法的有效性 比较多车次安排路线与单车次安 排路线的成本 第七章研究逆向需求模糊的同时集散货物路线问题 该问题的特点是客户 可以同时取货和发货 而且客户发货量在路线安排前是不确定的 首先用三角 模糊数表示客户发货量 建立基于模糊置信度理论的多目标模型 然后设计基 于模拟的改进禁忌搜索算法求解该模型 该算法用模拟的方法计算路线失败值 在路线搜索中采用路线内部改善和路线间改善两类邻域操作 而且采用重起策 略 通过算例计算验证该算法的有效性 并比较同时安排正逆客户的运输成本 与分开安排的运输成本 第八章研究逆向需求动态出现的混合集散货物路线问题 即逆向需求出现 的时刻 位置以及要求服务的时间和发货量事前是完全未知的 且具有时间窗 约束的混合集散货物路线问题 将问题的求解过程分为静态和动态两阶段 每 阶段分别用记录更新算法求解 记录更新法中采用随机大邻域搜索法及重起和 扰动策略来提高解的质量 并通过约束邻域搜索范围和设计常量可行性检查两 种策略来减少计算时间 通过数据测试验证算法的有效性 并比较单独安排动 态客户的运输成本和将动态客户整合在正逆客户中的运输成本 第九章为总结与展望 总结全文 给出论文研究结论和成果 并展望进一步 研究的问题 参考文献 1 国务院 物流业调整和振兴规划 e b o l b 主圭巳 z 盟 旦鱼塑 g q 璺丛么圣璺 照 圣q 坠g 兰 2 0 0 9 q t t 2 0 0 9 0 4 2 42 7 4 4 8 8 h t a 2 0 0 9 0 4 2 4 2 中国物流与采购联合会 中国物流发展报告2 0 0 7 2 0 0 8 r 1 北京 中国物资出版社 2 0 0 8 3 2 0 0 8 2 0 0 9 年中国快运快递业研究咨询报告 e b o l h t t p w w w c h i n a c c m c o m 4 8 4 8 1 1 1 4 8 1 l o l n e w s 2 0 0 8 0 7 1 7 11 5 1 2 6 a s p 2 0 0 8 7 一1 7 东南大学博士学位论文 4 达庆利 黄祖庆 张钦 逆向物流系统结构研究的现状及展望 j 中国管理科学 2 0 0 4 1 2 1 1 3 1 1 3 8 5 a l s m m r a n i 八m a t h u rkb a l l o urh r e v e r s el o g i s t i c s s i m u l t a n e o u sd e s i g no fd e l i v e r y r o u t e sa n dr e t u r n ss t r a t e g i e s j c o m p u t e r s o p e r a t i o n sr e s e a r c h 2 0 0 7 3 4 2 5 9 5 6 1 9 6 申成霖 基于循环经济理论的逆向物流网络规划研究 d 天津 天津大学管理学院 2 0 0 4 7 c a n e na s c o rlgb r i d g i n gt h e o r ya n dp r a c t i c ei nv r p 丁i j o u r n a lo ft h eo p e r a t i o n a l r e s e a r c hs o c i e t y 1 9 9 5 4 6 1 1 8 6 第二章正逆向物流一体化车辆路线问题相关文献综述 第二章正逆向物流一体化车辆路线问题相关文献综述 车辆路线问题自学者d a n t z i g 和r a m s e r 1 于1 9 5 9 年提出以来 产生了大量 的研究成果 为了展示其发展趋势 从单向和双向两个方面进行了总结 分析 了车辆路线问题的构成要素及拓展类型 概述各种单向车辆路线问题的研究现 状 重点综述了正逆向物流一体化车辆路线问题的特征 研究类型和求解算法 最后指出了单向车辆路线问题的发展趋势及正逆向物流一体化车辆路线问题研 究中存在的问题 2 1 单向车辆路线问题 单向车辆路线问题是一个经典的组合优化问题 其主要研究满足约束条件 的最优的车辆使用方案以及最优的车辆路线方案 从图论的角度 车辆路线问 题定义如下 设g r o d 为一个完备的无向图 其中v o 0 1 2 l 为节点 集 e f f 歹 v f 以为边集 v r o o 表示顾客点集 0 代表配送中 心 站点 一队具有相同额定载重量q 的车辆从配送中心 站点 对客户点进 行配送服务 每个客户有一个固定的需求吼和固定的服务时间窗 e z 三霉 每 条边 f j 赋有一个权重 表示旅离或者旅行费用白 通常 假设c c 玎 满足 三角不等式 即勺 f 砖 f k v 车辆路线问题的优化目标为 确定一个 具有最小车辆数和对应的最小距离或者费用的路线集 其满足下列约束条件 1 每一条车辆路线开始于配送中心 站点 而且也结束于配送中心 站 点 2 每个客户的需求必须满足 只能被访问一次 且只能由一辆车服务 3 每一条车辆路线总的顾客需求不超过车辆额定载重量o 4 每一条车辆路线满足一定的边约束 比如持续时间约束和时间窗约束 等 2 1 2 车辆路线问题的构成要素 车辆路线问题典型的要素包括 客户 司机 车辆 路线及道路 配送中 心 站点 数目 信息特征和目标函剡妒 各要素的主要特征如下 1 客户 本文用客户表示运输网络上的节点 可以代表实际车辆路线问题中任意类 7 东南大学博士学位论文 型的服务对象 比如零售商店 分销点 快递物流中的个体家庭 货物配送分 支点等 客户的典型特征包括以下儿个方面 时间窗 取货 送货或既取货也送货 对司机和车辆的特别要求 产品类型和数量要求 2 司机 司机的工作制度和驾驶水平均影响车辆的调度和安排 具体特征为 工作时间和休息时间 多车型的要求 相关法规的要求 3 车辆 车辆的具体特征包括以下几个方面 车队类型及规模 车辆货箱的结构 多门设计 多箱 车辆的特殊装备 装卸设备 无线通讯设备及定位系统等 是否需要回到出发场站 对司机的要求 不同的费用结构 4 路线及道路网络 两点间旅行时间是否随时间变化 道路是双向通道还是单向通道 根据运输网络中联接两点的道路特征的 不同 相应地弧可以分为有向弧和无向弧 有向弧是指车辆仅可以向一个方向 行驶的道路 比较典型的是城市交通网络中单向行驶的道路 无向弧是指车辆 可以在两个方向上行驶的双向道路 对应于每条弧 赋有一个非负的费用权重 根据实际研究的需要 可以赋予它不同的含义 例如可以表示两点间的旅行距 离 旅行时间等 5 配送中心 站点 数目 配送中心 站点 是指车辆出发或结束的地方 在车辆路线调度研究中 有多配送中心 站点 和单配送中心 站点 之分 6 信息特征 根据已知信息特征的不同 将车辆路线问题分为静态车辆路线问题和动态 车辆路线问题 其中静态车辆路线问题又可以分为确定性车辆路线问题和不确 第二章正逆向物流一体化车辆路线问题相关文献综述 定性车辆路线问题 7 目标函数 在车辆路线问题的研究中 常用目标函数有以下几个方面 最小化全部运输费用 最小化使用的车辆数 平衡路线差异 包括旅行时间和装载量 最小化惩罚费用 2 1 2 单向车辆路线问题的扩展 为了叙述方便 将学者d a n t z i g 和r a m s c r 哪提出的车辆路线问题称为经典车 辆路线 v e h i c l er o u t i n gp r o b l e m v r p 在经典车辆路线问题的基础上 通过修 改其假设条件或增加特征约束产生新问题 图2 1 给出车辆路线基本扩展问题 与经典车辆路线问题的关系 该图仅给出了加入单一特征之后的扩展车辆路线 问题 若将多种特征加入经典车辆路线中 将产生更加复杂的扩展问题 2 1 3 单向车辆路线问题的研究概述 由于车辆路线问题将运筹学理论和企业物流活动紧密联系在一起 自提出 后便引起运筹学 图论与网络分析 应用数学 物流科学 交通运输 计算机 应用等学科的专家和管理者的重视 成为运筹学和组合优化领域的前沿和热点 问题 单向车辆路线问题经过5 0 年的研究已取得了丰硕的成果 本文从确定性 不确定性和动态性三个方面总结单向车辆路线