（管理科学与工程专业论文）连锁店的物流配送路径选择问题研究.pdf

摘要 连锁经营是提高零售企业经营能力的一种有效方法，已经有1 0 0 多年的历史，是在发达国家普遍获得成功的零售经营方式和组织形 式。物流配送是实现连锁经营的必要条件，它连接着连锁企业的商品 销售和采购，保证连锁企业商品的正常流转，保证基层连锁店的正常 销售活动，满足市场的需求。由于目前我国多数企业在安排配送作业 时处于凭靠经验阶段，为了提高配送工作的效能、效率和降低配送成 本，有必要研究如何使商品配送数量科学化，商品配送路线优化及商 品配载合理化。 本文通过对连锁店物流配送业务介绍与分析，考虑了多配送中 心、多种车辆、车辆载重限制、有退货的、时间窗约束限制等因素， 提出了城市单配送中心的连锁店物流配送的成本决策模型以及区域 间多配送中心的连锁店物流配送的成本决策模型。前一个模型采用自 适应的混合遗传算法并在m a t l a b 6 5 环境中实现求解，取得了良好的 效果；后一个模型在前一个模型的基础上加以扩展，运用作者提出的 三阶段求解策略，并采用了作者提出的自适应的混合遗传算法。 在遗传算法的求解策略上，对配送路径采用直观的自然数染色体 编码方案，提出最优保留、最差淘汰和爬山法的组合策略，并对传统 的自适应交叉概率和变异概率提出了与进化世代有关的改进自适应 交叉概率与变异概率，并试验证明其有效性。 在通常的两阶段求解多配送中心车辆路径问题基础上，加入临界 节点局部调整的三阶段求解策略。 关键词：连锁店，物流配送，有时间窗约束的车辆路径问题，遗传算 法 a b s t r a c t c h a i n m a n a g e m e m i sa ne 仃e c t i v em e t h o dt o i m p r o v e r e t a i l m a n a g e m e n ta b i l i 够i th a sa1 0 0 _ h i s t o w r h i c hi sar e g u l a rs u c c e s s 血l r e t a 订m a n a g e m e mp o l i c ya n do 唱a 1 1 i z a t i o n 町l ei na d v a l l c e dc o u i l t i e s l o 西s t i c sd i s t r i b u t i o ni sn e c e s s a r yi nc h a i nm a r l a g e m e m ，w h i c hc o 皿e c t s c h a i ne n t e r p r i s e s s e i l i n ga i l d p u r c h a s i n g i te n s u r e sc h a i ne n t e r p r i s e g o o d sc i r c u l a t i n gr e g u l 蒯y ，p r i m a 叮c h a i ns t o r e ss e l l i n gn o 珊a l l 弘a 1 1 d m e e t sm a r k e td e m a n d s m a n yo fe n t e r p r i s e si no u rc o u n n ya r ei n e x p e r i e n c ed e p e n d e n ts 协g eo fp l 锄i n gd i s t r i b u t i o n i no r d e rt oi m p r o v e d i s t r i b u t i o ne f r e c t ，e f f i c i e n c ya n dd e d u c ed i s t r i b u t i o nc o s t ，ti sn e c e s s a l y t os t u d yh o wq u 锄t i t i e so fg o o d sd i s t r i b u t i o nt ob es c i e m i f i c ，r o u t so f g o o d sd i s t r i b m i o nt ob eo p t i m i z e da n da s s o n i n gg o o d si nv e h i c i e st ob e e q u i t a b l e i nm i sp a p e r ，m ea u m o ri n t r o d u c e s 柚da n a l y s e sd i s t m u t i o no fc h a i n s t o r e s ，r e g a r d so fm u l t i - d e p o t ，n e e ts i z e s ，v e h i c l ec 印a c i 吼b a c kg o o d s a n dt i m e w i n d o w sc o n s t r a i n t s t h ea u t h o ra i v a n c e st w om e t h o d s t h e o n ei sc o s tb a s e dp o l i c yo fc h a i ns t o r e sd i s t r i b u t i o nw i m s i n g i ed e p o ti n c i 够t h eo t h e ri sc o s tb a s e dp o l i c yo fc h a i ns t o r e sd i s t r i b u t i o nw n m u l t i d e p o t mr e g i o n t h ef i r s tm o d e lm l f i l l ss e l f 二a ( 1 a p t e dh y b r i dg e n e t i c 印p r o a c hi nm a t l a b 6 5 卸dr e a c h e sg o o dr e s u l t 1 1 h es e c o n dm e t 量1 0 di s e x t e n d e do ft h ef i r s tm o d e l t h ea u t h o ra d v a n c e st h r e e - s t a g ep o l i c ya n d u s e ss e l f a d a p t e dh y b r i dg e n e t i ca p p f d a c hp o l i c y ： ( ) 1 1 吐l eg e n e t i c 印p r o a c hp o l i 吼t i i ea u 1 0 ru s e sd i s t i n c ti n t e g e r c 小) m o s o m e 锄da d v a i l c e sam 恢p o l i c yo fb e s t - r e t a i l l ，w o r s t - e l i m i n a t e 硼dc l i m bs e a r c h t h ea u t h o ri m p r o v e sn l et 豫d i t i o n a l s e l f a d a p t e d c r o s s o v e r p r o b a b i l i 够 觚dm u t a t i o n p r o b a b i l i 够 w i t l l e v o l m i o n a r y g e n e m t i o nr e l a t e dp o l i c ya n dp m v e sh t 0b ee 仃e c t i v et l l r o u 曲t e s t i n g 0 | 1 lm eb a s eo f 删i t i o n a lt w 0 s t a g ep o l i c yo fs o l v i n gm u l t i d 印o t v e h i c l er o u t i n gp r o b l e m ，t h ea u t h o ra d d sc r i t i c a lp o i n t s p a r ta d j u s 仃n e m t o t h e m i r ds t a g e k e yw o r d s ：c h a i ns t o r e s ，l o g i s t i c sd i s t r i b u t i o n ，v e h i c l er o u t i n gp r o b l e m w i t i lt i m e - w i n d o w sc o n s t r a i m s ，g e n e t i ca i g o r i t 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢 的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不 包含为获得中南大学或其他单位的学位或证书而使用过的材料。与我 共同工作的同志对本研究所作的贡献均已在论文中作了明确的说明。 作者签名： 幽竺i !日期：二! 竺掣月二日 关于学位论文使用授权说明 本人了解中南大学有关保留、使用学位论文的规定，即：学校 有权保留学位论文，允许学位论文被查阅和借阅；学校可以公布学位 论文的全部或部分内容，可以采用复印、缩印或其它手段保存学位论 文；学校可根据国家或湖南省有关部门规定送交学位论文。 作者虢衅新签魈期：蛳蛳尘日 硕十学位论文第l 章绪论 第l 章绪论 1 1 问题的提出 连锁经营是提高零售企业经营能力的一种有效方法，已经有1 0 0 多年的历 史，是在发达国家普遍获得成功的零售经营方式和组织形式。连锁经营实现了 商品销售的最少环节、最短路径、最低费用、最高效率，从而降低了商品的零 售价格，提高了零售企业的市场竞争力。连锁经营通过规模化、标准化、专业 化、统一化、单纯化的经营，降低流通成本，提高服务质量，扩大企业影响力， 增加企业经济效益。 进入九十年代末。竞争日趋激烈的经济环境使得企业开始战略性资源重组， 许多带有连锁性企业为了改变传统分数、单体经营形式带来的弊端，力主采用 特许经营模式( f r a n c h i s ec h a i n ，f c ) 把众多中小企业连锁成“经济利益共同 体”，求得中小企业技术、组织两个创新体系的突破。从此连锁企业进入了以 特许经营方式快速扩张时期。美国未来科学家约翰莱斯比特预占，到2 0 l o 年， 由于连锁店的不断迅速扩张，将改变社会形态，使得社会经济向这以服务业为 主的方向发展：便利、优质和专业化将是未来连锁业的发展趋势。 连锁经营是众多分散营业、经营同类商品或服务的企业，在同一总部的统 一管理下，通过规范化经营，采取共同方针，一致行动，实现规模经营，以取 得规模效益的联合组织形式。作为一种新型的商业组织形式，有四个鲜明的一 致性，即经营理念的一致性：企业识别系统( c o r p o r a t ei d e n t i f ys y s t e m ，c i s ) 的一致性；业务综合服务的一致性；经营管理的一致性。在同一资本下，经营 同类商品或服务，并在某种程度上实行统一经营管理模式称其为直营连锁 ( r e g u l a rc h a i n ，r c ) ，又称为“直营店”。 特许经营指的是主导企业( 连锁总部或特许者f r a n c h i s o r ) 把自己开发的 商品、服务和营业系统( 包括商标、商号等企业象征的使用、经营技术、营业 场所和区域) ，以契约的形式授予加盟店( f r a n c h i s e e ) 在规定区域的经销权和 营业权。加盟店则须交纳一定的营业权使用费，承担规定的义务。 物流配送是实现连锁经营的必要条件，它连接着连锁企业的商品销售和采 购，保证连锁企业商品的正常流转，保证基层连锁店的正常销售活动，满足市 场的需求。配送中心是连锁经营企业组织中的关键部门，实施商品配送是配送 中心的关键工作。配送中心的配送工作要解决的基本问题是合理地向基层零售 商店配送商品，做到商品配送的适销、适时、适量，及时、合理地调剂各个连 锁商店商品的余缺，做到既不缺货又不积压；科学地统计和分析市场的商品需 求，以便制订合理的配送计划；合理地组织商品货源。为了提高配送工作的效 硕十学位论文 第l 章绪论 能、效率和降低配送成本，配送中心在具体实施商品配送的时候，要注重商品 配送数量的科学化，商品配送路线的优化及商品配载的合理化。 车辆路径问题( v e h i c l er o u t i n gp r o b l e m ，v r p ) 是连锁店的物流配送路 径选择的关键问题，己被证明是n p 难题。我国的连锁店物流配送大多数还是处 于凭靠经验的人工安排阶段，因此研究出切实可行的解决v r p 的系统科学方法 是当务之急。本研究目的是用自适应的混合遗传算法，得出理想的v r p 解决方 案。 1 2 文献综述 1 2 1 冲问题 图卜1 车辆路径问题 v r p ( v e h i c l er o u t i n gp r o b l e m ) 即车辆路径问题，是对一系列装货点或卸 货点，组织适当的行车路线，每个服务点有且只访问一次，使车辆有序地通过， 在满足一定的约束条件( 如货物需求量、发送量、交发货时间、车辆容量限制、 行驶里程限制、时间限制等) 下，达到一定的目标( 如路程最短、费用最少、 时间尽量少、使用车辆数尽量少等) 。图卜l 是一个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 e l i n d o w c o n s t r a j n t ，v r f r r w ) 是v r p 的衍生形式，除满足顾客载运需求和车辆载重限制 外，还需满足顾客指定的配送时间内到达的时间窗约束限制。 目前最常见的数学模型是f i s h e r 和j a i k u m r ( 1 9 8 1 ) 采用的0 1 整数规 划，其模式如下： 砌拥咖c 妇= c ， l t ni e n t “ m 节点集合 2 硕七学伊论文第l 章绪论 胚车辆集合 c 一需求点i 到需求点j 的距离 z 。：车辆k 是否由需求点i 到需求点j 大多数的物流配送运输调度问题可以归结为配送车辆的分配，行车路线的 组织问题( v r p 问题) ，即根据不同要求目标函数( 例如运距最短配送时间 最短，运输费用最少等) ，将配送运输过程归结为表述问题的数学模型，然后用 计算机求得合理可行的优化方案，在实际中付诸实施。 由于连锁店通常是定时定量配送，我们可以把连锁店配送路径选择问题转 化成v r p t w ，即每个连锁店铺有其固定配送时间，由配送中心向各连锁店配送， 使总运营成本最小化。 1 2 2 时间窗 时问窗约束可分为硬时间窗、软时间窗与混合型时日j 窗。三者分述如下： ( 1 ) 硬时日j 窗( h a r d t i m e w i n d o w s ) ：指配送车辆必须在特定时间区段( 如 图卜1 中的( e ，1 ) ) 内将货物送达顾客手中，不论是迟到或早到都完全不予接受。 图卜l 为一惩罚函数( p e n a l t yf u n c t i o n ) ，当货物送达时间超出( e ，1 ) 时，其 惩罚值p ( t ) 为一个非常大的正值，表示硬时间窗的限制。d e s r o c h e r s ( 1 9 8 8 ) 曾 指出硬时日j 窗宽度会影响寻优程序，并提出时间窗宽度评价指标，时间窗越宽 则v r p t w 问题越接近路线安排( r o u t i n g ) 问题，越窄则越接近行程安排 ( s c h e d u l i n g ) 问题1 。 p “】 1t 图1 1 硬时间窗 ( 2 ) 软时问窗( s o f tt i m ew i n d o w s ) ：指配送车辆如果无法将货物在特定 的时段( 如图卜2 中的( e ，1 ) ) 内送到顾客手中，则必须按照违反时间的长短施 以一定的罚金或其他惩罚法则。 -1t 图卜2 软时间窗 3 硕十学伊论文第1 章绪论 ( 3 ) 混合型时间窗( m i x e dt i 鹏w i n d o w s ) ：系统中有些顾客属于硬时间 窗，有些则属于软时间窗：同一顾客，往往软、硬两种时间窗混合使用。在实 际的物流配送中，配送车辆如果能在最佳时段( 如图卜3 中的( e ，1 ) ) 内将货物 送到顾客处，则不处罚；若在图卜3 中的( a ，e ) 或( 1 ，b ) 时段内才送达，则顾客 的满意度降低( 转化为惩罚函数) ，而且顾客不接受上述两个时段以外的时日j ( ( 一 一，a ) 或( b ，+ 一) ) 收货。 ，( t ) 一 图卜3 混合型时间窗 1 2 3v r p 求解策略回顾 学者b o d i n ( 1 9 8 3 ) 等人，将会影响车辆路径问题的主要因素整理如下表卜1 所示。根据这儿种影响因素的组合，可衍生出许多问题，如：多场站车辆路径 问题( m u l t i d e p o tv r p ) ，时间窗限制的车辆路径问题( v r p w i t h t i m e w i n d o w s ， v r p t w ) ，收送车辆路径问题( p i c k u pa n dd e l i v e r yv r p ，p d v r p ) ，随机需 求车辆路径问题( s t o c h a s t i cv r p ，s v r p ) ，多车种车辆路径问题( f l e e ts i z e a n dm i xv r p ，f s m v r p ) ，周期性车辆路径问题( p e r i o dv r p ，p v r p ) 等。 表卜1 影响调度和路径的主要因子 因素可能的选择 l 可行车队的大小一辆：多辆 2 可行车队的种类单一的( 仅有一种乍型) ；异质的( 多种车型) ；特 殊的 3 车辆的出发点 单一场站( 单一物流中心) ；多场站 4 需求的类型 确定性需求：随机性需求：允许满足部分需求 5 需求的位置在顾客点上；在路线上：混合型 6 网络形态问接：直接：混合：欧几里得几何 7 车辆容量限制全部一样：不一样：没有容营限制 8 最大行莘时间各绕路皆相间：不同绕路不同时间：没有时间限制 9 作业只有拣货：只有送货；有拣货和送货；分次运送 l o 成本变动成本( 或绕路成本) ；周定成本( 或乍辆成本) ； 一般成本( 没有服务时的成本) 1 1 目标最小绕路成本；最小同定成本与变动成本：最小车辆 使用数目；最大服务或便利效用函数；最大顾客优先 权效用函数 4 硕十学付论文第l 章绪论 学者b o d i n ( 1 9 8 3 ) 等人，将v r p 求解策略化为七种“”： ( 1 ) 先分群再派路线( c l u s t e rf i r s tr o u t es e c o n d ) ：先将需求点分成 几组群落，然后在依各个群落寻找最佳车辆路径。g i l l e t t 和m i l l e r ( 1 9 7 4 ) 所提出的扫描法则是属于这种方式，其利用极坐标的方式表示各个需求点的位 置，取任一点为起始位置，命其角度为零，以顺时针和逆时针分割车辆服务区 域，而每个区块再依旅行商问题的演算法求解。 ( 2 ) 先排路线再分群( r o u t ef i r s tc l u s t e rs e c o n d ) ：首先为所有需求 点建立一条经济路线( 可为非可行解) ，再依车辆的容量限制，拆成多个适合 的路线。如g o l d e n 等人( 1 9 7 4 ) 所提出的巨网分割法( g i a n tt o u r a l g o r i t l l m ) 。 ( 3 ) 节省法或插入法( s a v i n g so ri n s e r t i o np r o c e d u r e ) ：此法针对现 有路径做连接( n e w - j o i n ) 、并入( a t t a c h ) 、合并( m e r g e ) 等三种方式结合路径。 如c 1 a r k ea n dw r i g h t ( 1 9 6 4 ) 的节省法“”。 ( 4 ) 改善与交换法( i m p r o v e 吣n to re x c h a n g ep r o c e d u r e ) ：此法为改 善现有的可行解，将某路线中的连线与另一路线的连线相互交换，以得到较佳 解，如l i n ( 1 9 7 3 ) 的2 一o p t 法，c h r i s t o f i d e sa n de i l o n ( 1 9 6 9 ) 的3 一o p t 法、 0 r o p t 法等。 ( 5 ) 数学规划法( t h e 陋ti c a lp r o g r 咖i n ga p p r o a c h e s ) ：如f i s h e r a n d j a i k u 哪r ( 1 9 8 1 ) 利用数学规划法，将v r p 分解成一般指派问题和t s p 问题， 先解决指派问题，再针对每辆车作t s p 问题求解。 ( 6 ) 人机互动法( i n t e r a c t i v eo p t i m i z a t i o n ) ：决策者可透过人机互动 以详细了解实际状况，并根据以往经验及相关知识等进行各项设定与修订，以 做出最佳决策。 ( 7 ) 最佳解法( e x a c tp r o c e d u r e ) ：如分支界限法( b r a n c ha n db o u n d ) 。 动态规划法( d y n 栅i cp r o g r 锄i n g ) ，切平面法( c u t t i n gp 1 a n e ) 。 表卜2 是作者整理的国外在v r p 问题求解策略上的情况。 表卜2 国外v r p 问题求解策略的相关文献 提出学者研究重点应用 先分群再 1 9 7 4g i l l e t t 。m i l l e r 扫描法 v r p 排路线1 9 7 6g n l e t t ，j o h n s o n 多终点的车辆分派 v r p 1 9 7 7k a r p 分割演算加上几率分析 t s p 先排路线 1 9 7 6g o l d e n处理不同车队大小的车辆路径问v r p 后分群题 硕士学付论文第l 章绪论 节省与插 1 9 6 4c l a r k e ，w r i g h t节省法 v r p 入1 9 6 7g a s k e l 节省法中引入路线轮廓参数 v r p 1 9 7 0y e l l a w 节省法中加入权藿 v r p 1 9 7 6m o l e ，j 锄e s o n 将节省值概念应用f 循环路线构 v r p 造上，以离物流中心最远点作为 起点，配合最近插入法构建路线 1 9 7 7g o l d e n 利用h e a p 资料结构纪录节省值 v r p 改善与交 1 9 6 5l i n ，k e r n i g h a n 节线交换法 t s p 换 1 9 6 9c h r i s t o f i d e s。 将节线交换法应用于v r p v r p e i l o n 1 9 8 8s o l o m o n 由必要条件的检查，缩小使用交 v r p 换法后可行解的范围 1 9 9 0f a h r i o n w r e d e 以一次移动一条路线上的部分连 v r p 续客户至其他路线上，以减少车 辆行驶距离 数学规划 1 9 7 lc h r i s t o f i d e s 将拉格朗日松弛法应用于v r p v r p 法1 9 7 9s t e w a r t ，g o l d e n 将拉格朗日松弛法应用于v r p 沪 1 9 8 la s k e l l 先以需求量大于车容量一半的需 v r p 求点作种子点，根据插入点的成 本，决定该纳入哪一点 1 9 8 2h e l d ， k a r p 动态规划法应用 t s p 人机互动 1 9 7 lk r o l a k 以快速、简单、次佳的启发式解 v r p 法求得初始解，再依专业人员判 断，对所求路线调整 1 9 8 8g o l d e n 。a s s a d 提出入机互动的技巧 v r p 最佳解 1 9 6 0m i l l e r应用整数规划 t s p 1 9 7 0h e l d ， k a r p应用最小扩展树法 t s p 1 9 8 0c r o w d e r ，p a d e r g 发展割面法与分支界限法的合成 t s p 1 9 8 0c a r p a n e t o ，t o t h 应用分支界限法 v r p 1 9 8 lc h r i s t o f i d e s 应用分支界限法 v r p 1 9 8 5l a p o r t e 应用割面法 v r p 近年来发展的启发式演算法( m e t a _ h e u r i s t i c s ) 。1 ，十分具有弹性，让 使用者在取舍求解品质与速度后，可自定演算法需要的复杂度，其特点为欲获 得近似最优解，通常不需要太多问题本身的信息。由于启发式演算法可跳出局 部最优解，常与初始解的建构法及初始解的改善法合用，可在有限时间内求得 近似最优解。常用方法有：遗传算法( g e n e t i ca l g o r i th i i i ) 陬”，模拟退火法 6 硕士学付论文 第l 章绪论 ( s i 叫l a t e da n n e a l i n g ) ，禁忌搜索法( t 曲us e a r c h ) ”1 国内近几年的情况简述如下：西安交大的袁庆达先用g e n i u s ( g e n e r a l i z e d i n s e r t i o n ，u n s t r i n ga n ds t r i n g ) 算法生成一条容纳所有预选客户的长路线， 再用t a b us e a r c h 进行优化配送线路。湖南大学的肖鹏利用单亲遗传算法解决 v r p ，并证明其在寻优效率和“早熟收敛”问题上的优越性。西安交大的李军设 计了基于自然数编码的遗传算法，用于解决非满载车辆调度问题。昆明理工大 学的陈晓伟对节约法进行了优化。广西大学的苏一丹提出了用流体神经网络解 决物流配送。东北大学的张潜提出一种先用优先级综合聚类分析法将客户分类， 再用带有控制开关系统的改进遗传算法求解多目标v r p 的优化方法。鞍山钢铁 学院的李大卫把禁忌搜索法的记忆思想引入到遗传算法的搜索过程中，构造了 新的重组因子，并把禁忌搜索法作为遗传算法的变异算子。 1 2 4 遗传算法简介 遗传算法( g e n e t i c 舢g o r i t l i i 璐，g a ) 是美国m i c h i g 鼬大学h o l l 觚d 教授于 1 9 7 5 年受生物进化论的启发而提出来的。g a 是基于“适者生存”的一种高度 并行、随机和自适应的优化算法，它将问题的求解表示成“染色体”的适者生 存过程，通过“染色体”群的一代代不断进化，包括复制、交叉和变异等操作， 最终收敛到。最适应环境”的个体，从而求得问题的最优解惑满意解。目前， 随着计算机技术的发展，g a 愈来愈得到人们的重视，并在机器学习、模式识 别、神经网络、优化控制、组合优化等领域得到了成功应用。 1 2 4 1 基本流程 遗传算法是一类随机优化算法，但它不是简单的随机比较搜索，而是通过 对染色体的评价和染色体中基因的作用，有效的利用已有的信息来指导搜索有 希望改善优化质量的状态。 标准遗传算法的主要步骤可描述如下： ( 1 ) 随机产生一组初始个体构成初始种群，并评价每一个个体的适应值 ( 2 ) 判断算法收敛准则是否满足，若满足则输出搜索结果；否则执行以 下步骤 ( 3 ) 根据适应值大小以一定方式执行复制操作 ( 4 ) 按交叉概率执行交叉操作 ( 5 ) 按变异概率执行变异操作 ( 6 ) 返回步骤( 2 ) 上述算法中，适应值是对染色体( 个体) 进行评价的一种指标，是g a 进 行优化所用的主要信息，它与个体的目标值存在一种对应关系；复制操作通常 采用比例复制，即复制概率正比于个体的适应值：交叉操作通过交换两父代个 7 硕 ：学何论文第l 章绪论 体的部分信息构成后代个体，使得后代继承父代的有效模式，从而有助于产生 优良个体；变异操作通过随机改变个体中某些基因而产生新个体，有助于增加 种群的多样性，避免早熟收敛。 1 2 4 2 遗传算法的特点 遗传算法具有以下特性： ( 1 )平行搜寻：每次进化都是一群染色体同时进行，相当于对一群暂 时解同时进行搜寻，这与传统的搜寻法，如贪心法、模拟退火法、 门槛接受法等方法不同；g a 在平行搜寻时，是以交叉运算，交 换暂时解黾的片断信息，以形成新的下一代暂时解。 ( 2 )g a 的算子是直接作用于编码的参数空问，而 参数本身。 ( 3 )g a 只需要对问题本身所欲搜寻的目标定义好目标函数，亦即其 只要报酬( p a y o 疗) 信息，而不需要其他辅助信息。目标函数只 要能反映问题的目标，无可微分、连续性、单一性等限制。 ( 4 )可跳出局部最优解：g a 在搜寻下一代解的进化过程中，父代的 选取足以其适应度的大小，来决定其被选中的概率，这是一种概 率性的转移法则，其概率决定其适应度的大小，配合交叉算子， 使其搜寻虽为盲目的，但并非随机搜索。根据这种搜寻法则，较 劣的可行解亦有被选中的机会，这种随机性再加上变异机制，使 其可以有效的跳出局部最优解。 遗传算法的主要任务和目的，是设法产生或有助于产生优良的个体成员， 且这些成员能够充分表现初始解空间中的解，从而使算法效率提高并避免早熟 收敛现象。但是，实际应用遗传算法时，往往出现早熟收联和收敛性能差等缺 点。另外，对于有约束优化问题的求解，目前的方法一般只适用于简单的约束 问题，到目前为止，采用g a 求解高维、多约束、多目标的优化问题仍是一个 没有很好解决的课题，它的进展将会推动g a 在许多工程领域的应用。 1 3 研究的意义与目的 ( 1 ) 连锁经营是目前国内发展非常快的一种经营模式，物流配送是其中重要 的一个环节，如何提高配送效率，降低配送成本，是个值得研究的课题。 ( 2 ) 建立单( 多) 配送中心满足多种车辆、有车辆载重限制、有装货和退货、 有时间窗约束限制的v r p 问题且总运营成本最小的数学模型。 ( 3 ) 希望通过自适应的混合遗传算法，能够有效的、快速的找到问题的较佳 解决方案，以便在连锁店物流配送决策时采用。 8 硕士学静论文第1 章绪论 1 4 本文所作的工作 第2 章主要介绍连锁店的有关概念，连锁店物流配送的有关问题。 第3 章主要介绍城市单配送中心连锁店物流配送路径选择的数学模型的建 立，以及用自适应的混合遗传算法求解的方法与步骤。 第4 章探讨了区域日j 多配送中心的连锁店物流配送路径选择模型，以及三 阶段求解策略。 第5 章对连锁店物流配送进行仿真，并对算法进行分析和参数的灵敏度分 析。 9 硕十学付论文第2 章连锁佶物流配送概述 第2 章连锁店物流配送概述 2 1 连锁经营介绍 2 1 1 连锁经营的概念 所谓连锁经营是一种商业组织形式和经营制度，是由在同一经营字号的总 部统一领导下的若干个店铺或分支企业构成的联合体所进行的商业经营活动。 其特征是总部负责采购、配送，店铺负责销售，并通过企业形象的标准化，使 复杂的商业活动在职能分工的基础上，实现相对的简单化，从而实现规模经济 效益。这种组织形式有四个鲜明的一致性：经营理念的一致性；企业识别系统 ( c o r p o r a t ei d e n t i f ys y s t e m ，c i s ) 的一致性；业务综合服务的一致性；经 营管理的一致性。 连锁经营的分类在美国和日本有不同的分类方式“捌。美国将连锁经营分 为两类：一是商标商品连锁经营( p t ) ，这是传统的连锁经营方式，加盟店和 加盟总部的关系就像他们的经销商或代理商；二是营利公式的连锁经营( b f ) ， 这是一种新型的连锁方式，总部除了提供商品、商标外，还提供给加盟店全套 的管理和销售制度甚至财务上的沟通。 日本连锁经营分为三类：一是直营连锁( r e g u l a rc h a i n ，r c ) ，这是由总 公司直接经营的连锁店，连锁分店由总公司所拥有；二是自愿加盟( v o l u n t a r y c h a i n ，v c ) ，这种商店由于在加盟之i j 就已经存在，因此名称也有别于加盟店， 各零售店保存有自主经营的独立性，同时又享有永续经营的连锁经营的优势； 三是特许加盟( f r a n c h i s ec h a i n 。f c ) ，这种方式的店铺同总部之b j 签订合同， 同时取得使用总部的商标、商号、经营技术及销售总部开发商品的特许权，经 营权集中于总部。 2 1 2 连锁经营的特点 连锁经营本质特征就是将生产领域的专业化分工的基本原理运用于商品流 通领域，通过企业形象的标准化，经营活动的专业化，管理方式的规范化及管 理手段的现代化，使复杂的商业活动在职能分工的基础上，实现相对的简单化， 从而提高物流效率，降低物流成本，实现规模效益。在具体的经营活动中，连 锁经营有以下几个特点“： ( 1 ) 统一采购。即各连锁店铺向总部提出进货计划，由总部统一采购。 ( 2 ) 统一配送。即配送中心承担连锁店铺的储存、配送、送货、加工等 物流功能，对所有商品实行统一仓储运输，根据各连锁店铺的销售 情况、要货情况和要货订单，及时补货送货。 t o 硕十学伊论文第2 章连锁店物流配送概述 ( 3 ) 统一标识。即各连锁店铺都以同一名称命名，各店铺的外部色彩、 风格、内部装潢、商品陈列以及营业人员的服饰等都是同一的，连 锁店的规划、装修设计、广告宣传都是由总部统一制作。 ( 4 ) 统一营销策略。连锁店铺经营通常要有一个统一的发展战略，不同 时期、季节、商品，要有不同的服务方式、推销技巧，按总部制定 的统一营销策略运行，既能产生较大的影响，也可加深消费者对连 锁店的认识和信任。 ( 5 ) 统一价格。即由总部集中采购、供应商品，由总部统一确定商品的 价格，连锁店铺商品价格的调整必须通过总部来确定。 ( 6 ) 统一核算。即各连锁店铺采取报账制的办法，由总部财务直接与指 定银行发生信贷业务，各连锁店铺未经总部批准不得以任何理由与 银行发生信贷业务。 以上六个“统一”旨在店名、店貌、商品、服务标准化，采购，配送、销 售、决策、经营专业化，商品购销、信息汇集、广告宣传、员工培训、管理规 范的统一化，以提高经营效率，实现规模经济。 2 2 物流配送介绍 2 2 1 配送的概念 关于配送，目前尚无统的定义，有的从功能上给出定义，有的则包括作 业过程，甚至有的还对作业范围和作业地点进行了规定。英文中没有对配送对 应的词，美国配送的英文原词是d i s m b u t i ，是送货的意思，即强调的是将货 物送达。日本对配送最权威性的解释应该是日本工业标准( j i s ) 物流用语： “把货物从物流据点送交购货人。”这一定义也强调的是“送货”。1 9 9 1 年，日 本出版的物流手册对配送作了稍微详细一些的解释是：“与城市之间和物流 据点之间的运输相对而言，将面向城市内和区域范围内需要者的运输，称之为 配送。”这一解释从性质上把配送看成是一种运输形式，并局限在一个区域( 城 市) 范围内。上述经济发达国家对配送的定义或解释中，仅强调送达，并不十 分强调配，是因为在买方市场环境中“配”是完善“送”的经济行为，是进行 市场竞争和提高自身经济效益的必然延伸，既然是一种必然行为，因此就不需 要再强调的必要性。 我国国家标准物流术语中对配送的定义是：“在经济合理区域范围内， 根据用户要求，对物品进行拣选、加工、包装、分割、组配等作业，并按时送 达指定地点的物流活动。”这一定义比较全面地描述了配送的内容和功能。但是， 并不是所有的配送都一定需要这些作业，用户的要求不同、配送的客体不同， 硕十学伊论文第2 章连锁店物流配送概述 作业内容也就会有所取舍，如包裹快递配送就不需要加工、分割等作业。另外， 配送一般存一个集货过程，即把分散的货物集中起来，以便进行其他的配送作 业。 根据物流术语对配送的定义，配送的内涵包括以下几个要点：【5 1 1 ( 1 ) 以用户需求为出发点 配送必须根据用户的要求进行配货和送货，用户的要求包括配送品种、配 送数量、送达时问、送达地点、物品安全、经济性、环保、方便等多个方面。 即使是一个经济组织内部的配送( 如大型企业集团、连锁公司等) ，配送中心也 应该把被配送的部门或下属单位当成用户，并根据他们的要求进行配送。“以用 户需求为出发点”，这是配送的基本观念，但用户的需求必须是合理的，过分强 调“按用户要求”是不妥当的，这是因为用户受自身某些因素的局限，有些要 求实际会损害自我或双方的利益。 ( 2 ) “配”与“送”的有机结合 以“送”为主配送属于运输范畴，其功能主要是输送，是创造空间效用， 配是为送服务的，是为了更好的送。这是配送于一般送货的主要区别。一般送 货只是将用户自己取货改变为货主主动送货，强调服务方式的改变，其功能并 没有发生变化：配送既要实现送货服务，更强调在送货时能满足用户的多方面 需求，使用户感到更加经济和方便，甚至能做到与用户的生产或销售“无缝连 接”，把配送变成用户生产经营的一部分。 ( 3 ) 在经济合理的范围内进行 所谓经济合理，是指既要满足用户的需要，也要有利于实现配送的经济效 益。一般配送物品的批量小、批次多，所以远距离物品配送规模经济性较差， 运力浪费严重。因此，配送不宜在大范围内实施，通常仅局限在一个城市或地 区范围内进行。 ( 4 ) 处于末端的线路活动 在一个物流系统中，线路活动不可缺少，有时可能有多个线路活动相互衔 接成一个物流链，但如果有配送活动存在，则配送是处于末端的线路活动。 2 2 2 配送功能 配送本质上是运输，创造空间效用自然是它的主要功能。但配送不同于运 输，它是运输在功能上的延伸。相对于运输而占，配送除创造空日j 效用这一主 要功能外，其延伸功能可归纳为以下几个方面：【5 1 1 ( 1 ) 完善了运输系统 现代大载重量的运输工具，固然可以提高效率，降低运输成本，但只适于 干线运输，因为干线运输才可能是长距离、大批量，而且才有可能呈现高效率、 硕士学伊论文第2 章连锁店物流配送概述 低成本的运输。支线运输一般是小批量，如果使用载重量大的运输工具则是一 种浪费。支线小批量运输频次高、服务性强，要求比干线运输具有更高的灵活 性和适应性，而配送通过其他的物流环节的配合，可实现定制化服务，能满足 这种要求。因此，只有配送与运输的密切结合，使干线运输与支线运输有机统 一起来，才能实现运输系统的合理化。 ( 2 ) 消除交叉运输 交叉输送，如图2 - 1 所示，在没有配送中心的情况下，由企业直接运送货 物到用户，即使采取直接配送方式，交叉运输也是普遍存在的。由于交叉运输 的存在，使输送路线长，规模效益差，运输成本高。如果在企业与客户之日j 设 置配送中心，采取配送方式，如图2 - 2 所示，则可消除交叉运输。因为设置配 送中心以后，将原来直接由各企业送至各客户的零散货物通过配送中心进行整 合再实施配送，缓解了交叉运输，输送距离缩短，成本降低。 ( 3 ) 提高了末端物流的经济效益 采取配送方式，通过配货和集中送货，或者与其他企业协商实施共同配送， 可以提高物流系统末端的经济效益。 图2 1 交叉运输 图2 2 缓解交叉运输 硕+ 学伊论文 第2 章连锁店物流配送慨述 ( 4 ) 实现低库存或零库存 配送通过集中库存，在同样的满足水平上，可使系统总库存水平降低，既 降低了存储成本，也节约了运力和其他物流费用。尤其是采用准时制配送方式 后，企业可以依靠配送中心准时送货而无需保持自己的库存，或者只须保持少 量的保险储备，这就可以实现企业的“零库存”或低库存，减少资金占用，改 善企业的财务状况。 ( 5 ) 简化手续，方便用户 由于配送可提供全方位的物流服务，采用配送方式后，用户只需向配送供 应商进行一次委托，就可以得到全过程、多功能的物流服务。从而简化了委托 手续和工作量，也节省了歼支。 ( 6 ) 提高了供应保证程度 采用配送方式，配送中心比任何单独供货企业有更强的物流能力，可使用 户减少缺货风险。如巴塞罗那大众物流中心承担着为大众、奥迪、斯柯大、斯 亚特等大众系统四个品牌的汽车零部件的配送任务。四个品牌的汽车在整车下 线前两个星期，有关这些车辆8 8 0 0 0 种零配件在这曩可以全部采购到。假如用 户新买的车坏了，只要在欧洲范围内，2 4 小时内就会由专门的配送公司把用户 所需要的零部件送到手中。 2 2 3 配送功能要素 配送实际是一个物品集散过程，这一过程包括集中、分类和散发三个步骤。 这三个步骤由一系列配送作业环节组成，通过这些环节的运作，使配送的功能 得以实现。因此，通常将这些作业环节称为配送功能要素。 配送的基本功能要素主要包括集货、分拣、配货、配装、送货等。p 1 j ( 1 ) 集货 集货是配送的首要环节，是将分散的、需要配送的物品集中起来，以便进 行分拣和配货。为了满足特定用户的配送要求，有时需要把用户从几家甚至数 十家供应商处预定的物品集中到一处。 集货是配送的准备工作。配送的优势之一，就是通过集货形成规模效益。 如深圳中海物流公司为i b m 公司遍布世界各地的1 6 0 多个供应商提供的料件集 中到香港中转站，然后通关运到深圳福田保税区配送中心，这是一个很复杂的 集货过程。 ( 2 ) 分拣 将需要配送的物品从储位上拣取出来，配备齐全，并按配装和送货要求进 行分类，送入指定发货地点堆放的作业。分拣是保证配送质量的一项基础工作， 它是完善送货、支持送货的准备性工作。成功的分拣，能大大减少差错，提高 硕士学位论文 第2 章连锁店物流配送概述 配送的服务质量。 ( 3 ) 配货 配货足将拣取分类完成的货品经过配货检查，装入容器和做好标记，再运 到发货准备区，待装车后发送。