蚁群优化算法在物流配送车辆路径问题中的应用研究

车辆路径问题(VRP)是一类物流配送领域具有广泛应用的组合优化问题,属于NP难题。一种改进的蚁群优化算法可以用于求解VRP。实验结果表明,采用蚁群优化算法能有效求解VRP问题。

21年 1 0 1 2月

廊坊师范学院学报 (自然科学版 )Junl f a g n ecesC￣g( aua Si c d in ora o n f gT ahr oee N tr c neE io ) L a l e t

De 2 1 c. 01

第 1卷第 6期 1

V0 . l No 6 11 .

蚁群优化算法在物流配送车辆路径问题中的应用研究蒋萼己(台州职业技术学院，浙江台州 3 8 0 ) 10 0

【摘

要】车辆路径问题 ( R ) V P是一类物流配送领域具有广泛应用的组合优化问题，属于 N P难题。一种改进的

蚁群优化算法可以用于求解 V P R。实验结果表明，用蚁群优化算法能有效求解 V P问题。采 R

【关键词】车辆路径问题； 物流配送；蚁群优化算法；信息素

Ap ia in Re e r h o tCo o y Optm ia in g rt m plc to sa c fAn l n i z to Al o ih f rVe ce Ro i o lm n Lo itcDit i u i n o hil utng Pr b e i g si srb to

XI a-i nj Xi e【 bt c】 V h lr tg r l V P, h h e nso P r l siayi m i tn t i tn rb A s at r eie o i o e c u n p b m( R )w i l g t N o e, t c c b aoao i z i o— c b o p b m s p a o n i l p m ao p ll i l ui e g t i r ui . hrfr, ippr us ow r ni poe n o n pi i t n( C e wd y ti di l ii ds i t n T e oe t s a e p t fr ada rvda t l yot z i A O) m e l z n o sc tb o e h m co m aol o h t ov ag rt m o s le VRP. u, i Th s a VRP b s d o a e n ACO ag r h i i lme td. s ls ft e e p rme t r v h fe— o i m mpe n e Re u t h x e l t s o i n o e t ee fc pt e e so i n s fACO ag rt m n s li g VRP. v o h i ovn l i

【 e od】 vh lr t g r l; g t s btnato n p mztn

( C ) grh;hr oe K y rs eieo i o e l iid t uo; l y t i i A O a o tm pe m n w c u n p b m o sc ir i n c o o i ao i l i o[中图分类号]T 2 P9 (文献标识码] A (文章编号]17 6 4—3 2 (0 10—0 3 2 9 2 1) 6 0 0—0 2

1引言 2 1年 6月 1日，国人民银行发布《 0 0 0 1中 2 1

2蚁群优化算法在物流配送车辆路径问题上的数学模型2 1蚁群优化算法 .蚁群优化 ( n o n pi zt n AC算法 A t l vO .mi i, O) C o t ao是由 D r 0于 19提出的一种新型模拟进化 oi等 g 92年

中国区域金融运行报告》 J¨显示， 0 0年我国全 21社会物流总费用占 G P的 1%左右，高于发达 D 8远

国家 9%左右的水平。由此可见，国的相关物流我企业仅通过优化物流就能缩减成本，加利润。增 所以，如何减少运输成本是降低物流成本的切人点。对于物流企业降低物流成本，科学的排单派车是较为重要和关键的一环，体来讲就是如何具减少送货车辆数、缩短车辆行驶里程，化送货次优序的问题。此问题在运筹学中称为车辆路径问题， RP2 V _已经被证明是一个 NP难问题。对于

算法，其优越的问题分布式求解模式在组合优化问 题的求解中取得了极大成功，蚁群算法模拟真实蚁群的协作过程，已成功解决了一系列问题，如旅行商问题 ( S )分配问题， b hp TP, J—S o调度问题等组合 o优化问题，且取得的结果在解的质量和收敛速度上都优于或至少等效于演化算法、模拟退火算法以及其他一些启发式方法。 22配送车辆路径问题的数学模型 . V P问题一般这样描述为： R对于位置和货物需求量一定的客户点，合理安排车辆及车辆行驶路线， 使车辆在满足相应约束条件即每条配送路径上各客户需要配送货物量之和不超过配送车辆可载容量情况下，将相应货物及时、准确送达，且最终达到配送成本最低目标。设物流配送中心 (配送中心用 O表

V P近年来， R,研究者提出多种方法来解决车辆路

径问题。文献[] 3采用启发式算法，启发式算法针对性较强，但缺乏通用性

;文献[] 4采用遗传算法， 遗传算法又容易陷入局部最优解，参考以上成果， 本文提出一种改进的蚁群优化算法，于求解用V RP

[收稿日期] 2 1—1 8 0 1 0—2[作者简介]席先杰 (9 2,, 17一)男台州职业技术学院计算机工程系教师，高级工程师，究方向：研软件设计，计算机专业教学。

3 0

本文来源：https://www.bwwdw.com/article/xw64.html