（交通运输规划与管理专业论文）实时订货信息下物流配送车辆调度优化研究.pdf

摘要 由于电予商务和网际网络的兴起，越来越多的企业开始应用电子商务和网 络，同时顾客对商品到货时间要求越来越严格。可以说，对顾客进行产品的及时 配送是企业和电子商务成功的关键，而适当的车辆调度方式是较少配送时问和配 送成本的重要因素。 在过去，对实时订货信息下车辆调度优化的研究，只能将这些实时信息累积， 待各车辆服务完所有预定的顾客后再重新进行配送，一旦车辆路线决定并了进行 配送，在获得新的信息后将无法更改，而只能新增加车辆进行配送或者在途车辆 原路返回补货后再按原配送路线配送。事实上，这种调度方式已经失去了实时订 货信息所具备的优势，忽视了需求信息的改变对最佳配送路线的影响。它一方面 可能导致无法有效满足顾客的要求，另一方面，也可能大大增加配送中心的配送 成本。因此，传统的车辆调度问题算法已无法应付快速回应顾客需求以及配送中 心对物流配送提出的要求。 本研究尝试利用动态的观点处理实时订货信息下具有随机性需求量与需求 地点的车辆优化配送问题，期望在订货需求信息不断变动的情况下，适时改变车 辆配送的路线与增加车辆进行服务，使其能够更有效率的服务所有需求。为此， 本文探讨了电子商务出现后，实时订货信息对于物流配送的影响，并分析电子商 务下的配送与传统配送不同特性。由此构建出符合此物流配送特性的问题模式， 并结合实时的订货信息与车辆派遣，建立一套能够处理该模式的车辆调度方法。 在模型构建中，运用处理静态车辆调度问题的车辆运营变动成本模型，在此 基础上，充分考虑顾客对时间要求和实际配送特性，加入混合的时间窗模型，并 考虑本研究环境下，可能发生配送失败情形，配以配送失败的惩罚成本，构建符 合本问题的模式。并依据本研究的研究范围和假设，设计出适用于本研究的演算 流程：初始路线构建和路线改善。初始路线将遗传算法全局搜索能力强的特点和 局部搜索算法局部搜索能力强特点相结合，构建了适于本文的混合遗传算法，路 线改善采用禁忌搜索法，经案例测试，该方法在求解时间和效果上表现出良好的 性能，尤其是在求解大规模的车辆调度问题，具有一定的实际应用价值。 关键词：电子商务实时订货信息物流配送车辆调度优化时间窗混 合遗传算法禁忌搜索法 a b s t r a c t w i t ht h er i s i n go ft h ee l e c t r o n i cc o m m e r c ea n dn e t w o r k ，m o r ea n dm o r ef i r m s h a v ed e v o t e dt h e m s e l v e si nt h ea p p l i c a t i o no ft h ei n t e r a c tn e t w o r ko nt h e i rb u s i n e s s e s a n dt h ec u s t o m e r sa r em o r ea n dm o r e s t r i n g e n tt ot i m ef o rt h eg o o d sd e l i v e r y t h e c a p a b i l i t yo fd e l i v e r yt h e i rp r o d u c t st ot h ec u s t o m e r si nt h es h o r t e s tt i m ei st h ek e y f a c t o ro ft h es u c c e s so ft h ee l e c t r o n i cc o m m e r c e t h ea p p r o p r i a t ed e l i v e r yr o u t e a s s i g n m e n tp l a y sm a j o r r o l ei nt h er e d u c t i o no ft h ed e l i v e r y o p e r a t i o nt i m e t r a d i t i o n a l l y , t h es t u d i e sa b o u tv e h i c l es c h e d u l i n gp r o b l e m ( v s p ) o nr e a l t i m e d e m a n di n f r o m a t i o nc a nd i s t r i b u t eo n l ya f t e rg e tt o g e t h e rd e m a n di n f o r m a t i o na n d w a i t i n gf o ra l lv e h i c l e sh a v i n ga r r i v e d s oo n c et h er o u t es t r u c t u r ei sd e t e r m i n e d ，i t w i l ln o tb ea l t e r e d i fd i s t r i b u t i o nc e n t e rw i l lm e n tw i t hd e m a n do fc u s t o m e r s t h e y o f t e na d dv e h i c l e st os e r v i c eo ro r d e rv e c b i c l e sr e t u r n i n gt od i s t r i b u t i o nc e n t e rt o s u p p l yg o o d s i nf a c t ，t h e y c o u l d n tt a k ea d v a n t a g et ot h ea d v a n t a g eo fr e a l - t i m e i n f o r m a t i o nw e l l t h i st y p eo f a p p r o a c hi g n o r e st h ei m p a c t so f t h e c h a n g e s i nd e m a n d r e q u i r e m e n t sa n dt r a f f i cc o n d i t i o n so n t h eo p t i m a lr o u t es t r u c t u r e o nt h eo n eh a n d ，i t m a y l e a dt od i s t r i b u t i o nc e n t e rn o tt om e n tw i t hd e m a n do fc u s t o m e r s o nt h eo t h e r h a n d ，i tm a y a d dc o s t so fd i s t r i b u t i o ns i g n i f i c a n t l y t h e r e f o r e ，t h ep a s tm e t h o dc a n n t s a t i s f yw i t ht h ed e m a n do ft h ec u s t o m e r sa n dd i s t r i b u t i o nc e n t e r sf o rt h el o g i s t i c s d i s t r i b u t i o n t h ev s pw i t hs t o c h a s t i cd e m a n dl o c u sa n dq u a n t i t i e so nt h er e a l t i m ed e m a n d i n f o r m a t i o nw a sd e a l tw i t hi nt h i sp a p e r , e x p e c t i n gt oa d j u s tv e h i c l e sr o u t i n ga n da d d v e h i c l e st os e r v ec u s t o m e r ss ot h a tt h e yc a ns e r v em o r ee f f i c i e n t l y t h e r e f o r e ，t h e a f f e c to fr e a l t i m ed e m a n di n f o r m a t i o no nd i s t r i b u t i o nw a sd i s c u s s e di nt h ep a p e ra n d t h ed i f f e r e n c eb e t w e e nr e a l t i m ed i s t r i b u t i o na n dt r a d i t i o n a ld i s t r i b u t i o nw a s a n a l y z e d b a s e do ni t ，t h ep a p e rb u i l tac o r r e s p o n d i n gm a t h e m a t i cm o d e la n dd e s i g n e das u i to f m e t h o dt os o l v et h ep r o b l e m i nb u i l d i n gt h em o d e l ，t h ep a p e ra p p l i e st ov e h i c l ec h a n g i n gc o s to fs t a t i cs t a t e s v s p , a n da d d st oh y b r i dt i m ew i n d o w sm o d e la c c o r d i n gt od e m a n da n dd i s t r i b u t i o n c h a r a c t e r i s t i ci no u rc o u n t r y t a k i n gi n t oa c c o u n tp o s s i b l ef a i lt od i s t r i b u t eu n d e rt h e c o n d i t i o n so nt h i sp a p e r , t h ep u n i s hc o s tw a sa d d e dw h e nf a i l i n gt od i s t r i b u t ei nt h e p a p e r , t h u s ，t h et h r e ep a r t sm a d eu p o ft h em o d l e b yt h ec o n f i n e ，t h i sp a p e rd e s i g n e d am e t h o dt os o l v et h ep r o b l e m ：s t r u c t u r i n gi n i t i a l i z a t i o nr o u t ea n da m e l i o r a t i n gr o u t e o nt h eb a s i so fa n a l y z i n gt h ew e a k n e s so fg e n e t i ca l g o r i t h mi nl o c a ls e a r c h ，t h i sp a p e r b u i l d sah y b r i dg e n e t i ca l g o r i t h mw h i c hi st h ec o m b i n a t i o no fg e n e t i ca l g o r i t h ma n d l o c a ls e a r c h a l g o r i t h m f o rs o l v i n g p h y s i c a l d i s t r i b u t i o n r o u t i n gp r o b l e m w h e n a m e l i o r a t i n gr o u t e ，i ta d o p t e d t a b us e a r c h a l g o r i t h m ，e x a m p l e sp e r f o r m s w e l li nb o t h r e s o l v i n ge f f i c i e n c ya n dr e s u l tq u a l i t y , e s p e c i a l l yt ol a r g e s c a l e v e h i c l es c h e d u l i n g p r o b l e m w i t hp o t e n t i a lo f a p p l y i n g i np r a c t i c et os o m ee x t e n d k e y w o r d s ：t h ee l e c t r o n i cc o m m e r c e ；r e a l - t i m ed e m a n di n f o r m a t i o n ；p h y s i c a l 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 s ；h y b r i dg e n e t i ca l g o r i t h m ； t a b us e a r c ha l g o r i t h m i i i 长沙理工大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所 取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任 何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡 献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的 法律后果由本人承担。 作者签名：书形乞 日期：办卿年丫月嘲日 l 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意 学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文 被查阅和借阅。本人授权长沙理工大学可以将本学位论文的全部或部分内 容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存 和汇编本学位论文。 本学位论文属于 l 、保密口，在年解密后适用本授权书。 2 、不保密口。 ( 请在以上相应方框内打“”) 作者签名： 导师签名： 日期：l 一一年 日期：0 弘年 y 月踟日 4 月2 p 目 珐耘 叫h 彬讯 符号注释 文中变量说明如下： ( 1 ) 基本参数 c ( to ，z ) ：调度总成本： to ：车辆从仓库出发的时间向量： x ：任务向量。代表所有货运车辆需要走访的顾客及顺序： n ( f ) ：某一车辆要走访的第i 个顾客所在节点号： ：第，辆车将要走访的总顾客数目； m ：最大可用车辆数目： c ，。：第f 辆车的固定成本； c 。( f ，。，工，) ：车辆f 的运营成本： c 。o ，。，_ ) ：车辆z 的惩罚成本； e 。：车辆，在单位时间内的运营成本； t l * nn ( i ) ：车辆f 在第 ( f ) 个用户的出发时间； 丁l 。，n ( f ) ，n ( f + 1 ) ：车辆在节点，l o ) 和节点n ( f + 1 ) 之间的平均运行时间； f 。，m “) ：用户在甩0 ) 处的装载或卸载时间： p w 。) o 柚，t ，工，) ：车辆由时刻f 邶出发经f 时间到达_ ，l ( f ) 的概率； c 川。) o ) ：顾客在一o ) 处的延误惩罚； c 。( 。) ( f ) ：顾客在n ( f ) 处的提前惩罚，其惩罚函数因顾客和业主对配送要求 的不同而选用不同的函数； 彬o ，) ：车辆f 的载货量； 睚，：车辆l 的承载能力； 州矽：在稍于段，已使用的车辆所成的集合 爿f 矽： a k ( v ) iv k e 州矽) 丫砂： n d r ) fv 七州刁 p 时：t p k k | 奇、 n p ( r ) ：在r 时段，川矽与p r 矽的联集，因两者无交集，故等于f 砂护阳。 当，辆车被利用时 当z 辆车末被利用时 ，1 ，车辆m 经由需求点f 到需求向 。1 0 ，其它 。 f 1 ，当车辆七用来服务顾客f 时； y 42 1 0 ，当车辆七不服务顾客f 时。 。f 1 ，代表使用车辆胁； 。1 0 ，未使用车辆m 。 ( 3 ) 其它变量 口，：r 时段开始计算的时刻； q ：由顾客i 至j 的旅行成本。 吐：顾客i 之需求数量： t i j ：由顾客f 至，的行驶时间； 么：至f 时段为止，第k 辆车已载运的顾客需求容量； r ：任意极大之数目； 乱：车辆k 在顾客f 处停留时间，包含顾客服务时间及车辆等候或闲置时 间，视不同线上服务策略而定。 ；物流中心与所有需求点之集合； r 所有路径之集合； m = 所有车辆之集合； qt 车辆之容量限制； 丁= 每日最大工作时数； s 发生配送失败时，不足的货物每单位之惩罚成本。 k ：车辆k 对于顾客f 的服务开始时间。 吼。需求点i 的需求量。 t 需求点f 到需求点，的旅行成本。 e i ；顾客f 的时窗开始时间。 p 。违反时窗开始限制的惩罚系数。 t = 顾客f 之时窗结束时间。 p ，= 违反时窗结束限制的惩罚系数。 抚；车辆到达顾客i 时间。 s ；= 顾客i 的服务时间。 t 。= 需求点i 到需求点j 的旅行时问。 ( 6 。) 一在时间b ，对顾客i 的处罚成本。 1 1 研究的背景与动机 第一章绪论 近年来，物流作为“第三利润的源泉”受到国内外各行业的极大重视，并得 到了较快的发展。大量经营规模较大的制造企业和商业企业纷纷建立起配送中 心，向商品流通效率化发展挑战。与此同时，相当部分的大型运输、仓储和航运 企业开始转向第三方物流经营。可以说，物流已经成为各制造企业的共同话题。 在物流热的到来的同时，电子商务在全国和世界范围内迅速增长。而电子商务的 兴起，使得传统的物流配送发生了很大的变化，它改变了人们习以为常的消费活 动内容与形式。凭借网际网络的便利性，消费者可以经过上网来完成交易的动作， 再加上电子资料交换( e d d 技术的成熟，所有相关的订货信息能够在第一时问传 递到整个供应链系统，也就是消费者可以进行实时的订货。 实时的订货信息下的物流配送与传统的物流配送发生了很大变化，实时订货 信息下配送的定单客户分散、定单金额量小而批次多、商品数量繁多、送货时间 紧迫、存储空间狭小等，而且顾客对配送的速度、质量提出了更高的要求，使得 配送程序更加复杂化。而物流配送的车辆调度问题，是配送优化中的关键一环， 也是电子商务活动不可缺少的内容。对顾客进行产品的及时配送是企业和电子商 务成功的关键，而适当的车辆调度方式是较少配送时间和配送成本的重要因素。 过去，在物流配送中，由于通讯工具缺乏，物流业者难以在第一时间准确获 得所有的订货信息，这样导致服务的时间效率差，也难已综合各项任务进行批量 配送，对许多时间要求紧迫的配送任务，多以此单项任务进行配送，特别是对一 些配送批量小而时间短的，配送成本很高。另一方面，即使物流业者能够实时的 获得所有的订货信息，但因无法与车辆联络并得知其位置与货物剩余状况，除非 加派车辆去运送，否则无法对于这份订单实时的加以处理，处理流程见图1 1 。 圈1 1传统车辆调度框架 如今，随着电子商务的迅速发展，配送中心通过网络能迅速掌握所有订货信 息，并对各项订货进行批量处理。而且物流业者也从开始加装无线电对讲机，到 现在运用全球定位系统( g p s ) 、地理信息系统( g i s ) 等先进技术作为调度中心与 车辆间沟通的渠道，已经可以实现对于车辆的掌控与实时的调度，并迅速的将货 物经由最接近的车辆加以运送。可以说，许多先进的交通工具的应用使得业者迅 速的得知所要配送的需求点位置与其需求量并立即的加阱实时配送成为可能。 但是，尽管如今通讯工具和网络的发展为物流配送提供更快捷、准时服务和 降低服务成本的可能，但硬设备只是外在的工具，许多管理理论及决策模式的应 用才是核心的部份，只有充分利用这些硬件技术所提供的决策信息，并形成有效 的决策，才能发挥完整的功能，达到预期的效果。因此，纵然大多数的物流业者 愿意花费大额资金用于采用各项先进的通讯工具，但若仍旧依循过去的车辆调度 方法，很难满足如今顾客要求。 对车辆调度方法的研究，国内李军、郭耀辉等比较系统探讨单车场、多车场、 送货与取货、有时问窗限制等条件下的车辆调度问题，见文献f lj ，戴禾等人对 旅行时间不确定下的随机车辆问题进行初步分析，见文献r 2 j ，朗茂祥等采用各 种现代优化算法对各种静态车辆调度问题的算法进行设计，见文献3 j ，孟小平 和袁庆达，周再玲分别采用遗传算法和禁忌搜索法对有时间窗的问题进行讨论见 文献f 4 j 、文献5 j ，宋沽蔚，荣冈对成品油配送中时间窗的确定及运输安排 问题进行了分析。国外如g e n d r e a u ( 1 9 9 6 ) 以顾客需求量、车辆运送时间及顾 客是否有需求这三种变量，将v r p 分成六大类讨论，并整理出表格，但并未对各 种情况下的实现进行探讨，见参考文献r 6 j 。 回顾对物流配送中车辆优化调度的研究，通常仍以固定时间及固定路线在服 务范围内做配送服务为背景下的进行研究，对于临时出现的需求导致需求量与需 求点变动的情况，往往只能依据调度人员的经验指挥车辆做反应，其决策理论与 模式多半是采取较为静态的方式，并未能充分考虑外在条件不断变化的情形，且 虽然近年利用正确解法求解静态问题的发展迅速，其运算效率却仍难以求解此类 具有实时变动特性的问题。虽然也有部分文献对需求量发生变化时车辆调度问题 进行研究，如文献7 j ，但其采用的方法是在加入的订货需求导致车辆到达需求 点后车上的货物量无法满足需求量时，车辆重新返回仓库补货并继续原有的行车 路线进行服务。面对这种情况，会使车辆配送产生许多额外的成本。另外，文献 8j 对此类采用问题的策略就是增派车辆，然而实际上对于货运配送业者来说， 其所拥有的车辆数是有限制的，不可能遇到新的需求即派遣新的车辆去进行服 务。特别是现在同城配送发展，配送种类之多，配送时间性强，如很多配送中心 涉及鲜花、礼品、门票、各种信用卡以及各种小商品等，这种情形下，传统的车 辆调度方法只能大大增加配送成本。 事实上，最有效率的调度情况还是需指派位于附近的车辆更改路径加以服 务，当发生现有车辆无法服务的情况才增派车辆。因此，本研究将尝试在实时订 货信息下，需求量与需求点不断改变时，建立一套能动态处理该情形下的模型和 求解策略。即在获得新的需求信息后，判断是否发生配送失败( 按原先配送路径 无法满足所有所有顾客需求) ，一旦配送失败，适时更改在途车辆路径，当发生 在途车辆无法服务的情况才增派车辆服务，重新构成一套车辆的调度方法，完整 的调度方法流程可见图1 2 。 其组成的单元包含订单处理、设备及人员管理、货物追踪、车辆及路线排程、 车辆运输监控与通讯接口。其中车辆及路线排程主要用以辅助调度人员产生暂时 及最后的运送行程计画，将不同货物分派给适当的车辆，并决定其运送路线。这 部份是决定整个系统绩效优劣的关键因素。 图1 2 以实时信息为基础的车辆调度构架图 目前具有实时信息下的车辆优化调度的实务性问题已有许多，例如在 p s a r a f t i s ( 1 9 9 9 ) 中就列出了下列的应用： l 、燃油或工业瓦斯配送闯题：油品公司需要安排路线补充顾客的燃料存量， 但是每个顾客的需要量事前无法得知，因此很可能油罐车到达时却无法满足顾客 的需要。 2 、快递服务( c o u r i e rs e r v i c e ) ：小厢型车巡回于都市内收取小包裹或是快递 物品，如同城纯净水的配送等，顾客实时通知调度中心提供服务，调度中心则需 要立即指派车辆，并调整其路线。 3 、同时取货与送货服务( c o m b i n e dp i c k u pa n dd e l i v e r ys e r v i c e ) ：由多辆车 形成的车队，当顾客以电话或其它通讯方式实时通知调度中心时，必须尽快派车 前往服务。调度人员必须实时决定哪部车服务某一顾客，并调整其既有路线，同 时，维持合理的服务水准并尽量使车辆运用最佳化。 4 、拨召公车( d i a l a r i d 曲与出租车共乘( s h a r e a - c a b ) 与上述类似的服务， 利用小巴士或是出租车将不同乘客依据其起讫点安排运送路线顺序。 在这些应用中，其共同的特征即为问题求解所需的信息在事前无法完全得 知。而是随着时间经过才实时出现。 综上所述，由于现实环境的车辆调度方式仍与目前理论与现实的要求有所差 异，而随着产业竞争增加及市场消费形态的演变，这种实时性的服务将变得越来 越重要，快速的响应并满足顾客的需求，成为企业获利的基础。因此，故本研究 希望能够建立一套能够随时处理实时订货需求的车辆调度优化方式，以供营运者 做参考。 1 2 研究的目的与意义 物流的配送系统中，主要由车辆厂站、仓库、营业据点与道路、铁路等运输 设施所组成，将其视为由节点与节线所构成的型态，便可转化成网络的形式。物 流配送运输也正是基于此网络的基础上进行研究的。目前，一般意义上的物流配 送运输车辆调度，指配送中心按照不同客户的多频度、小批量的订货要求进行组 织配送，其主要内容指根据确定的配送货物量分配车辆和选择优化线路，也就时 广受研究的v r p ( v e h i c l er o u t i n gp r o b l e m ) 问题。由于从事物流配送的汽车 货运工作尤其是从事城市配送的汽车货运工作条件复杂，不仅货运点多、货物种 类繁多、道路网复杂，而且运输服务地区内运输网点分布也不均匀，同时，很多 客户还对配送需求提出了对时间的要求。因此，如何应用现代数学方法及计算机 快速求解优化调度方案是国内外专家学者普遍探索的重要课题。而过去的相关研 究中，都将物流配送视为一车辆路线问题( v r p ) 。但实际上若依据基本的车辆路 线问题的定义，其实有许多处与实际状况有所出入，故后续有许多学者破除各种 假设条件或增加考虑限制因素，而提出时窗限制车辆路线问题、随机性车辆路线 问题、动态车辆路线问题等，回顾过去这些研究，并无法确实反应电子商务环境 下实时订货信息其所拥有的一些优势，并利用于物流配送上。基于这一因素，本 研究将对于过去的相关研究作改进与结合，提出电子商务环境下的实时订货信 息的车辆调度模型。并针对这一改良的车辆路线问题提出求解架构。 车辆配送路线求解问题为一复杂性颇高的问题，精确算法及启发式算法 ( h e u r i s t i ca l g o r i t h m ) 是用来求解此类问题的传统方法。采用精确算法可求得 问题最优解( o p t i m a ls o l u t i o n ) ，但其求解时间往往随着问题规模的增大而成指 数增长，当所需处理的零售商数目较多时，要花费相当多的时间来求解，因此在 实际中的应用范围很有限。启发法通常针对问题的特性将问题分成数个小问题或 模块加以简化，并以较为直观的方式来求解。启发式算法可以大大减少计算时间 及其复杂度，但所求得的结果仅为近似晟优解，与最优解的近似程度不易衡量。 近年来，遗传算法( g e n e t i c a l g o r i t h m ) 在组合优化( c o m b i n a t o r i a lc i p t i m i z a t i o n ) 问题上的求解成效显著，因其快速运算、自我组织及平行处理的特性，不仅能在 可接受的时间内求得满意的答案，在问题的扩充性方面也颇具弹性。虽然遗传算 法的全局搜索能力较强，但是它的局部搜索能力较弱。本论文结合遗传算法和局 部搜索算法二者的优点，设计出一种效率比较高的混合遗传算法，将其应用在车 辆配送路线模型中初始路线构建上，并利用禁忌搜索法对信息更新后的配送路线 进行改进。 1 3 研究范围与假设 根据本文对于电子商务发展下的物流配送所进行的探讨，实时的订货信息便 会影响到各个需求点的需求量以及可能出现新的需求点，需求量和需求点会随时 间的变动而呈现不确定性的。相较于过去传统的车辆调度问题，当这类问题中的 某些参数具有不确定，一般称之为随机性车辆调度问题，本文研究背景符合随机 性车辆调度问题，因此，本文将以随机性车辆调度问题为基础，进行模型构建和 求解。由于该类车辆路线问题牵涉到的因素相当多，为避免问题过度复杂，故本 研究做了适度的简化。本研究的主要范围与假设如下所示： 1 、对物流中心特性界定： 所考虑的配送层级仅为二层的配送层级，即区位已知的单一物流中心与发 生需求的需求点之间的调度问题，而对多层级的配送问题，可以采用本研究方法 加以类比。 本研究中仅考虑单纯车辆送货或集贷的情况。 配送中心拥有一定数量的配送车辆，且每辆车的载重量一定。 物流中心无缺货可能且对顾客的基本配送资料( 需求量、地理位置、时间 窗约束) 为已知： 2 、车辆由物流中心出发，服务被指定的需求点后，再返回物流中心。区域 内的需求点假设为固定数量且位置已知，不会变动，只是不知道何时可能有需求 信息加入。 3 、假设调度中心能够掌握所有相关信息，如车辆位置、需求点各时段的总 需求量等。 4 、各需求点内的需求量具有随机性，会因订货信息的进入而变动，故在车 辆未到达前并无法得知正确的需求量，而这些需求量和需求点变动的信息在固定 的时间间隔会更新。 j5 、无中途指派：车辆一旦由前一顾客处出发之后，其下个停靠的顾客便 已确定，无法由新的顾客取代：因为若要有中途指派，则需要有最新的车辆动态 位置，由此位置计算距离及时间，以检查时窗限制，且须配合中途转派策略，将 使得问题过于复杂。 6 、假设没有交通变异因素，所以顾客之间的距离与旅行时间为确定值，因 此，车辆位置依据所服务顾客的顺序而移动，不考虑受阻误点或是半途故障。 1 4 本论文的主要工作与技术路线 为了达到上述研究目的，探讨一个能够反映电子商务环境下实时订货信息配 送的车辆调度优化方法，由于网际网络与电子商务兴起后，大幅强化各项信息的 流通，使得各类实时的信息能够较以往容易取得。故我们首先必须对于电子商务 出现后，对于物流业者所造成的变化进行探讨，并收集了国内外学者专家对车辆 路径和行程安排问题的相关研究，对文献资料进行了整理、分类，作为数学模型 建立的理论基础。结合二者提出了电子商务环境下实时订货信息的车辆调度优化 的数学模型，并对模型进行求解。在求解方法上，本文采取全局搜索能力较强的 遗传算法和局部快速收敛的启发式算法相结合的混合遗传算法，最后用c 语言 进行程序设计，实现本文提出的算法，并以一个算例分析比较该算法的性能。 本文结构如下： 第一章阐述本文的研究背景与动机、研究的意义和目的，提出研究范围和假 设； 第二章中，由于本文论述的车辆调度条件与电子商务的发展密不可分，因此 在第二章中论述了电子商务条件下的配送特性，以及其与传统配送方式的一些差 异。 第三章阐述国内外车辆优化调度问题上研究，特别是对随机性车辆调度问 题，探讨在该方面的研究，本分析目前在求解车辆优化调度问题的主要方法。 第四章根据本文限定的条件，参考历史的车辆调度模型，构建符合本文界定 的优化调度模型。 第五章针对这一模型，提出求解方法。并将问题分为两部分：一部分以混合 遗传算法构建初始路线，二部分以禁忌搜索法在时间更新时进行线路改善。 第六章以y c c 公司为例，对本文的算法进行测试，并对算法性能分析。 第七章对本论文进行总结，并提出下一步研究方向。 本文研究框架如图1 3 所示： 问题定义 j 文献回顾 卫 l毒士 l i 的物流配送特性p _ l 相关研究广。r i 求解相关方法l l ii il 量 模型构建 h。 。 。 一案例测试i 求解方法设计 u i 结论与建议 l 1 5 本章小结 图1 3 本文研究框架图 本章论述了本文研究的背景，即在电子商务与物流配送快速发展的同时，顾 客对物流配送服务质量要求越来越严格，实时的订货信息下配送中心或企业实时 对顾客进行配送，是企业成功的关键，而先进交通工具的应用使得实时配送成为 可能。并对比传统的配送方式与实时订货信息下配送方式比较，充分论述了本文 研究的目的与意义。由于车辆调度问题的复杂性，本章对文章研究的范围进行了 界定，以明确本文研究的各种条件，最后论述了本文的主要工作与技术路线。 第二章实时订货信息下的物流配送分析 2 1 实时订货信息下物流配送 2 1 1 物流配送的界定 物流配送指的是：在经济合理区域范围内，根据用户的要求，对物品进行拣 选、加工、包装、分割、组配等作业，并按时送达指定地点的物流活动。一般来 说，配送一定是根据用户的要求，在物流据点内进行分拣、配货等等工作，并将 配好的货物适时送交收货人的过程。它是物流中的一种特殊的、综合的活动形式。 它将商流与物流紧密结合。配送业务在美国、日本等国家开展比较旱，近几年来， 在我国也有较快的发展。目前配送已经形成了自身的特点： 1 、配送是从物流据点到用户之间的一种特殊送货形式。 2 、配送是连接了物流其他功能的物流环节，提高了物流系统的价值增值部分。 3 、配送是复杂的作业体系，通常伴随着较高的作业成本，但却能大大降低库 存成本和快速反应商品市场需求变化。 4 、配送在固定设施、搬运设备、运送工具、组织形式、通信信息等方面可集 成系统化的运作体系。 2 1 2 实时订货信息与电子商务 实时( r e a l - - t i m e ) 是指处理信号的过程是在实际发生事件过程的期间进行。 它是在信号发生时立即处理，作为实时系统，它能在某个持续的过程( 包含连续 的和离散的) 中，对应于系统的一组特定的输入值，在它们未发生有意义的变化 时，就作出恰当的反应。电子商务是实现实时订货信息的手段，离开电子商务， 实时的订货信息将成为一纸空文。通过电子商务，顾客可以上网随时查阅商品信 息并进行订货，向销售商或配送中心发出需求信息，同时销售商或配送中心实时 接收信息，并根据顾客要求进行配送。而且顾客可以通过网上安全的支付手段进 行在线支付费用，并对货物配送进行实时跟踪查询等。实时的订货信息的实现离 不开电子商务，因此，下面将进一步论述电子商务与物流配送关系，以期论述实 时订货信息下的配送特性。 2 1 3 电子商务与物流配送 物流配送经历了和正在经历三次革命：初期阶段就是送物上门，即为了改善 经营效率，国内许多商家较为广泛地采用了把货送到买主手中的方式，这是商务 的第一次革命：第二次物流革命是伴随着电子商务的出现而产生的，这是一次脱 胎换骨的变化，不仅影响到物流配送本身，也影响到上下游的各体系，包括供应商 和消费者；第三次物流革命就是物流配送的信息化及网络技术的广泛应用所带来 的种种影响，这些影晌是有益的，将使物流配送更有效率。以计算机网络为基础的 电子商务催化着传统物流配送的革命，反过来，物流对电子商务的发展也起着至 关重要的作用。 首先，物流是电予商务的重要一部分。电子商务的概念模型( 见图2 1 ) 是 对现实世界中电子商务活动的一般抽象描述，包括电子商务主体、电子市场、交 易事务和信息流、商流、资金流、物流等基本要素构成。任何一笔电子商务交易， 都包含着此“四流”，其中物流是其至关重要的一环。 其次，物流也是实现电子商务的保证，是实现电子商务的关键。没有现代物 流，任何轻松的商流活动只会是一纸空文。在电子商务下，消费者通过上网点击 购物，完成商品所有权的交割过程，即商流过程，但电子商务活动并未结束，只 有通过物流，将商品真正转移到消费者手中，商务活动才告终结。 图2 1 电子商务概念模型 2 1 4 实时订货信息下物流配送业务流程 实时订货信息下配送中心的一般业务流程比传统的配送流程有所区别，其流 程如图所示，其基本内容包括四个方面： 一是进货作业，主要包括订单处理作业、采购作业、进货入库作业。配送中 心的交易始于客户的讯价、业务部门的报价，然后由订单的接受、业务部门需查 询出货日的库存状况、装卸能力、包装能力、配送负荷等来满足客户的需求。 接受订单后，配送中心需向供货商或制造商订购商品，即为采购作业。开出采购 单后，进货入库管理员即可根据采购单上预定的入库日期进行入库作业调度。当 采购的产品入库时，进行入库信息查核、入库质检；当数量或质量不符时，即进 行适当修正或处理，并输入入库数据，即为入库作业。 二是库存作业。包括仓库区管理、库存控制以及补货及拣货作业。仓库区管 理指的是库区规划、产品进出库方式控制、仓储区货位的调整及交动：库存控制 则需要按产品出库数量、入库所需要的时间等来制定采购数量及采购时间，并建 立采购时间的预警系统。通过统计客户订单即可知道产品真正的需求量。在出库 日，当库存满足出货需求量时，即可根据需求量打印出库拣货单，进行拣货区域 规划。同时还需及时制定补货时点，进行补货作业调度。 三是出货作业。包括制定出货调度、决定集货方式、选用集货r 具、调派集 货人员，并决定运输车辆的大小与数量以及配送作业。即按照配送区域的划分或 配送路线安排送货，并在产品配送途中进行信息跟踪与控制以及配送途中以外状 况处理。 四是会计作业与各项管理及业绩管理作业等。 其作业流程如图2 2 ： 图2 2 实时订货信息下的物流配送中心作业流程图 2 2 实时订货信息下的物流配送特性分析 2 2 1 实时订货信息下物流配送特点 实时订货信息下的物流配送特点可总结为以下几方面： 1 、信息化。物流信息化是实时订货信息的必然要求。物流信息化表现为物 流信息的商品化、物流信息收集的数据库化和代码化、物流信息处理的电子化和 计算机化、物流信息传递的标准化和实时化、物流信息存储的数字化等。因此， 条码技术( b a rc o d e ) 、数据库技术( d a t a b a s e ) 、电子定货系统( e o s ：e l e c t r o n i c o r d e d n g $ y s t e m ) 、电子数据交换( e d i ：e e c t r o n i cd a t ai n t e r c h a n g e ) 、快速反 应( q r ：q u i c kr e s p o n s e l 及有效的客户反映( e c r ：e f f e c t i v ec u s t o m e r r e s p o n s e ) 、企业资源计划( e r p ：e n t e r p r i s er e s o u r c ep l a n n i n g ) 等先进技术与 管理策略在我国的物流中将会得到普遍的应用。 2 、自动化。自动化的基础是信息化，自动化的核心是机电一体化，自动化 的外在表现是无人化，自动化的效果是省力化，另外还可以扩大物流作业能力、 提高劳动生产力、减少物流作业的差错等。物流自动化的设施非常多，如条码 语音，射频自动识别系统、自动分拣系统、自动存取系统、自动导向车、货物自 动跟踪系统等。这些设施在发达国家已普遍用于物流作业流程中，而在我国由于 物流业起步晚，发展水平低，自动化技术的普及还需要相当长的时间。 3 、网络化。物流领域的网络化有两层含义：一是物流配送系统的计算机通 信网络，包括物流配送中心与供应商或制造商的联系要通过计算机网络，另外与 下游顾客之间的联系也要通过计算机网络通信，比如物流配送中心向供应商提出 定单这个过程，就可以使用计算机通信方式，借助于增值网( v a n ：v a l u e a d d e dn e t w o r k ) 上的电子定货系统( e o s ) 和电子数据交换技术( e d i ) 来自 动实现，物流配送中心通过计算机网络收集下游客户的定货的过程也可以自动完 成；二是组织的网络化，即所谓的组织内部网( i n t r a n e t ) 。比如，台湾的电脑业 在2 0 世纪9 0 年代创造出了“全球运筹式产销模式”，这种模式基本是按照客户 定单组织生产，生产采取分散形式，即将全世界的电脑资源都利用起来，采取外 包的形式将一台电脑的所有零部件、元器件、芯片外包给世界各地的制造商去生 产，然后通过全球的物流网络将这些零部件、元器件和芯片发往同一个物流配送 中心进行组装，由该物流配送中心将组装的电脑迅速发给订户。可见，物流的网 络化成为电子商务下物流活动的主要特征。 物流的网络化是物流信息化的必然，是实时订货信息下物流活动的主要特征 之一。当今世界i n t e r n e t 等全球网络资源的可用性及网络技术的普及为物流的 网络化提供了良好的外部环境，物流网络化不可阻挡。 4 、智能化。这是物流自动化、信息化的一种高层次应用，物流作业过程大 量的运筹和决策，如库存水平的确定、运输( 搬运) 路径的选择、自动导向车的 运行轨迹和作业控制、自动分拣机的运行、物流配送中心经营管理的决策支持等 问题都需要借助于大量的知识才能解决。在物流自动化的进程中，物流智能化是 不可回避的技术难题。好在专家系统、机器人等相关技术在国际上已经有比较成 熟的研究成果。为了提高物流现代化的水平，物流的智能化已成为电子商务下物 流发展的一个新趋势。 5 、柔性化。柔性化本来是为实现”以顾客为中心”理念而在生产领域提出的， 但要真正做到柔性化，即真正地能根据消费者需求的变化来灵活调节生产工艺， 没有配套的柔性化的物流系统是不可能达到目的的。2 0 世纪9 0 年代，国际生产 领域纷纷推出弹性制造系统( f m s ：f l e x i b l em a n u f a c t u r i n gs y s t e m ) 、计算机 集成制造系统( c i m s ：c o m p u t e ri n t e g r a t e dm a n u f a c t u r i n gs y s t e m ) 、制造资源 系统( m r p i i ：m a n u f a c t u r i n gr e q u i r e m e n tp l a n n i n g ) 、企业资源计划( e r p ： e n t e r p r i s er e