物流配送动态车辆调度系统.doc

前 言供应商客户配货客户配货供应商进货配送进货配送订货进货订货物流被称为“第三利润的源泉”，越来越受到人们的关注，日益成为国民经济的基础产业。配送是物流系统中一种特殊的、综合的活动形式，是物流与商流的紧密结合。配送是根据客户的要求，在配送中心或其他物流结点进行商品配备，并以最合理的方式交给客户的过程。所以，配送包含了备货、捡货配货、流通加工、远送等环节。配送按配送机构的经营权限和服务范围不同可分为配销模式和物流模式两种，其运作特点如图采购图1 物流配送业务流程图其中运输是物流中的重要环节，占物流成本的60%以上。车辆路径问题主要研究物流配送中车辆线路优化，以降低运输成本。该问题是运筹学和组合优化领域中的著名NP问题，在航班调度、列车编组等众多领域都有应用。车辆路径问题根据客户、道路、车型等多种约束因素可以分为多种模型。由于NP问题求解的复杂性，目前车辆路径问题的求解方法主要使用各种智能优化算法。针对第三方物流在国内的迅速发展，而国内车辆调度软件稀缺的现状，开发了智能车辆调度系统。在对国内外大量应用总结提炼的基础上，从车辆路径问题的模型和求解算法两方面，深入分析了车辆路径问题的国内外研究现状，根据不同因素，按照基本模型和衍生模型对车辆路径问题进行分类，解决目前研究的热点问题开放式车辆路径问题和动态网络车辆路径问题。系统包括车辆调度，承运单的管理，电子地图的显示，基础信息维护等功能。前 言11 国内外物流配送中心管理模式现状31.1欧美典型的物流配送中心31.1.1 美国干货物流公司DSC31.1.2食品配送公司31.1.3沃尔玛连锁公司的配送中心31.2 国内典型的物流配送中心41.2.1浙江统冠物流发展有限公司42 物流配送路径问题应用现状43 动态物流配送路径模型设计54 动态物流配送路径系统实现74.1系统的开发平台74.2系统的总体框架84.3 系统各功能的实现94.3.1 配送要求管理94.3.2基础信息管理104.3.3动态车辆调度管理125 关键技术145.1 Java实现路径规划145.2 ASP.NET实现业务管理205.3 Ajax实现地图控制与显示215.4 J2ME实现车辆GPS定位265.5 数据库设计306 软件系统推广应用316.1 推广范围316.1.1快递公司316.1.2第三方物流企业326.1.3企业自主物流326.2 应用模式326.2.1 独立软件销售326.2.2 SAAS和ASP模式336.3 预期赢利336.3.1 投入成本336.3.2 市场分析336.3.3 预期收入34物流配送动态车辆调度系统1 国内外物流配送中心管理模式现状1.1欧美典型的物流配送中心1.1.1 美国干货物流公司DSC干货物流公司主要业务是将300多家工厂生产的商品配送给美国各地7000多家零售企业，其中16家工厂的商品由该公司独家配送。主要为美国中西部的零售商配送商品。公司对配送的商品没有所有权与经营权，主要是为工厂服务，工厂生产的商品就近存入该公司各地的配送中心，零售商向工厂订货，工厂汇总后通知公司送货，送给谁由工厂决定，具体送货时间由各配送中心与零售商店协商确定。货款由零售商与工厂结算，配送中心向工厂收取相应的物流费用。所有环节包括存货、处理订单和配送商品都由以卫星通信为载体的电脑网络跟踪控制。通常的作业流程为：装满工厂货物的卡车从库房一侧卸货，然后根据商品的品类、生产厂家等资料，由工人刷涂该中心自编的仅供储存、发货之用的条形码，再用叉车送到指定的货架(指令由电脑终端给出)；接到配送货物的指令后，由工人拣选商品，送到库房的另一侧装入卡车。1.1.2食品配送公司食品配送公司是一家具有批发(分销)功能的配送公司。主要业务是根据市场调查的情况从生产企业进货 (买断或代理)，再根据零售企业的订单组织商品配送，货款结算时间对工厂是21-30天时间，对零售企业是7天时间。该中心仓库内没有自动分拣选设备，都是手工操作，由工人现场手写代码，分区存放(分为二类：需即时送走的和需储存一段时间的)。卡车调度的原则是尽可能多地利用社会卡车，只有为了降低成本时才用自有卡车，中心的38辆卡车由专门机构统一调度使用，并且通过公共电脑网络与货主、专业运输公司、卡车协会(即美国个体卡车司机协会)等组织保持联系，及时沟通货源与卡车流向的信息，以保证卡车回程运输的货源，避免卡车空驶。1.1.3沃尔玛连锁公司的配送中心沃尔玛连锁公司的Podteri11e配送中心连锁店铺将订单传递给临近的配送中心，配送中心汇总后报公司总部，商品由公司总部向工厂统一采购，店铺将货款汇至总部，由总部与工厂结算，配送中心不负责货款结算。该中心的自动化设施齐备，除了公司总部与各地配送中心，以及配送中心内部实行电脑管理外，库房内从货物入库时的分拣、刷码到进入指定的货架，从订单处理、拣选商品、传送到指定的库房门待装卡车，全部是自动化操作。1.2 国内典型的物流配送中心1.2.1浙江统冠物流发展有限公司城市食品冷链配送是统冠物流的重要特色。在电子商务的基础上，统冠物流以现代化的食品冷链物流分拣、仓储、同城配送为特色，实现了城市食品冷链快速配送的综合服务能力。在城市及周边范围内直接实现对超市及零售终端门店的配送覆盖。统冠物流服务范围还将不断扩大，从“点到点”、“门到门”到“JIT”物流服务的专业化水平和运作精度提升。为此，统冠物流围绕冷冻冷饮食品而形成仓储、运输、配送、加工等一体化综合物流服务，坚持品质至上，商品从入库到保存、理货、配送实行全程温控，在硬件设备、温控技术及管理制度上层层严格把关、全程保证品质。统冠物流提供多样化服务内容，如专案配合、促销后勤、流通加工等，创造物流附加价值。同时，配合淡旺季不同需求，整合作业流程与配送线路，机动调整，弹性配合，提升企业竞争力。 2 物流配送路径问题应用现状车辆路径问题又称车辆调度问题（Vehicle Scheduling Problem, VSP），主要研究物流配送环节车辆路线的优化，是物流配送优化中的关键一环。该问题是运筹学和组合优化领域著名的NP问题。通常可以描述为：对一系列装货点和（或）卸货点，组织适当的行车线路，使车辆有序地通过它们，在满足一定的约束条件（如货物需求量、发送量、交发货时间、车辆容量限制、行驶里程限制、时间限制等）下，达到一定的目标（如路程最短、费用最少、时间最少、使用车辆数最少等）。一般认为不涉及时间的是路径问题，涉及时间的是调度问题。如下图2-1所示。图 2-1 车辆路径问题的示意图车辆路径问题是NP难题，因为在实际的车辆行驶过程中，由于交通管理、交通流量、交通事故、天气变化等因素的影响，行驶的速度总是处在不断的变化之中，从而导致了路网中各个路段上的运行成本（时间）也相应地发生变化，有时顾客的需求是随时可变的，如在车辆已出发后，仍可能出现新客户提出服务请求，或者客户要求的服务时间随时发生变化，或一些突发事故使交通状况发生变化等。所以动态车辆调度技术具有较强的实际应用背景，在城市燃油配送系统、快递公司收发业务、城市物流宅急送业务中都有典型应用。目前许多物流研究机构提出了许多求解的方法，力图求出该问题的最优解，近似解或满意解。对于这类动态变化的车辆路径问题应该设计动态随机车辆运输模型，该模型可应用于邮政速递、产品配送和生产调度等众多领域。3 动态物流配送路径模型设计动态网络车辆路径问题的数学模型可以表示如下：假定配送中心最多可以用辆车对个客户进行运输配送，表示仓库。每个车辆载重为，每个客户的需求为。客户的时间窗是，开始服务客户的时间是，表示客户的服务时间，表示在客户的等待时间，客户到客户的在时间段内的运行时间为。表示一天中分的时间段数。表示无穷大的整数。优化的目标是最小化旅行时间，定义如下变量： 目标函数是最小化旅行时间： （3-1）约束条件： （3-2） （3-3） （3-4） （3-5） （3-6） （3-7） （3-8） （3-9） （3-10） （3-11） （3-12） （3-13）式（3-1）表示目标函数。式（3-2）保证每个客户都被服务。式（3-3）（3-4）保证客户是仅被一辆车访问。式（3-5）（3-6）保证同一条路线上的客户由同一辆车配送。式（3-7）保证车载量限制。式（3-8）消除子回路。式（3-9）（3-10）（3-11）保证满足客户的时间窗要求。式（3-12）（3-13）表示变量的取值范围。算法流程图3-1如下所示：结束，输出结果初始化粒子群计算粒子的适应度选择个体历史最优位置选择群体最优位置根据定义的速度、状态计算方法按照公式进行状态更新满足迭代条件是否图3-1算法流程图示意图4 动态物流配送路径系统实现4.1系统的开发平台配送路径系统的软件硬件平台分别如下：表4-1 系统的开发平台硬件名称硬件条件服务器网页服务器和数据服务器各一台CPUCore i3，频率:2930MHz内存2G硬盘160G，SCSI硬盘网卡10/100M自适应软件环境软件条件开发结构基于B/S结构，MVC开发模式操作系统Windows 2003 Server开发工具Java、ASP.Net语言数据库MS SQL Server 2005网页服务器IIS6.0前端页面展示ASP.NET + HTML + DHTML + Javascript系统采用B/S架构开发，以HTML + DHTML + Javascript作为前端静态页面展现工具，ASP.Net作为动态页面展示工具；后台调用Java WebService作为模型库、算法库及常用工具的实现方法；.Net用来实现页面控制和业务逻辑；数据库采用Microsoft SQL Server 2005作为数据库服务器；网页服务器采用IIS。下表4-2为手机GPS定位软硬件平台：硬件名称基本参数手机制式GSM，WCDMA屏幕大小3.2英寸屏幕像素360640像素数据传输GPRS，EDGE，HSPA操作系统Symbian 9.4 S60 5.0（S60第五版）CPUARM11，频率434MHz内存512MB ROM+128MB RAM内置Java版本CLDC1.1,MIDP2.0其他硬件内置GPS，支持A-GPS鉴于手机端软件采用J2ME开发，继承了Java语言的优点，具有良好的可移植性，同时全球大约78.6%的手机支持J2ME，智能手机100%支持J2ME，为平台的推广奠定了良好的市场基础。4.2系统的总体框架物流配送车辆调度平台主要用来验证动态路径规划的可用性，包括基础信息管理、配送要求管理、路径规划模块。系统的核心是路径规划模块，算法调用在该模块实现。其他模块是为该模块的运行提供可操作数据。系统的总体框架如下图4-1所示。图4-1 系统的结构框架动态车辆调度的核心工作就是根据配送要求，进行路径预规划，当发生新调度需求时，能根据当前车辆行驶实际状况对已规划的路径进行修正，规划结果采用地图形式直观显示。4.3 系统各功能的实现4.3.1 配送要求管理配送要求是配送中心管理各配送网点客户需求，信息主要包括：配送网点、客户、货物名称、配送日期、货物重量、载卸类型等信息。在配送要求管理中除正常配送需求管理外，为配合实时需求调度，添加了实时调度模块，将临时添加的配送需求输入到系统中等待重新路径规划。如下图4-2，图4-3所示：图4-2配送计划增加图4-3 配送查询列表4.3.2基础信息管理基础信息管理包括配送网点管理、车辆管理和客户管理模块。其中配送网点管理除管理网点基本信息外，还通过电子地图标注配送网点位置，所有已经添加的配送网点也可在地图上全部显示。如下图4-4，图4-5，图4-6，图4-7所示：图4-4配送网点设置图4-5各配送网点地理位置显示图4-6车辆信息管理图4-7客户信息管理4.3.3动态车辆调度管理动态车辆调度管理包括路径预规划和实时调度规划两部分。路径预规划是从已经产生的调度需求中按日期规划最优路径，而实时调度规划则是在车辆已经出发的基础上，根据最新的调度需求调用Web Service获取各车辆GPS数据，通过动态需求算法，在实际已行驶路径基础上重新规划。如下图4-8，图4-9，图4-10，图4-11所示:图4-8 多配送中心车辆调度路径静态规划结果的显示图4-9 多配送中心动态需求路径规划结果的图形化显示图4-10 单配送中心动态需求路径规划结果的图形化显示图4-11 单配送中心动态需求路径规划结果的图形化显示5 关键技术5.1 Java实现路径规划粒子群优化（PSO）算法是一种新兴的优化技术，其思想来源于人工生命和演化计算理论。PSO通过粒子追随自己找到的最好解来完成优化。PSO基本原理：粒子群优化算法源于对鸟群捕食行为的研究，一群鸟在随机搜寻食物，如果该区域里只有一块食物，那么找到食物的最简单有效地策略就是寻找目前离食物最近的鸟的作为区域。本系统中，配送车辆就是类似鸟，称之为“粒子”（Particle）或“主体”（agent）。给粒子都有自己的位置和速度（决定飞行的方向和距离），还有一个被优化函数决定的适应值。各个粒子记忆，追随当前的最优粒子，在解空间中搜索。每次迭代的过程不是完全随机的，如果在找到较好解，将会以此为依据寻找下一个解。在此过程中，粒子通过跟踪两个“极值”来更新自己：第一是粒子本身所找到的最好解，称之为个体极值点（pbest），另一个极值是整个群体所找到的最好解，即全局极值点（gbest）具体实现过程：1.初始化，初始化搜索点的位置。2.评价每一个粒子，计算粒子的适应度值。3.粒子的更新，更新粒子的速度和位置4.检验是否符合条件。在本系统中Java项目包含的info包主要实现数据库操作，fvrp包是预优化阶段调度算法实现，svrp包是二阶段调度优化实现。系统工作原理如图5-1所示。数据库Java算法包infofvrpsvrpAsp.NetWeb业务管理系统图5-1系统工作原理Java程序包核心代码如下所示。public class HeuristicAlgorithm public void twoOpt(List route)List r=new ArrayList();List rr=new ArrayList();for(int i=0;iroute.size();i+)r.add(route.get(i);rr.add(route.get(i);TargetValue tv=new TargetValue();tv.objective(route);double distance=tv.getSumDistance();int temp=0;for(int i=1;ir.size()-2;i+)for(int j=1;jr.size()-1;j+)temp=r.get(i);r.set(i,r.get(j);r.set(j,temp);tv.objective(r);if(tv.getSumDistance()distance) distance=tv.getSumDistance(); route.clear(); for(int k=0;kr.size();k+) route.add(r.get(k);r.clear();for(int n=0;nrr.size();n+)r.add(rr.get(n); /判断是否为发车点 private boolean judge(int point) boolean flag=true; for(int i=0;iSParam.FirstStepVehicle.length;i+) if(int)SParam.FirstStepVehiclei0=point) flag=false; return flag; public void routeOptimization(List route)List partRoute=new ArrayList();int n=0;int index=0;partRoute.add(int)SParam.FirstStepVehiclen0);for(int i=1;iroute.size();i+)if(route.get(i)!=0 & judge(route.get(i) partRoute.add(route.get(i);else twoOpt(partRoute); for(int j=0;jpartRoute.size();j+) route.set(index,partRoute.get(j); index+; partRoute.clear(); n+; if(n0) direction=-1; else if(quantumcolonyijk0*quantumcolonyijk10) direction=1; else if(quantumcolonyijk0*quantumcolonyijk10) direction=1;else if(quantumcolonyijk0*quantumcolonyijk10)direction=-1;else if(quantumcolonyijk1=0)if(rand.nextBoolean()=true) direction=1;else direction=-1;else if(quantumcolonyijk0=0)direction=0;double temp=quantumcolonyijk0;quantumcolonyijk0=Math.cos(angle*direction)*temp-Math.sin(angle*direction)*quantumcolonyijk1; quantumcolonyijk1=Math.sin(angle*direction)*temp +Math.cos(angle*direction)*quantumcolonyijk1;5.2 ASP.NET实现业务管理ASP.NET是基于WINDOWS平台的，简单易用，国内现在大部分的网站都是使用它来开发的，与此配套选择VS2005作为网站的开发工具，数据库则选择SQL SERVER2005保存和管理信息数据。业务管理系统实现为灵活的三层架构，分别是用户界面层、业务逻辑层和数据层（图1-7）。用户界面主要负责构建系统UI，处理与用户的交互。业务逻辑层则封装了实际的业务规则；数据访问层则完成对后台数据的访问操作，封装了所有的数据访问操作。而数据库则负责存储所有数据并提供数据服务。将显示逻辑从业务逻辑分离，即业务逻辑不关心数据如何表现，只处理业务逻辑并与数据层交互，数据层负责从数据库查询数据和更新数据。三层架构工作原理图如图5-2所示：图5-2 三层架构工作原理图在架构逻辑设计过程中应注意描述系统中包含的具体功能模块及功能模块间关系，尤其应该考虑项目的职责划分，如层、子系统和模块等的划分，设计一个系统的架构如同开发一个软件一样，需要实现一定的目标同时又有一定的要求与限制条件。解决方案中各类库对应层如图5-3所示。图5-3各类库对应层5.3 Ajax实现地图控制与显示本系统通过GIS导出相关区域地图信息，GIS (Geographic Information System，地理信息系统) 是获取、存储、理解、显示有组织的空间信息的计算机系统。该系统的核心技术是将，真实的地理数据，存储到计算机中，并通过一定的操作，读取计算机中的地理信息（如图5-4所示）。 图5-4地理信息展示由于本系统采用B/S模式，所有数据都从服务器读取，同时大量的地图信息的传输，加重了服务器的负载，影响了服务器的响应，增加了用户的等待时间，为此本系统采用Ajax实现地图信息的载入和操作。Ajax是一种创建交互式网页应用的网页开发技术，其最大优点就是在不更新整个页面的前提下维护数据，使Web应用程序更为迅捷地回应用户动作，并避免了在网络上发送重复的信息。地图控制与显示原理：1.用JavaScript脚本获取用户对相应的地图显示框的当前操作2.将用户操作信息传送给服务端。3.服务器获取信息，并通过一定的算法，将结果数据处理，发送个GIS。4.GIS中生成地图信息。（所生成的地图信息由JavaScript统一管理）5.服务器将GIS产生的地图信息通过Ajax技术发送给用户。（如图所示） 地图控制的JavaScript主要代码如下：SSystem.lOc = 2;SSystem.XOc = 3;function FZC(fdu, wdu, Ldu, xDU) this.element = fdu; = wdu = null ? : wdu;this.observer = Ldu;this.useCapture = xDU; FZC.prototype.GetElement = function() return this.element; function SMapParamOption() this.Zoom = -1; this.ecC = false; this.Name = ; this.Size = new SSize(400, 280);this.Center = null; this.TileSize = new SSize(256, 256);this.Resolutions = ;this.NumZoomLevels = 0;this.MaxExtent = new SBound(); function SLayerParamOption() this.IsMainLayer = false; this.Alpha = false; this.Visibility = true; this.Attribute = null; this.ImageSize = null; this.ImageOffset = null; XzC.BindyCC = function(ydU, hDu) var ZOu = Atotype.slice.apply(arguments, 2); if (ydU != null)return function() var NoU = ZOu.concat(Atotype.slice.apply(arguments, 0); return ydU.apply(hDu, NoU); .XzC.BindAsEventListenerHCC = function(boU, Uou) return function(evt) return boU.call(Uou, evt | window.event); function yZc() yZc.StartsWithzec = function(doU, OOU) return (doU.indexOf(OOU) = 0); yZc.Contains = function(COu, eou)return (COu.indexOf(eou) != -1); yZc.Trim = function(goU) return goU.replace(/s*(.*?)s*$/, $1); yZc.CamelizeUec = function(koU) var MOu = koU.split(-); var Pou = MOu0; for (var QOu = 1; QOu MOu.length; QOu+) var rOU = MOuQOu;Pou += rOU.charAt(0).toUpperCase() + rOU.substring(1);return Pou;function hZC() hZC.LimitSigDigsdEC我们在页面中调用Javascript方法对地图信息进行统一管理，使用效果如图5-5所示。图5-5使用效果图相关调用代码使用方法如下： function InitPage() Init(); var sc = new SDrawPointControl(vectorLayer, SHPoint, DrawMouseUpMonitor: function(geo) /document.getElementById(txtXY).value = geo.x + + geo.y; document.getElementById().value = geo.x; document.getElementById().value = geo.y; markerL.ClearMarkers(); , olControlDrawFeaturePoint); / var sc = new SDrawPointControl(vectorLayer, SHPoint, olControlDrawFeaturePoint); sc.Draw(new SPixel(10, 10); var scD = sc.GetDiv(); scD.innerHTML = 描点; sc.SetMap(map); scD._VV = sc; var ttv = document.getElementById(aP); ttv._VV = sc; ttv.onclick = function() this._VV.Activate(); var tt = document.getElementById(divMove); tt._VV = sc; tt.onclick = function() tt._VV.DeActivate(); AddEventListener(load, InitPage, false, window); 5.4 J2ME实现车辆GPS定位J2ME是一个新型的、较小的Java应用的环境，目前作为消费类产品和嵌入式设备的最佳解决方案，广泛应用于私人智能信息设备，蜂窝手机，双向寻呼，可视电话，以及POS终端。以J2ME手机平台为例,通过电信移动运营商的网络，获得移动终端用户的位置信息，在电子地图平台的支持下，为用户提供GPS定位服务。为了给用户提供更加精确，灵敏和快速的地位服务，美国高通公司提出了基于全球卫星定位系统的GPS的移动定位技术GPSOne解决方案，GPSOne是混合定位技术的典型代表，他将无线辅助GPS和高级前向链路三角定位法两种定位技术有机结合，利用来自无线网络的重要信息加快了处理进程，缩短了卫星数据采集时间。与传统车载GPS导航系统相比，基于手机等便携式移动设备的定位是需利用WAP和GPSOne技术有效结合就可以为用户构建以个一个“移动的定位秘书台”。 其基本的系统框架，如下图5-6所示， 图5-6基本的系统框架主要包括了网络构建的网关、WAP Push服务器、地图服务器及GMLC。其中GMLC(Gateway Mobile Location Center)是提供GSM移动网络系统内相关定位信息的通道。WAP Push技术是将服务前产生的最新数据，主动传送个用户。与以往传统基于Push的运作模式不同，用户不需要不断的向远端服务器不断的查询是否已有最新的资料更新过了，因此该技术能够比更有效的利用移动网络的资源。J2ME移动设备实现车辆GPS定位的主要过程为（如下图5-7）：1用户发送请求信息；2服务器透过HTTP网络协议取得使用者需求的信息；3并通过GMLC做定位协定的沟通并取得定位信息；4将地图资讯传给制定的用户；图5-7J2ME移动设备实现车辆GPS定位基于J2ME移动设备定位的移动导航具有良好的便携性、成本较低、使用方便，实现了移动设备定位和卫星导航的有效结合，在一定程度上拓展了移动设备定位业务应用。J2ME相关代码如下所示。class MyCanvas extends Canvas GISMIDlet GIS; public MyCanvas(GISMIDlet GIS) this.GIS = GIS; private double lat; private double lon; public void setInfo(double lat, double lon) this.lat = lat; this.lon = lon; protected void paint(Graphics g) Font f = Font.getFont(Font.FACE_SYSTEM, Font.STYLE_PLAIN, Font.SIZE_SMALL); g.setFont(f);/ use font height as a line height int lineHeight = f.getHeight();/ current line counter int line = 0; g.setColor(0xffffff); g.fillRect(0, 0, getWidth(), getHeight(); g.setColor(0x0000ff); g.drawString(Lat, Lon ( + GIS.formatDouble(lat, 5) + , + GIS.formatDouble(lon, 5) + ), 0, lineHeight * (line+), Graphics.TOP | Graphics.LEFT); public class GISMIDlet extends MIDlet implements CommandListener, LocationListener private Command exitCmd = new Command(Exit, Command.EXIT, 1);/private Form mainForm; private MyCanvas myCanvas; protected double lat; / 纬度 protected double lon; / 经度public String formatDouble(double value, int decimals) String doubleStr = + value; int index = doubleStr.indexOf(.) != -1 ? doubleStr.indexOf(.) : doubleStr.indexOf(,);/ Decimal point can not be found. if (index = -1) return doubleStr; / Truncate all decimals if (decimals = 0) return doubleStr.substring(0, index); int len = index + decimals + 1; if (len = doubleStr.length() len = doubleStr.length(); double d = Double.parseDouble(doubleStr.substring(0, len); return String.valueOf(d); / end method formatDouble public void locationUpdated(LocationProvider lp, final Location location) new Thread() public void run() if (location != null & location.isValid() Coordinates C = location.getQualifiedCoordinates(); if (C != null) lat = C.g