实时环境下的物流配送车辆调度优化及网格计算研究.pdfVIP

学兔兔 实时环境下的物流配送车辆调度优化及网格计算研究★ 口 周贵仔 口 周美琴 口 陈火根 1．浙江机电职业技术学院 杭州 310013 2．杭州市生产力促进中心 杭州 310012 3．浙江大学 杭州 310027 摘 要：考虑智能交通系统中的实时信息，采用混合整数规划方法建立了一个带时间窗的物流配送车辆调度与路径 优化的动态模型，可以根据实际的行驶时间对车辆调度计划作动态修改，包括车辆出发时问及顾客访问顺序。提出了利用 网格技术进行车辆调度优化求解的一种网格计算结构模型及其实现方法，以解决实时在线优化的计算瓶颈。实验结果表 明，此方法不仅能满足实时响应的要求，降低物流的总成本，还提高了对顾客的服务水平。 关键词：智能交通 动态模型 整数规划 网格技术 车辆调度 配送中心 中图分类号：TP393 文献标识码：A 文章编号：1000—4998(2008)12—0014—03 国内外学术界对物流配送中心车辆调度优化问题 对 m辆车、n个客户点，确定车辆分配(每辆车负责的 十分关注，研究也比较早，设计开发了许多优化求解模 顾客点)、每辆车的出发时间及行车路线，使总成本最 型与算法，如启发式算法、遗传算法、蚂蚁算法等“ 】。但 小，同时要满足以下约束条件。 这一传统问题还有必要作进一步的研究，主要原因有： 1)每辆车从一个仓库出发，对多个顾客点服务，并 ①这些优化算法大多是基于预测的车辆行驶时间进行 终止于出发地； 优化计算的(一般采用前一天的行驶时间)，与实际情 2)每一个顾客点仅有一辆车服务，而且所有的货 况可能有一定的差异，受当天交通路况的影响比较大。 物必须一次性装车； 由于智能交通系统的发展，特别是 GPs／GIs／GSM技术 3)每辆车负责顾客点的货物总重量不超过其最大 的应用，目前越来越多的物流配送中心的信息平台能实 载重量； 时地获取交通路况，甚至每辆车的具体位置、行驶时间 4)对每一个顾客点，车辆到达时间限制在某一时 等信息，因此可以根据实际的行驶时间进行车辆调度优 间段内，迟到或早到都要付罚金； 化；②实时信息的使用对优化求解效率提出了更高的 5)当～辆车到达一个顾客点时要根据实际的行驶 要求，必须实时响应，否则实时信息就会失去作用。 时间对车辆调度计划进行修订； 针对物流配送中心车辆调度优化，本文考虑交通 6)每辆车每天可多次使用，但每次出发和返回都 实时信息，采用 昆合整数规划方法建立了一个带时间 有时间限制。 窗口的车辆调度与路径优化的动态模型，并提出了利 2 优化模型 用网格技术进行车辆调度优化求解的一种网格计算结 构模型，以解决在线优化(Online Optimization)的计算 2．1 求解思路 瓶颈。实验结果表明，此方法不仅能满足实时响应的要 VR哪 一D问题的求解可以分两步进行。首先，将 求，降低物流的总成本，还提高了对顾客的服务水平。 各道路前一天的行驶时间作为初值对问题进行求解 ， 得到车辆调度计划 ，包括每辆车的初始出发时间和对 1 问题描述 顾客的访问顺序。然后，当一辆车到达一个顾客点时根 物流配送中心的车辆调度