基于多约束pdptw算法优化车辆调度系统

《基于多约束pdptw算法优化车辆调度系统》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、基于多约束PDPTW算法优化车辆调度系统　　摘要：本文架构一个GIS车辆调度系统，充分利用GIS系统的空间数据特性和决策优势，综合考虑配送过程中的各种约束条件，使用多约束PDPTW算法对系统进行优化，最终获得物流配送最佳方案。Abstract：OneGISvehicleschedulingsystemisbuiltinthispaper，itfullyusesofthespatialdatafeatureanddecisionadvantageofGIS，considersallkindsofconstraints.Thesystemisoptimized

2、withmulti-constraintedPDPTWalgorithmtogetthebestdistributionprograms.关键词：带时间窗装卸货问题;车辆路径规划问题;地理信息系统Keywords：PDPTW;VRP;GIS中图分类号：U116文献标识码：A文章编号：1006-4311（2015）04-0022-020引言7近年来，随着GIS技术的不断发展成熟，人们越来越习惯将这一技术与其他专业模型相结合并应用之规划领域，以有效解决实际规划问题。GIS的空间数据分析和系统决策分析等功能使其实现了对复杂空间数据的管理。GIS车辆调度系统实现了

3、如下功能：车辆和货物跟踪及导航、客户地理信息定位、物流网络布局和运输路线的模拟与决策等。多约束PDPTW在实际生活中有很广的应用，在工农业生产、经济领域、交通、物流管理和资源配置等方面有着广泛的现实意义。但由于它的复杂性，目前对其研究相对较少，还有大量工作要做。本文分析了在GIS平台支持下，采用多约束PDPTW算法解决实际生活中大规模、多车次、多货物种类并且有最大工作时间限制的车辆调度问题。1系统架构设计系统实现空间及客户多种信息的输入、存储、检索、综合分析、调度方案的确定等功能，主要包括客户数据管理、交通信息管理、车辆数据管理、地图显示和定位、线路优化等

4、模块。系统的总体结构层次模式描述如下：“用户级”完成用户和系统的各种交互操作，并创建问题决策任务。“系统级”则是系统设计和实现的核心工作，它由各个构件库组成。当业务级接收到用户级的任务后，对这个任务进行划分，创建各个构建的进程，通过这些构件对象利用数据级提供的数据支持完成分布式计算。“数据级”完成对决策支持数据的存储管理，为系统提供数据支持。系统基本流程如下文所述，结构图见图1。1.17信息采集：信息采集系统负责对交通信息和客户信息进行采集，并实时更新。采集的交通信息包括道路的变更（新增、删除、位置变化）、道路允许行驶速度和其它交通限制信息。采集的客户信息

5、包括客户的位置、送货交接时间和货物数量等。管理人员可以根据送货单的具体地理位置进行地图标示，即将客户地址标注在地图上。1.2选择配送路线并制定时间计划：根据客户的送货时间要求、地理位置、车辆配备、人员数据等建立起一个完整的车辆调度优化模型，优化货物资源分配。并选择最短路径，以保证在最短的时间内将货物送到。另外，管理人员还必须制定切实有效的时间计划，并尽可能地降低物流配送成本，提升其利润水平。1.3配送成本计算及管理：综合考虑运距、单位运距油耗量、车辆维修保养成本、司机工资、补贴等因素，准确计算出配送成本，并有重点、有针对性地进行配送成本管理。①方案优化后成

6、本：Cost=max（CostTime（Prv），CostDist（Prv））②实际成本：TotCost=max（CostTime（0.5），CostDist（0.5））×2CostTime：按配送时间计算的费用;CostDsit：按配送距离计算的费用;Prv：服务质量与服务成本的权重[0，100]。1.47对运算结果进行对比分析和综合判断，若其结果满足运算要求，则可进行下一步操作，否则需再次设置配送参数，再次计算。1.5输出行车路线图和装货清单。1.6按照路线图，以GIS电子地图和GPS实时导航为指导，完成装货和送货任务。1.7信息反馈：当配送任务圆满完

7、成后，应及时录入配送结果，并进行确认，及时反馈车辆行驶位置信息和订单配送完成情况。2车辆调度的多约束PDPTW算法2.1复杂条件下的PDPTW算法模型将VRP描述技术运用至订单配送领域，并确定配送路线，将配送中心编号设为0，任务编号设为1，2，…，m，订单及配送中心均以i表示，定义变量如下：yik=1订单i由车辆k完成0订单i不是由车辆k完成xijk=1车辆k访问弧（i，j）0车辆k不访问弧（i，j）设订单集合为V，cijk表示车辆k访问弧（i，j）的成本，k在一订单处装货或卸货量为gik（表示时间、质量或体积等），车辆k可载能力限制为qk，到达订单i的时

8、间为sik，在i的服务时间Tik，经过弧（i，j）的时间tijk，