从京东的物流配送谈车辆路径选择问题

1、精选优质文档-倾情为你奉上从京东的物流配送谈车辆路径选择问题1 京东商城简介京东商城是中国B2C市场最大的3C网购专业平台，是中国电子商务领域最受消费者欢迎和最具有影响力的电子商务网站之一，京东商城之所以能成功，很大一部分归因于它良好的经营模式。同时京东商城提供了灵活多样的商品展示空间，在线销售家电、数码通讯、电脑、家居百货、服装服饰、母婴、图书、食品、在线旅游等12大类数万个品牌百万种优质商品。消费者查询、购物都将不受时间和地域的限制。 1.1 京东商城规模京东商城总部设在北京， 管理中心和采购中心位于北京，一级物流中心有：北京、上海、广州、成都、武汉，二级物流中心有：沈阳、济南、西安、南京

2、、杭州、福州、佛山、深圳，全国客服中心设在宿迁。自2004年初正式涉足电子商务领域以来，京东商城一直保持高速成长，连续六年增长率均超过200%。京东商城始终坚持以纯电子商务模式运营，缩减中间环节，为消费者在第一时间提供优质的产品及满意的服务。京东商城目前拥有遍及全国各地2500万注册用户，近6000家供应商，在线销售家电、数码通讯、电脑、家居百货、服装服饰、母婴、图书、食品等11大类数万个品牌百万种优质商品，日订单处理量超过30万单，网站日均PV（page view）即页面浏览量超过5000万。对于物流仓储来说京东商城布局已久，从08年开始，京东就自建物流配送系统，经过几年的积累，目前，京东商

3、城已经具有完善的物流体系，仓储辐射范围以及终端配送辐射能力覆盖全国大部分城市。1.2 京东网B2C物流流程1. 下单：客户在京东网上决定购买某货物且提交提单的过程。 2. 系统确认订单：在顾客点击“提交订单”后新订单生成并将订单编号传递到系统。系统确认后有货，自动进入订单打印程序。 3. 订单打印：客户在网上下订单后，经过京东的网络系统可以在网上或现有的ERP系统中看到客户下的订购单。订单可分为单个打印和批量打印。待订单打印完后ERP系统中的打印栏由未打印变成已打印。再由信息员将已打印的订单进行确认，由订单变成为货物分拣界面。4. 取货：京东的仓库中，商品按照字母A-P的顺序依次摆放着。而出库

4、员手上的汇总订单也是按照A-P的顺序排列下来。这样就可以从A区到P区依次取货，正好绕着仓库走一圈，而不用走回头路。一次要为20份左右订单同时取货。 5. 分拣：在货物分拣完成后，交给发货包装组进行扫描出库和包装，同时分拣人员在ERP系统中的将分拣过的货品资料前面打勾后，点击确定。同时页面变成待发货页面，状态栏为待发货状态。再点击确定转为我们现有的ERP发货系统。 6. 扫描确认订单：库存组依据账物组交给的销售定单进行配货，配货结束在配货单上签字确认后交给发货组。发货组接到配货组交给的物品后依据销售定单号在ERP系统上进行扫描，扫描时核对销售单的数量，尺码大小。确认货品无误后送往发票开具区。7.

5、 打包：扫描和开具发票完成后，货品被送到打包区。打包员用塑料袋、泡沫和纸箱将货品包裹好封严。每一个打包员身边也有台电脑，打包员完成一次打包，就要往系统输入自己的编号和货品订单号。 8. 上车扫描：包裹在由仓库发往配送点时会进行上车扫描。如果选用第三方配送，快递公司把货物拿走的同时，会进行电脑扫描，此时，用户在页面上看到订单信息会变为已经配送。 9. 下车扫描：在包裹到达配送点后，操作员会对包裹进行“下车扫描”，这表示货物将分配给该区域的某一位配送员进行配送。 10. 配送：京东商城的GIS系统可以让在订单页面上看到包裹实时的移动轨迹。在订单页面的地图上包裹标识以一条红色的轨迹移动。包裹将要经过

6、的线路是一条红色的虚线，已经过的是条实线。 11. 收货：收货人收货然后在单上签字。 12. 退货及后续处理作业：退货及后续处理作业是物流配送流程的最后一个环节。客户因某种原因可能请求退货，企业应制订相应的退货处理政策。退货可集中由配送企业送回原仓储地点，由专人清理、登记、查明原因，如是产品质量问题应进行抽样检验，超出相应标准则及时通知采购作业流程停止订货，并通知网站管理部门将网页上有关货物的信息及时删除，尚未超标则作为验收不合格物品，进行退货处理；如退货还可继续使用，可进入库存，重新开始新的仓储管理配送过程。1.3 京东网物流配送模式 配送作业是物流配送的核心环节。配送部门由业务管

