（交通运输规划与管理专业论文）多配送中心车辆调度问题的模型和算法研究.pdf

北京交通大学硕士学位论文多配送中心车辆调度问题的模型和算法研究 摘要 配送是现代化物流系统的一个重要环节，它是指按用户的订货要 求，在配送中心进行分货、配货，并将配好的货物及时送交收货人。在 配送业务中，存在许多优化决策问题，其中配送车辆调度问题对配送企 业加快配送速度、提高服务质量、降低配送成本及增加经济效益影响较 大。根据配送中心数目的多少，配送车辆调度问题有单配送中心车辆调 度问题和多配送中心车辆调度问题之分。在城市物流体系中，往往存在 多个配送中心。因此，对多配送中心车辆调度问题的研究具有重要的现 实意义。 本文围绕多配送中心车辆调度的模型和算法开展研究，主要做了以 下工作： ( 1 ) 在对无时限多配送中心车辆调度问题和有时限多配送中心车 辆调度问题进行描述的基础上，分别建立了无时限多配送中心车辆调度 问题和有时限多配送中心车辆调度问题的基于直观描述的数学模型。 ( 2 ) 设计了多配送中心车辆调度问题的求解策略，即利用距离最 近分配法划定每个配送中心服务的客户，进而将个多配送中心车辆调 度问题转化成多个单配送中心车辆调度问题进行求解。 ( 3 ) 设计并实现了无时限多配送中心车辆调度问题的禁忌搜索算 法，并通过试验计算研究了禁忌长度、邻域选点策略、迭代搜索策略等 算法策略和运行参数对该算法性能的影响。 ( 4 ) 设计并实现了无时限多配送中心车辆调度问题的模拟退火算 法，并通过试验计算研究了初始温度、降温速度、迭代搜索策略等算法 策略和运行参数对该算法性能的影响。 ( 5 ) 设计和实现了求解有时限多配送中心车辆调度问题的禁忌搜 索算法和模拟退火算法。 t 北京交通大学硕士学位论文多配送中心车辆调度问题的模型和算法研究 关键词：配送；车辆调度问题；时间窗；禁忌搜索算法；模拟退火算法 i i 北京交通大学磺士学位论文 多配送中心车辆调度问题的横型和算法研究 a b s t r a c t d i s t r i b u t i o ni sa l l i m p o r t a n tc l e m e n ti n m o d e ml o g i s t i c s s y s t e m i t i n c l u d e sp i c k i n gu pg o o d sf r o md i s t r i b u t i o nc e n t e ra n dd e l i v e r i n gg o o d st o t h e c u s t o m e r so n t i m e a m o n g d i s t r i b u t i o nb u s i n e s st h e r ea r e m a n y o p t i m i z i n gs t r a t e g i e s t h ev e h i c l es c h e d u l i n gp r o b l e mh a sg r e a te f f e c to n i m p r o v i n g d i s t r i b u t i o n s p e e d ，q u a l i t y o fs e r v i c ea n d e c o n o m y b e n e f i t a c c o r d i n g t ot h en u m b e ro fd i s t r i b u t i o n c e n t e r , t h ev e h i c l es c h e d u l i n g p r o b l e mc a nb ed i v i d e d t o s i n g l ed i s t r i b u t i o n c e n t e rv e h i c l es c h e d u l i n g p r o b l e m a n dm u l t i - d i s t r i b u t i o nc e n t e rv e h i c l e s c h e d u l i n gp r o b l e m t h e m o d e m c i t yl o g i s t i c ss y s t e mu s u a l l yi n c l u d e sm a n y d i s t r i b u t i o nc e n t e r s s o t h i sp a p e rh a sb o t ht h e o r e t i c a la n d p r a c t i c a lv a l u e f o c u s i n g o nt h em o d e l sa n da l g o r i t h m so fm u l t i - d i s t r i b u t i o nc e n t e r v e h i c l es c h e d u l i n gp r o b l e m s ，t h i sp a p e rm a i n l yi n c l u d e st h en e x tc o n t e n t s ， ( 1 ) o nt h e b a s i so fd e s c r i b i n gt h em u l t i - d i s t r i b u t i o nc e n t e rv e h i c l e s c h e d u l i n gp r o b l e ms y s t e m a t i c a l l y , t h i sp a p e r b u i l d st h em o d e lo f m u l t i - d i s t r i b u t i o nc e n t e rv e h i c l es c h e d u l i n gp r o b l e mw i t hn ot i m ew i n d o w s a n dw i t ht i m ew i n d o w sb a s e do nn a t u r a ld e s c r i p t i o n ( 2 ) t h i sp a p e rd e s i g n s t h et a c t i c so n s o l v i n g t h em u l t i d i s t r i b u t i o nc e n t e r v e h i c l es c h e d u l i n gp r o b l e mb yu s i n gt h em i n i m u md i s t a n c ed i s t r i b u t i o n m e t h o d t h r o u g h t h i s m e t h o d ，a n m u l t i - d i s t r i b u t i o nc e n t e r v e h i c l e s c h e d u l i n gp r o b l e mc a r l b ed i v i d e di n t os e v e r a l s i n g l e d i s t r i b u t i o nc e n t e r v e h i c l es c h e d u l i n gp r o b l e m s ( 3 ) t h i sp a p e rd e s i g n sa n da c c o m p l i s h e st h et a b us e a r c ha l g o r i t h m f o r s o l v i n gm u l t i - d i s t r i b u t i o n c e n t e rv e h i c l es c h e d u l i n gp r o b l e mw i t hr i ot i m e w i n d o w s t h r o u g hc o m p u t a t i o n a le x p e r i e n c e ，t h i sp a p e ra l s o s t u d i e st h e l t i 韭蔓壅塑查兰曼主兰竺堕塞墨里堂! ! 圭塑塑壅曼堕竺塑型塑蔓鎏堡壅 i n f l u e n c eo fa l g o r i t h mt a c t i c sa n dp a r a m e t e r ss u c ha st a b ul e n g t h ，l o c a l s e a r c h i n g t a c t i c sa n ds e a r c h i n g s t e p s o nt h ef u n c t i o n so ft a b us e a r c h a l g o r i t h m ( 4 ) t h i sp a p e rd e s i g n s a n d a c c o m p l i s h e s t h es 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 mf o rs o l v i n gm u l t i - d i s t r i b u t i o n c e n t e rv e h i c l es c h e d u l i n gp r o b l e m w i t hn ot i m ew i n d o w s t h r o u g hc o m p u t a t i o n a le x p e r i e n c e ，t h i sp a p e ra l s o s t u d i e st h ei n f l u e n c eo fa l g o r i t h mt a c t i c sa n dp a r a m e t e r ss u c h a si n i t i a l t e m p e r a t u r e ，t e m p e r a t u r e d e s c e n d i n gs p e e d a n d s e a r c h i n gs t e p s o nt h e f u n c t i o n so fs i m u l a t e da n n e a l i n ga l g o r i t h m ( 5 ) t h i sp a p e rd e s i g n sa n da c c o m p l i s h e st h e t a b us e a r c ha l g o r i t h m sa n d 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 o l v et h em u l t i d i s t r i b u t i o nc e n t e rv e h i c l e s c h e d u l i n gp r o b l e m s w i t hh a r dt i m ew i n d o w s k e yw o r d s ：d i s t r i b u t i o n ；v e h i c l es c h e d u l i n gp r o b l e m ；t i m ew i n d o w ；t a b u s e a r c ha l g o r i t h 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 簦京交通大学硕士学位论文 多配邀中心车辆调度问艏的模型和算法研究 1 绪论 1 1 配送车辆调度问题概述 1 1 1 配送车辆调度问题的提出 当前，现代物流已被公认为是企业在降低物质消耗、提高劳动生产 率以外创造利润的第三个重要源泉，也是企业降低生产经营成本，提高 产品市场竞争力的重要途径”。配送是物流系统中的一个重要环节，它 是指按客户( 包括零售商店、用户等) 的订货要求( 包括在货物种类、 数量和时间等方面的要求) ，在配送中心进行分货、配货工作，并将配好 的货物及时送交收货人的物流活动。配送过程主要包括以下作业环节； 从生产工厂进货或运达并集结的集货作业；根据各个客户的不同需求， 在配送中心将所需要的货物挑选出来的分货和配货作业；考虑配送货物 的重量和体积，充分利用车辆的载重和容积的货物配装作业；合理确定 车辆配送路线并及时送货的作业。 在配送业务中，配送车辆调度问题的涉及面较广，需要考虑的因素 较多，对配送企业提高服务质量、降低物流成本、增加经济效益的影响 也较大。 国外将配送车辆调度问题归结为v r p ( v e h i c l er o u t i n gp r o b l e m ，即 车辆路径问题) 、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 ，即车辆调度问题) 和m t s p ( m u l t i p l e t r a v e l i n gs a l e s m a n p r o b l e m ，即多路旅行商问题) 。该 问题于1 9 5 9 年由d a n t z i g 和r a m s e r 提出后t 2 1 ，很快便引起运筹学、应用 数学、组合数学、图论与网络分析、 家以及运输计划制定者的极大重视， 物流科学、计算机应用等学科的专 并一直是运筹学与组合优化领域的 前沿与热点问题。在现实生产和生活中，邮政投递问题、飞机、铁路车 辆、水运船舶及公共汽车的调度问题、电力调度问题、管道铺设问题、 北京交通丈拳预士学位论文 多配送中心车辆调度问菹韵模型和算法研究 计算机网络拓扑设计问题等都可以抽象为配送车辆调度问题。 1 1 2 配送车辆调度问题的描述 配送车辆调度问题可以描述为：在一个存在供求关系的系统中，有 若干台车辆、若干个配送中心和客户，要求合理安排车辆的行车路线和 出行时间，从而在给定的约束条件下，把客户需求的货物从配送中心送 到客户，并使目标函数取得优化。 配送车辆调度问题可归结为如下的一般网络模型：设g = ( v ，e ，a ) 是一个连通的混合网络，v 是顶点集( 表示配送中心、客户、停车场等) ， e 、a 分别为无向的边集和有向的弧集，e 中的边和a 中的弧均被赋权( 可 以表示配送的距离、时间或费用) ，v 、e 、a 分别为v 、e 、a 的子集， 求满足约束条件( 包括客户的货物需求数量约束、需求时间约束、配送 车辆一次配送的最大行驶距离约束、车辆的最大载重量约束等) ，并包含 v 、e 、a ，的一些巡回路线，使目标函数取得优化，目标函数可以取配 送总里程最短、配送车辆总吨位公里数最少、配送总费用最低、配送总 时间最少、使用的配送车辆数最少、配送车辆的满载率最高等。 1 1 3 配送车辆调度问题的构成要素 配送车辆调度问题主要包括货物、车辆、配送中心、客户、运输网 络、约束条件和目标函数等要素。 ( 1 ) 货物。货物是配送的对象。可将每个客户需求的货物看成一批 货物。每批货物都包括品名、包装、重量、体积、要求送到( 或取走) 的时间和地点、能否分批配送等属性。 ( 2 ) 车辆。车辆是货物的运载工具。其主要属性包括：车辆的类型、 ! ! 至至塑壁婴主兰堡堡苎 墨墼耋! ：堡圭塑塑堕塑壁塑堡型塑蔓兰堡壅 装载量、一次配送的最大行驶距离、配送前的停放位置及完成任务后的 停放位置等。 ( 3 ) 配送中心。是进行集货、分货、配货、配装、送货作业的场所。 在某配送系统中，配送中心的数量可以只有一个，也可以有一个以 上。对于某个配送中心，其供应的货物可能有一种，也可能有多种；其 供应的货物数量可能能够满足全部客户的需求，也可能仅能满足部分客 户的需求。 ( 4 ) 客户。也称为用户，包括分仓库、零售商店等。客户的属性包 括需求货物的数量、需求货物的时间、需求货物的次数及需求货物的满 足程度等。 某客户需求货物的时间，是指要求将货物送到的时间，对配送时间 的要求可分为以下几种情况：无时间限制；要求在指定的时间区间 ( 也称为时间窗) 内送到；有时间限制，但可以不遵守，只是不遵守 时要给予一定的惩罚。 ( 5 ) 运输网络。运输网络是由顶点( 指配送中心、客户、停车场) 、 无向边和有向孤组成的。边、弧的属性包括方向、权值和交通流量限制 等。 ( 6 ) 约束条件。配送车辆调度问题应满足的约束条件主要包括： 满足所有客户对货物品种、规格、数量的要求。 满足客户对货物送到时间范围的要求。 在允许通行的时间进行配送( 如有时规定白天不能通行货车等) 。 车辆在配送过程中的实际载货量不得超过车辆的最大允许装载 量。 在配送中心现有运力范围内。 ( 7 ) 目标函数。对配送车辆调度问题，可以只选用一个目标，也可 北京交通大学碗士学位论文多配送中心车辆调度问题的模型和算法研究 以选用多个目标。经常选用的目标函数主要有： 配送总里程最短。配送里程与配送车辆的耗油量、磨损程度以及 司机疲劳程度等直接相关，它直接决定运输的成本，对配送业务的经济 效益有很大影响。由于配送里程计算简便，它是确定配送路线时用的最 多的指标。 配送车辆的吨位公里数最少。该目标将配送距离与车辆的载重量 结合起来考虑，即以所有配送车辆的吨位数( 最大载重吨) 与其行驶距 离的乘积的总和最少为目标。 综合费用最低。降低综合费用是实现配送业务经济效益的基本要 求。在配送业务中，与送货有关的费用包括：车辆维护和行驶费用、车 队管理费用、货物装卸费用、有关人员工资费用等。 准时性最高。由于客户对交货时间有较严格的要求，为提高配送 服务质量，有时需要将准时性最高作为确定配送路线的目标。 运力利用最合理。该目标要求使用的较少的车辆完成配送任务， 并使车辆的满载率最高，以充分利用车辆的装载能力。 劳动消耗最低。即以司机人数最少、司机工作时间最短为目标。 1 1 4 配送车辆调度问题的分类 配送车辆调度问题可按照其构成要素划分为不同的种类。 ( 1 ) 按配送中心的数目分，有单配送中心问题( 配送系统中仅有一 个配送中一l i , ) 和多配送中心问题( 配送系统中存在多个配送中一t l , ) 。 ( 2 ) 按客户对货物取( 送) 时间的要求分，有无时限问题( 客户对 货物送到的时间无具体要求) 和有时限问题( 客户要求将需求的货物在 规定的时间窗内送到，也称为有时间窗问题) 。有时限问题又可以分为硬 时间窗问题( 客户要求货物必须在规定的时间窗内送到，不能提前也不 4 北京交通大学硕士学位论文多配送中心车辆调度问题的模型和算法研究 能拖后) 和软时间窗问题( 客户要求将货物尽量在规定的时间窗内送到， 但也可以提前或拖后，只不过在提前或拖后时，要对配送企业实施一定 的惩罚) 。 ( 3 ) 按车辆类型数分，有单车型问题( 所有配送车辆的载重量相同) 和多车型问题( 配送车辆的载重量不完全相同) 。 ( 4 ) 按优化目标数分，有单目标问题( 仅考虑一个配送目标) 和多 目标问题( 同时考虑多个配送目标) 。 ( 5 ) 按配送中心的货物数量有无限制分，有容量无限的问题( 即假 定配送中心的货物数量充足，能够满足所有客户的要求) ，和容量有限的 问题( 即配送中心的货物数量是有限的) 。 1 2 多配送中心车辆调度问题的研究现状 1 2 1 研究多配送中心车辆调度问题的意义 根据配送系统中配送中心数目的多少，配送车辆调度问题有单配送 中心问题和多配送中心问题之分。在城市物流体系中，往往存在多个配 送中心。因此，对多配送中心车辆调度问题的研究具有重要的现实意义。 从理论研究看，现有对配送车辆调度问题的研究主要集中在单配送 中心问题上，对多配送中心车辆调度问题的研究很少，国内对该问题的 研究基本是空白。对于多配送中心车辆调度问题，不能简单地直接使用 单配送中心车辆调度问题的求解思路和方法，必须在深入研究其特点的 基础上，选择合适的方法进行求解 效率、降低配送成本的目的。可见 重要的理论意义。 从而达到减少运力浪费、提高运输 研究多配送中心车辆调度问题具有 北京交通大学硕士学位论文多配送中心车辆调度问题的模型和算法研究 1 2 2 多配送中心车辆调度问题的研究文献综述 g u y d e s a u l i n i e r s ，t a i h i sw u ，b u r a kk a z a z 、r o b e r tt s u m i c h r a s t 、 s s a l h i 、n r a c h u t h a n 、s t e f a ni m i c h 、m i c h a e 1 v a s n e r 等专家对多配 送中心车辆调度问题进行了研究 3 - 1 0 】，并取得了一些很有价值的研究成 果。其中，g u yd e s a u l n i e r s 等研究了有时间窗的多配送中心车辆调度问 题：t a i h s iw u 等人将多配送中心车辆调度问题分解成两个子问题：多 配送中心的选址问题和一般的单配送中心车辆调度问题；s t e f a ni m i c h 研 究了多车型取送混合的多配送中心车辆调度问题。 现有研究文献对于多配送中心车辆调度问题的求解，基本上可以 分为以下两种方法： ( 1 ) 将多配送中心车辆调度问题转化为多个单配送中心车辆调度 问题，然后进行优化组合，这种方法的研究重点在多配送中心的分离 策略和最后解的优化组合方案选择上： ( 2 ) 将多配送中心车辆调度问题本身看作一个复杂的组合优化问 题进行研究，这种方法的研究重点集中在如何合理地缩小搜索空间和简 化求解步骤上。 本文选用第一种方法求解多配送中心车辆调度问题，即先选择合适 的分区方法将多配送中心车辆调度问题分解为几个相对独立的单配送中 心车辆调度问题，然后分别对各个单配送中心车辆调度问题进行求解。 北京交通大学硕士学位论文 多配送中心车辆调度问题的模型和算法研究 2 多配送中心车辆调度问题的数学模型 2 1 多配送中心车辆调度问题的描述 现实中的多配送中心车辆调度问题是十分复杂的，为了方便建模和 求解，需要对现实问题进行一些抽象和简化。现对本文研究的多配送中 心车辆调度问题做如下界定： ( 1 ) 从多个配送中心向多个客户送货，配送中心和客户的位置一定， 配送中心供应的货物，能够满足所有客户的需求。 ( 2 ) 各个客户需求的货物均可以相互混装，即可以装在同一配送车 辆内；每个客户的货物需求量不超过配送车辆的最大载重量；每个客户 的送货要求必须满足，且仅能由一台车辆完成，不允许分批配送。 ( 3 ) 每台配送车辆的最大载重量一定，不允许超载；每台配送车辆 一次配送的最大行驶距离一定，不允许超过；配送时，设每台车辆都从 配送中心出发，向一些客户提供配送服务后，最终返回原配送中心。 ( 4 ) 配送中心与客户之间以及客户相互之间的最短距离已知且固 定；配送车辆在配送中心、客户间的行驶时间已知且固定；不考虑运输 网络中车辆流量的限制。 2 2 无时限多配送中，b 车辆调度问题的模型 无时限多配送中心车辆调度问题，是指在制定配送路线时不考虑客 户对货物送到时间要求的配送车辆调度问题。 无时限多配送中心车辆调度问题可以描述为：从多个配送中心用多 台配送车辆向多个客户送货，每个配送中心的位置一定，每个客户的位 置和需求量一定，每台配送车辆的载重量一定，其一次配送的最大行驶 距离一定，配送中心供应的货物，能够满足所有客户的需求，要求合理 北京交通大学葡士掌位论文多配送中心车辆调度问题的模型和算法研究 安排车辆配送路线，使目标函数得到优化，并满足以下条件：( 1 ) 每条 配送路径上各客户的需求量之和不超过配送车辆的载重量；( 2 ) 每条配 送路径的长度不超过配送车辆一次配送的最大行驶距离：( 3 ) 每个客户 的需求必须满足，且只能由一台配送车辆送货。 本文对多配送中心车辆调度问题的求解，采用的是通过分区将多配 送中心车辆调度问题分解为几个单配送中心车辆调度问题进而分别求解 的思路。 基于以上求解思路，通过参考现在文献中单配送中心车辆调度问题 的数学模型，本文建立多配送中心车辆调度问题的数学模型。 设某城市中有h 个配送中心，要给m 个客户送货。按照一个配送中 心分别为一定数量的客户提供配送服务的思路，将城市划分为h 个区域， 第h 个配送中心要向l 。( h - 1 ，2 ，h ) 个客户送货，第h 个配送中 心有k h 台配送车辆，每台车辆的载重量为q h k ( k = l ，2 ，k h ) ，其 一次配送的最大行驶距离为d h k 。第h 个配送中心服务的第i 个客户的货 物需求量为q h i ( i - 1 ，2 ，l 。) ，客户i 到j 的运距为d i j ( i ，产1 ，2 ， l 。) ，该配送中心到第j 个客户的距离为氐( h _ 1 ，2 ，h ；j _ 1 ，2 ， l 。) ，再设n h k 为第h 个配送中心中第k 台车辆配送的客户数( ? 2 h k m 0 表 示未使用第k 台车辆) ，用集合凰k 表示第h 个区域中的第k 条路径，其 中的元素，h k 表示客户，h k i 在第h 个区域中的路径k 中的顺序为i ( 不包 括配送中心) ，令h k o = o 表示配送中心，若以配送总里程最短为目标函数， 则可建立如下无时限多配送中心车辆调度问题的数学模型： f k 。f n 。 r a i n z = i d 。+ 九啪。s i g n ( , n ) l 2 1 ) 自= 11k = l li = l 北京交通大学硕士学位论文 多配送中心车辆调度问题的模型和算法研究 s t g 瓯 = 1 d h m ，+ d m 。s i g n ( n 肿) d 肌 0 ms l “ k “ n 扩厶 h l 。= m z l r 。= _ 女i i7 k ， 1 ，2 ，。 ，i = 1 , 2 ，”m ) ( 2 2 ) ( 2 3 ) ( 2 4 ) ( 2 5 ) ( 2 6 ) ( 2 7 ) 胄ir m ，= 妒v h k l ( 2 8 ) s z g n ( n 。，= 托姜君 眩，5 ) 2 1 0 姜他 9 上述模型中，( 2 1 ) 式为目标函数，即要求配送总里程( 即各条配 送路径的长度之和) 最短；( 2 2 ) 式保证每条路径上各客户的货物需求 量之和不超过配送车辆的载重量；( 2 3 ) 式保证每条配送路径的长度不 超过配送车辆一次配送的最大行驶距离；( 2 4 ) 式表明每条路径上的客 户数不超过总客户数：( 2 5 ) 式表明所有分区的配送客户数之和等于总 的客户数；( 2 6 ) 式表明每个客户都得到配送服务；( 2 7 ) 式表示每条路 径的客户的组成：( 2 8 ) 式限制每个客户仅能由一台配送车辆送货；( 2 9 ) 式表示当区域h 中第k 辆车服务的客户数1 时，说明该台车参加了配 送，则取s g r l ( n h k ) = l ，当第k 辆车服务的客户数 1 时，表示未使用该台 车辆，因此取s i g n ( n h k ) = 0 。 上述无时限多配送中心车辆调度问题的基于直观描述的数学模型与 相关研究文献中基于网络图的模型相比，具有以下特点：考虑的目标 北煮交通大学硕士学位论文多配送中心车辆调度问题的模型和算法研究 函数和约束条件较为全面和接近实际； 件的表示较为自然、直观和易于理解； 编程求解；具有较好的可扩充性。 决策变量、目标函数和约束条 便于设计求解算法和用计算机 2 。3 有时限多配送中心车辆调度问题的数学模型 所谓有时限配送车辆调度问题，是指在确定配送路线时，不仅考虑 客户的货物需求数量约束和配送车辆一次配送的最大行驶距离约束，而 且要考虑客户对货物送到时间的要求。随着企业j i t 战略的实施，零库 存成为许多企业追求的目标，于是客户对货物的送到时间提出了更高的 要求。可见，研究有时限配送车辆调度问题具有十分重要的现实意义。 般地，客户要求将货物送到的时间是个时间段，这个时间段也 称为时间窗。因此，有时限配送车辆调度闻题也称为有时间窗约束的配 送车辆调度问题。根据时间窗约束的严格与否，有时限配送车辆调度问 题可分为硬时间窗配送车辆调度问题和软时间窗配送车辆调度闯题。硬 时间窗配送车辆调度问题是指每个客户都要求将货物在指定的时间窗内 送到，既不能提前，也不能拖后，如果在时间窗之外将货物送到，客户 将会拒收货物。软时间窗配送车辆调度问题也称为弹性时间窗配送车辆 调度问题，即客户要求将货物尽量在时间窗内送到，但也允许提前或拖 后，只不过提前或拖后对，要对配送企业实施一定的惩罚，惩罚量与提 前与拖后的时间有关，可以是线性的，也可以是非线性的。另外，提前 与拖后的惩罚系数一般也是不同的，一般情况下，提魏的惩罚系数小予 拖后的惩罚系数。 有时限多配送车辆调度问题可以描述为：从多个配送中心用多台配 送车辆向多个客户送货，每个配送中心的位最一定，每个客户的位置和 需求量一定，要求将货物送到的时间窗一定，每台配送车辆的载重量一 o 北京交通大学硕士学位论文 多配送中心车辆调度问题的模型和算法研究 定，其一次配送的最大行驶距离一定，配送中心供应的货物，能够满足 所有客户的需求，要求合理安排车辆配送路线和行车时间，使目标函数 得到优化，并满足以下约束条件：( 1 ) 每条配送路径上各客户的货物需 求量之和不超过配送车辆的载重量；( 2 ) 每条配送路径的长度不超过配 送车辆一次配送的最大行驶距离；( 3 ) 每个客户的货物需求必须满足， 且只能由一台配送车辆送货；( 4 ) 货物必须在客户指定的时间窗内送到。 设某城市有h 个配送中- t l , ，要给m 个客户送货。第h 个配送中心要 给l 。( 肛1 ，2 ，h ) 个客户送货，第h 个配送中心有k h 台配送车辆， 每台车辆的载重量为q h k ( k 1 ，2 ，k h ) ，其一次配送的最大行驶距 离为d i 似第h 个配送中心服务的第i 个客户的货物需求量为q h ( i = 1 ， 2 ，l 。) ，且要求货物在时间范围 a h ，b h i 】内运到，客户i 到j 的运距 为毗( i ，j = 1 ，2 ，l 。) ，该配送中心到第j 个客户的距离为咖( h - 1 ， 2 ，h ；j = l ，2 ，l 。) ，设8 h ，表示车辆到达客户i 的时刻，h ，表 示车辆在客户i 的等待时间，t i j 表示配送车辆由客户i 行驶到客户j 的旅 行时间；再设h h k 为第h 个配送中心中第k 台车辆配送的客户数( n h k = o 表示未使用第k 台车辆) ，用集合月h 。表示第h 个区域中的第k 条路径， 其中的元素h k 表示客户7 h 在第h 个区域中的路径k 中的顺序为i ( 不 包括配送中心) ，令r h k o = o 表示物流中心，s h o = o 表示配送车辆从配送中 心h 出发的时刻为0 ：取目标函数为配送总里程最短；则可建立如下硬 时间窗多配送中心车辆调度问题的基于直观描述的数学模型： r a i n z = 姜 善 警d 。+ d 。s 辔”c ”。， ) c z1 0)hffi1 = l 。，+ d 。咖( ) l ( 2 l ik ；l l i 。1 l s t q 。 ( 2 1 1 ) 垄茎皇运大学硕圣掌位论文多配遘中心车辆调度阍照的模型和算法讲究 d m + d 岷阳s i g , ( n h ) s d 舨 厶= m d r “= 。i 。 1 ，2 ，l 。l f = 1 2 。h 。 v h & 蛾 ”“1 其他 ( 2 1 2 ) ( 2 1 3 ) ( 2 1 4 ) ( 2 1 5 ) ( 2 1 6 ) ( 2 17 ) ( 2 1 8 ) j h t ，一1j + t f h + f 州， “= 5 1 “ i = 1 ，2 ，n h k ；h = l ，2 ，h ( 2 1 9 ) t h i - - - m a x a h i - s h i ，0 ) i = 1 ，2 ，l h ；h = l ，2 ，h ( 2 2 0 ) s 6 f i = 1 ，2 ，l h ：h = l ，2 ，h( 2 2 1 ) 上述模型中，( 2 1 0 ) ( 2 1 8 ) 式的含义与第2 章中( 2 1 ) ( 2 9 ) 式的含义相同，此处不再重述；( 2 1 9 ) 式表示每条配送路线上配送车辆 到达下一个客户的对刻一车辆到达当翁客户的对刻+ 配送车辆在当前客户 的等待时间+ 从当前客户到下一个客户配送车辆的行驶时削；( 2 2 0 ) 式 表示酉0 送车辆在某个客户的等待时闯取决于车辆到达该客户的时亥与该 客户时间窗丌始时刻的关系，当车辆到达该客户的时刻小于( 即早于) 该客户的时间窗开始时刻时，车辆需要在该客户处等待一直等到时间 0 = “ 鲰 北京交通大学硕士学位论文多配送中心车辆调度问题的模型和算法研究 窗开始时刻，才进行卸货，即等待时间为该客户的时间窗开始时刻与车 辆到达该客户的时刻的差；当车辆到达该客户的时刻大于( 即晚于) 或 等于该客户的时间窗开始时刻时，则车辆在该客户处不等待，即等待时 间为0 ；可见，该式保证了配送车辆卸货的时刻大于或等于该客户的时 间窗开始时刻：( 2 2 1 ) 式表示车辆到达某个客户的时刻必须小于( 即早 于) 或等于该客户的时间窗结束时刻；( 2 1 9 ) 式和( 2 2 1 ) 式共同保证 满足客户的硬时间窗约束。 北京交通大学硕士学位论文 多配送中心车辆调度问题的横型和算法研究 3 无时限多配送中心车辆调度问题的禁忌搜索 算法 3 1 多配送中心车辆调度问题的求解思路 由于多配送中心车辆调度问题涉及面很广、影响因素众多。为了求 解方便，需要将问题做适当简化。为此，可以采用将一个多配送中心车 辆调度问题转化成多个单配送中心车辆调度问题进行求解的思路。将一 个多配送中心车辆调度问题转化成多个单配送中心车辆调度问题时，决 定每个配送中心服务的具体客户是问题的关键。解决该问题主要有如下 两种方法： ( 1 ) 距离最近分配法 即根据距离最近原则，决定为某客户提供服务的配送中心。鉴于多 配送中心车辆调度问题以总配送里程最短为优化目标，计算某客户与各 配送中心的距离，该客户离那个配送中心最近，就将其分配到那个配送 中心，由该配送中心为其提供服务。 设d 。表示第i 个客户到第h 个配送中心的距离。选择 d 。= m i n d 门，d 。d 。) ，( 其中，h 表示配送中心数量) 为当前所求，并 将该客户分配给配送中心m 。得到为每个客户服务的配送中心后，也就 得到了每个配送中心服务的具体客户。 ( 2 ) 边界分配法 设d ( 一) 表示用户i 和配送中心h 之问的距离，记为集合 9 = 臼，( ) h = l ，。一 ，h 是配送中心的个数，计算r ( i ) = ”1 。， m i n d 和s u b m i n d 分别表示集合d 中的最小值和次小值，选取适当的 1 4 北京交通大学硕士学位论文多配送中心车辆调度问越的模型和算法研究 6 ，0 6 l ，比较r ( i ) 和6 的大小，当r ( i ) = 6 ，这时用户i 为边界点，对边界 点的分配如下： 当r ( i ) 1 时，利用节约法分配，首先考虑由最近的配送中心发 出配送车服务每一个点，构成初始解。各点对最近配送中心的分派都是 暂时的，一旦两个和多个点已被分派给一个配送中心的线路，这些点就 不再分派给其他的配送中心。当点i 和j 都不与配送中心相连时，进行 连接的节约量是s ：= ( 矗? ) + ( 穆) + d p ，其中( 群) = ( 2 m i n d , h 一嘞) 或 ( t i t ) 。根据节约值，连接客户i 和j 。在第一种情况下，点i 被分配到 离它最近的配送中心，总距离节约2 r a i nd | ，在第二种情况下，点j 插入 到配送中心和点i 之间。 当r ( i ) = l 时，如果点j 和点k 以分派给一种配送中心h ，插入 点i ，对配送中心h 而言产生的附加距离是屯( ) = d 。+ d j l d n ，并且 将用户i 分派给使得d 。( h ) 最小的配送中心。 通过改变6 的大小，可以控制边界点的个数。当6 = 0 时，所有的用 户都是边界点，当6 = l 时，所有的用户均分派给最近的配送中心。 当所有的用户都相应分配到配送中心后，便可按照求解单配送中心 车辆调度问题的方法进行求解。 北京交通大学硕士学位论文 多配送中心车辆调度问题的模型和算法研究 3 2 求解单配送中，b 车辆调度问题的几个搜索算法策 略 3 2 1 解的表示 用启发式算法求解单配送中心车辆调度问题时，确定解的表示方法 是一项非常关键的基础工作，因为它将直接决定算法实现的难易程度和 算法性能的优劣。国内外学者研究用启发式算法求解配送车辆调度问题 时用得最多的是客户与虚拟物流中心共同排列的解的表示方法。郎茂祥 在现有研究成果的基础上，提出了客户直接排列的表示方法1 1 l 】。这种表 示方法是直接产生l 个1 l 间的互不重复的自然数的排列，该客户排列 就构成一个解，并对应一种配送路径方案。按照单配送中心车辆调度问 题的约束条件，可依次将解的元素( 客户) 划入备台车辆的配送路径中。 例如，对于一个用3 台车辆向9 个客户送货的单配送中心车辆调度问题， 设某解中的客户排列为4 1 2 8 7 6 9 3 5 ，可用如下方法得到其对应的配送路 径方案：首先将客户4 ( 解中的第1 个客户) 作为第1 台配送车辆服务 的第1 个客户，然后判断能否满足问题的约束条件，即客户4 的需求量 是否超过第l 台车辆的最大载重量，且路径0 - 4 0 的总长度是否超过第1 台车辆一次配送的最大行驶距离，设能够满足，这时可将客户1 ( 解中 的第2 个客户) 作为第1 台配送车辆服务的第2 个客户，然后判断能否 满足问题的约束条件，即客户4 和1 的需求量之和是否超过第1 台配送 车辆的最大载重量，且路径0 - 4 1 0 的总长度是否超过第1 台车辆一次配 送的最大行驶距离，设仍能满足，这时可将客户2 ( 解中的第3 个客户) 作为第1 台配送车辆服务的第3 个客户，然后判断能否满足问题的约束 条件，设仍能满足，这时可将客户8 作为第1 台配送车辆服务的第4 个 客户，设此时不能满足问题的约束条件，这说明客户8 不能由第1 台配 北京交通大学硕士学位论文多配送中心车辆调度问题的模型和算法研究 送车辆服务，由此可得第l 台车辆的配送路径：o 4 1 2 0 ；然后，将客 户8 作为第2 台配送车辆服务的第1 个客户，若能满足问题的约束条件， 则可将客户7 作为第2 台配送车辆服务的第2 个客户，若仍能满足问题 的约束条件，则可将客户6 作为第2 台配送车辆服务的第3 个客户，若 仍能满足问题的约束条件，则可将客户9 作为第2 台配送车辆服务的第 4 个客户，若此时不能满足问题的约束条件，则说明客户9 不能由第2 台配送车辆服务，由此可得第2 台车辆的配送路径：o 一8 7 6 0 ；仍按上 述方法可将解中的其它客户也依次加入到其它车辆的配送路径中。采用 这种表示方法，也可以得到配送路径数小于车辆总台数的配送路径方案。 若某个解中的排在最后的若干个客户不能纳入到车辆的配送路径中，则 说明该解为一个不可行解。这种解的表示方法占用的计算机存储量较少， 表示也较为直观，也容易产生可行解。 3 2 2 锯的评价 在用启发式算法求解单配送中心车辆调度问题时，需要对解进行评 价，以比较解的优劣，使算法在迭代过程中，不断搜索到质量更优的解， 并最终得到问题的最优解或近似最优解。根据单配送中心车辆调度问题 的数学模型，对于某个解要判定其优劣，首先要得到该解所对应的配送 路径方案，然后要判断该配送路径方案是否满足问题的约束条件，同时 计算该配送路径方案的目标函数值，在满足问题的约束条件的前提下， 其目标函数值越优，则配送方案越优，解的质量越高。下面针对前述解 的表示方法，讨论其解的评价方法。 用客户直接排列表示方法产生的解所确定的配送路径方案，能够满 足每条配送路径上各客户需求量之和不超过配送车辆的最大载重量及每 条配送路径的长度不超过车辆一次配送的最大行驶距离的约束条件，但 l7 北京交通大学硕士掌位论文多j 芒送中心车辆调度问题的模型和算法研究 不能保证所有的客户全部都能得到配送服务。对于某个解，若全部客户 均能纳入到车辆的配送路径中，则取该配送路径方案的不可行路径数 m = o ，表示该解为一个可行解；若排在最后的若干个客户不能纳入到车 辆的配送路径中，则取该配送路径方案的不可行路径条数m = i ，表示该 解为一个不可行解，设该解对应的配送路径方案的目标函数值为z ，将 m 和z 代入公式( 3 1 ) 并设对每条不可行路径的惩罚权重为p w ( 该权 重可根据目标函数的取值范围取一个相对较大的正数) ，同样可计算出该 解的评价值e 。 e = z + m p w ( 3 1 ) 3 2 3 邻域选点方法 确定邻域选点方法是构造搜索算法的一个重要步骤。由于邻域选点 也可以看成是对原解实施的一种邻域操作，因此，在本文中也将邻域选 点方法称为邻域操作策略。根据现有研究文献，在用搜索算法求解组合 优化问题时，普遍采用换位法( 特别是其中的两交换法) 、逆转法和插入 法实施邻域操作。 实施邻域操作后，要保证得到的原解的邻居仍为解空间中的一个点， 既保持解的有效性。 采用客户直接排列的解的表示方法时，可以采用以下几种邻域选点 方法： ( 1 ) 换位法。该方法是指随机选择解中的若干个元素，并交换其位 置的邻域选点方法。最常用的是两交换法，现举例说明之。设某解为 s = 1 2 3 4 5 6 7 8 9 ，随机产生的换位点为第4 位和第7 位，则实施两交换后可 得原解的邻居s = 1 2 3 7 5 6 4 8 9 。也可以采用随机选