基于蚁群算法的物流配送多路径优化问题研究
|
摘要
物流配送车辆路径优化,是物流系统优化中关键的一环。对物流配送车辆路线进行优化,可以提高经济效益、实现物流科学化。对配送车辆线路优化的理论与方法进行系统研究是物流集约化发展、构建综合物流系统、建立现代调度指挥系统、发展智能交通运输系统和开展电子商务的基础。
物流配送车辆路径优化问题计算复杂,属于NP-hard问题。本文研究了有条件限制的多车辆路径优化问题模型的构建,引入了蚁群算法(Ant System,AS),将其进行了改进,并成功运用于有条件限制的多车辆路径优化问题,并结合Google Map,增加优化路径时所需数据的有效性和对车辆实时信息管理的有效性。本文的主要工作:
(1)深入研究蚁群算法的基本原理,并提出了改进方案,在不同阶段使用不同的更新策略,前期增加搜索的广度,后期加快算法收敛。
(2)建立有条件限制的多车辆物流配送路径优化问题的数学模型,讨论多车辆与单车辆情况的不同点,结合蚁群优化算法实现该模型,讨论算法实现过程中需要注意的问题。
(3)结合Google Map实现一个原型系统,通过使用Google Map获取真实的数据、对车辆提供导航信息、帮助对车辆进行管理。
物流配送车辆调度优化,是物流配送优化中关键的一环,也是电子商务活动不可缺少的内容。对货运车辆进行调度优化,可以提高物流经济效益、实现物流科学化。对货运车辆调度优化理论与方法进行系统研究是物流集约化发展、建立现代调度指挥系统、发展智能交通运输系统和开展电子商务的基础。目前,问题的形式已有很大发展,该问题以不仅仅局限于汽车运输领域,在水运、航空、通讯、电力、工业管理、计算机应用等领域也有一定的应用,其算法已用于航空乘务员轮班安排、轮船公司运送货物经过港口与货物安排的优化设计、交通车线路安排、生产系统中的计划与控制等多种组合优化问题。
Vehicle routing optimization in logistics is one of the most critical parts in logistics. It can improve the economic benefit and realize the scientific process of logistics. The study of vehicle scheduling optimization theory and method definitely has its significant importance. It can enhance the intensive development of logistics; construct integrated logistics system and modern scheduling system of command; develop intelligent traffic transportation system and be a basic platform of electronic business.
Vehicle Routing Problem is a NP-hard problem. In this paper, the model of Vehicle Routing Problem of multi car is built, then introduces and improves Ant System, which is successfully applied for Vehicle Routing Problem of multi vehicle.
(1) Make further study of basic principle of ant algorithm, at different stages we are using different update strategy: we increase the breadth of search in early stage, we accelerate the convergence late.
(2) We build the conditional multi-vehicle logistics path optimization logistics model combined with ant colony optimization algorithm, discuss the differences between multi-vehicle and single vehicle and the issues of algorithm implementation process.
(3) We achieve a prototype system integrated with Google Map. In this prototype system, We gather the real data and help manage vehicle by using the this prototype system. VSP is both a pivotal tache in logistic distribution optimization and indispensable in electronic commerce. It can increase logistic economic benefit and realize logistic rationalization.. Now, the problem is not only applied to the field of auto transportation, but also to ship, avigation, communication, electricity, industry management, computer application etc. The algorithm has been applied into many combinatorial optimization problems such as the trainman's shift arrangement in avigation, the optimization design of cargo arrangement in ship company, traffic routing arrangement, and the plan and control in the production system.
物流配送车辆路径优化问题计算复杂,属于NP-hard问题。本文研究了有条件限制的多车辆路径优化问题模型的构建,引入了蚁群算法(Ant System,AS),将其进行了改进,并成功运用于有条件限制的多车辆路径优化问题,并结合Google Map,增加优化路径时所需数据的有效性和对车辆实时信息管理的有效性。本文的主要工作:
(1)深入研究蚁群算法的基本原理,并提出了改进方案,在不同阶段使用不同的更新策略,前期增加搜索的广度,后期加快算法收敛。
(2)建立有条件限制的多车辆物流配送路径优化问题的数学模型,讨论多车辆与单车辆情况的不同点,结合蚁群优化算法实现该模型,讨论算法实现过程中需要注意的问题。
(3)结合Google Map实现一个原型系统,通过使用Google Map获取真实的数据、对车辆提供导航信息、帮助对车辆进行管理。
物流配送车辆调度优化,是物流配送优化中关键的一环,也是电子商务活动不可缺少的内容。对货运车辆进行调度优化,可以提高物流经济效益、实现物流科学化。对货运车辆调度优化理论与方法进行系统研究是物流集约化发展、建立现代调度指挥系统、发展智能交通运输系统和开展电子商务的基础。目前,问题的形式已有很大发展,该问题以不仅仅局限于汽车运输领域,在水运、航空、通讯、电力、工业管理、计算机应用等领域也有一定的应用,其算法已用于航空乘务员轮班安排、轮船公司运送货物经过港口与货物安排的优化设计、交通车线路安排、生产系统中的计划与控制等多种组合优化问题。
Vehicle routing optimization in logistics is one of the most critical parts in logistics. It can improve the economic benefit and realize the scientific process of logistics. The study of vehicle scheduling optimization theory and method definitely has its significant importance. It can enhance the intensive development of logistics; construct integrated logistics system and modern scheduling system of command; develop intelligent traffic transportation system and be a basic platform of electronic business.
Vehicle Routing Problem is a NP-hard problem. In this paper, the model of Vehicle Routing Problem of multi car is built, then introduces and improves Ant System, which is successfully applied for Vehicle Routing Problem of multi vehicle.
(1) Make further study of basic principle of ant algorithm, at different stages we are using different update strategy: we increase the breadth of search in early stage, we accelerate the convergence late.
(2) We build the conditional multi-vehicle logistics path optimization logistics model combined with ant colony optimization algorithm, discuss the differences between multi-vehicle and single vehicle and the issues of algorithm implementation process.
(3) We achieve a prototype system integrated with Google Map. In this prototype system, We gather the real data and help manage vehicle by using the this prototype system. VSP is both a pivotal tache in logistic distribution optimization and indispensable in electronic commerce. It can increase logistic economic benefit and realize logistic rationalization.. Now, the problem is not only applied to the field of auto transportation, but also to ship, avigation, communication, electricity, industry management, computer application etc. The algorithm has been applied into many combinatorial optimization problems such as the trainman's shift arrangement in avigation, the optimization design of cargo arrangement in ship company, traffic routing arrangement, and the plan and control in the production system.
引文
[1]于芹,翁正新;基于蚁群算法的物流车辆路径优化问题的研究.
[2] Dantzig G, Ramser J.; The trunk dispatching problem[J], Management Science 1959(6): 80-91
[3] Christofides N., Mingozzi A., Toth P.; The Vehicle Routing Problem[C], Combinational Optimizaton, New York'Johnly Wiley, 1979
[4] Clark G.and Wright., Scheduling of vehicles from a central depot to a number of delivery points, Opens, Res; 1964, No.4.
[5] Billy E. Gillet and Leland R. Miller; A Heuristic Algorithm for the vehicle dispatch Problem. Operation Research, Vol. 22, 340-349, 1974.
[6] Willard J. A. G.; Vehicle Routing using P-optimal Tabu Search. M.S. thesis, Management School, Imperial College, London. 1989.
[7] Michel Gendreau, Alain Hertz, and Gilbert Laporte; A Tabu Search Heuristic for the Vehicle Routing Problem. Management Science, Vo1.40, No.10, 1276-1290. 1994.
[8] Barbarosoglu G. and Ozgur D.; A Tabu Search Algorithm for The Vehicle Routing Problem. Computers & Operations Research, Vol.26, 255-270. 1999.
[9] C. T. Su and H. H. Chen; Vehicle Routing Design of Physical Distribution Center. Journal of the Chinese Institute of Industrial Engineers, Vol. 16, No.3, 410-417. 1999.
[10]李军,郭耀煌;物流配送车辆优化调度理论与方法[M].北京:中国物资出版社, 2001.
[11]李人卫等;遗传算法在有时间窗车辆路径问题上的应用[J].系统工程理论与实践, 1999, 19(8).
[12]蔡延光,钱积新,孙优贤;多重运输调度问题模拟退火算法,系统工程理论与实践, 1998(10) 10-1.
[13]李大卫,王莉,王梦光;遗传算法在有时间窗车辆路径问题上的应用,系统工程理论与实践.
[14]姜大立,杨西龙,杜文,周贤伟;车辆路径问题的遗传算法研究,系统工程理论与实践, 1999.
[15] M. Dorigo and L. M. Gambardella. Ant colony system: A cooperative learning approach tothe traveling salesman problem. IEEE Transactions on Evolutionary Computation, 1(1):53-66, 1997.
[16] Marco Dorigo, Vittorio Maniezzo, Alberto Colnrni; Ant System: Optimization by a Colony of Cooperating Agents. IEEE Transactions on Systems, Man, and Cybernetics-PART B: Cybernetics, VOL. 26, No. 1, Feb. 1996.
[17] Dorigo M; Optimization, Learning and Natural Algorithm (in Italian) [M]. Ph.D. thesis Dipartimento di Elettronica, Politecnico di Milano, 1992.
[18] Colorni A, Dorigo M, and Maniezzo V; Distributed optimization by ant colonies [C]. In Proceedings of the First European Conference on Artificial Life. Elsevier, 1992. 134-142.
[19] Colorni A, Dorigo M, Maffioli F, Maniezzo V and Trubian M; Heuristics from nature for combinatorial problems [J]. International Transactions in Operational Research, 1996, 3(1): 1-21.
[20] Dorigo M and Di Caro G; The Ant Colony Optimization meta-heuristic [C]. In Corne D, Dorigo M, and Glover F, New Ideas in Optimization. London: McGraw Hill, 1999. 11-32.
[21] Dorigo M and Stutzle T; Ant Colony Optimization [M]. MIT Press, 2004.
[22] Gambardella L. M. and Dorigo M.; Solving Symmetric and Asymmetric TSPs by Ant Colony. Proceedings of IEEE International Conference, 1996. 622-627.
[23] T. Stutzle and H. Hoos. The MAX-MIN ant system and local search for the traveling salesman problem. In T. Back, Z. Michalewicz, and X. Yao, editors, Proceedings of the 1997 IEEE International conference on Evolutionary Computation (ICEC'97), pp. 137154. Piscataway, NJ, IEEE Press.
[24]吴庆洪,张继会,徐心和;具有变异特征的蚁群算法,计算机研究与发展, 1999, 36(10): 1240-1245.
[25]陈烨;带杂交算子的蚁群算法,计算机工程, 2001, (12), 74-76.
[26]王颖,谢剑英;一种自适应蚁群算法及其仿真研究,系统仿真学报, 2002年1月,第14卷第1期, 31-33.
[27]曹浪财,罗键,李大成;智能蚁群算法一蚁群算法的改进[J].计算机应用研究, 2003(l0): 62-64.
[28]李士勇;蚁群算法及其应用[M].哈尔滨:哈尔滨工业大学出版社, 2004.09.
[29] Jun Wu, Dingfang Chen; Simulation on Ant Colony Optimization for TSP[C]. The 8th International Conference on Computer-aided Industrial Design & Conceptual Design. 2007.08.
[30] Costa D., Hertz A and Dubuis O., Imbedding of a sequential algorithm within an evolutionary algorithm for coloring problem in graphs, Janu. of heuristics, 1989, 20(1), 105-128.
[31] Bilchev G. and Parmee I. C., Searching heavily constrained design spaces. In: Proc. of 22nd Int. Conf. Computer Aided Design‘95. Yelta, Ukraine, 1995, 230-235.
[32]魏平,熊伟清;用于一般函数优化的蚁群算法,宁波大学学报, 2001, 14(4), 52-55.
[33]伍文城,肖建,基十蚁群算法的中国旅行商问题满意解,计算机与现代化, 2002, 4: 6-8.
[34]叶志伟,郑肇葆.蚁群算法中参数α,β,ρ设置的研究[J].武汉大学学报(信息科学版), 2004. 7. 29(7).
[35] M.Dorigo. Optimization, Learning and Natural Algorithms[in Italian]. PhD thesis[A], Dipartimento di Elettroico, Politecnico di Milano, Milan, 1992.
[36] M.Dorigo, V.Maniezzo & A.Colorni, Positive feedback as a search strategy[R]. Technical report 91-016, Dipartmento di Elettronica, Politecnico di Milano, Milan, 1991.
[37] B.Bullnheimer, R.F.Hartl & C.Strauss. Anew rank-based version of the Ant System: A computational study. Central European Journal for Operations Research and Economics[J], &(1), 25-38, 1999.
[38]左洪浩.蚁群优化算法及其应用研究[D].中国科技大学博士论文, 2006年10月.
[39]丁立言,张铎;物流基础.北京:清华大学出版社. 2000. 4. P15.
[40]菊池康也著,丁立言译;物流竹理.北京:清华大学出版社. 1999. 10. P76.
[41]宋华,胡左浩.现代物流与供应链竹理.北京:经济竹理出版社. 2000. 5. P294-299.
[42]董千里;高级物流学.北京:人民交通出版社. 1999. P153-182.
[43]国家物流标准术语.中国物质流通. 2001. 16. P38-40.
[44] Rego C.A Subpath Ejection Method for the Vehicle Routing Problem Management Science, l998, (10): P1447-1459.
[45]李军.物流配送车辆优化调度理论[M].北京:中国物资出版社, 2001, P47-52.
[46]胡运权.运筹学教程[M].北京:清华大学出版社, 1998. P101-121.
[2] Dantzig G, Ramser J.; The trunk dispatching problem[J], Management Science 1959(6): 80-91
[3] Christofides N., Mingozzi A., Toth P.; The Vehicle Routing Problem[C], Combinational Optimizaton, New York'Johnly Wiley, 1979
[4] Clark G.and Wright., Scheduling of vehicles from a central depot to a number of delivery points, Opens, Res; 1964, No.4.
[5] Billy E. Gillet and Leland R. Miller; A Heuristic Algorithm for the vehicle dispatch Problem. Operation Research, Vol. 22, 340-349, 1974.
[6] Willard J. A. G.; Vehicle Routing using P-optimal Tabu Search. M.S. thesis, Management School, Imperial College, London. 1989.
[7] Michel Gendreau, Alain Hertz, and Gilbert Laporte; A Tabu Search Heuristic for the Vehicle Routing Problem. Management Science, Vo1.40, No.10, 1276-1290. 1994.
[8] Barbarosoglu G. and Ozgur D.; A Tabu Search Algorithm for The Vehicle Routing Problem. Computers & Operations Research, Vol.26, 255-270. 1999.
[9] C. T. Su and H. H. Chen; Vehicle Routing Design of Physical Distribution Center. Journal of the Chinese Institute of Industrial Engineers, Vol. 16, No.3, 410-417. 1999.
[10]李军,郭耀煌;物流配送车辆优化调度理论与方法[M].北京:中国物资出版社, 2001.
[11]李人卫等;遗传算法在有时间窗车辆路径问题上的应用[J].系统工程理论与实践, 1999, 19(8).
[12]蔡延光,钱积新,孙优贤;多重运输调度问题模拟退火算法,系统工程理论与实践, 1998(10) 10-1.
[13]李大卫,王莉,王梦光;遗传算法在有时间窗车辆路径问题上的应用,系统工程理论与实践.
[14]姜大立,杨西龙,杜文,周贤伟;车辆路径问题的遗传算法研究,系统工程理论与实践, 1999.
[15] M. Dorigo and L. M. Gambardella. Ant colony system: A cooperative learning approach tothe traveling salesman problem. IEEE Transactions on Evolutionary Computation, 1(1):53-66, 1997.
[16] Marco Dorigo, Vittorio Maniezzo, Alberto Colnrni; Ant System: Optimization by a Colony of Cooperating Agents. IEEE Transactions on Systems, Man, and Cybernetics-PART B: Cybernetics, VOL. 26, No. 1, Feb. 1996.
[17] Dorigo M; Optimization, Learning and Natural Algorithm (in Italian) [M]. Ph.D. thesis Dipartimento di Elettronica, Politecnico di Milano, 1992.
[18] Colorni A, Dorigo M, and Maniezzo V; Distributed optimization by ant colonies [C]. In Proceedings of the First European Conference on Artificial Life. Elsevier, 1992. 134-142.
[19] Colorni A, Dorigo M, Maffioli F, Maniezzo V and Trubian M; Heuristics from nature for combinatorial problems [J]. International Transactions in Operational Research, 1996, 3(1): 1-21.
[20] Dorigo M and Di Caro G; The Ant Colony Optimization meta-heuristic [C]. In Corne D, Dorigo M, and Glover F, New Ideas in Optimization. London: McGraw Hill, 1999. 11-32.
[21] Dorigo M and Stutzle T; Ant Colony Optimization [M]. MIT Press, 2004.
[22] Gambardella L. M. and Dorigo M.; Solving Symmetric and Asymmetric TSPs by Ant Colony. Proceedings of IEEE International Conference, 1996. 622-627.
[23] T. Stutzle and H. Hoos. The MAX-MIN ant system and local search for the traveling salesman problem. In T. Back, Z. Michalewicz, and X. Yao, editors, Proceedings of the 1997 IEEE International conference on Evolutionary Computation (ICEC'97), pp. 137154. Piscataway, NJ, IEEE Press.
[24]吴庆洪,张继会,徐心和;具有变异特征的蚁群算法,计算机研究与发展, 1999, 36(10): 1240-1245.
[25]陈烨;带杂交算子的蚁群算法,计算机工程, 2001, (12), 74-76.
[26]王颖,谢剑英;一种自适应蚁群算法及其仿真研究,系统仿真学报, 2002年1月,第14卷第1期, 31-33.
[27]曹浪财,罗键,李大成;智能蚁群算法一蚁群算法的改进[J].计算机应用研究, 2003(l0): 62-64.
[28]李士勇;蚁群算法及其应用[M].哈尔滨:哈尔滨工业大学出版社, 2004.09.
[29] Jun Wu, Dingfang Chen; Simulation on Ant Colony Optimization for TSP[C]. The 8th International Conference on Computer-aided Industrial Design & Conceptual Design. 2007.08.
[30] Costa D., Hertz A and Dubuis O., Imbedding of a sequential algorithm within an evolutionary algorithm for coloring problem in graphs, Janu. of heuristics, 1989, 20(1), 105-128.
[31] Bilchev G. and Parmee I. C., Searching heavily constrained design spaces. In: Proc. of 22nd Int. Conf. Computer Aided Design‘95. Yelta, Ukraine, 1995, 230-235.
[32]魏平,熊伟清;用于一般函数优化的蚁群算法,宁波大学学报, 2001, 14(4), 52-55.
[33]伍文城,肖建,基十蚁群算法的中国旅行商问题满意解,计算机与现代化, 2002, 4: 6-8.
[34]叶志伟,郑肇葆.蚁群算法中参数α,β,ρ设置的研究[J].武汉大学学报(信息科学版), 2004. 7. 29(7).
[35] M.Dorigo. Optimization, Learning and Natural Algorithms[in Italian]. PhD thesis[A], Dipartimento di Elettroico, Politecnico di Milano, Milan, 1992.
[36] M.Dorigo, V.Maniezzo & A.Colorni, Positive feedback as a search strategy[R]. Technical report 91-016, Dipartmento di Elettronica, Politecnico di Milano, Milan, 1991.
[37] B.Bullnheimer, R.F.Hartl & C.Strauss. Anew rank-based version of the Ant System: A computational study. Central European Journal for Operations Research and Economics[J], &(1), 25-38, 1999.
[38]左洪浩.蚁群优化算法及其应用研究[D].中国科技大学博士论文, 2006年10月.
[39]丁立言,张铎;物流基础.北京:清华大学出版社. 2000. 4. P15.
[40]菊池康也著,丁立言译;物流竹理.北京:清华大学出版社. 1999. 10. P76.
[41]宋华,胡左浩.现代物流与供应链竹理.北京:经济竹理出版社. 2000. 5. P294-299.
[42]董千里;高级物流学.北京:人民交通出版社. 1999. P153-182.
[43]国家物流标准术语.中国物质流通. 2001. 16. P38-40.
[44] Rego C.A Subpath Ejection Method for the Vehicle Routing Problem Management Science, l998, (10): P1447-1459.
[45]李军.物流配送车辆优化调度理论[M].北京:中国物资出版社, 2001, P47-52.
[46]胡运权.运筹学教程[M].北京:清华大学出版社, 1998. P101-121.