7、理部门进行统一配送调度，京东商城根据客户的具体要求，打印相应的送货单，在运输途中通过GIS信息查询系统，GPS车辆定位系统进行实时监控，及时沟通和反馈配送信息，并在货物到达目的地，经客户确认签字无误后，凭回单向业务管理部门确认。 我国的配送作业环节在经过几年的发展后虽然取得了显著进步，但整体体系还不算完善，存在着许多问题，阻碍了配送作业的工作效率。其主要原因在于缺乏高效的物流配送体系。一方面，在配送的硬件上，基础设施较差，不配套，各种运输方式之间装备标准不统一，物流器具标准不配套，物流包装标准与物流设施标准之间缺乏有效衔接，现代化水平低；另一方面，在软件上，物流企业的社会化程度、组织

8、化程度低，没有形成覆盖面广的社会化的物流网络服务体系。缺乏适合京东的高效物流配送体系是目前京东商城发展中的一个主要障碍，导致物流无效作业环节增加，物流速度降低和物流成本上升，影响了物流的效率和效益。所以京东需要建立自己的物流体系。 目前京东商城的物流模式主要有两种：自建物流体系与自建体系+第三方物流相结合称为混合型物流模型。1.3.1 自建物流体系 2009年，京东网上商城陆续在天津、苏州、杭州、济南等23座重点城市建立了城市配送站，最终，配送站将覆盖全国200座城市，均由自建快递公司提供物流配送、货到付款、移动POS刷卡、上门取换件等服务。此外，京、沪、粤三地仓

9、储中心也已扩容至8万平方米，仓储吞吐量全面提升。目前，分布在华北、华东、华南的三大物流中心覆盖了全国各大城市。2009年3月，京东网上商城斥资2000万元人民币成立了上海圆迈快递公司，上海及华东地区乃至全国的物流配送速度、服务质量得以全面提升。2010年4月初，京东商城在北京等城市率先推出“211限时达”配送服务。2010年5月15日在上海嘉定占地200亩的京东商城“华东物流仓储中心”内，投资上千万的自动传送带已投入使用。1.3.2 自建体系+第三方物流相结合 随着互联网应用的深入，京东业务阵营已经扩展到二级城市或三级城市，现在二级城市的利润不足以维持物流中心的运营。正因于此，大多数

10、B2C网站都与第三方物流合作完成配送。 在北京、上海、广州之外的其他城市，京东商城和当地的快递公司合作，完成产品的配送。而在配送大件商品时，京东选择与厂商合作。其主要的第三方物流公司有宅急送、中国邮政等。3、其他物流方式 除了与第三方的物流公司合作，京东商城还在各地招一些高校代理。高校的学生是一个比较大的消费群体，但他们的不确定因素也是最多的。产品配送的时间大都是在白天，可白天是高校学生的上课时间，他们希望快递公司在晚上把货送来，但快递公司却不提供这样的服务。于是经常发生这样的情况：配送人员到学校门口告诉学生货到了，学生却不能取货。 第二个难题是，绝大多数高校的保

11、安都不允许快递人员进入校园，快递人员只能和高校学生用电话联络。但部分高校学生使用手机的频率不高，或者关机，或者是忘记携带。快递人员经常打电话找不到人。结果双方都有意见，学生抱怨快递公司送货不及时，快递公司抱怨联系不上学生。为了解决这个问题，京东商城招一些人做高校代理。1.4 京东商城模式分析1.4.1自建物流模式的SWOT分析优势：1.节省开支，公司内部人员做物流比较放心，可以给客户贴心的感觉。2.可以使企业掌握对物流的控制力。3.可以保持旺盛的竞争力。4。自营物流可以使物流、资金流、商品流、信息流结合的更加紧密，从而提高物流作业的效率，减少资金占用。劣势：1.企业自营物流增加了企业的投资负担

12、，削弱了企业抵御市场风险的能力。2.企业配送效率低下，管理难于控制。3.初期投入太高，在初期自建物流未完善之前，系统管理更不上，专业化程度不够高。4.存储货物过多，难于管理等等。机遇：1.网民群体扩张速度很快，网络覆盖的范围也越来越广泛。2.物流配送逐步发展完善。3.越来越多的投资人对自营物流感兴趣，可以帮助B2C网站更好的对物流和仓储的投入与发展。威胁：1.竞争对手和其他的物流公司所造成的竞争压力很大。2.未来会有越来越多的B2C网站加入到这个物流模式中，因此京东商城压力很大。1.4.2京东商城外包物流的SWOT分析优势：1.归核优势。外包物流企业的专门化很高，物流作业高效，而且物流成本相对

