全部 标题 作者
关键词 摘要

OALib Journal期刊
ISSN: 2333-9721
费用:99美元

查看量下载量

相关文章

更多...

蚁群算法及其在有硬时间窗的车辆路径问题中的应用

, PP. 0-0

Keywords: 有硬时间窗的车辆路径问题,自适应混合蚁群算法,可行解两阶段构造策略,回路两阶段构造策略,紧迫性因子,匹配度因子

Full-Text   Cite this paper   Add to My Lib

Abstract:

为求解有硬时间窗的车辆路径问题,提出了一种基于可行解两阶段构造策略的自适应混合蚁群算法。在第一阶段,用蚂蚁的局部遍历代替传统的全局遍历,每个蚂蚁采用蚁群算法进行局部遍历,构造一个回路,蚂蚁转移采用回路两阶段构路策略;在第二阶段,由前一阶段所构造的回路通过采用近似解可行化策略来组合形成可行解。此外,为提高算法的寻优能力,在转移规则中引入了基于时间窗的紧迫性因子和匹配度因子,并与节约算法和爬山法有机结合。实验结果表明,自适应混和蚁群算法性能优良,能够有效地求解有硬时间窗的车辆路径问题。

References

[1]  ??BALINSKI M, QUANDT R.On an integer program for a delivery problem[J].Operation Research,1962,10(2):300-304.
[2]  ??RAO M R,ZIONT S.Allocation of transportation units to alternative trips-a column generation scheme with out-of-kilter sub-problems[J].Operation Research,1968,15(1):52-63.
[3]  ??BERGER J, BARKAOUI M.A parallel hybrid genetic algorithm for the vehicle routing problem with time windows[J].Computers and Operations Research,2004,31(12):2037-2053.
[4]  ??LI Dawei,WANG Li,WANG Mengguang.Genetic a1gorithm for vehicle routing problem with time windows[J].Systems Engineering-Theory & Practice,1999,19(8):65-69(in Chinese).[李大卫,王??莉,王梦光.遗传算法在有时间窗车辆路径问题上的应用[J].系统工程理论与实践,1999,19(8):65-69.]
[5]  ??ZHANG Liping,CHAI Yueting,CAO Rui.Improved genetic a1gorithm for vehicle routing problem with time windows[J].Computer Integrated Manufacturing Systems,2002,8(6):451-454(in Chinese).[张丽萍,柴跃廷,曹??瑞.有时间窗车辆路径问题的改进遗传算法[J].计算机集成制造系统,2002,8(6):451-454.]
[6]  ??BADEAU P,GUERTIN F, GENDREAU M,et al.A parallel tabu search heuristic for the vehicle routing problem with time windows[J].Transportation Research Part C: Emerging Technologies,1997,5(2):109-122.
[7]  ??PHILIPPE B,FRANCIOS G.A parallel tabu search heuristic for the vehicle routing problem with time window[J].Transportation Research Part C,1997,5(2):109-122.
[8]  ??ZHANG Jiong,LANG Maoxiang.The tabu search algorithm of distribution vehicle scheduling problem with time windows[J].Journal of Northern Jiaotong University,2004,28(2):103-106(in Chinese).[张??迥,郎茂祥.有时间窗配送车辆调度问题的禁忌搜索算法[J].北方交通大学学报,2004,28(2):103-106.]
[9]  ??TAN K C, LEE L H, OU K.Artificial intelligence heuristics in solving vehicle routing problems with time window constraints[J].Engineering Applications of Artificial Intelligence,2001,14(6):825-837.
[10]  ??DORIGO M, MANIEZZO V, COLORNI A.Ant system:optimization by a colony of cooperating agents[A].IEEE Transaction on System,Man,and Cybernetics,1996,26(1):29-41.
[11]  ??MANIEZZO V,COLORNI A.An ants heuristic for the frequency assignment problem[J].Future Generation Computer Systems,2000,16(8):927-935.
[12]  ??COLORNI A,DORIGO M,MANIEZZO V,et al.Ant system for job shop scheduling[J].Operations Research,1994,34(1):39-53.
[13]  ??JOHN E B,PATRICK R M.Ant colony optimization techniques for the vehicle routing problem[J].Advanced Engineering Informatics,2004,18:41-48.
[14]  ??REIMANN M,DOERNER K, HARTL R F.D-ants: savings based ants divide and conquer the vehicle routing problem[J].Computers & Operations Research,2004,31:563-591.
[15]  ??GAMBARDELLA L M, TAILLARD E, AGAZZI G.MACS-VRPTW:a multiple ant colony system for vehicle routing problems with time windows[A].New Ideas in Optimization[C].London,U.K.:McGraw-Hill,1999.63-73.
[16]  ??REIMANN M, DORENER K, HARTL R F.Insertion based ants for vehicle routing problems with backhauls and time windows[A].Ant Algorithms[C].Berlin/Heidelberg,Germany:Springer LNCS 2463,2002.135-147.
[17]  ??LIU Zhishuo.Study on theory and method of intelligent logistics system[D].Beijing:Beijing Jiaotong University,2004(in Chinese).[刘志硕.智能物流系统理论与方法研究[D].北京:北京交通大学,2004.]
[18]  ??DORIGO M, LUCA M.A study of some properties of ant-Q[A].Proceedings of 4th International Conference on Parallel Problem Solving form Nature (PPSN) [C].Berlin,Germany:Springer Verlag,1996.656-665.
[19]  ??CLARCK G, WRIGHT J W.Scheduling of vehicles form a central depot to a number of delivery points[J].Operations Research,1964,12(4):568-581.
[20]  ??STUTZLE T, HOOS H.MAX-MIN ant system[J].Future Generation Computer Systems Journal,2000,16(8): 889-914.
[21]  ??LANG Maoxiang.Study on models and algorithms for distribution vehicle scheduling problem[D].Beijing:Beijing Jiaotong University,2002(in Chinese).[郎茂祥.物流配送车辆调度问题的模型与算法研究[D].北京:北京交通大学,2002.]

Full-Text

Contact Us

service@oalib.com

QQ:3279437679

WhatsApp +8615387084133