基于数据挖掘的VRPSD问题的研究与应用.pdf

《基于数据挖掘的VRPSD问题的研究与应用.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、2010年第l2期科技管理研究ScienceandTechnologyManagementResearch2010No．12文章编号：1000—7695(2010)12—0057—03基于数据挖掘的VRPSD问题的研究与应用刘岚，薛华成(1．上海财经大学信息管理与工程学院，上海200433；2．复旦大学管理学院，上海200433)摘要：在车辆路径问题中，由于配送过程中各种不确定状况的出现，使得随机VRP逐渐成为研究者关注的焦点。数据仓库和数据挖掘技术的出现，给解决随机VRP问题提供了技术支持。针对随机需求VRP问题构建了相应的数据库及数据挖掘模型

2、，最后用启发式算法对给定数据用例进行了求解，取得良好的效果。关键词：VRP；VRPSD；数据挖掘；BP神经网络中图分类号：F224文献标识码：AVRP问题最早由著名学者Dantzig和Ramser于1959年首(2)DCVRP(Distance—ConstrainedVRP)是有距离限制的次提出。VRP可被认为对一系列发货点和(或)收货点，VRP问题，即每条路径都有最远行驶距离(或最大行驶时间)调用一定的车辆，组成适当的行车路径，使车辆有序地通过的限制。它们，在满足一定约束条件下达到一定的目标(如车辆空驶(3)VRPrw(VRPwithTimeW

3、indows)是有时间窗约束的里程最短，运输总费用最低，车辆按一定时间到达，使用的VRP问题，即每个顾客都有一个服务时问间隔[ai，bi]，称为车辆数最少等)。VRP是物流配送过程中的关键环节，该时间窗(包括硬时间窗和软时间窗)J。环节处理的好坏将直接影响对客户需求的响应速度、客户对(4)VRPB(VRPwithBackhauls)是带回程运输的VRP问物流环节的满意度以及服务商的配送成本。题，在VRPB中，顾客集由两个子集构成，一个为有送货需求的VRP问题中，随机需求车辆路径问题(VRPSD，Vehicle顾客子集，另一个为有取货需求的顾客子集

4、。RoutingProblemwithStochasticdemands)属于动态需求VRP。(5)VRPPD(VRPwithPickupandDelivery)是带有送货和在VRPSD中，可使用预测的方法先构造一条初始行车路线，取货需求的VRP问题，即在每个顾客i处有对同质商品进行本文给出了一个如何构造初始路径以减少车辆回程的方法，送货和取货的服务。当随机需求在一定误差范围内的时候，构造的初始路径是可2随机需求VRP问题行的。本文案例中，测试数据为一组某邮局的数据，数据库中在以往的研究中，人们一般假定在构造路径之前，所有的已有车辆送货和取货的数

5、据，数据仓库和数据挖掘模型可以信息(包括顾客信息、车辆信息、路况信息和路径制定者信息)用来预测行车需求。将预测的数据代人VRPSD模型中求解，都是确定的，并且这些确定信息与时间无关。在这样假定前提得出可行的行车初始路径。下，规划的车辆路径也是相对固定的，因而这类VRP也被称为确定性VRP或者静态VRP问题。但是由于在客观世界中存1VRP问题的定义和分类在着大量的不确定因素，如天气状况、交通拥挤、车辆突发故障VRP问题一般定义为：图G=(V，A)，V={v。，v一，v}及顾客需求临时变更等因素，这需要对已安排好的车辆路径是顶点集合，A={(v．，v

6、)：i，j{0，⋯，n}，vi，vV}是顶点进行及时调整，动态地改变车辆的行驶路线或交货时间，此时，间弧的集合。集合A生成矩阵L=(L)，L．．．为顶点v．到顶点确定性VRP问题转变成为不确定性VRP问题。vj之间的距离，L与路径总成本成正比。运输过程中，可以有不确定性VRP问题根据需求的随机性，可以给出随机需一辆或多辆车从仓库v。出发，访问一系列用户顶点(v一，求VRP(SVRP，StochasticVehicleRoutingProblem)的概念，即v)，在满足所有顶点的需求以后返回仓库。在VRP一系列的参数里至少有一个参数具有随机性。SV

7、RP一般VRP问题根据实际应用情况的不用可以被划分为众又可以分为随机顾客VRP(VRPSC，VehicleRoutingProblem多子集，如图1所示：withStochasticCustomers)，随机旅行时问VRP(VRPSTF，Vehi—cleRoutingProblemwithStochasticTravelTimes)，随机需求VRP(VRPSD，VehicleRoutingProblemwithStochasticDemands)。如图2所示：VRPSD一般被定义为：图G=(V，A，D)，V={v0，一，v}是顾客顶点集合，其中v

8、。为仓库，A={(v，vi)：i，j{0，⋯，CVKP；DCVRP：vRPTwVRPB；VRPPD：L⋯．．⋯．．!i．．⋯．⋯．．jL