改进的蚁群算法在矿山物流配送路径优化中的研究.pdf

维普资讯 第28卷 第6期 中 国 钼 业 V01．28No．6 2004年 12月 CHINA M0LYBDENUM INDUSTRY December 2OO4 改进 的蚁群算法在矿 山物流配送路径优化 中的研究 杨瑞 臣．云庆夏 (西安建筑科技大学，西安 71o055) 摘 要：物流配送路径优化问题是公认的NP难题，本文运用一种新型的模拟进化算法——蚁群算法对其进行求 解 。针对车辆路径问题及蚁群算法各 自的特点，本文对蚁群算法进行多方面改进 ，以优化其搜索能力和加快收敛 速度。文中通过对实例计算求解，取得了满意的结果，从而证明了新算法的有效性。 关键词 ：蚁群算法；车辆路径问题 ；物流配送 中图分类号 ：TD5 文献标识码 ：A 文章编号：1006—2602(2004)06—0016—03 STUDY oF RoVED ANT CoLoNY SYS’I’EM IN ’I．HE RoU’I’ING oP，I唧 ZATIoN FoR P=HYSICAL DIsTRⅡI唧 oN IN ～ⅡNES YANGRui—then，YUNQing—xia (Xi~LnUniversityofArchitectureTechnology，xi锄， 710055，Shaanxi，China) Abstract：PhysicaldistributionroutingoptimizingisafamousNP—Hardproblem．1’IIispaperuseantcolonysystem (ACS)，whichisanovelsimulatedevolutionaryalgorithm，tosolvetheproblem．Accordingtohtefeaturesofhte VehicleRoutingProblem andhtealgorihtm ，ACS isimprovedtoenhnacehtesearchingabilitynad convergence． Satisfiedcomputationalresul~ongivenproblemsraereported，whichshowshtathteimprovedACSisusefulna def- fective． Keywords：natcolonysystem ；vehicleroutingproblem；physical distribution 高求解效率。 1 概 述 从一般意义上讲 ，物流配送是指按顾客的要求， 在露天矿 山中，运输 费用通常 占矿石成本 的 用多个车辆从配送中心对顾客进行配给。各顾客点 60％～70％。因此，运输路径的优化具有 巨大的经 的位置和需求量为已知，各车辆的载重量已知，力求 济意义。通常，矿山运输路径的优化包括矿石、废石 寻找一个优秀的配送方案 ，使得总代价最小(所用 及材料的运输，可统称为物料配送路线的优化。它 车辆尽量少，行车总距离尽量短)，同时满足以下条 是一类 NP—HARD问题 ，精确的算法有分枝定界 件及假设 ： 法、K状树法 、Lagrangdecomposition等，但它们只能 ① 所有的配送车辆以配送 中心为起点并最终 求解相对简单的问题。有些研究者提出过几种启发 回到配送 中心。 式算法 ，如节约法 、扫描法等 ，这些方法尽管能够解 ② 每条配送路径上各需求点的需求量之和不 决此类问题，但也存在一定的缺陷，如节约法的组合