（交通运输规划与管理专业论文）基于模拟退火遗传算法的车辆调度问题研究.pdf

中文摘要 摘要 2 1 世纪是经济全球化的世纪，随着市场经济的深入发展，作为“第三利润源 泉”的物流在我国的生产、分配、流通和消费的各个领域起着越来越重要的作用。 物流配送是物流中一个重要的直接与消费者相连的环节，因此配送的地位十分突 出，如何实现快速而准确的配送是企业在经营方面必须解决的重要课题。一般意 义上的物流配送指配送中心按照不同客户多频度、小批量订货要求组织配送，其 中主要内容是根据确定的货物量进行车辆的分配和配送路线的安排，亦即广受研 究的车辆路线问题( v e h i c l es c h e d u l i n gp r o b l e m ) 。由于从事物流配送的汽车 货运工作尤其是从事城市配送的汽车货运工作条件复杂，这就需要建立更加科学， 优化的配送调度模型来满足顾客对于服务的高质量需求。 本文首先对物流配送车辆调度问题作了简要的概述，通过对问题的简化，给出 了相应的数学模型。并对问题的常规求解思路作以介绍。第三章介绍了遗传算法 的基本思想及车辆调度问题中蘧传算法的应用。由于遗传算法固有的缺陷以及模 拟退火算法局部寻优的能力，在遗传算法中结合模拟退火算法正好实现了优势互 补，从而形成了退火遗传算法。接着详细介绍了退火遗传算法的步骤。第四章针 对第二章简化后得出的物流配送车辆调度问题，给出一种新的染色体编码方式， 使得运用退火遗传算法进行优化寻找运输成本最低解时，该算法能在一定范围内 自动搜索所需的最优车辆数。最后用算例说明了在新的编码方式下，运用退火遗 传算法解决物流配送问题的有效性和通用性。文章在最后对本文的研究工作做了 总结，并指出了进一步的研究方向。 关键词：车辆调度问题；模拟退火算法；遗传算法 英文摘要 r e s e a r c ho nv e h i c l es c h e d u l i n gp r o b l e m b a s e do ng e n e t i cs i m u l a t e d a n n e a l i n g a l g o r i t h m a b s t r a c t e c o n o m i cg l o b a l i z a t i o ni s b o o m i n gi n t h e2 1 “c e n t u r y w i t ht h et h o r o u g h d e v e l o p m e n ti nm a r k e te c o n o m y ，l o g i s t i c sa st h et h i r ds o u r c eo fp r o f i tp l a y sa l l i m p o r t a n t r o l ei n e v e r y f i e l do f m a n u f a c t u r e ，d i s t r i b u t i o n ，t r a n s p o r t a t i o n a n d c o n s u m p t i o ni no u rc o u n t r y d i s t r i b u t i o ni sac r u c i a lt a c h ei l l l o g i s t i c s w h i c hi sd i r e c t l y c o n n e c t e dw i t h c o n s u m e r s t h u s , t h es t a t u so fd i s t r i b u t i o ni sv e r yp r o m i n e n t h o wt or e a l i z et h ef a s t a n de x a c td i s t r i b u t i o nb e c a m e 蛐i m p o r t a n ts u b j e c tt h a tm u s tb es o l v e di nt h e m a n a g e m e n to fc o r p o r a t i o n s g e n e r a l l y ，d i s t r i b u t i o nm e a n st h ed i s t r i b u t i o n c e n t e r s o r g a n i z et h ed i s t r i b u t i o na c c o r d i n gt o t h ef r e q u e n ta n ds m a l lo r d e r so fd i f f e r e n t c u s t o m e r s t h em a i ni st oa s s i g nt h ev e h i c l e sa n dp l a nt h ec o u r s e sa c c o r d i n gt ot h e a s s u r e dc a r g oq u a n t i t i e s ，a n d j h a ti st h ew i d e - r e s e a r c h i n gv e h i c l es c h e d u l i n gp r o b l e m s i n c et h ec o n d i t i o n so fc a r r i a g eo fg o o d sb yv e h i c l e si nd i s t r i b u t i o na ，r e c o m p l e x ， e s p e c i a l l yt h eu r b a nd i s t r i b u t i o n ，i ti sn e c e s s a r yt oe s t a b l i s ht h em o r es c i e n t i f i ca n d b e t t e rd i s t r i b u t i o n s c h e d u l i n gm o d e li no r d e rt os a t i s f yt h ec u s t o m e r s h i g h q u a l i t y r e q u e s t s i nt h i st h e s i s ，i th a sf i r s t l yg i v e nab r i e fs u m m a r yo nv e h i c l es c h e d u l i n gp r o b l e m b ys i m p l i f y i n gt h ep r o b l e m ，i tg i v e st h ec o r r e s p o n d i n gm a t h e m a t i c a lm o d e la n dt h e i n t r o d u c t i o no fr e g u l a rw a yo fs o l v i n gt h ep r o b l e m i nt h et h i r dc h a p t e r ，i ti n t r o d u c e d t h eb a s i ci d e ao fg e n e t i ca l g o r i t h m ，t h ea p p l i c a t i o no fg e n e t i ca l g o r i t h mi nv e h i c l e s c h e d u l i n gp r o b l e m s i n c et h eg e n e t i ca l g o r i t h mh a si t si m m a n e n tl i m i t a t i o n sa n dt h e s i m u l a t e da n n e a l i n ga l g o r i t h mh a st h ea d v a n t a g e si ns o m ea s p e c t s ，c o m b i n e dt h e s e t w oa l g o r i t h m st o g e t h e rj u s ta c h i e v et h ep e r f e c t i o n t h i sc o n c l u d e st h eg e n e t i c s i m u l a t e da n n e a l i n ga l g o r i t h m i nt h i sc h a p t e r ，i tp u t sf o r w a r dak i n do fs t r u c t u r eo f g e n e t i cs i m u l a t e da n n e a l i n ga l g o r i t h m t h e n ，i ti n t r o d u c e st h es t e p so ft h i sa l g o r i t h m i nt h ef o r t hc h a p t e r ，i tg i v e san e wc h r o m o s o m ec o d ea i m i n ga tt h es i m p l i f i e dv e h i c l e s c h e d u l i n gp r o b l e mm o d e li nl o g i s t i c s w i t ht h i sc o d i n gm o d e ，w h e na p p l y i n gg e n e t i c s i m u l a t e da n n e a l i n ga l g o r i t h mt os e a r c ht h el o w e s tt r a n s p o r tc o s t s ，t h i sa l g o r i t h mg a l l 墨壅塑墨 s e a r c h a u t o m a t i c a l l yt h er i g h tn u m b e ro fv e h i c l e si n c e r t a i n r a n g e s f i n a l l y ，i t e x p l a i n e sw i t hc a l c u l a t i o nt h a t w i t ht h i sn e wc o d i n gm o d e ，g e n e t i cs i m u l a t e d a n n e a l i n ga l g o r i t h mh a si t sv a l i d i t ya n dp o p u l a r i t yi nd e a l i n gw i t ht h ev e h i c l e s c h e d u l i n gp r o b l e mi nl o g i s t i c s a tt h ee n do ft h et h e s i s ，i tg i v e st h ec o n c l u s i o no ft h e r e s e a r c ha n di n d i c a t e st h ef u r t h e rr e s e a r c hd i r e c t i o n k e yw o r d s ：v e h i c l es c h e d u l i n gp r o b l e m ；s i m u l a t e da n n e a l i n ga l g o r i t h m ； g e n e t i ca l g o r i t h m 大连海事大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：本论文是在导师的指导下，独立进行研究工作所取得的成果， 撰写成硕士学位论文：基王攫型逞么重佳簋洼的奎麴通廑闷星婴塞：。除论 文中已经注明引用的内容外，对论文的研究做出重要贡献的个人和集体，均已在 文中以明确方式标明。本论文中不包含任何未加明确注明的其他个人或集体已经 公开发表或未公开发表的成果。 本声明的法律责任由本人承担。 论文作者签名：l 样目竹；月，j 日 学位论文版权使用授权书 本学位论文作者及指导擞师完全了解“大连海事大学研究生学位论文提交、 版权使用管理办法”，同意大连海事大学保留并向国家有关部门或机构送交学位 论文的复印件和电子版，允许论文被查阅和借阅。本人授权大连海事大学可以将 本学位论文的全部或部分内容编入有关数据库进行检索，也可采用影印、缩印或 扫描等复制手段保存和汇编学位论文。 保密口，在年解密后适用本授权书。 本学位论文属于： 保密口 不保密一( 请在以上方框内打“一) 论文作者签名：l 司装、习导师签名：嘻磷 日期：抽1 年；月 基丁模拟退火遗愕算法的车辆调度问题研究 第1 章绪论 1 1 选题背景及课题研究的意义 2 1 世纪是经济全球化的世纪。随着市场经济的深入发展，作为“第三利润源 泉”的物流在我国的生产、分配、流通和消费的各个领域起着越来越重要的作用。 社会对物流需求的数量和质量萨在不断的提高，物流因此越来越受到人们的普遍 重视并得到了较大发展“1 。大量规模较大的生产企业、商业企业纷纷建立起物流配 送中心向商品流通的高效率化发起了挑战，物流中心的成立可以有效的简化配送 程序，减少配送的频率。与此同时，相当部分的大型运输、仓储和航运企业也开始 朝向第三方物流经营，物流配送开始在我国迅速兴起。 物流配送是物流中一个重要的直接与消费者相连的环节。配送是在集货、配 货基础上，按货物种类、品种搭配、数量、时间等要求所进行的运送，是“配” 和“送”的有机结合锄。物流配送过程主要包括：从生产工厂进货并集结的集货作 业；根据各个用户的不同需求，在配送中心将所需要的货物挑选出来的配货作业； 考虑配送货物的质量和体积，充分利用车辆的载重和容积的车载货物的配装及配 送路线的确定。 由于配送是对顾客服务的重要一环，因此配送的地位十分突出，如何实现快 速而准确的配送是企业在经营方面必须解决的重要课题。鉴于此，研究运用科学 方法合理组织物流配送，以提高企业的服务质量、减少库存、降低经营成本、增 加经济效益是十分必要的。 一般意义上的物流配送“1 指配送中心按照不同客户多频度、小批量订货要求组 织配送，其中主要内容是根据确定的货物量进行车辆的分配和配送路线的安排，亦 即广受研究的车辆路线问题( v e h i c l es c h e d u l i n gp r o b l e m ) 由于从事物流配 送的汽车货运工作尤其是从事城市配送的汽车货运工作条件复杂，不仅货运点多、 货物种类繁多、道路网复杂，而且运输服务地区内运输网点分布不均匀。这就需 要运用更加科学，优化的配送调度方案来满足顾客对于服务的高质量需求。 第1 章绍论 此外，物流企业要想在激烈的市场竞争中立于不败之地，必须具各自己的核 心竞争力，而物流配送系统中车辆路径优化，是竞争力的直接表现。 因此，如何应用现代数学方法及计算机快速求解路线优化方案是国内外专家 学者普遍探索的重要课题。 1 2 物流配送车辆调度问题的研究现状 1 2 1 问题的提出 国外将物流配送车辆调度问题称之为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 e s c h e d u l i n gp r o b l e m 物流配送车辆调度问题最早是由d a n t z i g 和r a m s e r 于1 9 5 9 年首次提出的，自此，很快引起运筹学、应用数学、组合数学、图论与网络分析、 物流科学、计算机应用等学科的专家与运输计划制定者和管理者的极大重视，成 为运筹学和组合优化领域的前沿与研究热点问题。各学科专家对该问题进行了大 量的理论研究和实验分析，取得了很大的进展。 该问题的一般定义为：对一系列装货点和( 或) 卸货点，组织适当的行车路 线，使车辆有序的通过它们，在满足一定的约束条件( 如货物需求量、发送量、 交发货时闻、车辆容量限制、行使里程限制、时间限制等) 下，达到一定的目标 ( 如路程最短、费用最少、时间尽量少、使用车辆数尽量少等) 。它很好的解决 了物流配送过程中存在的成本与效率之问的二义背反性，提高了客户满意度，降 低了企业的运输成本。 目前，问题的形势已有很大发展，该问题已不仅仅局限于汽车运输领域，在 水运、航空、通讯、电力、工业管理、计算机应用等领域也有一定的应用，其算 法已用于轮船公司运送货物经过港口与货物安排的优化设计、交通车线路安排、 生产系统中的计划与控制等多种组合优化问题。 1 2 2 算法 物流配送车辆调度问题的求解方法非常丰富，m a g n a n t j ( 1 9 8 1 ) ，b o d i n 和 g o l d e n ( 1 9 8 3 ) ，l a p o r t e 和o s m a n ( 1 9 9 5 ) 等许多学者对v s p 求解方法的分类进 墓丁i 模拟退火遗传算法的1 - 辆调度问题研究 行了研究，认为究其实质可以分为精确算法和启发式算法两大类： 1 精确算法 精确算法指可以求出其最优解的算法，精确算法主要有： 分枝定界法b r a n c ha n db o u n da p p r o a c h 割平面法c u t t i n gp t a n e sa p p r o a c h 网络流法n e t w o r kf l o wa p p r o a c h 动态规划方法d y n a m i cp r o g r a m m i n ga p p r o a c h 精确算法的计算量一般随问题规模的增大呈指数增长，因此在实际中其应用 范围很有限。 2 启发式算法h e u r i s t i c s 由于v s p 是强n p 难题，高效的精确算法存在的可能性不大，所以寻找近似算 法是必要和现实的。启发式算法( h e u r i s t i c s ) 是指一种基于直观或经验构造的算 法，目标是在可接受的花费( 计算时间、占用空间等) 下得出待解决问题的满意解， 而不一定是最优解。目前已提出的启发式算法很多，有以下几类： ( 1 ) 构造算法( c o n s t r u c t i v ea l g o r i t h m ) ” 根据一些准则，每一次将一个不在线路上的点增加进线路，直到所有的点都 被安排进线路为止。该类算法的每一步，把当前的线路构形( 很可能是不可行的) 跟另外的构形( 也可能是不可行的) 进行比较并加以改进，后者或是根据某个判 别函数( 例如总费用) 会产生最大限度的节约的构形，或是以最小代价把一个不 在当前构形上的需求对象插入进来的构形，最后得到一个较好的可行构形 ( a l t i n k e m e r 和g a v i s h ，1 9 9 1 ：d e s r o c h e r s 和v e r h o o g ，1 9 8 9 ) 。 构造算法是最早提出来解决旅行商问题( t s p ) 及v s p 的，这些方法一般速度 快，也很灵活( j a m e s 和j i e f e n g ，1 9 9 9 ) ，但这类方法有时找到的解离最优解差 得很远。 ( 2 ) 两阶段算法( t w o p h a s ea l g o r i t h m ) 学者们通过对构造算法的研究，认为由构造算法求得的解可以被进一步改进， 为此提出了两阶段法。第一阶段得到可行解，第二阶段通过对点的调整，在始终 第1 章绪论 保持解可行的情况下，力图向最优目标靠近。每一步都产，皇另一个可行解以代替 原来的解，使目标函数值得以改进，一直继续到不能再改进目标函数值为止 ( g i l l e t t 和m i l l e r ，1 9 7 4 ：c h r i s t o f i d e s 、m i n g o z z i 和t o t h ，1 9 7 9 ：f i s h e r 和 j a i k u m a r ，1 9 8 1 ：r e n a u d 、b o c t o r 和l a p o r t e ，1 9 9 6 ：b r a m e l 和s i m c h i l e v i ，1 9 9 5 ) 。 一般第一阶段常用构造算法在第二阶段常用的改进技术有2 - o p t 。1 、3 - o p t 州和 o r o p t ”1 交换法，这是一种在解的邻域中搜索，对初始解进行某种程度优化的算法， 以改进初始解。 一些基于数学规划的算法也属于两阶段法，把问题直接描述成为一个数学规 划问题，根据其模型的特殊构形，应用一定的技术( 如分解) 进行分划，进而求 解己被广泛研究过的子问题( f i s h e r 和j a i k u m a r ，1 9 8 1 ) 。 ( 3 ) 不完全优化算法( i n c o m p l e t eo p t i m i z a t i o na l g o r i t h m ) 以启发式准则来代替精确算法中的决策准则，以缩小解搜索的空间。 ( 4 ) 改进算法( i m p r o v e m e n tm e t h o d s ) 从一初始解开始，通过对当前的解进行反复地局部扰乱以达到较好的解。基 于启发式算法的并行算法和一些称为亚启发式算法( m e t a h e u r i s t i c s 、 l a p o r t e & o s m a n ，1 9 9 6 ) 的方法都属于此类。 用并行算法求解v s p 还处于起步阶段，a l t i n k e m e r 和g a v i s h ( 1 9 9 1 ) ，p o t v i n 和r o u s s e a u ( 1 9 9 3 ) ，t a i l l a r d ( 1 9 9 3 ) ，f i e c h t e r ( 1 9 9 4 ) 等用并行算法求解了 v s p ，他们的并行算法都是基于一种启发是规则如节约算法、插入式算法等等。 亚启发式算法包括表搜索算法( t a b us e a r c h ) 9 1 0 0 1 、模拟退火算法( s i m u l a t e d a n n e a li n g ) 、遗传算法( g e n e t i ca l g o r i t h m ) 、神经网络( n e u t r a ln e t w o r k s ) 算法等。 国内在物流配送车辆调度问题上，郭耀煌教授，李军教授，谢秉磊博士在该领 域做了相当的研究，其主要研究领域包括对该类问题的分类以及解决问题的算法 如启发式算法：c w 节约算法；亚启发式算法：模拟退火、遗传算法，随机、适时 的配送调度求解等。北方交通大学的郎茂祥教授在文献中对配送问题进行了综述， 用遗传算法与爬山算法构成的混合遗传算法来求解此类问题，取得了一定的成就； 基丁模拟退火遗传算法的下辆调度问题研究 祝崇隽等较全面地回顾了配送优化领域的最新发展；袁庆达和汪寿阳等分别对库 存路径问题和定址路径问题进行了评述。 1 3 本文的主要内容 现有研究文献对于多配送中心问题的求解，基本上可以分为以下两种方法。 ( 1 ) 将多配送中心问题转化为多个单配送中心问题，然后进行优化组合，这种 方法的研究重点在多配送中心的分离策略和最后解的优化组合方案选择上。本文 称之为分解法。 ( 2 ) 将多配送中心问题本身看作一个复杂的组合优化问题进行研究，这种方法 的研究重点集中在如何合理地缩小搜索空间和简化求解步骤上。本文称之为整体 法。 对于多配送中心问题，较为常见的做法是以单配送中心问题为基本问题，将 其转化为多个单配送中心问题。本文的基本思路是，将多配送中心问题看作是问 题的一般化，建立相关的数学模型，进而运用退火遗传算法求解。而单配送中心 问题只是前述问题的般化，因此可以运用同一算法加以解决，只是车场数目应 设定为l 而己。 一 退火遗传算法( g e n e t i cs i m u l a t e da n n e a l i n ga l g o r i t h m ) 是遗传算法和模 拟退火算法相结合的种优化方法。该算法的特点是利用了模拟退火算法在一定 概率控制下暂时接受一些恶化解的特征，改进了遗传算法的局部搜寻能力，扩大 了遗传算法的搜索领域，从而有效地解决了遗传算法早熟收敛的现象。它既具有 遗传算法的全局性和并行性，又具有模拟退火算法的局部搜索能力和退火特征， 使得遗传算法的搜索性能得到了极大改进。 第一章介绍了论文的研究背景和意义，并对物流配送车辆调度问题的研究现 状做以介绍。 第二章对物流配送车辆调度问题进行描述，给出了车辆调度问题的数学模型。 同时介绍了解决问题的常规思路和一般算法。 第1 章绪论 第三章介绍了遗传算法的基本流程，以及遗传算法在物流配送车辆调度问题 中的应用并对该算法作相应的评价，提出了遗传算法的改进方法，详细介绍了退火 遗传算法的特点、效率分析和算法步骤。 第四章介绍车辆调度问题中退火遗传算法的实现，并运用具体的算例说明该 算法的有效性和通用性。 第五章本文总结和工作展望。 基于模拟退火遗传算法的车辆调度问题研究 第2 章物流配送车辆调度问题及其常规求解思路 2 1 物流配送车辆调度问题概述 物流配送车辆调度问题1 可以描述为：在一个存在供求关系的系统中，有若干 台车辆、若干个配送中心和客户，要求合理安排车辆的行车路线和出行时间，从 而在给定的约束条件下，把客户需求的货物从配送中心送到客户，并使目标函数 ( 总运输成本) 取得优化。 l 物流配送问题的构成要素 物流配送问题主要包括货物、车辆、物流中心、客户、运输网络、约束条件 和目标函数等要素。 ( 1 ) 货物 货物是配送的对象，可将每个客户的需求( 或供应) 看成一批货物，每批货物 都包括品名、包装、重量、体积、要求送到( 或取走) 的时间和地点，能否分批配 送等属性。 ( 2 ) 车辆 车辆是货物的运载工具，其主要属性包括：车辆的类型、载重量、车辆的工作 时间、配送前的停放位置及完成任务后的停放位置等。 ( 3 ) 物流中心 也称为物流基地、物流据点，是指可以进行集货、分拣、配货、送货作业的 配送中心、仓库、车站、港口等。在配送系统中，物流中心的数量可以只有一个， 也可以有一个以上。 ( 4 ) 客户 包括分仓库、零售商店等，客户的属性包括需求( 或供应) 货物的数量、需求( 或 供应) 货物的时间、需求( 或供应) 货物的次数及需求( 或供应) 货物的满足程度等。 ( 5 ) 运输网络 运输网络是由顶点( 指物流中心、客户、停车场) 、无向边、有向弧组成的， 第2 章物流配送车辆调度问题及其常规求解思路 边、弧的属性包括方向、权值和交通流量限制等。运输网络中边或弧的权值可以 表示为距离、时间或费用。边或弧的权值变化分为以下几种情况：固定，即不随着 时间和车辆的不同而变化；随时间段不同而变化；随车辆的不同而变化；既随着 时间的不同而变化，又随着车辆的不同而变化。对运输网络中的定点、边或弧的 交通流量要求分为以下几种情况：无流量限制；边、弧限制，即每条边、弧上同时 行驶的车辆数有限；项点限制，即每个顶点上同时装、卸货的车辆数有限；边、 弧、顶点都有限制。 ( 6 ) 约束条件 配送问题应满足的约束条件主要包括：满足所有客户对货物品种、规格、批数 的要求；满足客户对货物发到时间范围的要求；在允许的时间进行配送( 如有时规 定白天不能通行货车等) ；车辆在配送过程中的实际载货量不得超过车辆的最大允 许装载量；在物流中心现有的运力范围内等。 ( 7 ) 目标函数 对配送问题，可以只选用一个目标，也可以选用多个目标。经常选用的目标 函数主要有：配送总里程最短、配送车辆总吨位公里数最少、配送总费用最低、配 送总时间最少、使用的配送车辆数最少、配送车辆的满载率最高等。 2 物流配送问题的分类 物流配送问题可按照其构成要素划分不同的种类“州“3 。 ( 1 ) 按物流中心的数目分：有单物流中心问题( 配送系统中仅有一个物流中 心) 和多物流中心问题( 配送系统中存在多个物流中心) 。 ( 2 ) 按车辆载货状况分：有满载问题( 由于客户需求和供应的货物数量大于或 等于车辆的载重量，所以完成一项配送任务需要一辆及其以上的配送车辆，配送 车辆需要满载运行) 、非满载问题( 由于客户需求或供应的货物数量小于车辆载重 量，多项配送任务可以共用一辆配送车辆，车辆在配送过程中经常处于不满载状 态) 以及满载和非满载混合问题( 由于一部分客户需求和供应的货物数量大于或等 于车辆的载重量，而另一部分客户需求或供应的货物数量小于车辆的载重量，造 成一些配送车辆需要满载运行，而另一些车辆则经常处于不满载状态) 。 基丁模拟退火遗传算法的中辆调度问题研究 ( 3 ) 按配送任务特征分：有纯送货问题( 仅考虑从物流中心向客户送货，也称为 纯卸问题) 、纯取货问题( 仅考虑把各客户供应的货物取到配送中心，也称为纯装 问题) 及取送混合问题( 即考虑将客户需求的货物从物流中心送到各个客户，同时 考虑将客户供应的货物从客户取到物流中心，也称为装卸混合问题或者集、送货 一体化问题) 。 ( 4 ) 按客户对货物取( 送) 时间的要求分：有无时间约束问题( 客户对货物的取 走和送到的时间无具体要求) 和有时间约束问题( 客户要求将需求的货物在规定的 时间窗内送到，将供应的货物在规定的时间窗内取走，也称为有时间窗的问题) 。 有时间约束问题又分为硬时间窗问题( 客户要求货物必须在规定的时间窗内送到 或取走，不能提前或拖后) 和软时间窗问题( 尽量在规定的时间窗内送到或取走客 户的货物，但可以提前或拖后，发生提前或拖后的情况时，要对配送企业实施一 定的惩罚) 。 ( 5 ) 按车辆类型分：有单车型问题( 所有配送车辆的载重量相同) 和多车型问 题( 配送车辆的载重量不完全相同) 。 ( 6 ) 按车辆对车场所属关系分：有车辆开放问题( 即车辆完成配送任务后可以 不返回其发出车场) 和车辆封闭问题( 车辆完成配送任务后必须返回其发出车场) ( 7 ) 按优化目标数分：有单目标问题( 仅考虑一个配送目标) 和多目标问题( 同 时考虑多个配送目标) 。 2 2 物流配送车辆调度问题的数学模型 2 2 1 问题的简化 根据配送系统中配送中心数目的多少，物流配送问题有单配送中心问题和多配 送中心问题之分。而现实中城市物流体系中，往往存在多个配送中心。因此，对 多配送中心问题的研究具有重要的现实意义。 现实中的多配送中心问题是十分复杂的，为了方便建模和求解，需要对现实 问题进行一些抽象和简化。现对本文研究的多配送中心问题做如下界定“”： ( 1 ) 从多个配送中心向多个客户送货，配送中心和客户的位置一定，配送中 第2 章物流配送卞辆调度问题及其常规求解思路 心能够满足所有客户的需求，且各个配送中心车辆充足。 ( 2 ) 各个客户需求的货物均可以相互混装，即可以装在同一配送车辆内；每 个客户的货物需求量不超过配送车辆的最大载重量；每个客户的送货要求必须满 足，且仅能由一台车辆完成，不允许分批配送。 ( 3 ) 每台配送车辆的最大载重量一定，不允许超载；配送时每台车辆都从配 送中心出发，向一些客户提供配送服务后，最终返回原配送中心。 ( 4 ) 对于客户要求将需求( 或供应) 货物送到( 或取走) 的时间，分别考虑以下 三种情况：无时间限制；要求在指定的时间窗内完成送货( 或取货) 任务，不 允许提前或拖后；有时间限制，但可以不遵守，不遵守时要对配送企业给予一 定的惩罚。 ( 5 ) 配送中心与客户之间以及客户相互之间的最佳路径的距离己知且固定；配 送车辆在配送中心、客户间的行驶时间己知且固定( 即在一个很小的范围内变动， 可以看成是固定) 。 2 2 2 问题的数学模型 车辆调度问题描述为：有m 个车场，各自拥有一定容量的车辆k ( m = 1 ，m ) 辆，负责对n 个用户进行货物分送工作，用户i 的货物需求量为g 。( i = l ，n ) ，且 最小于车辆的载重量g 。，每个用户可以由任意一个车场的车辆在特定的时间段内 服务，但只能有一辆车服务一次，每辆车完成运送任务后必须返回原车场，需求 一合适的调度方案使各车场的车辆能满足所有用户的需求，并使车辆总的运输成 本最低。 设用户编号为1 ，2 ，n ，车场编号为n + i ，n + 2 ，n + m 。 定义变量： x 孑。 = ：喜盏“的车辆。从用户1 行使到用户。 f1 车场m 的车辆k 被使用 y 。t 2 1o 否则 基丁模拟_ 退火遗传算法的车辆调度问题研究 g 。表示使用车场m 的第k 辆车的固定成本 表示车场m 的第k 辆车的载重量限制 e t , ，王 表示到达第i 个用户的时间要求 量表示第i 个用户的实际服务丌始时间 数学模型表示如下“州川“” m 1 n 5 善1 4 蒌k ( ”善+ m t l 蓍+ m d 。z + g 。，t ) + b 耄m a x 晖i 一 ) + 只套m a x ( 一_ ，。) k 乏，蒌z j _ 置一 再，z ；。乏z ；_ 1 w mm x 再，三，荟。z ；“ 一再蒌。蒌。j ；二1 一 荟g 一毛。； 模型中： 1 2 m n + 1 ，+ 2 ，n + m ) i 2 m ，+ l ，+ 2 ，n + m ) k 1 2 ，k ) i e 1 2 ，n ) j 1 2 ，n ) m n + 1 ，n + 2 ，n + m ) k 1 2 。k ) i m + l + 互n + m k 1 ，2 ，k 以表示用户i 到用户j 的运输成本，这里只考虑距离。 ( 1 ) 代表目标函数，即最短路径长度； ( 2 ) 表示各车场派出车辆的数目不能超过该车场所拥有的车辆数； ( 3 ) 确保车辆都是从各自的车场出发，并回到原车场； 1 1 ( 1 ) ( 2 ) ( 3 ) ( 4 ) ( 5 ) ( 6 ) ( 7 ) 第2 章物流配送下辆调度问题及其常规求解思路 ( 4 ) 和( 5 ) 确保每个用户只能被一辆车服务一次； ( 6 ) 定义了车辆容量约束； ( 7 ) 表示车辆不能从车场到车场。 为了增强模型的实用性，本论文在目标函数中增加了各车辆的使用固定成本。 该模型有较强的通用性，经过参数的不同设定，可以将其转化为不同类型的问题。 对于本模型中式( 1 ) ，当最和罡为零时，即转化为没有时间窗的多配送中心问题； 当它们充分大时，则转化为具有硬时间窗的多配送中心问题；当m = i 时，则转化为 相应的单车场问题。 2 3 物流配送车辆调度问题的常规求解思路 现有文献对于多配送中心问题的求解很多都采用了分解法。以下将对分解法 进行简要说明，同时对单配送中心求解的几种常规方法加以介绍。 2 3 1 分解法求解多配送中心问题 由于多配送中心问题涉及面很广、影响因素众多，为了求解方便，需要将问 题做适当简化。而分解法就是简化多配送中心问题的有效方法。分解法是将一个 相对复杂的多配送中心问题转换成多个相对简单的单配送中心问题，整个问题的 求解转换成分别对几个简单且相互独立的子问题的求解，而各个子问题最优解的 合成就是整个问题的最优解。分解法的优点在于能将复杂的大规模问题转化成几 个简单且规模较小的子问题，不但有效的简化了整个问题，同时也有效的减少了 得到最优解的计算时间。 ( 1 ) 最近距离分配法 即根掘距离最近原则，决定为某客户提供服务的配送中心。鉴于多配送中心 问题以总配送里程最短为优化目标，计算某客户与各配送中心的距离，该客户离 哪个配送中心最近，就将其分配到哪个配送中心。 设d 伽) ( 1 玎= 1 ，2 ，3 - m ，m 表示配送中心数量) 表示第i 个客户到第m 个配送中 心的距离。记集合d i = d ( m ) ，m = l m ，并选择m i n d i ，将该客户分配给配 基于模拟遄j c 遗传算法的乍辆调度问题研究 送中心m 。得到为每个客户服务的配送中心后，也就得到了每个配送中心服务的具 体客户。 采用此分配方法分配客户，有简单和快捷的特点。缺点是只单独考虑了各个 配送点与配送中心距离的因素，而没有考虑配送点之间的距离因素。 ( 2 ) 边界分配法叫 设d ( m ) ( m = 1 ，2 ，3 - m ，m 表示配送中心数量) 表示第i 个客户到第m 个配送中 心的距离。记集合d i = d ( m ) ，m = l m 。计算r ( i ) = m i n d i s u b m i n d i ，m i n d i 和s u b m i n d i 分别表示集合d i 中的最小值和次小值，选取适当的8 ，o 8 l 比 较r ( i ) 和8 的大小，当r ( i ) = a ，这时用户i 为边界点，对于边界点采用节约法分配： 假设有h 个边界点，通过r ( i ) 和8 的比较为配送中心m ( m = l ，2 ，3 m ) 分得帆 个配送点，则壹+ h = n 其中n 为配送点总数将边界点i ( i = l h ) 分别分配 给配送中心i l l ( m = l ，2 ，争。m ) ，并计算边界点i 分配给配送中心m ( m = l ，2 ，3 - - m ) 后， 与配送中心的其它各配送点的距离节约值s ( f ，) ： s 。( f ，) 一c 。f + c ，+ c j + c 一一( c 。j + c j 一+ c ) i c l 。+ c 。i cq 其中j = 1 j ：，e ，表示i ，j 之间的距离 s ：- 皇j - i ( “) ( m 2 1 m ，i = 1 h ) 即为分界点i 与配送中心m 的其它配送点的距离节约值总和。如果 s ( f ，m ) - m 口x ( s ：) ， ( m = 1 m ) 则将边界点分配给配送中心m 。边界分配法的优点是同时考虑了各个配送点与配 送中心距离及各个配送之问距离的因素。 第2 章物流配送下辆调度问题及其常规求解思路 2 3 2 单配送中心问题的常规求解法 对于单配送中心车辆调度问题，精确算法的计算量一般随问题规模的增 大呈指数增长，在实际中其应用范围很有限。因此这里主要介绍常规启发式算法： ( 1 ) s w e e p 算法 g i l l e t 和m i l l e r 的s w e e p 算法，其目的在于形成需求点的径向区域，从车 场出发的射线扫过这个区域，使不超过车辆容积的需求点组成一个区域，一个区 域就是一个组，当形成一系列这样的组后，再对每一组中的各点安排路线。 ( 2 ) 节约法( s a v i n gm e t h o d ) 节约算法。”1 是c l a r k e 和w r i g h t 在1 9 6 4 年提出的，它是目前用来解决v r p 模型最有名的启发式算法。它的核心思想是：将运输问题中存在的两个回路合并成 为一个回路。在合并过程中，整个运输问题的总运输距离将发生变化，如果变化 后的总运输距离下降，则称节约了运输距离。相应的变化值，叫做节约距离。它 是对旅行商问题的c - w 算法进行修正： 设勺为车辆从点i 行驾驶到点j 的费用。由c - w 算法，得到s u = + 。句一勺， 即为把点i 和点j 连接在一起时比i 和j 单独各在一条线路上的费用节省值。当 不考虑时间约束时，其算法与c - w 算法类似，只是在连接点对时，需考虑车辆载 重约束，即一条线路上各客户的货运量之和应不大于车辆的载重量。 若各项任务要求在一定的时间范围内完成，按费用节约值s 。连接点i 与j 时， 可能会使j 后面的任务的执行不满足时间要求。当连接点i 和点j 所在的线路时， 若车辆到达j 点的时间比原线路上j 点任务的开始时间提前，则车辆在j 后面的 任务处有可能需要等待；若连接后到达j 点的时间比原线路上j 点任务的开始时 间推迟，则j 后面的任务在完成时可能会发生延迟。 以e f 表示连接点i 和点j 所在的线路后，车辆到达j 点的时问比原线路上j 点任务的开始时间的推迟( 或提前) 量，则e f 可如下得到 ef |一st+ti + t l i si 基丁模拟退火遗传算法的乍辆调度u j 题研究 显然，e f ，t0 时，j 点任务的开始时间提前；e f ，o 时，开始时间不变 e f j ，o 时，开始时间推迟。 设车辆在线路上i 后面的各任务处均不需要等待的j 点的到达时间的最大可以 提前量为可，线路上i 后面的任务不会违反时间窗约束的j 点的到达对闯的最大 允许推迟量为0 ，和；可分别按下式计算： aj 。m i n s ，一a ，) ；m ，。i ，n - b ，一s ，) 当考虑连接点i 和点j 所在的线路时，需检查是否违反时间约束，即f ，t0 时， ef ，ta i ，车辆在j 后面的任务处不需要等待，否则，要等待；当q ，0 时， 若有ef ，s 。j ，则j 后面的任务的执行不会延迟，否则，要延迟进行a 由于时间约束的引入，在对称的费用情况下，连接点j 和点i 与连接点i 和 点j 已不再相同。 ( 3 ) 运用遗传算法解决单配送中心车辆调度问题，具体情况将在下一誊介绍。 1 5 第3 章 退火遗传算法一基丁遗传算法的对卞辆调度问题的解决 第3 章退火遗传算法一基于遗传算法的对车辆调度问题的解决 3 1 遗传算法及其在车辆调度问题中的应用 3 1 1 遗传算法概述 遗传算法( g e n e t i ca l g o r i t h m 简称g a ) 就是一种模拟自然进化的的仿生算法， 它模仿的机制是一切生命与智能的产生与进化过程。它通过模拟达尔文“优胜劣 汰、适者生存”的原理激励好的结构；通过模拟孟德尔遗传变异理论在迭代过程 中保持己有的结构，同时寻找更好的结构哺1 。 遗传算法起源于6 0 年代对自然和人工自适应系统的研究，最早由美国密执安 大学的h o l l a n d 教授提出。h o l l a n d 不仅设计了遗传算法的模拟与操作原理，还运 用统计决策理论对遗传算法的搜索机理进行了理论分析，建立了著名的模式定理 和隐含并行性原理，- 为遗传算法的发展奠定了基础