（电力电子与电力传动专业论文）遗传算法在物流配送车辆优化调度中的研究及应用.pdf

上海海事大学硕士研究生学位论文 w mt h ed e v e l o p m e n to fm a r k e te c o n o m ya n dl o g i s t bt e c h n o l o g y , l o g i s t i c sb u s i n e s sd e v e l o p e dr a p i d m i nl o g i s t i c s b u s i n e s s ，t h ev e h i c l e s c h e d u l i n gp r o b l e ma f f e c t sm o s u y0 1 1r a i s i n gs e r v i c eq u a l i t y , r e d u c i n gl o g i s t i c s c o s ta n di n c r e a s i n ge c o n o m i cb e n e f i t so fl o g i s t i c se n t e r p r i s e s ，w h i c hi st h e e s s e n t i a lt h i n gi nt h eo p t i m i z a 石o no fi o g i s t i c es y s t e ma n de s s e n t i a lc o n t e n ti n e l e c t r o n i cc o m m e r c e t h a ti st o s a yt h es y s t e mr e s e a r c ho fl o g i s t i c s d i s t r i b u t i o nv e h i c l e o p t i m a ls c h e d u l i n g i st h ed e v e l o p m e n to f i o c j i s t i c s i n t e n s i f i e d ，c o n s t m c t i o no ft h es y n t h e s i sl o g i s t i c ss y s t e m 。t h ee s t a b l i s h m e n to f m o d e ms c h e d u l i n gc o n h o l s y s t e m ，t h ed e v e l o p m e n t o f i n t e l l i g e n c e t r a n s p o r t a t i o ns y s t e m sf o u n d a t i o n i nd a l l yl i f ea n dp r o d u c t i o n ，m a n yp r o b l e m s s u c ha sm a l l d e l i v e r yp r o b l e m s ，b u ss c h e d u l i n gp r o b l e m s ，e l e c t r i c i t y d i s p a t c h i n gp r o b l e m s ，p i p e l i n el a y i n gp r o b l e m sa n dc o m p u t e rn e t w o r k d e s i g n i n gp r o b l e m sc a na l lb es e e na sl o g i s t i s sd i s t r i b u t i o nv e h i c l es c h e d u l i n g p r o b l e m s t a k i n gl o g i s t i c s d i s t r i b u t i o nv e h i c l es c h e d u l i n g p r o b l e ma s 如 s t u d y i n go b j e c t , t h i sp a p e rh a sb o t ht h e o r e t i c a la n dp r a c t i c a lv a l u e 1 1 1 e l o g i s t i c s d i s t r i b u t i o nv e h i c l es c h e d u l i n g p r o b l e m i sar e s t r a i n t c o m b i n a t i o n o p t i m i z a a o nq u e s t i o nb e l o n g s t ot h en p p r o b l e m ( n o n d e t e r m i n i s t i cp o l y n o m i a lp r o b l e m ) a i o n gw i t ht h eq u e s t i o ni n p u ts c a l e e x p a n s i o n ，t h es o l u t i o nt i m ea s s u m e st h eg e o m e t r i cs e r i e sr i s e i nt h i sa r t i c l e 。i d i s c u s sw n ht h eg e n e t i ca l g o r i t h mo ft h ei n t e l l i g e n c ea l g o r i t h mt os o l v e st h e v e h i c l e ss c h e d u l i n gp r o b l e m f i r s t l y t h i sa r t i c l ea n a l y z e st h eo u t l i n eo ft h ei o g i s t i s sd i s t r i b u t i o nv e h i c l e s c h e d u l i n go p t i m i z a t i o nq u e s t i o n 。a sw e l la st h ef o u n d a t i o no ft h i sq u e s t i o n p r o p o s e d 。w h i c hh a sc a r r i e do nt h ed e s c r i p t i o n 。t h em a t h e m a t i c a lm o d e i a n a l y s i sa sw e l l a st h ec o r e s p o n d i n gs o l u t i o n a l g o r i t h ma n a l y s i st o t h e q u e s t i o nc o m m o n l yu s e dt w ou s e dt w ok i n d so fv s p t h e ni nt h ef o u n d a t i o no f d e t a i l e di n t r o d u c t i o no f g e n e t i ca l g o r i t h m ，u s i n gm a t l a b 7 0s i m u l a t i o n s o f t w a r et oh a v ei n h e r i t e dt h es i m u l a t i o no ft h eg e n e t i ca l g o r i t h ma n dt h e c o m p a r a t i v ea n a l y s i s ，c o n f i r m e dt h ef e a s i b i l i t yo ft h eg e n e t i ca l g o r i t h mt os o l v e t h eq u e s t i o no ft h ed i s t r i b u t i o nw a yo p t i m i z a t i o n ，i nt h ef o u r t hc h a p t e r ，i a n a l y z e dt h et r a v e ls a l e sp r o b l e mo ft h eg e n e t i ca l g o r i t h mo ft h en o n - f u l ll o a d 上海海事大学硕士研究生学位论文 v e h i c l e s o p t i m i z a t i o ns c h e d u l i n g , t h e c o m m o nv e h i c l e s o p t i m i z e t j o n s c h e d u l i n gp r o b l e ma sw e l la st h et i m ew i n d o wo fv e h i d e so p d m i z a t t o no f t s c h e d u l i n gp r o b l e ms e p a r a t e l yt oc a r r yo nt h eh e r e d i t yt h eg e n 酬ca l g o r i t h m d e s i g n ，w e l la st e s ts i m u l a t i o na n a l y s i s ，i nt h e 触c h a p t e r , lh a dc o n s i d e r e d u n d e rt h es i t u a t i o no ft h ed a l l ys c h e d u l i n gw o r ko fl o g i s t i c sd i s t r i b u t i o nw a s v e r yb i ga n dt h ec a r d e rv e h i c l ew a sv e r yg r e a t 。t h es i t u a t i o nt h 献p u r e l yu s e d t h ea r t i f i c i a lm e t h o di nt h es c h e d u l e dt i m ec o n t i n u o u s l yt od e t e r m i n et h ed a l l y f u r t h e s ts c h e m eo fd i s t r i b u t i o nv e h i c i ew h o l es c h e d u l i n gi s i m p o s s i b l e 。 p r o p o s e dt oe s t a b l i s ht h e1 0 9 i s t i c sd i s t r i b l n i o nv e h i c l es c h e d u l i n gs y s t e m o p a m i z a t i o n ，i tn e e dt oc o m p u t e rr e a l i z a t i o no ft h ei o o i s t i c sd i s l d b u d o nv e h i d e s c h e d u l i n ga l g o r i t h mo no p u m i z a 舡o n ，a n dd i s c u s s e di t sc o r r e l a t i o nd a t a p r o c e s s i n ga n dt h er e a l i z a d o np r o c e s so fa l g o r i t h mi nt h i sc h a p t 计 k e y w o r d s ：l o g i s t i c sd i s t n b u t i o n , v s p , g e n e t i ca l g o r i t h m a nu j 蚰( r o w e re l e c t r o n i c s p o w e r1 ) r i v e ) d i r e c t e db yp r o f y uh o n g s h e n g i i l 论文独创性声明 本论文是我个人在导师指导下进行的研究工作及取得的研究成 果。论文中除了特别加以标注和致谢的地方外，不包含其他人或其 他机构已经发表或撰写过的研究成果。其他同志对本研究的启发和 所做的贡献均已在论文中作了明确的声明并表示了谢意。 作者签名：壑兰星日期：型翌丝 论文使用授权声明 本人同意上海海事大学有关保留、使用学位论文的规定，即： 学校有权保留送交论文复印件，允许论文被查阅和借阅；学校可以 上网公布论文的全部或部分内容，可以采用影印、缩印或者其它复 制手段保存论文。保密的论文在解密后遵守此规定。 作者签名：量兰呈导师签名：日期：竺翌：墨：芝! 漩 上海海事大学硕士研究生学位论文 第一章绪论 1 1 课题研究背景与实际意义 在经济全球化和信息化的推动下，现代物流业已从为社会提供传统运输服 务，扩宽到以现代科技、管理和信息技术为支柱的综合物流系统。物流是在2 0 世纪5 0 年代新发展起来的一门实践性很强的综合性交叉学科，是当代最有影响的 新科学之一，它全面融会了运筹学、经济科学及管理科学，揭示了运输、储存、 装卸搬运、包装、流通加工、物流信息等物流各要素的内在联系，物流在经济发 达国家被视为继原材料、劳动力以外的“第三利润源泉”在现代物流集约化、 一体化的发展中，车辆优化调度是直接与消费者相连的重要环节，涵盖的面也比 较广其中包括配货作业，即货物的分拣过程，根据各个用户的不同需求，在配 货中心将所需要的货物迅速的挑选出来的过程，加大车辆调配执行的效率，这需 要仓储的优化：车载货物的配装，即在配送货物时要考虑车辆的载重和容积，使 车辆的载重和容积充分利用，还要考虑配送多个客户的问题：配送线路的确定， 配送线路合理与否对配送速度、成本、效益影响很大，特别是多用户配送线路的 确定更为复杂。采用科学的、合理的方法来确定配送线路是车辆优化调度的核心 部分，是物流系统优化、物流科学化的关键一环。对车辆进行优化调度，即合理 的进行配货优化、货物配装优化，特别是配送路线优化，能够提高里程利用率， 降低行驶费用，大大减少车辆空驶里程，增加货运量，节约燃料，降低大修费， 提高营运收入，从而带来巨大的经济效益。另外，还可以产生良好的社会效益， 体现在减少废气排放量，降低城市空气污染水平，降低交通事故率。 目前，在我国一些地区，公路货物运输一方面存在超负荷运行：另一方面由 于缺乏科学组织，造成货运车辆使用效率低下，浪费严重。运输经营管理落后是 一个重要问题，表现为先进的管理手段采用较少，管理方法落后，一般仍凭经验 调度，调度质量差、优化程度低，空驶率高、严重浪费，不能充分发挥运输工具 的效能。而在国外一些发达国家，货运车辆优化调度己广泛地运用于生产、生活 上海海事大学硕士研究生学位论文 的各个方面，如报纸投递线路的优化、牛奶送达线路优化、电话预定货物的车辆 线路设计、垃圾车的线路优化及垃圾站选址优化、连锁商店的送货线路优化等等 为了改善货物运输的质量状况，充分发挥运输车辆的效能，除了进一步扩大和改 善城市道路系统和交通设施之外，加强运输的科学组织管理也是极其重要的一个 方面而且从所需投资和见效迅速等方面考虑，后者往往更为现实，从而意义更 大经济的发展要求协调的综合运输体系支持，即整个运输形成网络，这样对相 应的组织管理也提出了更高的要求。因此，加强货运组织的科学管理，对货运车 辆进行优化调度，配送线路进行优化管理，有着极为重要的意义。可以说对货运 车辆调度，配送线路优化理论与方法进行系统研究是建立现代调度指挥系统、发 展智能交通运输系统的基础。 1 2 国内外研究现状及分析 由于车辆线路的优化是车辆优化调度的核心，目前国内外对车辆优化调度的 研究基本是针对于车辆配送线路优化的研究下面我们就来考察一下国内外对车 辆调度问题的研究车辆优化调度问题( v e h i c l er o u t i n ga n ds c h e d u l i n g p r o b l e m ，简记v r p v s p ) ，是由d a n t z i g 和r a m s e r 于1 9 5 9 年首次提出的( w a t e r s 1 9 8 4 ) 2 ，自此，很快引起运筹学、应用数学、组合数学、图论与网络分析、 物流科学、计算机应用等学科的专家与运输计划制定者和管理者的极大重视，成 为运筹学与组合优化领域的前沿与研究热点问题。各学科专家对该问题进行了大 量的理论研究及实验分析，取得了很大进展。所谓配送优化，就是在配送的诸环 节，如流通加工、整理、拣选、分类，配货、末端运输中，从物流系统的总体目 标出发，运用系统理论和系统工程原理和方法，充分利用各种运输方式优点，以 运筹学等数量方法建立模型与图表选择和规划合理的配送线路和配送工具，以最 短的路径、最少的环节、最快的速度和最少的费用，组织好物质产品的配送活动， 避免不合理配送情况和次优化的出现。车辆优化调度f 司题一般定义为：对一系列 装货点和( 或) 卸货点，组织适当的行车线路，使车辆有序地通过他们，在满足一 定的约束条件( 如货物需求量、发送量、交发货时间、车辆容量限制、行驶里程 限制、时间限制等) 下，达到一定的目标( 如路程最短、费用最少、时间尽量小、 利润最大、使用车辆数尽量少等) 。 2 上海海事大学硕士研究生学位论文 国外对v r p 和v s p 作了大量而深入的研究，目前，问题的形式已有很大发展， 该问题己不仅仅局限于公路交通运输领域，在水运、航空、通讯、电力、工业管 理、计算机应用等领域也有一定的应用，其算法已用于航空乘务员轮班安捧、生 产系统中的计划与控制等多种组合优化问题。对v r p 与v s p ，是根据问题的空间特 性和时问特性的相对重要性来划分的( b o d i n1 9 8 3 ) ”一般认为，当不考虑时 间要求，仅根据空间位置安捧线路的称为r o u t i n g ，根据时间要求安排线路的称 为s c h e d u l i n g ，同时考虑空间位置和时问要求的称为r o u t i n g 和s c h e d u l i n g 混合 问题。也有不区分两者的，如有具体约束则加上定语，如将有时间要求的车辆调 度问题称为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 。因为在现实应用中， s c h e d u l i n g 比r o u t i n g 范围宽，因此学者们主要研究s c h e d u l i n g ，即货运车辆优 化调度( v e h i c l es c h e d u l i n gp r o b l e m ，简称v s p ) 。 在配送网的优化方面，由于配送网的优化过程中要考虑局部的交通环境，购 买能力，配送站点的选取以及配送品种的选取等，在配送时要考虑节省成本，又 要满足顾客的需求，因此是一个多目标优化问题，同时也是个n p 难问题。 针对这个问题，国内已经有多种解决方法，主要包括如下的方法： ( 1 ) 压缩遗传算法与模糊数学相结合的方法 该算法运行可以节省内存，同时具有较高的效率，求解时一个个体可以表达 多种信息，因此很适合求解多目标的优化难题。迸而还可以引入最小二乘法进行 加速，来获得满意的结果，另一方面客户的满意程度和交通环境等也是一个不能 用确定的方法来描述的量，因此可以采用模糊的方式来表达。 ( 2 ) 蚁群算法和模糊数学相结合的方法 蚁群算法是模仿自然界中蚁群寻找食物的过程来进行优化的，由于每一蚂蚁 都可以走不同的路径。因此蚁群算法适合分布计算，特别是多目标的求解问题。 对于这种配送网的优化调度问题也不例外。另一方面如前所述对于问题中人为因 素大不能确定表达可以采用模糊数学的方式。 ( 3 ) 路径的选择问题 路径的选择中不但要考虑运输成本，即使路径尽量的短，还要考虑运输的时 间，运输中的收费问题，避免因此在路径的选择时要实时的考虑交通状态，避免 塞车。对这样的问题实时性要求比较高因此应该采用实时调度，以便驾驶员随时 调整行车路径。 上海海事大学硕士研究生学位论文 1 3 论文的主要工作内容及成果 1 3 1 研究预期目标及研究方法 1 3 1 1 研究预期目标 货物输送是指配货作业完成后，将用户所需的货物使用汽车或其他运输工具 从配送仓库或配送中心送至各用户的活动，配送货物输送包括送货计划的制定， 货品出库，车辆调度与配状，运输路线的优化与决策，客户服务，车辆营运与行 车人员的管理等内容，是配送核心活动环节之一，它体现的是配送活动的。送” 的特色功能，是配送管理的重点与难点。 对物流配送车辆优化调度问题，有的学者是根据问题的空间特性和时间特性 的相对重要性来划分的( b o d i n1 9 8 3 ) 一般认为，当不考虑时间要求，仅根据 空问位置安捧线路时称为车辆线路安排问题( v e h i c l er o u t i n gp r o b l e m ，v r p ) ： 考虑时间要求安排线路时称为车辆调度问题( v e h i c l es c h e d u l i n gp r o b l e m ， v s p ) ；同时考虑空间位置和时间要求时称为r o u t i n g 和s c h e d u l i n g 混合问题 ( v e h i c l er o u t i n ga n ds c h e d u l i n gp r o b l e m ，简记v r p v s p ) 对于v r p 与v s 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 本文认为，s c h e d u l i n g 比 r o u t i n g 范围广，因此对r o u t i n g 简单介绍以及其应用遗传算法实例计算、仿真 的基础上，重点介绍s c h e d u l i n g ，将本文的车辆优化调度问题统称为v s p 1 3 1 2 研究方法 1 、车辆优化调度问题是一个有约束的组合优化问题，属于n p 难题 ( n o n d e t e r m i n i s t i c p o l y n o m i a l p r o b l e m ) 。随着问题输入规模的扩大，求解时间呈几 何级数上升。本文中讨论用智能算法中的遗传算法来求解车辆调度问题。 遗传算法主要由选择、交叉和变异三个算子组成，分别模仿自然界进化过程 中的自然选择和群体遗传过程中发生的交配和突变等现象。采用遗传算法求解车 辆优化调度问题时，一般按照以下步骤进行： ( 1 ) 确定染色体的编码和初始群体 4 上海海事大学硕士研究生学位论文 采用自然数对可行线路进行编码，如长度为l + m 的染色体可写为： ( o n 4 m ，b0 4 2 1 ，抽o ，o 钿， 。) 其中，硒表示第吗项任务，这样的染色体结构可理解为车辆从车场0 出发，经过 任务f l l ，i 1 2 ，i u 后回到车场0 ，形成子路径l ；然后又从车场0 出发，经过 任务i 2 l ，b 后返回车场，形成路径2 ，如此反复，直到所有的肼项任务全部 被完成为止在子路径1 内交换i l l 和i 1 2 的位置表示行走路径的改变，也使函数 目标改变，这样，下面的遗传叠代可使函数目标最小，也即趋向于最佳或较佳的 路径 初始群体的产生采用随机方法，随机产生f 个城市的全捧列，根据任务的源 点和汇点将o 标准插入捧列中，形成一条初始染色体。如此反复，直到满足群体 数，群体数一般大于2 0 个 ( 2 ) 确定适应度函数 车辆调度的优化目标有多种多样，常见的目标有总运费最小，总运输时间最 短，空载车总运行时间最小，完成任务所需的车辆最小总运输时间最短，空载车 总运行时间最小，完成任务所需的车辆最小等，以总运费最小为例，其目标函数 为： c = m i n 善善g 式中，c , - j 为从源点i 到汇点，每辆车的单位费用，局为每班从源点i 到汇点 ，的满载车的数量。m , n 为源点和汇点的数目。 ( 3 ) 处理约束 为保证车辆调度优化的正确性，约束往往必不可少，常见的约束有汇点处理 能力约束，非负约束，车流连续性约束。 一般采用惩罚的方法来处理约束，如果一个染色体对应的解违反了某个约 束，根据其违反程度给予一定的惩罚，使其具有较小的适应度值。这样在不损失 群体数目的基础上，随着叠代的进行，使不可行解的数目在群体中所占比例越来 越小，可行解的数目则逐渐增加，并趋向最优解。 ( 遗传算子 经典的遗传算子包括复制、交叉、变异。复制算子的目的是保留优良个体， 上海海事大学硕士研究生学位论文 避免基因缺失，提高全局收敛性和效率目前常用的复制算子有放回式随机复制 又称轮盘赌复制，无放回式随机复制等十几种。 交叉算子的作用是组合出新的个体，在染色体空间进行有效搜索，同时降 低对有效模式的破坏概率染色体采用自然数编码时，交叉算子一般有部分匹配 交又，顺序交叉，圈交叉等。染色体采用二进制编码时，常采用的交叉算子有单 点交叉，双点交叉等。交叉算子中采用的交叉率一般在0 7 5 - - 0 9 5 之间 变异算予是为了克服基因缺失和不成熟收敛。目前常用的变异算予有常规 位变异，均匀交异和菲均匀变异等。变异算子的变异率一般为0 0 0 5 0 0 1 。 除了上述的经典遗传算子外，人们又研究了其他一些算子，称为高级算子， 如显性算予、倒位算予、分离和易位算子、迁移算子等 固确定调度方案 通过上述的遗传操作，产生性能最优的染色体串，根据初始的编码规定将该 串解码成最优调度方案。实用中，人们往往将遗传算法与其他方法如启发式方法 和模拟退火算法杂合，以及将调度专家经验融入模型和遗传搡作中，以提高求解 的效果。 1 3 2 可行性与创额性 在大规模物流配送系统中无论是配送网络的优化，库存管理的控制，运输中 的路径选择，还是仓库的优化问题都可以归结为n p 完全类的多目标优化调度问 题，这类问题随着规模的不断增加，求解的难度将成指数级增加，因此用现有的 优化算法如整数规划，分支定界等经典算法来解决会有运行时间慢，效率低的缺 点。当问题规模进一步增大时，就会不可行。 车辆优化调度问题是一个有约束的组合优化问题，属于n p 难题 ( n o n d e t e n n i n i s t i cp o l y n o m i a lp r o b l e m ) 。随着问题输入规模的扩大，求解时间呈几 何级数上升。 求解车辆优化调度的方法可以分为精确算法、启发算法和智能算法。精确算 法主要有分支界定法等；启发式算法主要有构造算法、两阶段法等：智能算法分 为神经网络方法、遗传算法和模拟退火算法等。精确算法的计算量随着车辆优化 问题规模的增大呈指数增长，如当卸货点的数目超过2 0 个时，采用精确算法求 6 上海海事大学硕士研究生学位论文 解最短运输路径的时间在几个小时之上。精确算法不适应求解大规模的车辆优化 调度问题，所以本文采用智能算法中的遗传算法来解决车辆优化调度问题是可行 的 配送路线是指各送货车辆向各个客户送货时所要经过的路线。配送路线合理 与否对配送速度，成本，效益影响大，采用科学的合理的方法来优化配送路线， 是配送活动中非常重要的一项工作。配送活动中涉及许多优化决策问题，配送线 路的选择就是其中一个在选择配送路径时，不仅要考虑运输距离，运输环节， 还要考虐运输工具，运输时间和运输费用等因素。因此，配送线路的选择实际上 是一个多目标决策。决策目标可以是运输费用最少，运输分险最小，运行时间最 短或需求满足情况最好。 本文的创新之处在于在优化方法上，将国内外一些最新的软计算方法对调度 算法进行融合，同时也加入自身的创新，提出了新的软计算的算法。这些算法用 在大规模复杂调度方面收到了很好的效果。概括起来，这些算法运行效率高，能 在规定的时间内找到满意解；可操作性强，容易用软件实现，同时编制出的软件 健壮性好，可移动性强，适于扩展，适合编制组态软件。 7 上海海事大学硕士研究生学位论文 第二章物流配送车辆优化调度问题综述 2 1 物流配送车辆优化调度问题 2 1 1 物流配送车辆优化调度的概述 随着社会主义市场经济的发展，作为“第三利润源泉”的物流对经济活动的 影响日益明显，越来越引起人们的重视，成为当前“最重要的竞争领域”，未来 的市场竞争，物流将起着举足轻重的作用。 配送是物流中一个重要的直接与消费者相连的环节。配送一般定义为，将货 物从物流结点送达收货人的过程。配送是在集货、配货基础上，完全按用户要求， 包括种类、品种搭配、数量、时问等方面的要求所进行的运送，是。配”和“送 的有机结合形式配送流程一般如下图所示。 工 厂 图2 _ l 配送流程图 l b 1 进 闺母一三 货 l1 ” 电子商务的发展，新的物流配送模式的出现，存贮已不是必然的环节。因此 配送主要包括以下几部分： ( 1 ) 集货作业。从生产工厂进货、并集结的过程。 ( 2 ) 配货作业。配货即货物的分拣过程，根据各个用户的不同要求，在配 送中心将所需要的货物挑选出来的过程。 ( 3 ) 车载货物的配装。由于配装作业本身的特点，配装工作所需车辆一般 为汽车，由于配送货物的质量和体积的差异，在配装货物时要考虑车辆的载重和 容积，为使车辆的载重和容积充分利用，还要考虑一趟多送几户的问题。 ( 4 ) 配送线路的确定。配送线路合理与否对配送速度、成本、效益影响很 8 用 户 上海海事大学硕士研究生学位论文 大，特别是多用户配送线路的确定更为复杂、采用科学的、合理的方法来确定配 送线路，是配送活动中非常重要的一项工作。 随着物流配送集约化、一体化的发展，常将配送的各个环节综合起来，核心 部分为配送车辆的集货、货物配装及送货过程。进行配货系统优化，主要就是配 送车辆优化调度，包括集货线路优化、货物配装及送货线路优化，以及集货、货 物配装和送货一体化优化在国外，类似的工作已广泛地运用于生产、生活的各 个方面，如报纸投递及线路的优化、牛奶配送及送达线路的优化、电话预订货物 的车辆载货和线路设计、垃圾车的线路优化及垃圾站选址优化、连锁商店的送货 及线路优化等等。 物流配送车辆优化调度，是物流配送优化中关键的一环，也是电子商务活动 不可或缺的内容。对货运车辆进行优化调度，可以提高物流经济效益、实现物流 科学化。对货运车辆优化调度理论与方法进行系统研究是物流集约化发展、建立 现代调度指挥系统、发展智能交通运输系统和开展电子商务的基础 2 1 2 物流配送车辆调度问题的提出 国外将物流配送车辆优化调度问题归纳为或称之为v e h i c l er o u t i n g p 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 。 物流配送车辆优化调度问题最早是由d a n t z i g 和r a m s e r 于1 9 5 9 年首次提出 的，自此，很快引起运筹学、应用数学、组合数学、图论与网络分析、物流科学、 计算机应用等学科的专家与运输计划制定者和管理者的极大重视，成为运筹学与 组合优化领域的前沿与研究热点问题。各学科专家对该问题进行了大量的理论研 究及实验分析，取得了很大进展。 国外对物流配送车辆优化调度问题作出了大量而深入的研究，例如早在1 9 8 3 年b o d i n 、g o l d e n 等人在他们的综述文章中列举了7 0 0 余篇文献。在 c h r i s t o f i d e s ( 1 9 8 5 ) ，g o l d e n 和a s s a d ( 1 9 8 8 ) 编辑的论文集，以及h l t i n k e m e r 和g a b i s h ( 1 9 9 1 ) ，l a p o r t e ( 1 9 9 2 ) ，s a l h i ( 1 9 9 3 ) 等的综述文章中都进行了详尽 的阐述。该领域的代表人物有b o d i n ，c h r i s t o f i d e s ，g o l d e n ，a s s a d ，b a l l ， l a p o r t e ，r i n n o o yk a n ，l e n s t r a ，d e s r o s i e r s 和d e s r o c h e r s 等人。 目前，问题的形式已有很大发展，该问题已不仅仅局限于汽车运输领域，在 9 上海海事大学硕士研究生学位论文 水运、航空、通讯、电力、工业管理、计算机应用等领域也有一定的应用，其算 法已用于航空乘务员轮班安捧、轮船公司运送货物经过港口与货物安摊的优化设 计，交通车线路安排、生产系统中的计划与控制等多种组合优化问题。 对物流配送车辆优化调度问题，有的学者是根据问题的空间特性和时间特性 的相对重要性来划分的( b o d i nt 9 8 3 ) 。一般认为。当不考虐蹲河耍哥乙返根据 - - 空间位置安捧线路时称为车辆线路安捧问题( v e h i c l er o u t i n gp r o b l e m ，v r p ) , 一， 考唐时回要塞塞挂线懿刖甬滂珀确峨刚萎阎题j 皿出址l 金曼b ! 坐! ! ! ! 塑旦! ! 竺： 幽_ 垦堕董查窒旦垡重塑堕塑墨耋堕整盘_ 里塑蔓堡堡! ! ! ! 竺! ! 竺兰竺望矍 ( v e h i c l er o u t i n ga n ds c h e d u l i n gp r o b l e m ，简记v r p & v s p ) 对于v r p - qv s 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 本文认为，s c h e d u l i n g 比r o u t i n g 范围广，因此对r o u t i n g 简单介绍以及 其应用遗传算法实例计算、仿真的基础上，重点介绍s c h e d u l i n g ，将本文的车 辆优化调度问题统称为v s p 。 该问题一般定义为：对一系列装货点和卸货点，组织适当的行车线路，使车 辆有序地通过它们，在满足一定的约束条件( 如货物需求量、发送量、交发货时 间、车辆容量限制、行驶里程限制、时问限制等) 下，达到一定的目标( 如路程 最短、费用最少、时间尽量少、使用车辆数尽量少等) 。 该问题在实际应用中，主要分为以下三类： 1 时间表安排问题：到达服务结点或弧的时间是事先规定的。如航空公司 人员的值班安排表。 2 路线安排问题：若到达时间没有规定，就是路线安排问题。如钢铁厂的 钢铁扎制计划的编制问题。 3 时间表安排和路线安排的混合问题：对时间和线路都有要求的问题，如 物资供应的配送问题。 v s p 被提出后，引起了国内外各学科学者的重视，他们从不同的角度，不同 方向对其进行研究。本文按不同的分类标准对v s p 进行分类，如表2 1 所示： 表2 - 1 车辆优化调度问题归类分析表 l 1 运输费用最小2 车辆空载率最低 i目标性质 3 行驶路程最短4 效率最高 l 5 所需车辆数量小 6 服务准确性最高 上海海事大学硕士研究生学位论文 优化目标数目1 单目标问题2 多目标问题 车辆对车场的所属关系 1 车辆开放问题2 车辆封闭问题 车辆数目1 单车场问题2 多车场问题 车辆类型 1 单车型问题2 多车型问题 车辆载货情况1 满载问题2 非满载问题 l - 纯装问题幺纯卸问题 任务特征 3 装卸混合问题 1 纯棒的时间表安捧时间问题 服务时问2 车辆路线安捧和时间表安捧的混合问题 3 车辆路线安捧问题( 没有时间规定) 1 有向网络2 无向网络 基本运输网络 3 混合问题 1 所有车辆容量约束相同 车辆容量约束 2 不同车型容量约束不同3 没有规定 1 所有车辆最大车辆运行耐间相同 最大车辆运行时间2 不同车型最大车辆运行时间不同 3 没有严格规定 1 可变成本 2 变动成本 运输成本 3 延迟或等待的惩罚费用 需求点的性质1 确定性的2 随机性的 其它约束 从表2 - 1 不难看出，这个归类分析表包括了常用车辆路线安排问题的多种可 能形式。例如，已知单车场、单车型、无容量限制的车辆在无向网络的需求点收 集单位需求量、只考虑运输费用最小所遍历路线的总长度的目标函数，该问题就 是常见的旅行商问题。由于情况不同，车辆调度问题的模型构造及算法有很大差 别，对调度问题的正确描述将有利于问题的建模与求解。 2 2 常用的两类v s p 的数学描述 在日常生活和生产实际中，许多问题多集中在只有装货任务或只有卸货任务 的车辆调度问题。如有一个配送中心需要向几个顾客运送货物，每个顾客对货物 有一定要求，运送货物的车辆在配送中心装满货物后出发，把货物送到客户处， 完成任务后返回货场，如何确定满足用户需求的费用最小的车辆行驶线路，即送 货车辆优化调度。又如，若干厂家生产一些产品，需要运到中心仓库，车辆从仓 库出发，到各厂家去装货，装满后返回仓库，在满足厂家发货的要求下，按什么 线路行驶可使总费用最少，即集货车辆优化调度问题。这两个问题的实质是相同 的。 研究配送方式下的车辆优化调度问题一般有几个前提条件： 1 1 上海海事大学硕士研究生学位论文 1 配送中心到客户之间的运输距离已知； 2 。每一次车辆调度中客户位置和需求量已知； 3 被配送的物资可混装； 4 车场有足够的运输能力； 5 流通中心有足够的物资可配送； 6 对带有时间窗问题的车辆调度问题，客户限定的服务时问范围已知； 7 服务中的工作时间已知，即装、卸货时间已知。 配送车辆优化调度的目标是使总的运输费用最小，其中影响总运费的最主要 因子是运输总吨公里数。配送计划中的最优配送路线一般须符合以下约束条件： 1 满足用户提出的到货时问范围的要求； 2 满足所有客户的品种、数量、规格需求； 3 各配送路线的货物量不超过车辆容积和载重量的限制； 4 出于安全考虑，对发送车辆每天的总行驶时间和总行驶距离预设上限； 5 在配送中心现有运力允许的范围内。 在实际遇到的问题中，上述条件可能全部考虑，也可能只考虑其中几项。配 送系统的有效调度方案应明确给出符合实际约束条件下应派出的车辆数、车型、 行车路线、运行时间和到达时间。实施配送车辆调度方案时，在保证服务质量的 前提下，使总的运费最小。本文给出三种常用的车辆优化调度模型，以供物流企 业参考使用 2 2 1 集货或送货非满载车辆的优化调度模型 2 2 1 1 问题的描述 该类问题一般描述为：现有一个配送中心 o ) ，拥有容量为d 的车辆k 辆( 一 般k 没有限制) ，为n ( n = 1 ，2 ，玎) 个客户提供服务，已知客户点f 的货运 量为g 。( f = l ， ) ，且g ，q ，求满足货运需求的费用最小的车辆行驶路 线。在日常生活和生产实际当中，许多类似的问题都可归结为这类问题。如有一 个配送中心，需向几个顾客运送货物，每个顾客对货物有一定的需求，运送货物 的车辆在配送中心装满货后发出，把货送到各顾客处，完成任务后返回配送中心， 如何确定满足用户需求的费用最小的车辆行驶路线，即送货车辆优化调度。又如， 上海海事大学硕士研究生学位论文 若干厂家生产一些产品，需要运到中心仓库，车辆从仓库出发，到各厂家去装货， 装满后返回仓库，在满足厂家发货要求的情况下，按什么线路行驶，可使总费用 最小，即集货车辆优化调度 这两个问题实质是相同的，只有装货任务或只有卸货任务。在货物量较少的 情况下，用一辆车完成一项任务时，车辆不能满载，这样，车辆的利用率较低， 因此可考虑用一辆车完成多项任务。如图2 - 2 所示，配送中心用3 辆车承担7 个 客户点的送货任务时，安排行驶线路( 图中同心圆表示配送中心，小圆圈表示客 户点) 圈2 _ 2 配送运输示意图 2 2 1 2v s p 数学模型分析 该类问题的数学模型如下： m i n z - 艺c 岱班( 2 - 1 ) g ；y 。墨q vk(2-2) y t 一1 i ：1 ，n ；( 2 - 3 ) x 社一y 业j 氆1 ，皿v k 芝x 秘一y m i ；0 ，1 n ；v k ( 2 国 x f i o 。= g l i ，j = o ，1 ，砧v k ( 2 - 6 ) y n o 魏 i ：0 ，1 ，皿v k ( 2 - 7 ) 其e p 的变量定义如下： ( 1 ) 决策变量y 。，x 驰 f 1 客户点韵需求由车辆i 完成 y * = j o 否则 上海海事大学硕士研究生学位论文 1 车辆i 从点珩驶到点， z 广1 0 否则 l ( 2 ) g 。：代表客户点i 的货物需求量 ( 3 ) q ：配送中心车辆的额定载重量，且g 。o ( 4 ) c 口：从点i 到点j 的运输成本，它的含义可以是距离、费用；时间等，一般 根据实际情况确定，可同时考虑车辆数和运行费用，如下确定： 当i = o ( 即i 表示配送中心) 时，包括固定费用和运行费用 c o j - c o + c l o j j = 电1 ，丑； 当i 为任务点时，只有运行费用，即 c 目- c ，目i - oj 砘1 ，n ； 其中，c ，为相对于运行时间的费用系数；c 。为车辆的固定费用，即增加一辆车的边际费用 一般认为，派出一辆车的固定费用远远高于车辆行驶费用，因此该模型是在极小化车辆数的 前提下，再极小化运行费用减小c o 的值将会使使用的车辆数增多，而线路