（企业管理专业论文）B2C电子商务企业物流模式及车辆调度研究.pdf

n o r t h e a s t e r nu n i v e r s i t y j u l y2 0 0 8 j 卜气 i ： 毫。，； 独创性声明 本人声明，所呈交的学位论文是在导师的指导下完成的。论文中 取得的研究成果除加以标注和致谢的地方外，不包含其他人己经发表 或撰写过的研究成果，也不包括本人为获得其他学位而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均己在论文中作了明确 的说明并表示谢意。 学位论文作者签名：弘石磊 日 期：z 一8 7 巧 学位论文版权使用授权书 本学位论文作者和指导教师完全了解东北大学有关保留、使用学 位论文的规定：即学校有权保留并向国家有关部门或机构送交论文的 复印件和磁盘，允许论文被查阅和借阅。本人同意东北大学可以将学 位论文的全部或部分内容编入有关数据库进行检索、交流。 作者和导师同意网上交流的时间为作者获得学位后： 半年口一年1 7一年半两年口 学位论文作者签名：降石磊 签字日期：少1 6 7 。f 5 ， j 导师签名：枷噬 签字日期：w 曾7 ，厂 ， ， 一 一 - 、。 l 东北大学硕士学位论文摘要 b 2 c 电子商务企业物流模式及车辆调度研究 摘要 新世纪，因特网的应用所爆发出的能量以几何级的速度影响到了人类社会的 各个方面，全球经济将以全新的模式飞速发展，以电子商务为核心的经营理念使 整个社会的经济结构、经营模式发生了前所未有的变化。 电子商务的实现过程中需要对信息流、资金流、商流和物流进行整合运作。 随着信息技术的不断发展，前三种“流”已经能用计算机和通信网络瞬间实现， 而必须在网下实现的物流成了电子商务最耗时的部分，电子商务的快捷与否就取 决于物流的效率。对涉足电子商务的制造商、零售商、门户网站和物流公司而言， 首要的问题是解决物流模式的问题，在不同的环境下，需要根据具体的情况进行 物流决策，组建最适合企业自身的物流模式。 结合发达国家的经验、中国的国情以及物流配送的特征，探讨了涉及电子商 务的企业主体如何选择适合自己的物流模式这一问题。本文采取理论结合实践、 定性结合定量的方法，通过实例对自营物流、第三方物流进行了详细的论述，并 提出论证了物流联盟模式和物流一体化模式。同时，考虑到电子商务终端配送的 重要性( 最后一公里) ，本文探讨了企业物流模式中的带有多时间窗的车辆调度问 题，创新性提出了在多时间窗条件下车辆调度的优化模型，并引入启发式算法对 模型进行求解。 本论文主要完成了以下三方面的工作： 第一，根据b 2 c 电子商务企业物流配送的特征，结合发达国家物流配送的发 展经验和国内一些典型b 2 c 电子商务企业物流配送的发展现状，系统总结了当前 主流的几种电子商务物流模式，详细介绍了企业自营物流、第三方物流、物流联 盟模式的利弊及适用性，并提供了基于物流战略地位的物流模式选择方法。 第二，讨论了物流模式选择中遇到的共同难题运输车辆的调度问题。阐 述了物流配送对提高b 2 c 电子商务市场竞争力的重要性，提出了优化带有多时间 窗的物流配送车辆运输调度问题的数学模型。 第三，采用启发插值混合算法来求解理想状态下( 即只考虑车辆装载容 量限制和总运行距离或时间的约束) 带有多时间窗的车辆运输调度优化问题，并 通过算例证明该方法具有极强的有效性。对提高物流企业的配送效率，节约物流 配送成本具有较高的指导意义。 关键词：b 2 c 电子商务；物流模式；多时间窗；v r p ；启发式算法 一i i l r e s e a r c ho nt h el o g i s t i c sm o d e lo f b 2 c e c o m m e r c ee n t e r p r i s ea n dv e h i c l es c h e d u l i n g s t r a t e g y a bs t r a c t i nn e wc e n t u r y , t h ea p p l i c a t i o no fe - c o m m e r c ea f f e c tt h ee v e r yi n c ho fo u rs o c i e t y t h eg l o b a le c o n o m yw i l ld e v e l o pa tf u l ls p e e dw i t han e wm o d e l t h e n e wm a n a g e m e n t c o n c e p t i o nt a k i n ge - c o m m e r c ea st h ec o r ew i l lr e g e n e r a t et h ee c o n o m i c a ls t m c t l l r ea n d t h eb u s i n e s sm a n a g e m e n tm o d e l r e a l i z a t i o nc o u r s eo fe - c o m m e r c es h o u l di n t e g r a t ef o u rf l o w s ：i n f o r m a t i o n ，f u n d ， t r a d ea n dl o g i s t i c s w i t ht h eh e l p o fd i g i t a la n dc o m m u n i c a t i o n a lt e c h n o l o g y , e c o m m e r c ec a l li n t e g r a t et h ep r e v i o u st h r e ef l o w s ，b u tc a n ts o l v et h el o g i s t i c sp r o b l e m f o rt h ec o m p a n yw h i c hs e t t i n gf o o ti nt h ee - c o l n e n e r c e ，t h ep r i m a r yp r o b l e mi sm a k i n g t h ed g c i s i o no fl o g i s t i c sm o d e l 。u n d e rd i f f e r e n te n v i r o n m e n t , t h ec o m p a n y m u s tc h o o s e t h ed i f f e r e n tl o g i s t i c sm o d e l t h i st h e s i s ，t h r o u g hd e e p l yr e s e a r c ho nt h ee - c o m m e r c el o g i s t i c ss i t u a t i o no f n a t i o n a la n dn o n n a t i o n a l ，p r o b i n gi n t oh o wt oc h o o s et h es u i t a b l em o d e li nc h i n a t h e p a p e ru s et w om e t h o d st oa n a l y z et h ep r o b l e m ：t h e o r yc o m b i n e sp r a c t i c e ；q u a l i t a t i v e a n a l y s i s c o m b i n e sq u a n t i t a t i v ea n a l y s i s t h ea u t h o rg i v et h ed e t a i l e da n a l y s e so n s e l f - b u i l dl o g i s t i c sa n dt h i r dp a r t yl o g i s t i c s ，a n dp u tf o r w a r dan e wm o d e l ( 1 0 9 i s t i c s a l l i a n c e ) o nt h eb a s i so fi m p r o v i n gt h ep a s tl o g i s t i c se v a l u a t i o nc r i t e r i o n ，t h i sp a p e r d i s c u s s e dv e h i c l e ss c h e d u l i n gp r o b l e mw i t ht i m ew i n d o w si nt h ee n t e r p r i s el o g i s t i c s m o d e l ，a n de m p h a t i c a l l yp r o p o s e dt h eo p t i m i z e dm o d e lo f v e h i c l ed i s p a t c h i n gp r o b l e m ， a n di n t r o d u c e dt h eh e u r i s t i ca l g o r i t h mt os o l v et h eo p t i m i z e dm o d e l t h et h e s i sf o c u s e so nt h ef o l l o w i n ga s p e c t s ： f i r s t l y , a c c o r d i n gt ol o g i s t i c sa l l o c a t i o n s f ea _ 嘶o fb 2 ce - c o m m e r c ee n t e r p r i s e ， l o g i s t i c sa l l o c a t i o n se x p e r i e n c eo ft h ed e v e l o p e dc o u n t r ya n dl o g i s t i c s a l l o c a t i o n s d e v e l o p m e n ts i t u a t i o n o fs o m ed o m e s t i cb 2 ce - c o l r m e r c ee n t e r p r i s e s ，t h et h e s i s s 1 】m m a r i z e ss e v e r a lc u r r e n tm a i l l s t r e a me - c o m m e r c el o g i s t i c sm o d e l ，i n t r o d u c e st h e s e l f - b u i l dl o g i s t i c s ，t h et h i r dp a r t yl o g i s t i c s ，t h el o g i s t i c sa l l i a n c em o d e l sa d v a n t a g e s a n ds e r v i c e a b i l i t yi nd e t a i l ，a n dh a v ep r o v i d e ds e l e c t i o nm e t h o do fl o g i s t i c sm o d e l b a s e do nt h el o g i s t i c ss t r a t e g i cp o s i t i o n s e c o n d l y , t h et h e s i sd i s c u s s e st h ec o m l t l o nd i f f i c u l t yi nt h es e l e c t i o no fl o g i s t i e s 一i 一 东北大学硕士学位论文 a b s t r a c t m o d e l v e h i c l e s s c h e d u l i n gp r o b l e m ，e l a b o r a t e st h ei m p o r t a n c eo fl o g i s t i c sa l l o c a t i o n t oe n h a n c et h eb 2 ce - c o m n l c t c c e n t e r p r i s e sm a r k e t c o m p e t i t i v e n e s s ，p r o p o s e s m a t h e m a t i c a lm o d e lt oo p t i m i z e p t wo f l o g i s t i c sd i s t r i b u t i o n t h i r d l y , t h et h e s i s u s e s h e u r i s t i c - i n t e r p o l a t i o nm i x e da l g o r i t h mt oo p t i m i z e v r p t wu n d e rt h ep e r f e c tc o n d i t i o n ( i e j u s tc o n s i d e r r i n gv e h i c l e s sc a p a c i t ya n dt o t a l m o v i n gd i s t a n c e ) ，a n dp r o v e st h eg r e a tv a l i d i t yo ft h em e t h o dt h r o u g ht h ee x a m p l e i ti s 一 - 、- 0 东北大学硕士学位论文 目录 目录 独创性声明i 摘要 a b s t r a c t i 第1 章绪论1 1 1 研究背景1 1 2 研究的目的和意义1 1 3 研究方法。2 1 4 研究的主要内容和创新点2 1 4 1 主要内容3 1 4 2 创新点。3 第2 章b 2 c 电子商务物流概述5 2 1 相关基础理论及背景5 2 2 电子商务物流概念的界定6 2 3b 2 c 电子商务背后的实物配送7 2 4b 2 c 电子商务物流配送特征7 2 4 1 配送客户的特殊性7 2 4 2 配送商品的特殊性。8 2 4 3 配送质量和成本的特殊性8 2 4 4 配送供应链系统的特殊性8 2 5 电子商务对物流配送的要求。1 0 第3 章b 2 c 电子商务物流的发展现状及问题1 1 3 1 国外b 2 c 电子商务物流发展阶段和特点1 1 3 1 1 发达国家b 2 c 电子商务物流发展阶段1 1 3 1 2 发达国家b 2 c 电子商务物流发展特点1 3 3 1 3 发达国家b 2 c 电子商务物流发展趋势 3 2 国内企业电子商务物流发展现状1 9 3 2 1 国内电子商务物流企业分类1 9 3 2 2 国内b 2 c 电子商务企业物流配送流程2 1 3 2 3 国内企业的电子商务物流运营效果2 2 目录 第4 章b 2 c 电子商务企业物流模式选择2 5 4 1 企业自营物流模式2 5 4 1 1 企业自营物流的利弊2 5 4 1 2 企业自营模式案例。2 6 4 2 第三方物流模式2 7 4 2 1 第三方物流模式的利弊2 8 4 2 2 第三方物流模式的选择。2 8 4 2 3 企业第三方物流案例2 9 4 3 组建物流动态联盟。3 0 4 3 1 物流联盟模式的利弊。3 1 4 3 2 物流联盟模式的选择3 1 4 3 3 物流联盟模式成功案例3 2 4 4 物流一体化模式。3 2 4 5 电子商务物流模式的综合比较3 3 4 6 基于物流战略地位的物流模式选择3 3 4 7 电子商务物流模式决策案例分析3 6 4 7 1 梅林正广和概况。3 6 4 7 2 定性的物流决策方法- 3 8 第5 章b 2 c 电子商务中带有多时间窗的车辆调度问题模型4 1 5 1 相关基础理论及背景。4 1 5 2 物流配送车辆调度问题的提出4 2 5 2 1 问题的提出4 2 5 2 2 车辆调度问题在配送运输中的应用。4 2 5 3 物流配送问题的数学描述4 4 5 3 1 物流配送车辆调度问题的分级求解 5 3 2 对时间窗的界定4 6 5 3 3b 2 c 电子商务环境下时间窗的现实涵义4 7 5 4 物流配送( 有时间窗约束) 问题的数学模型4 7 5 4 1 物流配送( 有时间窗约束) 问题描述4 8 5 4 2 物流配送车辆调度( 有时间窗约束) 数学建模4 8 第6 章车辆调度模型的启发式算法及其算例5 1 东北大学硕士学位论文目录 6 1v r p 的一般算法5 1 6 1 1 遗传算法5 1 6 1 2 人工神经网络5 2 6 1 3 禁忌搜索算法5 3 6 2 启发式算法的引入5 4 6 2 1 算法的基本原理5 5 6 2 2 算法的构成和实现5 6 6 3 理想状态下车辆调度启发式算法。5 6 6 3 1 算法原理5 6 6 3 2 求解步骤。5 7 6 4 算例计算5 8 6 4 1 启发式插值算法5 8 6 4 2l i n g o 计算软件6 2 6 5 总结与分析6 3 第7 章结束语6 5 7 1 研究成果及结论。6 5 7 2 展望6 5 参考文献6 7 附录a 7 1 附录b 7 7 致谢。8 1 攻读硕士学位期间发表论文情况8 3 东北大学硕士学位论文第1 章绪论 1 章绪论 1 1 研究背景 随着电子商务的迅猛发展，物流在电子商务发展中所起的作用越来越大。现 代物流强调采用先进的组织方式和管理技术，是企业降低生产经营成本，提高产 品竞争力的重要手段。b 2 c 电子商务是最有利于最终客户服务的一种商务模式， 它直接为最终客户提供商品，免除了中间环节，降低了经营成本，可以使最终客 户享受价格实惠；可以在网上面对面地同最终客户直接交流，详细了解他们的需 求，为他们“在需要的时候，按需要的量，提供需要的产品扫1 1 j 。 得宜于物流高度的信息化和电子化，美国的电子商务企业迅速跨越了概念炒 作阶段，b 2 c 电子商务企业亚马逊等标志性企业开始盈利；沃尔玛连锁集团 也借助自己强大的物流能力，进军b 2 c 电子商务市场。这些电子商务企业解决物 流的模式和方法尽管各不相同，但有一个共同的特点，他们都有一个高度信息化 和电子化的物流系统。 b 2 c 电子商务在中国出现只有短短几年时间，但发展十分迅速。物流系统作 为b 2 c 电子商务的重要组成部分，极大地影响着现代企业的长足发展。现代物流 业的发展水平，一定程度上反映了一个国家的综合国力和企业的市场竞争力。虽 然和西方发达国家相比，我国的现代物流业发展相对滞后，但市场空间巨大。中 国企业的领导者已经意识到发展物流业的重要性和电子商务环境下物流“瓶颈 对企业的巨大影响。b 2 c 电子商务的发展和物流的发展并不是各自独立的两个问 题，相互之间有着密不可分的联系。虽说电子商务将成为企业决胜未来市场的重 要工具，但如果没有现代物流体系作为电子商务的支点，电子商务的发展也无从 合进行研 电子商务 其深层次 出了解决 配送环节 下的车辆 东北大学硕士学位论文第1 章绪论 调度问题，并引入了启发式插值算法求解。 本文通过研究解决以下几个方面的问题： ( 1 ) 为解决我国b 2 c 电子商务配送问题提供理论依据 本文将分析物流配送如何满足b 2 c 电子商务交易的客户需求，包括客户服务 的质量与成本、人性化服务需求及配送供应链管理需求，从而为解决b 2 c 电子商 务配送问题提供理论依据。 ( 2 ) 提出b 2 c 电子商务物流模式选择的方法 本文通过分析当前我国b 2 c 电子商务配送存在的主要问题及其原因，提出有 针对性的选择方法，并通过案例分析，对方法在实际中的应用进行可行性论证。 ( 3 ) 从定量的角度分析b 2 c 电子商务物流配送的效率和成本 本文在总结国内外先进物流模式的基础上，提出了几种适用不同b 2 c 企业的 物流模式，探讨了各种物流模式的特点和局限性，就其在实践中取得的成效进行 总结，并进一步从定量角度讨论车辆在进行物流配送时的效率与成本因素，对实 践中的管理有较强的参考作用。 1 3 研究方法 ( 1 ) 系统分析方法 系统方法是用系统的观点来研究和处理有关对象的整体联系的科学方法。系 统科学方法要求从事物的整体、相互联系、有序等方面把握事物。电子商务物流 存在成本和效率的二律背反问题，因此需要用系统的思想去分析，这一思想贯穿 全文。 ( 2 ) 案例分析方法 案例研究对于电子商务物流模式选择研究是常用的方法。本文以海尔集团和 中外运空运公司为例，从企业自身发展的角度，运用战略分析的方法，验证了海 尔物流和选择自营物流的正确性，为电子商务企业在不同阶段选择不同物流模式 提供了方法和借鉴。 ( 3 ) 定性分析和定量分析相结合的方法 在如何选择电子商务物流组建模式时，本文运用定性的方法分析：战略决策； 在进一步讨论物流模式中车辆配送问题时，引入了定量的分析方法：启发式算法。 1 4 研究的主要内容和创新点 2 、 一 东北大学硕士学位论文 第1 章绪论 1 4 1 主要内容 本文研究的主要内容如下： 第1 章，绪论。阐述b 2 c 电子商务配送问题的研究背景，本文研究目的与意 义，研究方法，主要内容和本文创新点。 第2 章，b 2 c 电子商务物流概述。介绍了电子商务物流的概念，b 2 c 电子商 务物流配送的特征以及电子商务对物流配送的要求，寻找电子商务和物流概念的 切合点。 第3 章，b 2 c 电子商务物流运营现状及问题分析。 第4 章，比较分析b 2 c 电子商务环境下几种物流模式。对b 2 c 电子商务环境 下的企业自营、物流联盟、第三方物流等模式进行分析比较，总结出每种模式的 优缺点；通过分析各种物流模式的成功企业案例，对每种模式的适用性和有效性 有较全面和深入的研究。 第5 章，b 2 c 电子商务中带有多时间窗的车辆调度问题的建模。从定量的角 度分析b 2 c 电子商务企业物流模式的效率，寻找一种多时间窗约束条件下的配送 线路优化方法，指导b 2 c 企业改进物流模式。 第6 章，引入启发式算法并求解实例。 第7 章，结束语。 1 4 2 创新点 本文的创新点主要表现在两个方面：( 1 ) 对b 2 c 电子商务企业的物流运营模 式进行了系统的概括和总结，为不同类型的电子商务企业选择合适的物流模式提 供了理论依据。( 2 ) 针对b 2 c 电子商务中物流终端配送( 最后一公里) 的特点， 提出了带有多时间窗的车辆调度模型，进一步提出了针对该模型的的启发式算法， 并利用算例和计算软件验证了启发式算法的可行性和有效性。 3 一 东北大学硕士学位论文第2 章b 2 c 电子商务物流概述 第2 章b 2 c 电子商务物流概述 2 1 相关基础理论及背景 国外物流专家和电子商务专家对电子商务配送进行了大量研究。主要研究对 象为电子商务物流配送作用、模式、供应链系统及配送质量。 对于电子商务物流配送作用，美国学者h a u ll e e ，s e u n g i nw h a n g 在( w i n n i n g t h el a s tm i l eo fe c o m m e n c e ) ) 【2 l 一文中指出：“物流配送能实现网上交易商品的末 端配送，是完成整个电子商务活动的最后一个环节玢。配送专家詹姆斯阿尔里德 在其专著无声的革命【3 l 中写道：“主要通过提供物流配送打竞争战的时代已经 悄悄来临。看清这点的企业和管理人员才是未来竞争激流中的弄潮儿，否则，一 个企业将可能在新的物流配送环境下苦苦挣扎，甚至被淘汰出局。日本物流专家 汤浅和夫在其著作 卸货点，组织适当的 行车线路，使车辆有序的通过它们，在满足一定的约束条件( 如货物需求量、发 送量、交发货时间、车辆容量限制、行使里程限制、时间限制等) 下，达到一定 的目标( 如路程最短、费用最少、时间尽量少、使用车辆数尽量少等) 。它包括两 部分内容，其一是车辆行车路线的安排，其二是出行时间表安排。一个车辆路线 4 2 东北大学硕士学位论文第5 章b 2 c 电子商务中带有多时间窗的车辆调度问题研究 就是一辆车辆对应一系列需求点，从一个资源点出发，有序地通过它们，最后再 回到出发的资源点。一个车辆的时间表就是对应一系列需求点的到达和离开的时 间表。车辆必须按一定的次序在规定的时间通过这些点1 4 9 1 。 如果到达节点的时间是事先规定的，则称该问题是带时间窗要求的问题；若 到达和离开时间没有规定，则称该问题就是一个直接的路线安排问题。 由于运输任务的性质和特点不同、道路条件及车辆类型不同，即使在相同收 发货运点间完成同样任务时，所采用的行驶路线方案也可能不同。而车辆按不同 运行路线完成同样的运输工作时，其利用效果是不一样的。因此，在满足货运任 务要求前提下，如何选择最经济的运行路线，是车辆路线安排的一项重要工作。 所谓最经济的运行路线，就是在保证货物需求的前提下，运输时间和运输费用( 通 常为吨公里) 最省的路线。 5 2 2 2 车辆调度问题在b 2 c 中现实作用 考虑这样一类问题：假定有一配送中心，需向几个顾客运送货物，每个用户 对货物有一定需求，运送货物的车辆在配送中心配装发车后，把货物送到各用户 处，如何确定费用最小的车辆行使路线? 又如，零售商将若干生产商生产的产品 运到其配送中心，车辆从配送中心出发，到各个厂家去装货，装满后运到配送中 心。在满足厂家发货要求的情况下，按什么路线行使，可使总费用最小? 这两个 问题的实质是相同的，如果货物量大，车辆为完成任务需满载运行，则车辆按最 短路径行使即可。若货物量较少，若用一辆车完成任务时，车辆不能满载，这样， 车辆的利用率较低，因此可考虑用一辆车完成多项任务。这种将各分散用户组织 起来，联合送货的方式就是配送运输的基本特点。 随着传统批发、交通运输、仓储业向现代物流转化，尤其是配送方式的采用， 对运输成本和时间的有效控制日渐成为物流配送车辆调度的一项重要目标。v r p 问题一直以来都是车辆调度所重点研究的方向。而配送方式恰恰具备了v r p 问题 的一般特征和优化调度条件。图5 1 和图5 2 分别显示了传统运输方式和配送运输 方式下车辆行驶路线的对比。可见，配送通过将多个用户联合在一条路线上，并 为车辆选择优化的绕行次序，可以很好的实现降低成本、提高效率的要求。 研究物流配送下的问题一般先作以下几点前提条件： ( 1 ) 被配送的是可混装的物资； ( 2 ) 各个用户的所在地和需求均已知； ( 3 ) 从配送中心到各个用户间的运输距离已知； 4 3 东北大学硕士学位论文第5 章b 2 c 电子商务中带有多时间窗的车辆调度问题研究 膨 图5 2 巡回配送图 f i g5 1t h ec h a r to fd e l i v e r i n gg o o d s f i g 5 2t h ec h a r to fc i r c u l a t i o gd i s t r i b u t i o n o f o n en o d e ( 4 ) 配送中心有足够的资源以供配送，并且拥有足够的运输能力。 配送的目标是使总的运输费用最小，在一般情况下，是使总运输吨公里数最 小。配送计划中的最优派车路线，必须符合下列基本约束条件： ( 1 ) 必须满足所有用户的品种、数量需求； ( 2 ) 对每辆发送车辆的装载量有一定限制，不允许超载运行； ( 3 ) 对发送车辆每天的总运行时间或总运行距离有预定的上限； ( 4 ) 必须满足用户提出的到货时间要求。 对某一具体问题，上述约束条件可能全部存在，也可能只存在一部分。配送 优化方案应明确地规定在符合上述约束条件的基础上应派出的车辆数、车型和各 车辆的具体行车路线和抵达时间。实施这一运输方案，保证按时、按量完成当日 的运输任务，又必须使总运输吨公里最小。 5 3 物流配送问题的数学描述 5 3 1 物流配送车辆调度问题的分级求解 由于配送运输业务类型的多样性和复杂程度的不同，我们对实际应用中的车 辆调度问题按照复杂程度进行分级，在每种情况下，我们一方面描绘出某些约束， 然后把这些约束再加进先前讨论过的问题中，以使它更复杂和更现实。 为方便讨论，我们称某个地区内的工厂、配送中心、仓库等装货点称为资源 点或发点，它们要把不同的货物发送到该地区另外一些卸货点，称之为需求点或 收点。 4 4 东北大学硕士学位论文第5 章b 2 c 电子商务申带有多时间窗的车辆调度问题研究 车辆调度问题按照复杂程度分为： ( 1 ) 简单的路线优化问题( a 级问题) 首先，我们描述这样一个简单运输问题。在一个资源点( o n ec e n t r a ld e p o t ) p 上有一台容量为口的货车，现有m 个需求点的货运任务需要完成，已知需求点f 的 货运量为g i ( f 一1 ，2 ，m ) ，且罗g ，gq ，求在满足各收点需求约束条件下，总发送 距离最短的货车送货路线。事实上，这个问题可以归结为m + 1 个点的旅行商问题 ( t s p ) 。它的解是，从p 点出发，对所有的用户巡回一次再回到p 点的距离最短 的路线。所谓旅行商问题是，假定有一个推销员，要到儿个城市巡游，当各个城市 间的距离已知，并规定每个城市只访问一次，请问按怎样的顺序巡游，其距离最 短【铝1 。 ( 2 ) 理想状态下的配送问题( b 级问题) 对以上的简单问题进行推广：资源点或发点的车辆不止一辆，而是一个车队 q ，( ，t1 ，2 ，册) ，在理想状态下它是齐次的( 每辆车的容量均为口) ，且有足够的 运力保证任务的完成，需求点i 的货运量满足罗g ；苫q ， 且 n q 罗毋苫口( i 一, 2 , - - - , m ) 。也就是说为了完成运输任务需派若干辆车，全部发送 路线为几条大的路线组成，每辆发送车辆从配送中心出发后，沿一条覆盖若干用 户的大路线送货，然后返回配送中心( 见图5 2 ) 。 ( 3 ) 考虑实际约束( 主要指时间窗约束) 的配送问题( c 级问题) 配送的一个重要特点在于用户往往会指定发送或交货的时间限制要求。假设 一组有 个需求点要求送货，并表示为1 ，2 ，f ，n ，需求点f 有一个固定的完成时 间霉、一个服务时间墨( 如卸货时间) 。例如，若l - 1 2 ：3 0 ，墨一1 小时，那么货 车必须安排在1 1 ：3 0 到达需求点f 。在任何两个需求点f ，j 之间的运输时间用 d h ( i ，j f ) 表示，距离用略表示。假设，如果乙一s ， l + d h ( i ，j ) ，那么弧( f ，j f ) 就 存在。对弧( f ，_ ) 指定费用c o d h ( i ，| ) ( 或d 甜) ，于是，该问题就化为用给定数目的 从起点f 到终点f 的路径( 这些路径规定了一种先后次序) ，经过所有节点，以使在 所有车辆的时间表安排中的总运输时间( 或总运输距离) 最小。 以上时间表的安捧只是假定每个需求点的开始或结束时间是固定的。然而， 有的用户还规定有完整时间窗，要求配送到货必须在窗内完成，例如，任务需在 1 l ：3 0 到1 2 ：3 0 之间完成，那么问题就是一个路线和时间表安排的混合问题。该 问题必须在满足用户时间窗要求下，安排路线的以使总的运费达到最小。 ( 4 ) 多发车点的配送问题( d 级问题) 4 5 东北大学硕士学位论文第5 章b 2 c 电子商务中带有多时间窗的车辆调度问题研究 上面所讨论问题的一个直接推广就是允许车辆从一个以上的地点发出，这些 地点可以是多个配送中心或多个车场，因而配送问题就成为有几个封闭循环线路 的巡回销售员问题。毫无疑问这是一个组合优化问题。调度寻求为完成所有任务 而必须的最少车辆数以及各车的优化路线。 5 3 2 对时间窗的界定 5 3 2 1 时间窗的定义及种类 ( 1 ) 定义 设为客户f 服务( 卸货、装货) 的时间表示为s ，又设为客户服务的开始时间 需在一定的时间范围陋正，l t , 】内，其日为客户i 允许的最早开始时间，l t , 为客 户f 允许的最晚开始时间。如果车辆到达f 的时间早于e z ，车辆需要等待，如果车 辆到达时间晚于l 正，服务就要延迟进行。 以以表z 车辆到达客户i 的时间，一般应有关系式：e l d 。 2 ，这时时闯窗约束较松，可能存在时问可行的回路，时问约束一般 能够满足，问题的空问性质处于支配地位，一般来说，根据位置情况安排线路即 可。 0 t w 2 ，这时时间窗约束较紧，时间可行的回路较少或没有，问题的 时间性质与空间性质相比更可能属于支配地位，在进行车辆调度时，必须考虑时 间约束。 5 3 2 2 对本文时间窗的界定 本文所研究的时间窗配送问题是指为客户f 开始服务的时间必须在客户i 允许 的最晚开始时间l z 前进行，若超过这个时间，则得到的解为不可行解。车辆可以 在客户f 允许的最早开始时间e r , 前到达，但车辆必须在此等待直到e r , 。 5 3 3b 2 c 电子商务环境下时间窗的现实涵义 自从2 0 0 0 年我国的电子商务网站数量大增，涉及的经营业务范围不断延伸， 但是因为b 2 c 电子商务交易模式特点以及我国目前电子商务模式的发展阶段的限 制，还是以图书、礼品、服侍、日用品，音像制品为主。在商品的配送环节，“最 后一公里的效率和时间要求对增强的市场企业竞争力起到了至关重要的作用。 我国当前大多数电子商务企业的“最后一公里”主要依靠个人配备简单车辆来完 成，在送货车辆从配送中心发出前，会通过电话与消费者进行直接沟通，商定好 送货的具体时间。根据当当网对网上购物人群的分析报告，经常采用b 2 c 电子商 务方式购物的人群以高学历为主，职业分布主要以都市自领和大学学生，这部分 人群的时间特点是平时工作学习较忙，生活比较有规律，一般是早晨上班上课前 或者晚上下班后有空暇时间。对于物流配送的话，既要考虑物流配送人员的工作 时间安排，又要符合消费者的空暇时间要求，对消费者空暇时间进行交集，就会 得出对于每个不同的消费者每天存在的空暇时间区间，这个空暇时间表现为一个 或几个时间区间，即时间窗的概念【5 1 l 。 本文通过对时间窗约束问题的讨论，可以指导车辆在做物流配送时，更好的 规划车辆的行车路线，既能满足需求客户在收货时间上的要求，还能保证车辆配 送成本相对最低，研究的结果对提高b 2 c 电子商务企业物流的配送效率有较高的 借鉴作用。 5 4 物流配送( 有时间窗约束) 问题的数学模型 - 4 7 - - 东北大学硕士学位论文 第5 章b 2 c 电子商务中带有多时间窗的车辆调度i - 1 题研究 由于配送实际中，配送中心一般自接到订单后在一定时间范围内( 如2 4 小时 内) 将货送到即可，所以b 级理想状态下的配送运输存在较多，a 级简单配送路 线、c 级有时间窗约束的配送运输以及d 级多发车点配送运输在实际中存在相对 较少。鉴于篇幅所限，本文对b 级和c 级问题进行研究。因为c 级问题包含b 级 问题，下面我们选取c 级有时间窗约束的配送运输问题，建立其数学模型，然后 用优化调度算法的求解b 级问题。 5 4 1 物流配送( 有时间窗约束) 问题描述 带时间窗的单向多目标物流配送线路选择问题可以描述为：从物流中心( 物 流据点) 用多台汽车向多个地理上分散的客户送( 取) 货，物流中心和每个客户 的位置一定，客户的需求( 供应) 量一定，每台配送车辆的载重量一定，各需求 点所需货物量较小( 小于车辆容量) ，且各需求点距配送中心以及各需求点间的距 离为已知，客户要求将需求( 供应) 货物送到( 取走) 的时间窗也一定。要求合 理安排车辆的配送路线和行车时间，使运输时间、运输费用及全部客户等待时间 这三个目标函数得到优化，并满足以下约束条件：车辆在配送过程中的载货量 不超过其最大载重量；每个客户需求( 供应) 的货物必须送到( 取走) ；客户 需求( 供应) 的货物要在客户指定的服务时间窗内送到( 取走) 。 5 4 2 物流配送车辆调度( 有时间窗约束) 数学建模 设配送中心为p ，可用车辆集合为日。 = 1 ，2 ，m ) ；q 。为车辆的载重量，用 户集合为g ；( f 一1 2 ，万) ，g i 为用户f 的货运量，由于是可混装的运输，因此有 m a x g ； m a x q 。以略表示用户z 与用户j f 之间的最短距离，设岛为车辆从用户f 行 驶到用户_ i 的时间，以墨表示用户i 的货运任务的开始时刻，以岛表示该任务的终 止时刻，霉完成任务所需的服务时间( 装货或卸货) ，显然z 一岛一s t ；。用户f 的 货运任务要求在一定的时间范围【e 正，l r , 】内( 称为时间窗) 必须开始，其中e r , 为 用户的允许最早开始时间，l 为用户的允许最迟开始时间，即要求e r , s 墨s l r , 。 如果车辆到达f 的时间早于e t ；，则车辆需在f 处等待，如果车辆到达时间晚于l r , ， 则任务j 要延迟进行。以m 表示用户f 存在时间窗的个数。车辆总运行时间或距离 上限为l i m ，气为目标函数的成本系数，当它为用户f ，_ | 之间的距离d 计时，则目 标为使车辆的总运距最短；当它为用户i ，l j 的运输时间f d 时，则目标为使车辆的 总运行时间最短。 为构造数学模型，定义变量如下： 4 8 东北大学硕士学位论文第5 章b 2 c 电子商务中带有多时间窗的车辆调度问题研究 y 材4 1o 否则 f1车辆k 从点i 行驶到点i 5 1 o 否则 则可得到配送调度模型p ，如下： 目标函数 m i n za c o z 秘 一一_ v 约束条件 g j y 蔚sq v k y 矗；1 i