13、较低。2.业务优势。使得生产企业可以获得自身企业不能提供的物流服务，并且能够降低物流设施和信息网络滞后对企业的影响。3.服务优势，可以实现商品的快速交易，增加客户的满意度。劣势：1.生产企业对物流的控制降低，从而影响效率。2.客户关系管理的风险，企业与客户的关系会减弱，客户信息泄露风险。3.连带经营风险。机遇：1.第三方物流企业的发展壮大，物流技术现代化。2.仓储业飞速的发展，减少了流通环节，降低了物流费用。威胁：1.我国的现代物流发展还不够完善，与国外物流现代化程度相差较大。2.我国整个第三方物流市场比较分散，专业化程度不高。3.我国物流的仓储、运输现代化还不够高。2 同时送货和取货车辆路径

14、问题研究2.1 逆向物流简介逆向物流主要思想概括起来包括三个方面：第一、逆向物流的目的是为了重新获得废弃产品或有缺陷产品的使用价值、或是对最终的废弃物进行正确的环保处理；第二、逆向物流的流动对象是产品、用于产品运输的容器、包装材料及相关信息，将它们从供应链终点沿着供应链的渠道反向地流动到相应的各个节点；第三、逆向物流的活动包括对上述流动对象的回收、检验、分类、再制造和环保处理等活动。逆向物流主要包括退货逆向物流和回收逆向物流两部分，退货逆向物流是指供应链下游的消费者将不符合订单要求的产品退回给供应链上游供应商所形成的与常规产品流向正好相反的物流；回收逆向物流是指将最终用户所持有的废旧物品或其部

15、件以及可循环使用的物品回收到供应链上各节点企业所形成的物流，它主要包括回收、检验、分类、再制造和环保处理等环节。本文中将逆向物流过程形成的运输货物统一称为返回货物。逆向物流产生的主要动机是节约成本和保护环境。结合逆向物流的路径问题，如旅行商问题和车辆路径问题必须同时考虑配送货物（送货）和返回货物（取货）而进行必要的修改和调整。如果我们单独运作前向物流和逆向物流，从运营角度看，对于每一种方式都要分别解决单独的车辆路径问题(Vehicle Routing Problem， VRP)，具体运作上难度很大，也不利于环境的保护。此外，在许多配送系统中，单独运作前向物流和逆向物流会导致车辆能力的无谓浪费。

16、如果把车辆路径中的送货和在客户点的取货充分结合起来，可以减少车辆能力的浪费，这就出现了带有回程的车辆路径问题(Vehicle Routing Problem with Backhauls，VRPB)，在 VRPB 中，客户的取货和送货是单独运作的，送货是在配送过程中完成的，而取货则是在回程中完成的。在实际中，许多与环境保护密切相关的配送过程中，许多客户既有送货需求，又有取货需求，如软饮料工业中，在送货的同时回收空瓶，送气和送水的同时回收容器等。因为各项耗费是由送货和取货共同引起的，他们并不希望这两项活动分开来处理。如果同时完成送货和取货，可以大量减少劳动耗费，因此客户只接受具有单一停靠的同时取

17、送货服务，对于这一类问题的车辆路径问题，我们称之为同时送货和取货车辆路径问题(Vehicle Routing Problem with Simultaneous Delivery and Pick-up，VRP-SDP)。为了不引起表述和理解的混乱，我们指出所谓送货、取货任务是相对于配送中心而言，配送货物是指在配送中心将客户需要的货物装车，然后按照每个客户的要求将货物送达，该服务过程相对于配送中心是送货任务（delivery）；返回货物是指在每个客户处卸货后将配送中心需要返回的货物装车送达配送中心，该服务过程相对于配送中心是取货任务(pick-up)。在每个客户点，规定送货交付作业先于取货作业

