基于启发式算法的药品物流系统的配送优化及实现.pdf

上海大学 硕士学位论文 基于启发式算法的药品物流系统的配送优化及实现 姓名：孙永松 申请学位级别：硕士 专业：软件工程 指导教师：叶飞跃 20090401 卜海大学硕士学位论文 摘要 现代物流业作为“第三利润源泉已为越来越多的企业界和物流界人士所 关注。目前许多发达国家和地区已形成了比较成熟的物流管理理念、先进的物流 技术和高效的物流运营系统。但是人们对物流的认识还远远不够，特别是在药品 物流方面，对药品的存储、配送等物流特性，人们还不是十分清楚，因此对药品 物流的内在规律还需不断的研究和探索。 物流配送是物流活动中重要环节，是“配”与“送”的有机结合。其核心内 容是备货、配装和车辆的送货过程。这是物流配送系统的关键环节。进行药品物 流配送系统优化，也主要是这些关键环节的关键技术优化问题，包括合理备货、 最佳配装及配送车辆线路优化。对药品配送系统各环节技术优化研究，可以提高 物流经济效益，实现药品物流科学化管理，因此对该问题的研究具有非常重要的 意义。 对药品物流配送系统关键技术优化问题的研究，国外开始很早，对该类问题 的研究已有相当一批研究成果相继问世，并已广泛应用。在国内对该类问题的系 统研究还不多见，处于起步探索研究阶段，就研究的深度和广度来说，还远不能 适应当前我国药品配送业以及物流业迅猛发展的需要。 本文在已有理论研究成果基础上，结合实际项目，对药品物流配送中备货、 配装问题进行了较深入的系统研究。 作为课题的研究基础，论文阐述了课题的来源和研究背景，对物流配送系统 中货物装载等优化方法问题的国内外研究现状进行了综述，对目前连锁药店经营 现状及存在的问题进行了分析。 论文对配送中使用货车车厢进行优化研究，在分析了集装箱问题的优化方法 基础上，结合定序、定位规则，使用构造式启发算法提出了按层装填车厢的方法， 结合剩余空间搜索策略以及空隙融合策略，在装车时充分利用剩余空间填充过程 中浪费掉的许多空隙，提高了算法的有效性，为车厢装载提出了一种合理的布局 及装载方案。 论文针对药品物流配送系统的特点，进行了系统分析，阐述了系统总体设计 v 上海大学硕士学位论文 思想和原则，通过功能设计和结构设计以及系统数据模型的建立，给出了药品物 流配送优化计算机子系统的总体设计方案。并在此基础上进行了系统软件开发和 实施。通过初期的实际应用，基本上实现了该公司配送中心药品配货和装车的优 化：通过与原有业务系统对比，有效的提高了包装纸箱和车厢空间的利用率，减 少了配送车俩，在节约成本的同时，提高了配送效率。 关键词：药品配送车厢装载启发式算法 上海大学硕十学位论文 a b s t r a c t a s “t h et h i r ds o u r c eo fp r o f i t ”，t h em o d e r nl o g i s t i c sh a sa t t r a c t e d m o r ea t t e n t i o no fp e o p l ee n g a g e di nb u s i n e s sa n dl o g i s t i ci n d u s t r y a t p r e s e n t ，m a n yd e v e l o p e d c o u n t r i e sa n d r e g i o n s h a v ef o r m e d c o m p a r a t i v e l ym a t u r el o g i s t i c sa d m i n i s t r a t i o nc o n c e p t ，a d v a n c e d l o g i s t i ct e c h n o l o g ya n de f f i c i e n tl o g i s t i co p e r a t i o ns y s t e m b u ta s e v e r y o n ek n o w s ，t h ea c q u a i n f a n c ew i t ht h el o g i s t i c si sn o te n o u g h p e o p l ea r en o ts oc l e a ro fm o s tp o t e n t i a ll o g i s t i cd i s c i p l i n e s ，s ot h e i n t e r n a ld i s c i p l i n e sf o rt h el o g i s t i c sn e e dt ob ec o n t i n u o u s l yr e s e a r c h e d a n de x p l o r e d v s pi s d i s t r i b u t i o n a n d d e l i v e r y a r ec o m b i n e do r g a n i c a l l ya n d t h ec o r eo ft h e s ea c t i v i t i e si s p r e p a r a t i o n so fm e r c h a n d i s e ，g o o d s d i s t r i b u t i o na n dl o a d i n ga sw e l la sg o o d sd e l i v e r y t h em e n t i o n e dt h r e e e l e m e n t sa r et h ek e yj o i n t si nl o g i s t i cs y s t e ma n dt h eo p t i m i z a t i o no f m e d i c a l l o g i s t i cs y s t e m i s a c t u a l l yt h eo p t i m i z a t i o n o ft h e k e y t e c h n o l o g yi nt h es a i dk e yj o i n t si n c l u d i n gr e a s o n a b l ep r e p a r a t i o no f m e r c h a n d i s e ，b e s td i s t r i b u t i o na n dl o a d i n go fg o o d sa sw e l la st h e d e l i v e r yr o u t i n e o p t i m i z a t i o nr e s e a r c ho ne a c hj o i n to fm e d i c a ll o g i s t i c s y s t e mc a np r o m o t ee c o n o m i cb e n e f i ti nl o g i s t i ci n d u s t r ya n dr e a l i z e s c i e n t i f i cm a n a g e m e n ti nm e d i c a ll o g i s t i c s ，s o 计i sv e r ys i g n i f i c a n tt o u n d e r g ot h er e s e a r c ho nt h ei s s u e t h er e s e a r c ho no p t i m i z a t i o no fm e d i c a ll o g i s t i cs y s t e ms t a d e de a r l y a b r o a da n dr e l e v a n ta c h i e v e m e n t sh a v eb e e ns u c c e s s i v e l yk n o w nt o p e o p l e ，e v e na p p l i e di nm a n u f a c t ur n ga n dd a i l yl i f e i nc h i n a ，l i t t l e r e s e a r c hi sd o n ea n ds e e n ，a c t u a l l yw eh a v ej u s ts e tf o o ti nt h ew o r l do f l o g i s t i c s ，w h e t h e rf r o mt h ev i e wo fd e p t ho rt h ew i d t h ，t h er e s e a r c hc a n n o tm e e tt h ed e m a n d so ft h er a p i dd e v e l o p m e n ti nd i s t r i b u t i o no f v u 一卜海大学硕士学位论文 m e d i c i n ea n dl o g i s t i ci n d u s t r yi nc h i n e s e b a s e do nt h ee x i s t i n ga c h i e v e m e n t s t h e o r e t i c a ir e s e a r c hi n l o g i s t i c s ，t h i st h e s i s ，c o m b i n i n gw i t hp r a c t i c a lp r o g r a m s ，c a r r i e so n f u r t h e rs y s t e m a t i cr e s e a r c ho nt h ei s s u eo fd i s t r i b u t i o na n dl o a d i n go f m e d i c i n e a sar e s e a r c hb a s i so ft h ei s s u e i nf h i st h e s i sf h es o u r c ea n dt h e r e s e a r c hb a c k g r o u n do ft h ei s s u ea r ei l l u s t r a t e d ：r e v i e wo nt h ee x i s t i n g m e t h o d so fo p t i m i z a t i o nf o rg o o d sl o a d i n gi n l o g i s t i cd i s t r i b u t i o na t h o m ea n da b r o a da r eg i v e n ；t h ec u r r e n ts i t u a t i o no fo p e r a t i o n a n d t h ep r o b l e me x i s t e di nc h a i np h a r m a c e u t i c a ls t o r ea r ea n a l y z e d i nt h i st h e s i s ，w ec o n s i d e rt h ep r o b l e mo fo p t i m i z a t i o nf o rt h el o g i s t i c s v e h i c l ew h i c ha r ep r o v i d e da n dd e l i v e r e di nl o g i s t i cd i s t r i b u t i o n o nt h e b a s i so fa n a l y z i n gt h eo p t i m i z a t i o nm e t h o do ft h ec o n t a i n e rl o a d i n g p r o b l e m ，a n du t i l i z i n gp o s i t i o n i n gr u l e sa n ds e q u e n c i n gr u l e s ，w ep u t f o r w a r dam e t h o do fl o a d i n gt h ev e h i c l ea c c o r d i n gt ot h el a y e rw i t h h e u r i s t i ca l g o r i t h m c o m b i n i n gt h ed i s c a r d e ds p a c es e a r c h i n gt a c t i c s a sw e l la st h es p a c em e r g i n gt a c t i c s ，t h ed i s c a r d e ds p a c el o s ti nt h e c o u r s eo fl o a d i n gc a nb ef u l l yu t i l i z e d ，i tc o u l df u r t h e r i m p r o v et h e v a l i d i t yo ft h ea l g o r i t h m ，a n dp u tf o r w a r dar a t i o n a lp a c k i n ga n dl o a d t h es c h e m ef o rl o a d i n g i nv i e wo ft h e f e a t u r e so fm e d i c a ll o g i s t i cd e l i v e r y ，w ec o n d u c t s y s t e m a t i ca n a l y s i s ，i l l u s t r a t et h ew h o l ep r i n c i p l e so ft h es y s t e md e s i g n t h r o u g hf u n c t i o n a ld e s i g na n ds t r u c t u r a ld e s i g na sw e l la sm o d e l i n g s y s t e md a t a ，w ep r o p o s et h et o t a ld e s i g np r o j e c to ft h ec o m p u t e r s u b s y s t e mf o rt h eo p t i m i z a t i o no fd r u gl o g i s t i cd e l i v e r y a n db a s e do n p r e v i o u sr e s e a r c h ，w ew o r k0 ns y s t e ms o f t w a r ed e v e l o p m e n ta n dp u ti n p r a c t i c e t h r o u g hp u t t i n gt h es y s t e mi n t op r a c t i c a la p p l i c a t i o n ，t h e o p t i m i z a t i o nf o rp r e p a r a t i o na n dl o a d i n go fd r u gi nad i s t r i b u t i o n v 海大学硕十学位论文 c e n t e r si sr e a l i z e d ；t h er a t i oo fr o o mu s e di nt h eb o xa n di nt h e c a r r i a g e i s i m p r o v e d ，t h en u m b e ro fv e h i c l ew h i c ha r en e e d e di n d i s t r i b u t i o ni sr e d u c e d ； m o r e o v e r ，t h ee f f i c i e n c i e so fd e l i v e r ya r e i n c r e a s e da n dt h ec o s t sa r ed e c r e a s e d k e y w o r d s ：m e d i c i n ea n dd e l i v e r ，c a m a g el o a d i n g ，h e u r i s t i ca r i t h m e t i c 上海大学硕士学位论文 原创性声明 本人声明：所呈交的论文是本人在导师指导下进行的研究工作。 除了文中特别加以标注和致谢的地方外，论文中不包含其他人已发表 或撰写过的研究成果。参与同一工作的其他同志对本研究所做的任何 贡献均已在论文中作了明确的说明并表示了谢意。 签名：鱼：丞主竺日期：垒丝 本论文使用授权说明 本人完全了解上海大学有关保留、使用学位论文的规定，即：学 校有权保留论文及送交论文复印件，允许论文被查阅和借阅；学校可 以公布论文的全部或部分内容。 ( 保密的论文在解密后应遵守此规定) 签名：圣包丞五生导师签名：枷期： 上海大学硕士学位论文 1 i 课题的来源 第一章绪论 本课题来源于上海市某大药房连锁经营有限公司e r p 系统。 该公司作为上海市一家颇具规模的药品零售连锁经营企业，连锁药店，包括 直营店和加盟店，合计有3 0 0 多家，遍布全市，包括奉贤、金山等市郊。公司 配送中心负责药店的药品及医疗器械的配送工作。公司的药品采购、库存、销售 等业务都是通过计算机系统进行，实现对人流、物流、资金流、信息流等多方面 的管理。通过网络，可以对各大连锁分店进行实时信息管理，实现远程业务、远 程报表、远程审计和远程管理。同时还能实现公司内部管理、财务、供应、销售 之间的协同，公司与社会相关部门如药品监督管理局、社保局等之间的协同。系 统运行6 年多来，给公司带来了良好的经济效益和社会效益。 然而，该公司配送中心所属的业务部和仓库，每天的业务量繁忙，仓库和业 务部人员每天都在消耗大量时间和精力来进行出库前的理货、备货以及装车工 作；由于药品品种繁多，包装形态、储运性能不一样，加上公司下属零售药店一 般不单独设仓库，都是零散要货，还有的以最小包装单位进行要货；而且每家店 所要的药品品种、数量都不一样，这就给二次包装带来很大问题；有的药店要的 药品多，工人们怕一箱装不下，一般选用大的纸箱来包装，由于一般不在一个大 纸箱中混装其它药店的药品，所以造成纸箱使用空间浪费，同时也浪费货车使用 空间。往往都是仓库工人凭借多年的经验在操作，工作效率低，劳动强度大；装 车方面，往往由于要货时问紧，配送中心离要货的目的地距离又较远，一辆车未 装满就发车；有的时候又为了装满一车，车厢甚至连驾驶室都塞的满满的，不但 增加了药品装、卸货时间，也影响了行车安全；而且车子由于所装药品所属目的 地较多，没有考虑运输路线，仅凭司机的感觉和经验在送货，运输路线没有优化， 极大的增加了运输成本，延长了送货时间。多年来，成本高，配送效率低的局面 未得到改观。 上海大学硕十学位论文 本论文的研究意义在于解决或部分解决以上存在的问题，对药品连锁经营企 业配送中心( 包括专业药品物流公司) 降低配送成本，提高配送效率，提高客户 满意度具有重要的应用价值。 1 2 课题背景 计算机技术在物流上的应用已远远超过了数据处理，事务管理，正跨入智能 化管理领域，在国内，研究和开发的物流信息系统也有了较完整的管理模块。比 如，用户可以随时通过网络远程查询货物及其流动情况；系统支持无纸化作业和 条形码技术；用户可以随时查看仓库库存等。国内物流企业通过计算机系统基本 上实现了货物的采购、库存、出库等计算机化管理，使企业降低了成本，提高了 效益；但是在国内绝大多数物流企业的系统中考虑物流配送的较少。我们知道， 配送是物流环节中很重要的一部分，配送业务，主要是货物的分拣，包装，装车 和运输，是“配与“送”的有机结合。目前，在实际操作中仍然凭借经验进行 配货装车，往往不能很好的利用车辆的运能；在发车时，没有考虑最佳行驶路线， 增加了运输成本；这样，既消耗了大量的人力、物力和财力，又浪费了大量时问， 造成成本居高不下，配送效率低，服务质量差的局面。所以，有必要对物流企业 物流系统配送部分进行研究和优化。 1 3 国内外物流配送的研究综述 自从2 0 世纪物流配送产生以来，物流配送一直是研究的热点课题。在配送 的发展过程中，出现的主要配送模式有集中配送模式、及时配送模式、计划配送 模式、共同配送模式、一体化配送模式及第三方物流模式和第四方物流模式。国 外的第三方物流已经发展比较成熟1 1 】，并出现第四方物流，而在国内，第三方物 流正在发展阶段，第四方物流处在理论研究阶段【2 1 。 现在随着物流配送集约化、一体化的发生，常将配送各环节综合起来，核心 部分为配送车辆的集货、货物配装及送货路线的优化，以及一体化的优化。进行 2 海人学硕士学位论文 药品配送系统优化，主要就是进行药品的配货装载及配送车辆优化调度。考虑到 该公司的配送业务是上海市，而上海市的道路交通情况比较复杂，受道路拥挤、 交通事故而进行的交通管制，以及单行道路、天气等复杂因素的影响，使得车辆 路径优化变得异常复杂化，需要及时、灵活的选择，所以本文的重点放在配货及 装载方面，对配送车辆优化调度路径问题不作研究。下面就从药品装载问题来看 药品物流配送优化国内外的研究现状。 1 3 1 货物装载问题研究现状 对于货物装载问题，国外于上个世纪六七十年代就开展了一定的研究，之后 相继出现了一些经典的算法，各种算法各有特点和侧重，目前常用的方法有数学 规划法、图论法、启发式算法等。 g e h f i n g 3 提出按阶段填充、在深度方向按层布局的启发式算法，不仅考虑 了空间利用率，而且考虑了重心平衡。 c h r i s f o f i d e s 和w h i t l o c k 4 1 提出了一种利用树搜索来解决布局中一刀切问题 的算法。该算法将动态规划和运算规则融于树的搜索中，通过施加“使布局模式 最优化“ 这一限制条件来缩小树的大小，适用于中等规模的一刀切问题优化布局 方案的确定。 m a n n c h e n 5 设计树搜索算法，理论上对三维箱体布局有效，但由于三维箱 体布局属完全问题，随着布局箱体增多，解空间暴增，计算效率较低。 就国内而言，对于货物装载问题研究开展的时间较短，对该问题的研究比较 少，由于其涉及到不同学科领域，所以理论研究相对薄弱，下面就国内的一些研 究情况作简要介绍。 姜义东、查建中【6 1 等人针对集装箱内货物装载布局问题，提出一种利用三叉 树结构来表达三维矩形物体稀局状态空间分解的方法，对集装箱货物运输有一定 借鉴作用。 何大勇1 7 】等在姜义东研究的基础上运用遗传算法做了改进，其优点是能处理 多目标、多约束的问题，缺点是在货物很多时，应用遗传算法对每件货物进行整 数编码构成的染色体，基因数量多，规模巨大加上众多约束条件，导致算法收敛 3 上海大学硕士学位论文 非常慢，甚至大多数情况下得不到可行解。 对货物装载问题，特别是对药品这类物体，目前研究较少，主要研究集中在 对集装箱、托盘以及零担货物的装载方面。虽然对于装箱问题研究的较多，但是 主要是针对一维、二维的装箱问题的研究，常用的三维空间装箱，由于实际应用 约束条件很复杂，难度大，目前的研究相对较少。因此有必要对药品的装载进行 进一步的研究。 综上所述，国内外在物流系统的配送优化方面作了一些分散、独立的研究， 在国外，一些研究成果已开始运用于生产实践，而我国对物流配送研究才刚刚开 始，而且侧重于学术研究，与实际应用差距很大，尤其在药品连锁经营企业的药 品配送优化研究与实现方面几乎没有，许多药品连锁经营企业也还是把大量精力 集中在增设销售药店，扩大销售上，对如何降低运行成本，提高配送效率的认识 不足。 1 3 2 配送系统发展综述 配送中心的迅速发展与以计算和通讯技术为基础的管理信息系统的应用密 不可分，它及时准确地传递、反映市场信息，使信息处理由分散处理变为分布处 理和集中控制相结合，综合利用各种信息使配送中心相关部门合理地组织商品流 通，减少库存积压，加快资金周转。由于计算机运算速度快、数据存储量大，可 以利用数学模型对企业的管理活动进行模拟或利用各种计算方法进行定量定性 分析，提高配送管理决策的准确和科学性；另一方面，可以对过去的大量数据进 行分析、总结、找出规律，做到事前有预测，使管理工作由被动变为主动。 随着科学的不断进步，特别是感测技术( 激光扫描) 、条码、r f i d 及计算机控 制等技术的使用，实现了物流作业的自动化，无纸化。其中计算机技术在物流上 的应用已远远超过了数据处理，事务管理，正在跨入智能化管理领域。g i s ，g p s 技术的运用使动态跟踪货物在运输途中的位置信息，用户随时可以了解所需货物 的行程得以实现。同时如果配送过程中出现问题，能够及时派其它车辆完成任务。 国外一些物流企业已经得到了较好的运用。 国外的物流企业大多都具有良好的信息处理系统和传输系统，如美国洛杉矶 4 上海大学硕士学位论文 西海报关公司与码头、机场、海关信息联网。当货从世界各地起运时，客户便可 以从该公司获得到达的时间、到泊的准确位置，使收货人与各仓储、运输公司等 做好准备，使商品在几乎不停留情况下，快速流动、直达目的地。又如，美国干 货储藏公司( d s c j 有2 0 0 多个客户，每天接受大量的订单，需要很好的信息系 统。为此，该公司将许多表格编n - f 计算机程序，大量的信息可迅速输入、传输， 各子公司也是如此。再如，美国橡胶公司( u s c o ) 的物流分公司设立了信息处理 中心，接受世界各地的订单：i b m 公司只需按动键盘，即可接通u s c o 公司订货， 通常在几小时内便可把货送到客户手中。良好的信息系统能提供极好的信息服 务，以赢得客户的信赖【8 】。 我国作为一个发展中国家，物流业起步较晚、水平低，在引进电子商务时， 并不具备能够支持电子商务活动的现代化物流水平。从全国范围来看，我国长期 以来受计划经济的影响，物流社会化程度低，物流管理体制混乱，机构多元化， 这种分散的多元化物流格局，导致社会化大生产、专业化流通的集约化经营优势 难以发挥，规模经营、规模效益难以实现，设施利用率低，布局不合理，重复建 设，资金浪费严重。由于利益冲突及信息不通畅等原因，造成余缺物资不能及时 调配，大量物资滞留在流通领域，造成资金沉淀，发生大量库存费用。另外，由 于我国物流企业与物流组织的总体水平低，设备陈旧，损失率大，效率低，运输 能力严重不足，形成了瓶颈，制约了物流的发展1 9 1 。 国内物流企业通过计算机系统基本上实现了货物的采购、库存、出库等计算 机化管理，使企业降低了成本，提高了效益；但是在国内绝大多数物流企业的系 统中考虑物流配送的较少。我们知道，配送是物流环节中很重要的一部分，配送 业务，主要是货物的分拣，包装，装车和运输，是“配“ 与“送一的有机结合。 目前，在实际操作中仍然凭借经验进行配货装车，往往不能很好的利用车辆的运 能，增加了运输成本；这样，既消耗了大量的人力、物力和财力，又浪费了大量 时间，造成成本居高不下，配送效率低，服务质量差。 5 上海大学硕上学位论文 1 4 本论文的主要工作内容 本课题研究的是药品物流的配送优化及系统实现。本文参考了国内外的有关 文献和书籍，采用构造型启发式算法与具体应用相结合；对文献中有关集装箱装 载问题的研究基础上，提出货车车厢装载的布局方案。 首先，对该公司配送中心目前的箱式货车装车情况进行了描述，分析了装车 问题的相关概念和规则，将车厢空间按垂直分层，根据药品矩形包装的不同边长 作为层厚进行空间分割。在运用启发式算法方面，前人算法是将待装物逐个搜索 处理，影响了算法的效率，本文将一层看作一个整体，将对物体的搜索转化为对 物体不同层厚的分层策略进行空间搜索，有效提高了算法的效率。对于不能进行 完全层装填的待装物体仍采用三叉树进行空间分割装载。由于装填过程中对空间 进行了切割，会产生虚拟的废弃空间，在进行下一步装填时，这些废弃空间可以 结合再利用。 其次，对该公司配送中心的业务流程进行了分析，给出了配送优化子系统的 功能设计、结构设计、功能需求模块设计以及数据模型的建立等。 最后，在分析、设计的基础上，开发了配送优化子系统软件，进行了系统实 现，通过试运行，给出优化结果。 本文共分六章。研究内容分别为：第1 章绪论，介绍课题背景与来源以及 课题的内容，国内外的相关研究现状。第2 章阐述目前连锁药店的经营现状及存 在的问题。第3 章给出箱式货车的装车描述及相关的概念和规则，集装箱装载相 关问题的研究，集装箱装载问题的特点、分类。最后是启发式算法求解，详细给 出本文问题的描述，重点放在剩余空间搜索策略上。第4 章是配送优化子系统的 分析和设计。第5 章基于计算机软件技术的系统实现，通过该公司药品配送中心 的试运行，进行了优化效果分析，给出优化结果。第6 章结论和展望，对所做的 工作进行总结，并对未来的研究做了展望。 6 上海大学硕士学位论文 第二章连锁药店经营现状分析 2 1 连锁经营概述 2 1 1 连锁经营的来源及现状 世界公认的第一家连锁商店“大西洋和太平洋茶叶公司一于1 8 5 9 年在美国 成立，它是当时世界上最早的正规连锁公司。该公司发展到1 8 6 5 年已经拥有了 2 5 家连锁店，并开始增加食品经营，同样也获得成功，到18 8 0 年，该公司己发 展壮大到1 0 0 家连锁店。 在其后的1 0 0 多年时间里，连锁经营在欧美各国均取得了不同程度的发展， 特别是近2 0 年，随着计算机技术的发展和普遍运用，连锁经营得到了空前发展。 据美国商务部统计，在19 个大的行业中，都己经实现了连锁化。目前连锁经营 在美国零售业中具主导地位，连锁店的销售额己占零售额的6 0 以上。 我国连锁经营自9 0 年代初起步，经过十几年的发展，己成为零售业、餐饮 业和服务业普遍应用的经营方式和组织形式。我国的连锁经营的确发展很快。 19 9 9 年销售额超过5 0 0 0 万元的零售企业中，半数以上是中国连锁经营协会的 会员单位，会员企业占企业总数的6 5 。同时，连锁经营的发展还存在两大突出 问题，首先是企业规模小，其次是规范化水平低。统一采购、统一配送比重不高， 信息系统建设滞后，管理的科技含量较低，大多数连锁企业还没一个完善的有形 成、规范化运作的经营管理体制。 2 2 连锁药店现状分析及存在问题 2 2 1 药品零售业的发展 随着我国医药商业管理体制的改革，购销政策的放开，被国家垄断经营3 0 年之久的医药零售业准入坚冰被打破，上世纪九十年代药店准入门槛的降低，引 7 卜海火学硕士学位论文 来资本大举进入。特别是自2 0 0 1 年以来，民办药店政策解冻，各地相继解除了 “封停“ 两三年的零售药店的开办限制，实行国家药品生产质量规范标准( g m p ) 和国家药品经营质量管理规范( g s p ) ，只要符合规范的企业，就可以获准进入医 药市场，于是民营资本、个体经营者纷纷投资开办药店。众多的药店如雨后春笋 般的出现在各个城市，开展药品零售服务。随着药店经营能力的增强，开展连锁 经营是必然趋势，连锁药店已成为药品零售业发展的主流。 截至2 0 0 8 年3 月3 1 日，我国医药批发企业2 7 0 0 0 多家，全国药品连锁企 业己达3 2 16 家，零售药店已达2 7 8 0 17 家，连锁门店达3 2 万家，连锁企业销 售额超过2 6 0 亿元，相对于2 0 0 0 年医药商业19 4 的增长，医药连锁业呈现成 倍增长的趋势，初步显示这种先进的营销模式的优势。 连锁药店带给人们不仅是高品质的生活享受，它也改变了人们生活方式和消 费习惯，也改变了人们对传统药店的认识，得到了消费者的欢迎。我国连锁药店 自身的实力也不断的增强，出现了太极集团、深圳海王星辰、重庆和平药房等航 母型连锁药店。如太极集团在川、渝己拥有“桐君阁”、“太极“ 两个品牌的药店 4 0 0 0 多家药店，建成全国规模最大的医药商业零售网络，依靠该销售平台，今 年上半年，太极累计完成销售总额3 5 3 2 亿元，实现利税1 5 2 亿元，同比增长 达2 6 。 2 2 2 药品零售业在信息技术发展中存在的问题 连锁药店配送中心是承担物流专业化管理职能的组织机构，它是药品连锁经 营的核心。这是因为药品连锁经营的集中化、统一化管理在很大程度上是靠配送 中心来具体实施的，通过配送中心的作业活动，不仅可以大大简化各分店的活动， 从而降低连锁药店的物流总费用，而且还能实现药品在流通领域中的增值，并向 分店提供增值服务。药品连锁经营配送中心的业务活动，是从供应商处取得药品 后，按照各连锁分店的经营需要，快捷准确地将药品配送到各个分店，并且依据 高效率的信息、传递和管理手段，对各分店的业务活动进行监督和控制。 配送业务，主要是货物的分拣，包装，装车和运输，是配一与“送“ 的有 机结合。目前，在实际操作中仍然凭借经验进行配货装车，往往不能很好的利用 8 上海人学硕士学位论文 车辆的运能，增加了运输成本；这样，既消耗了大量的人力、物力和财力，又浪 费了大量时间，造成成本居高不下，配送效率低，服务质量差。 根据经济学理论分析，规模越大，管理成本越高，对于地点分散的连锁店更 是如此，美国连锁药店充分运用现代信息技术工，实现了高效率的管理，从而节 省了费用，保证了经济效益。各家药店均有先进的计算机系统终端遍布各分店， 从而实现流程化、标准化管理，包括电子数据管理、卫星通讯、配送盘货控制、 销售分析、员工的绩效考核分店每日营业数据，都以最快的速度汇总至总部，由 总部在充分掌握具体情况的条件下，决定下一步的对策，总部的任何指令几乎同 时到达数百家或上千家分店很多药店自己不设立配送中心，而由批发商来担任这 个角色，依靠电子订货系统，与批发商或供应商在网上联络，实现沟通的流畅无 阻系统、及计算机网络的运用给连锁经营带来了不可估量的价值【1 0 l 。国外发达 国家各种企业采用商务智能的水平已经远远超过了我国。美国管理集团公司每年 对欧洲、北美和日本家大中型企业的商务智能技术的采用情况进行了调查，结果 显示，在金融领域，商务智能技术的应用水平已经达到或接近，在营销领域也达 到，并且在未来的年中，各个应用领域对该技术的采纳水平都将提高约5 。 早在19 8 7 年，美国c v s 就开始将其药房部的销售实现计算机化，当年底其 家分店已经全部安装了的计算机系统年，电子收款机扫描系统在所有的分店安装 完毕，该技术可使总部快速获得产品流动和库存的详细信息，从而增加销售，提 高利润率，减少削价次数和人工成本全美首家安装了处方自动审核系统，开通小 时电话服务，应用药店系统实现处方调配的现代化，还在客流量大的门店增加自 动点药机。我国的连锁药店大约只相当于美国七十年代的水平，我国医药流通领 域万余家企业的药品销售收入总额亿元合亿美元，不及美国最大的药品流通企业 年销售收入亿美元的一半，连锁药店的计算机系统还在完善之中。信息技术应用 没有释放其潜能。信息技术应用的深度远远不够。如美国的零售批发业普遍采用 电子数据交换系统工、电子订货系统、电子转账系统、条码技术特别是商业智能 技术，在我国的医药流通企业的应用还只处于初级阶段。随着企业规模的扩大， 医药连锁企业计算机系统的更新和改造是企业面临的问题。 据联商网独家发布的中国零售业信息化调查报告，该报告是调查了中国 9 上海大学硕士学位论文 国内近家不同地域、不同业态、不同规模的零售企业后得出的真实有效的调查分 析报告，详细阐述了国内零售业信息化建设的现状和存在的问题。从调查结果来 看，国内零售业信息化建设跟前几年相比，已经有了明显的进步，一系统等一些 传统技术的应用变得日益普遍，零售企业对信息化建设也日益重视，所投入的财 力和入力也不断加大但从整体来看，目前国内零售企业的信息化水平还处在一个 较低的层次，有很多企业的水平还只是停留在代替手工记账和对手工的模拟操作 上。客户关系管理、连锁门店间的信息化、供应链管理、电子商务、数据的准确 与数据模型、系统的稳定性等等都是摆在零售企业面前急需解决的一些问题，也 是它们最关心的一些问题。而造成国内零售业信息化发展水平缓慢的原因也是多 方面的。连锁药店信息技术应用的初级化归结起来有以下一些原因： 第一，我国连锁药店的经营模式还很不成熟，处在吸收借鉴国外先进模式， 同时寻找适合本国实际的模式的阶段。管理信息系统的应用本就重管理远大于重 技术，在这样的大环境下，对系统自身的适应性、灵活性提出很高的要求，导致 连锁企业与企业之间的沟通总是不畅，系统应用一段时问就不适应需求的现象很 普遍。在这种情况下，更谈不上深入应用了。 第二，管理信息系统应用没有释放其潜能的另一原因就是企业在应用信息技 术时，总是沿用旧的或现成的方式做事，而不是注重“工作应该怎样做，然后 考虑应用手段来辅助实现它。如果在原有低效的业务流程上使用新技术，往往只 会让流程变得更加无效。从这一点看，国内连锁药店与国外连锁药店在信息技术 的应用差距上不是体现在技术的先进性上，而是体现在与应用这些先进管理技术 和管理手段相适应的组织架构、管理机制、业务流程等方面。 第三，连锁药店信息技术人才的极度匾乏也成为阻碍管理信息系统深入应用 的原因之一。技术与连锁管理的完美结合，需要企业培养出这方面的复合型人才， 不是一个，而是一支队伍。企业虽然对此有认识，但重视程度远远不够。 因此，对于连锁药店管理信息系统的应用研究是及时、必要和务实的。连锁 药店的继续迅速而良性的发展必须是伴随着信息化的深入应用才能实现的，这不 仅包括管理信息系统的深入应用，还包括物流信息技术的深入应用。信息系统的 应用虽然不是连锁药店应对激烈竞争环境的充分手段，但毋庸置疑的是必要手 上海大学硕士学位论文 段，这是连锁药店打造核心竞争力的基础。 一j ：海大学硕：l 学位论文 第三章装车问题的描述及优化 3 1 货物装车问题概述 3 1 1 货物装车的一般描述 在实际运输中，为了产品的安全和便于运输，很多产品在生产出来后就被装 入到各种尺寸的矩形木箱或纸箱中，然后这些箱子再被装入货车进行运送。目前 该配送中心主要以厢式货车为主，所以货物装车问题可以简化为集装箱装载问 题。 集装箱装载是一种很重要的集装化方式，它有利于货物的装卸和运输管理。 所谓的集装箱装载问题( c o n t a i n e rl o a d i n gp r o b l e m ，简称c l p ) ，是指将一 些长方体货物按一定的方式装入集装箱，从而最大限度的提高集装箱的空间利用 能力。集装箱问题是矩形货物在集装箱中的摆放安排问题，以最大化集装箱空间 的使用率为目标。一般情况下，称这类问题称为三维装箱问题。 集装箱装载问题( 以下简称c l p ) 是一个非常有价值的研究课题，在学术上属 于相当复杂的几何组合优化问题( g e o m e t r i cc o m b i n a t o r i a lo p t i m i z a t i o n ) 。 集装箱装载问题是布局问题领域的三维问题，在理论上属于n p 完全问题。在实 际问题上直接利用数学中的优化方法很难解决，因为数学优化方法一般是对量的 优化，通过方程求解得到目标解。但是集装箱装载问题不仅是量的问题，它还需 要对物体以及剩余空间进行形状描述，使得该问题无法用纯数学方法进行描述， 无法通过数学公式进行求解，因此该类问题只能通过一些近似的方法来解决1 1 0 。 集装箱装载问题广泛地出现在铁路货车车厢装载，汽车车厢装载，轮船配载， 集装箱装载中。集装箱装载是配送过程的关键环节，如何给出一个合理的布局及 装载方案，在保证装运的稳定性、多目的地运送、负重限制、箱体内的重量分布、 装箱效率等问题的基础上，使集装箱的空间利用率最大，是这类问题的主要目标。 分别从集装箱和货物两方面考虑，根据现有文献显示，集装箱配载大致分为 四种配装情形，相同体积货物与不同体积货物的配载、单个集装箱和多个集装箱 卜海大学硕士学位论文 的配载。d y c k h o f f 在文献【1 1 】中提出将集装箱装载分为单个集装箱与多个集装 箱的配装( d y c k h o f f ，19 9 0 ) 对于体积不同货物的配装情形，b o r f f e l d t 又将之细分为弱差异情形( w e a k l y h e t e r o g e n e o u s l 与强差异情形( s t r o n gh e t e r o g e n e o u s ) ，弱差异即只有少数几 种体积不同货物但每种货物数量较多情况，反之多种体积不同的货物但每种数量 较少则称为强差异情形 1 2 1 ( g e h r i n g ，19 9 7 ) 。 就本文药品连锁配送企业来说，虽然使用多辆车进行配送，但为了使总的车 辆使用数尽量少，只有提高每辆车的空间装载利用率，属于单个集装箱装载情况。 又由于上一章药品要货除原厂的整箱包装外，还采用原有的大量空箱来包装，类 似体积相同的货物数量较多情况，可以视为单集装箱弱差异情形。 货物的装载问题我们通常作如下假设： 1 车厢的长、宽、高分别代表笛卡尔坐标系的z 、x 、y 轴方向，坐标原点位于 前端右下角，后开门，如下图所示。 y z 图孓1 车厢的三维表示 2 货物的放置方向必须与坐标轴平行或正交，货物不能与其它货物交叠放置， 货物不得超出车厢的尺寸范围，货物的挤压变形可以忽略。 3 假设货物可以任意旋转。 1 3 上海大学硕十学位论文 3 1 2 三维装车问题的分类 按照不同的标准三维装载问题有多种分类方法，以下是几种常见的分类方 法： 1 以装载的箱式货车有限和无限来划分：货车数量无限，货物必须全部装完， 要求使所用的车辆数量尽量少；车辆数量有限，待装货物数量超过了车辆的装载 能力，要求被装载货物的总体积达到最大，使车厢空间利用率最高。 2 根据所装货物的类型可分为：所有货物的类型体积、三维大小等相同。货物 的类型不同，且类型多，每种类型的货物数量少。货物的类型不同，但是类型少， 每种类型的货物数量多。 3 1 3 装车问题的相关概念 3 1 3 1 分层的概念 在求解的诸多启发式算法中，为了便于装填，大都引入了分层的概念【1