基于矩阵变换的车辆路径问题仿真优化方法.pdf

第11卷第4期 管理科学学报 VoI．11NO．4 2008年8月 JOURNALOFMANAGEMENTSCIENCESINCHINA Aug．2008 基于矩阵变换的车辆路径问题仿真优化方法① 胡祥培1，李永先1”，郭建文1 (1．大连理工大学系统工程研究所，大连116024；2．辽宁师范大学管理学院，大连116029) 摘要：针对车辆路径问题这一求解难题，提出基于启发式变换的仿真优化原理和求解方法，建 立了基于邻接矩阵的车辆路径问题的数学模型；利用启发式运行规则对仿真运行的参数进行 了分析，通过矩阵变换改进优化有哪些信誉好的足球投注网站策略并找出最优解或满意解．算例求解表明，基于矩阵变 换的仿真优化方法具有良好的稳定性和求解效率．该项研究为求解车辆路径问题这一难题提 供了新思路． 关键词：车辆路径问题；仿真优化；邻接矩阵；矩阵变换；启发式变换 中图分类号：TP391 文献标识码：A 0 引 言 更加复杂，因而对这一难题的研究也就更具学术 价值．目前，车辆路径问题的求解方法大多采用启 车辆路径问题(vehicle 发式算法，但它们的求解结果都不尽如人意．计算 routingproblems，简称 VRP)是物流管理领域关注的热点和难点问题．合机仿真是解决复杂系统问题的有效方法，是管理 理地安排车辆、行车路径和出行时间，以最低成本 科学与运筹学领域应用最广泛的技术手段．仿真 将货物准时送达客户，实现物流配送系统高效低 技术为复杂物流系统问题提供了技术性和经济性 成本的运作，这是物流运营及管理部门致力追求 的最佳结合点和直观有效的分析方法．因此，本文 的目标，也是长期以来困扰学术界的难题之一．该 拟从仿真优化的角度来探讨车辆路径问题的求 项研究对于物流企业降低物流成本、提高管理水 解，提出基于启发式变换的仿真优化方法，为解决 平具有重要的现实意义；对于丰富物流管理理论 这一难题提供了新思路．它主要涉及启发式算法 和方法也具有重要的理论价值．车辆路径问题于 和仿真优化方法两大方面，国内外学者在这两方 面的主要研究进展如下． 1959年由Dantzig和Ramser提出以后，很快引起 了管理学、运筹学、应用数学、物流科学及计算机 应用等学科专家学者的高度重视，并已取得了较 大的进展，其成果已在运输系统、物流配送系统及 Renaud[51等又提出了两阶段算法．此后，高级启 快递收发系统中得到广泛应用．然而，由于车辆路 发式算法如遗传算法(geneticalgorithm)，模拟退 火(simulated search) 径问题的复杂性(已被证明为NP—hard问题…)， annealing)，禁忌有哪些信誉好的足球投注网站(tabu 当节点规模较大时，将很难得到问题的精确解．尤 在求解VRP中得到了广泛的应用，取得了较好的 其是对于电子商务所涉及的城区物流配送系统， 效果[6q0|．宁爱兵等¨川提出了广泛适用于组合 除了考虑成本因素之外，还要考虑配送时间和环 优化问题的竞争决策算法，并用其通用模型设计 境等方面的因素，这就使问题的建模和求解变得 了一个求解车辆路径问题的快速求解算法．这些 ①收稿日期：2006—06—09；修订日期：2007一01—23． 作者简介：胡祥培(1962一)，男，安徽绩溪人，博士，教授．Email：drhxp@dlut．edu．cn 万方数据 一68一