18、进行，即先卸货后装货。因此，车辆在到达某一指定地点之前的当前负载，等于初始负载减去所有已经交付的量，加上所有己经收取的量。VRP-SDP的显著特征是所有送货任务都由车场开始，服务结束时所有的取货量被带回车场，并在不违背车辆容量、最大行驶距离等约束的条件下，任何客户都同时存在送货和取货服务。车辆路径问题为一复杂性颇高的 NP 难题，而同时送货和取货车辆路径问题整合了前向物流和逆向物流，每个客户同时存在送货和取货服务，比传统的车辆路径问题要复杂得多，本文根据该问题的特征，设计一种改进的差分进化算法求解该问题。2.2 差分进化算法基本理论简单差分算法(Simple Differential Evol

19、ution Algorithms，SDEA)的基本思想是：对当前种群进行变异和交叉操作，产生另一个新种群，然后利用基于贪婪思想的选择操作对这两个种群进行一对一的选择，从而产生最终的新一代的种群。变异操作、杂交操作和选择操作三种基本差分操作实施简单，它们是算法的基础和核心。构成简单差分算法的要素主要有：个体适应度评价、差分操作以及参数设置等等。（1）适应度函数在差分算法中，差分操作主要通过适应度函数（fitness function）的导向来实现的，它是用来评估一个个体相对于整个群体的优劣的相对值的大小。（2）基本差分算法通常使用下述三种差分操作：变异算子：通常按照定的加权因子，改变个体中的某些

20、代码的值。交叉操作：随机地从初始群体中取得两个个体，并按照某种交叉策略使两个个体互相交换部分个体代码，从而形成两个新的个体。选择操作：按照某种策略从父代中挑选个体进入中间代。（3）差分算法的运行参数有以下四个运行参数需要提前设定：群体大小（ NP），即群体中所含个体数量；终止迭代代数（M ）；加权因子（ F ）；变异概率（CR）。这四个参数对差分算法的求解结果和求解效率都有很大的影响。因此，要合理设定这些参数，才能获得较好的效果。2.3 改进差分进化算法DE(差分进化算法)是一种基于群体智能进化理论的优化方法，通过群体内个体间的合作与竞争来实现对优化问题的求解，具有记忆个体最优解和种群内信息共

21、享的特点，DE的整体结构类似于遗传算法，其本质是一种基于实数编码的具有保优思想的贪婪遗传算法，与遗传算法相比，差分进化算法最大的特点就是在每个新个体的生成过程中用到了父代多个个体的线性组合，而不是遗传算法传统单一的父代染色体交叉技术，与遗传算法的主要区别是：DE在进化的过程中依靠产生的试验染色体（或临时染色体）与目标染色体进行比较来进化种群，试验染色体的产生与进化贯穿算法始终。改进差分进化算法的具体步骤如下：（1）初始种群及适应度函数针对车辆路径问题，我们采用不同于通常的DE的浮点（实数）编码，而是类似于遗传算法采用比较直观的序数编码。根据服务的客户数目（n），随 机 产 生 一 个 关 于

22、客 户 数 目 的 排 列 作 为 一 条 染 色 体 ，即 ：Chrom (i ,:)= randperm(n); i = 1,2,.,NP, 其 中 NP 为 种 群 规 模 ， 则 染 色 体 集 合Chrom (i,:)（ i = 1,2,.,NP）为需要的初始种群。由于车辆在送货时必须在配送中心装满其服务的所有客户的货物，而在服务过程中每个客户都同时存在送货和取货任务，故编码中一个重点和难点是根据约束条件找到染色体中的启用新的车辆的断开点（即子路径的起始点），对于一条确定的染色体，我们分两步找到断开点，首先从左到右考虑客户的送货需求之和，根据车辆容量约束找到初始断开点，得到每辆车的最

23、大可能服务客户数目，形成初始子路径；然后在该初始子路径内，再考虑在每个客户处的送货和取货容量约束以及最大距离等约束，得到最终的断开点，形成最终子路径；然后以该最终断开点的下一客户为起始点，在染色体中从左至右重复上述过程，得到该染色体的其它子路径。（2）变异操作差分进化算法的变异不同于其它进化算法中的变异操作。在进化算法中是将个体染色体编码串中的某些基因座上的基因值用该基因座的其它等位基因来替换，从而形成新的个体。在差分进化算法的变异中是在当前种群中依次对每条染色体（称为目标染色体，用 Chrom (c,:)表示）产生一个变异染色体（用 v(i,:)表示），试验染色体通过当前种群中的随机选择的两

24、个染色体的基因值差分与目标染色体组合后产生.（3）交叉操作交叉操作是为了增加群体的多样性，对于当前种群中目标矢量个体 Chrom (i,:)，将与变异矢量 v (i,:)按照某个交叉概率CR交换染色体的部分基因，产生试验（临时）染色体 trial (i,:)。为保证个体 Chrom (i,:)的进化，首先通过随机选择，使得 trial (i,:)的基因至少有一位由 v (i,:)贡献，而对于其它基因，利用交叉概率因子 CR ，决定trial (i,:)中哪位由 v (i,:)贡献，哪位由 Chrom (i,:)贡献。（4）选择操作选择又称为复制（reproduction），是建立在对当前种群中

25、试验染色体与目标染色体的适应度进行评价的基础上，按照“物竞天择，适者生存”原则，在实验染色体和目标染色体二者中选择生命力强的个体产生新的后代的过程，它是对种群中的个体进行优胜劣汰的操作，根据二者适应度大小进行选择，适应度高的个体被选择到下一代种群中的概率较大，适应度较低的个体被选择到下一代种群中的概率较小，从而使种群中个体对应的解不断接近最优解。选择操作的主要目的是为了避免种群中优胜个体信息的丢失，提高全局收敛性和计算效率。故选择算子确定的好坏，将直接影响到算法的计算结果。按照本节前面的方法得到试验染色体和目标染色体的适应度后，DE采用将试验染色体 trial (i,:)与目标染色体Chrom

26、 (i,:)按照适应度的大小进行一对一的“贪婪”的搜索策略，只有当 trial (i,:)的适应度较 Chrom (i,:)更优时才被选作子代，否则，直接将目标染色体 Chrom (i,:)作为子代。2.4 VRP-SDP 的数学模型VRP-SDP 可以描述为：给定一个配送中心，拥有确定数量的具有相同容量的车辆，车辆从配送中心出发对具有确定数量的客户集进行服务，完成服务后开回配送中心。每个客户具有确定的位置，车辆在配送中心装好客户需要的货物，将客户需要的货物送达，同时从客户手中带回配送中心的取货需求，车辆离开配送中心的初始装载量和返回配送中心的最终取货量的都不能超过车辆容量，每个客户的服务只能

27、由一辆车一次完成，求完成所有送货和取货服务的车辆路径最短的配送方案。为了表达方便，我们有如下的符号体系：V 为客户集合，客户数量为 n= V ；0 为配送中心；V0= V 0;cij 为客户 i 和 j 之间的距离；p 为客户 j的取货量， dj 为客户 j 的送货量， j = 1, 2,n;Q 为车辆容量； k 为配送中心最大车辆数目； yij 为途经弧（ i ， j ）的i之前（包含 i ）的客户取货总量；zij 为途经弧（ i ， j ）的 i 之后的客户送货总量。经过上面的描述，VRP-SDP 的整数规划数学模型可以表示为：在上述表达式中，目标函数为完成所有送货和取货服务的总的车辆行驶

28、距离；约束条件（2.2）说明每个客户仅能由一辆车一次完成服务；约束条件（2.3）说明对每个客户达到和离开它的车辆相同；约束（2.4）说明最多只能使用k 辆车；等式（2.5）说明每个客户取货量等于离开该点时的取货总量与达到该点时的取货总量之差；等式（2.6）表示送货量等于到达该点时的送货总量与离开该点时的送货总量之差；约束（2.7）为每条路径客户间的容量约束；约束（2.8）是每辆车的行驶距离约束，L是每辆车的最大行驶距离；约束（2.9）为决策变量属性。2.5 算例分析实验 1 考虑客户数目较少的情形。1 个配送中心给 8 个客户同时送货和取货，各客户的送货量（id ）和取货量为（ip ）(单位：

29、吨)由表 2.1 给出。这些客户由容量为 8 吨的 3 车辆完成配送，汽车的行驶速度设为 50km/h，配送中心与各客户间的距离(单位：公里)由表 2.2 给出。要求合理安排车辆的行驶路线，使总的路径最短。设置差分进化算法的种群规模 NP为 40，最大交叉概率maxCR 为 0.9，最小交叉概率minCR 为 0.3，每辆车的最大行驶距离 L 为 400，最大迭代次数为 200 次，将上述改进的差分进化算法运用 MATLAB7.0 进行编程，使用 Pentium4、3.06GHz微机运行程序，进行 10 次实验的平均结果如表 2.3，进化结果如图 2.1 所示。运行 200 次迭代的程序，10 次实验中，10 次得到 40 条染色体表现为相同的配送方案，100%达到最优结果，最终结果为：总的路径长度为 790km，使用 3 辆车完成配送任务，其中第一辆车的配送线路为：03510，离开配送中心时的实际装载量为 8 吨，实现满载，回到配送中心时的装载量为 8 吨，路径长度为215 km。第二辆车的配送线路为：06720，离开配送中心时的实际装载量为 8 吨，满载率为 100%，回到配送中心时的装载量为 6.5 吨，路径长度为 305km。第三辆车的配送线路为：0840，离开配送