物流配送企业集配货一体化VRP研究
|
摘要
配送车辆的路径规划问题,是物流配送优化中的一个关键环节,也是困扰物流配送企业由来已久的难题。从文献查阅来看,目前对车辆路径规划问题的研究大都集中于单向的物流配送,而对集货业务和配货业务同时存在的双向物流的研究还很不成熟。本文从企业实际配送需求出发,考虑客户点同时存在集配货混合作业的双向物流情况,允许在客户点同时进行集货作业和配货作业,即配送车辆只需服务客户一次,就可以满足客户点的配货和集货需求,展开集配货一体化路径规划问题研究与实例分析。
首先,本文介绍了研究背景,回顾了车辆路径规划问题的研究现状,针对前人的不足,阐述了本文研究的意义,并提出了本文的主要研究内容。
其次,通过对现实问题的深入研究,对车辆出行成本加以考虑,并考虑车辆从物流配送中心出发时的满载情况,设定了问题的假设条件和参数,并对各种约束条件进行抽象化、数学化,最终建立了集配货一体化车辆路径规划问题的更加符合现实情况的数学模型。
然后,选择了模拟退火算法对集配货一体化车辆路径规划问题数学模型进行求解。介绍了模拟退火算法的基本原理及其在组合优化方面的应用,并分析了其优缺点。针对其存在的缺点,本文对算法邻域操作策略进行了改进,以扩大其搜索解空间的能力,为算法添加了记忆功能,以得到算法每次计算的最优解,并改进了算法的终止准则,以合理节省算法的迭代步数。进而将其应用于求解集配货一体化车辆路径规划问题。
最后,本文选取了权威数据对算法进行测试计算,结果表明,本文设计的算法具有可行性和优越性。进而以某物流配送企业位于长沙定王台的图书配送中心为实例,进行了集配货一体化车辆路径规划问题的应用研究。
The vehicles routing optimization is a key link in the logistics distribution optimization, as well as is the hard problem of logistics distribution enterprises. But the solution of the vehicle routing problem in former research often focuses on unidirectional logistics distribution. And the research of bi-directional logistics is still immature. According to the reality, this article considers the situation that a customer point exits bi-directional logistics and is allowed to delivery and pick up goods at the same time. In other words, the vehicle meets the customers’needs of pick-up and delivery by only once service which called the vehicle routing problem with pick-up and delivery (VRPPD). This paper researches on the VRPPD and analyses an example of it.
Firstly, the paper introduces the research background and reviews the current research status of vehicle routing problem. According to the lack of previous researches, the author describes the significance of this research and puts forward the main content of this paper.
Secondly, the paper sets the assumptions and parameters of VRPPD by researching practical problems and considering the vehicle fixed cost and the full load of vehicle when it start from distribution center. Through the abstraction and mathematization of various constraints and setting up the parameter and premise of the reaseach, finally, the paper builds a more reality mathematical model of VRPPD.
Then, the paper chooses simulated annealing algorithm to solve VRPPD, and introduces the basic principles of simulated annealing algorithm and its application of combinatorial optimization and analysis of its advantages and disadvantages as well. According to its disadvantages the author try to improve the algorithm strategy to enlarge the ability of searching solution space and designs a new simulated annealing algorithm with memory function for VRPPD.
Finally, the paper selects authoritative date to test the algorithm. Compared to the experimental results, the algorithm designed by this paper is feasibility and superiority. At last, the algorithm is proved working when the paper takes the example of a logistics enterprise in Changsha for Dingwangtai books distribution.
首先,本文介绍了研究背景,回顾了车辆路径规划问题的研究现状,针对前人的不足,阐述了本文研究的意义,并提出了本文的主要研究内容。
其次,通过对现实问题的深入研究,对车辆出行成本加以考虑,并考虑车辆从物流配送中心出发时的满载情况,设定了问题的假设条件和参数,并对各种约束条件进行抽象化、数学化,最终建立了集配货一体化车辆路径规划问题的更加符合现实情况的数学模型。
然后,选择了模拟退火算法对集配货一体化车辆路径规划问题数学模型进行求解。介绍了模拟退火算法的基本原理及其在组合优化方面的应用,并分析了其优缺点。针对其存在的缺点,本文对算法邻域操作策略进行了改进,以扩大其搜索解空间的能力,为算法添加了记忆功能,以得到算法每次计算的最优解,并改进了算法的终止准则,以合理节省算法的迭代步数。进而将其应用于求解集配货一体化车辆路径规划问题。
最后,本文选取了权威数据对算法进行测试计算,结果表明,本文设计的算法具有可行性和优越性。进而以某物流配送企业位于长沙定王台的图书配送中心为实例,进行了集配货一体化车辆路径规划问题的应用研究。
The vehicles routing optimization is a key link in the logistics distribution optimization, as well as is the hard problem of logistics distribution enterprises. But the solution of the vehicle routing problem in former research often focuses on unidirectional logistics distribution. And the research of bi-directional logistics is still immature. According to the reality, this article considers the situation that a customer point exits bi-directional logistics and is allowed to delivery and pick up goods at the same time. In other words, the vehicle meets the customers’needs of pick-up and delivery by only once service which called the vehicle routing problem with pick-up and delivery (VRPPD). This paper researches on the VRPPD and analyses an example of it.
Firstly, the paper introduces the research background and reviews the current research status of vehicle routing problem. According to the lack of previous researches, the author describes the significance of this research and puts forward the main content of this paper.
Secondly, the paper sets the assumptions and parameters of VRPPD by researching practical problems and considering the vehicle fixed cost and the full load of vehicle when it start from distribution center. Through the abstraction and mathematization of various constraints and setting up the parameter and premise of the reaseach, finally, the paper builds a more reality mathematical model of VRPPD.
Then, the paper chooses simulated annealing algorithm to solve VRPPD, and introduces the basic principles of simulated annealing algorithm and its application of combinatorial optimization and analysis of its advantages and disadvantages as well. According to its disadvantages the author try to improve the algorithm strategy to enlarge the ability of searching solution space and designs a new simulated annealing algorithm with memory function for VRPPD.
Finally, the paper selects authoritative date to test the algorithm. Compared to the experimental results, the algorithm designed by this paper is feasibility and superiority. At last, the algorithm is proved working when the paper takes the example of a logistics enterprise in Changsha for Dingwangtai books distribution.
引文
[1]林自葵,汝宜红,郑凯.我国图书物流的现状与发展对策.图书·情报·知识, 2004, (4): 45-47.
[2] Gregory Gutin, Abraham P. Punnen. The Traveling Salesman Problem and Its Variations. Boston: Kluwer Academic Publishers, 2002, 1-7.
[3]李军民,林淑飞,高让礼.用混合遗传算法求解多目标TSP问题.西安科技大学学报, 2006, 19(4): 515-518.
[4]王会颖,贾瑞玉,刘慧婷等.一种求解TSP问题的分段交换蚁群算法.计算机工程与应用, 2006, 46(35): 30-32.
[5]胡大伟,陈诚,郭晓汾.带集货和配送的多站点VRP优化算法研究.数学的实践与认识, 2007, 37(2): 98-104.
[6] Laporte G, Nobert Y. Exact algorithm for the vehicle routing problem. Amsterdam: North-Holland Publishing, 1987, 47-84.
[7] Eleni Hadjiconstantinou, Nicos Christofides, Aristide Mingozzi. A new exact algorithm for the vehicle routing problem based on q-path and k-shortest path relaxations. Annals of Operations Research, 1995, 61(1): 21-43.
[8] Fisher M L. Vehicle routing with time windows: Two optimization algorithms. Operations Research, 1997, 45(3): 488-492.
[9] Dimitris J. Bertsimas, David Simchi-Levi. A new generation of vehicle routing research: robust algorithms, addressing uncertainty. Operations Research, 1996, 44(2): 286-304.
[10] G. Clarke, J. W. Wright. Scheduling of vehicles from a central depot to a number of delivery points. Operations Research, 1964, 12(4): 568-581.
[11] Glover F. Tabu search: part I. Journal on Computing, 1989, 3(1): 190-206.
[12] Laporte G. The vehicle routing problem: An overview of exact and approximate algorithm. European J of Op erational Research, 1992, 59(3): 345-358.
[13] Osman I H. Metastrategy simulated annealing and tabu search algorithm for combinatorial optimization problems. Annals of Operations Research, 1993, 41(3): 421-451.
[14] Holland J. Adaption in natural and artificial 5f. Ann Arbor: The University of Michigan Press, 1975, 336-354.
[15] Ombuki B M, Nakamura M, Osamu M. A hybrid search based on genetic algorithms and tabu search for vehicle routing. In: IASTED InternationalConference on Artificial Intelligence and Soft Computing. Palma de Mallorca, 2002, 247-251.
[16] R Bent, P Van Hentenryck. A two-stage hybrid local search for the vehicle routing problem with time windows. Transportation Science, 2004, 38 (4): 515-530.
[17] Golden B L, Baker E K, Alfaro J L,et al. The vehicle routing problem with backhauling: two approaches. Working Paper MS/S, University of Maryland, College Park, 1985, 103-119.
[18] Casco Do, Golden B L, Wasil E A. Vehicle routing with backhauls: models algorithms, and case studies. Elsevier: Amsterdam, 1988, 127-147.
[19] Salhi S, Nagy G. A cluster inserition heuristic for single and multiple deport vehicle routing problems with backhauling. Journal of the Operational Research Society, 1999, 50(1): 1034-1042.
[20] Mosheiov G. The travelling salesman problem with pick-up and delivery. European Journal of Operation Research, 1994, 79(1): 299-310.
[21]蔡延光,钱积新,孙优贤.带有时间窗的多重运输调度问题的自适应Tabu Search算法.系统工程理论与实践, 2000, 20(12): 42-50.
[22]张涛,王梦光.遗传算法和3-opt结合求解带有能力约束的VRP.东北大学学报, 1999, 20(3): 254-256.
[23]李军,郭强,刘建新.组合运输的优化调度.系统工程理论与实践, 2001, 21(2): 117-121.
[24]郎茂祥,胡思继.用混合遗传算法求解物流配送路径优化问题的研究.中国管理科学, 2002, 10(5): 51-56.
[25]邓爱民.城市物流配送系统优化研究: [武汉理工大学博士学位论文].武汉: 2005, 100-119.
[26]张潜,高立群.物流配送路径多目标优化的聚类-改进遗传算法.控制与决策, 2003, 18(4): 418-422.
[27]崔雪丽,马良,范炳全.车辆路径问题(VRP)的蚂蚁搜索算法.系统工程学报, 2004, 19(4): 418-422.
[28]黄红.基于GIS的物流配送系统路径优化的算法.计算机技术与发展, 2006, 16(8): 47-48.
[29]刘敬青.基于TransCAD的物流配送VRP解决方案.权威论坛, 2006, (12): 99-102.
[30]孙丽君,胡祥培,王征.车辆路径规划问题及其求解方法研究进展.系统工程, 2006, 24(11): 31-37.
[31]孙小年,陈幼林,杨东援.装卸一体化车辆路径问题的遗传算法研究.系统工程理论与实践, 2007, (2): 149-152.
[32] Jan Dethloff. Vehicle routing and reverse logistics: the vehicle routing problem with simultaneous delivery and pick-up. OR Spektrum, 2001, 23(12): 79-96.
[33] Lau HC, Liang Z. Pickup and delivery with time windows: algorithms and test case generation. Int J Artif Intell Tools, 2002, 11(1): 455–472.
[34]谢秉磊,李良,郭耀煌.求解配送\收集旅行商问题的模拟退火算法.系统工程理论方法应用, 2002, 11(3): 240-243.
[35]霍佳震,张磊.求解配送\收集旅行商问题的启发式算法.同济大学学报(自然科学版), 2006, 34(1): 134-138.
[36]郎茂祥.装卸混合车辆路径问题的模拟退火算法研究.系统工程学报, 2005, 10(5): 485-491.
[37]姜大立,杨西龙,杜文.车辆路径问题的遗传算法研究.系统工程理论与实践, 1999, 19(6): 40-45.
[38] Asvin Goel, Volker Gruhn. Large Neighborhood Search for rich VRP with multiple pickup and delivery locations. In: 18th Mini Euro Conference on VNS, 2005, 1-11.
[39] Mauro Dell’Amico, Giovanni Righini, Matteo Salani. A branch-and-price approach to the vehicle routing problemwith simultaneous distribution and collection. Transportion Science, 2006, 40(1): 235-247.
[40] J-F Chen and T-H Wu. Vehicle routing problem with simultaneous deliveries and pickups. Journal of the Operational Research Society, 2006, 57(14): 579-587.
[41] Carrabs F, Cordeau J-F, Laporte G. Variable neighbourhood search for the pickup and deliverytraveling salesman problem with LIFO loading. Informs Journal on Computing, 2007, 19(4): 618-632.
[42]蓝伯雄,张跃.求解装-卸载问题的概率式禁忌搜索算法.中国管理科学, 2004, 12(2): 66-72
[43] Ronald H.Ballou著,王晓东,胡瑞娟等译.企业物流管理-供应链的规划组织和控制.北京:机械工业出版社, 2005: 104-129.
[44]康立山,谢云,尤矢勇等.非数值并行计算,第一册.模拟退火算法.北京:科学出版社, 1997, 17-93.
[45] S.Kirkpatrick, C.D.Gelatt Jr., M.P.Vecchi. Optimization by simulated annealing. Science, 1983, 220(4598): 671-680
[46] D.S.Johnson, C.R.Aragon, L.A.Mc Geoch, et al. Optimization by simulated annealing: An experimental evaluation, Part I. AT&T Bell Laboratories, Murray Hill (NJ), 1987, 59-67.
[47] Nahar, S.Sahni, S.Shragowitz. Experiments with simulated annealing. In: Design Automation 22nd conference, 1985, 748-752.
[48] Christopher C.Skiscim, Bruce L.Golden. Optimization by simulated annealing: A preliminary computational study for the TSP. In: the 15th conference on Winter Simulation, 1983, 523-535.
[49] E.H.L. Aarts, J.H.M. Korst. Simulated annealing and Boltzmann Machines. Chichester: John Wiley and Sons, 1989, 90-93.
[50]郎茂祥.物流配送车辆调度问题的模型和算法研究: [北方交通大学博士学位论文].北京:北方交通大学交通运输学院运输管理工程系, 2002, 128-135.
[2] Gregory Gutin, Abraham P. Punnen. The Traveling Salesman Problem and Its Variations. Boston: Kluwer Academic Publishers, 2002, 1-7.
[3]李军民,林淑飞,高让礼.用混合遗传算法求解多目标TSP问题.西安科技大学学报, 2006, 19(4): 515-518.
[4]王会颖,贾瑞玉,刘慧婷等.一种求解TSP问题的分段交换蚁群算法.计算机工程与应用, 2006, 46(35): 30-32.
[5]胡大伟,陈诚,郭晓汾.带集货和配送的多站点VRP优化算法研究.数学的实践与认识, 2007, 37(2): 98-104.
[6] Laporte G, Nobert Y. Exact algorithm for the vehicle routing problem. Amsterdam: North-Holland Publishing, 1987, 47-84.
[7] Eleni Hadjiconstantinou, Nicos Christofides, Aristide Mingozzi. A new exact algorithm for the vehicle routing problem based on q-path and k-shortest path relaxations. Annals of Operations Research, 1995, 61(1): 21-43.
[8] Fisher M L. Vehicle routing with time windows: Two optimization algorithms. Operations Research, 1997, 45(3): 488-492.
[9] Dimitris J. Bertsimas, David Simchi-Levi. A new generation of vehicle routing research: robust algorithms, addressing uncertainty. Operations Research, 1996, 44(2): 286-304.
[10] G. Clarke, J. W. Wright. Scheduling of vehicles from a central depot to a number of delivery points. Operations Research, 1964, 12(4): 568-581.
[11] Glover F. Tabu search: part I. Journal on Computing, 1989, 3(1): 190-206.
[12] Laporte G. The vehicle routing problem: An overview of exact and approximate algorithm. European J of Op erational Research, 1992, 59(3): 345-358.
[13] Osman I H. Metastrategy simulated annealing and tabu search algorithm for combinatorial optimization problems. Annals of Operations Research, 1993, 41(3): 421-451.
[14] Holland J. Adaption in natural and artificial 5f. Ann Arbor: The University of Michigan Press, 1975, 336-354.
[15] Ombuki B M, Nakamura M, Osamu M. A hybrid search based on genetic algorithms and tabu search for vehicle routing. In: IASTED InternationalConference on Artificial Intelligence and Soft Computing. Palma de Mallorca, 2002, 247-251.
[16] R Bent, P Van Hentenryck. A two-stage hybrid local search for the vehicle routing problem with time windows. Transportation Science, 2004, 38 (4): 515-530.
[17] Golden B L, Baker E K, Alfaro J L,et al. The vehicle routing problem with backhauling: two approaches. Working Paper MS/S, University of Maryland, College Park, 1985, 103-119.
[18] Casco Do, Golden B L, Wasil E A. Vehicle routing with backhauls: models algorithms, and case studies. Elsevier: Amsterdam, 1988, 127-147.
[19] Salhi S, Nagy G. A cluster inserition heuristic for single and multiple deport vehicle routing problems with backhauling. Journal of the Operational Research Society, 1999, 50(1): 1034-1042.
[20] Mosheiov G. The travelling salesman problem with pick-up and delivery. European Journal of Operation Research, 1994, 79(1): 299-310.
[21]蔡延光,钱积新,孙优贤.带有时间窗的多重运输调度问题的自适应Tabu Search算法.系统工程理论与实践, 2000, 20(12): 42-50.
[22]张涛,王梦光.遗传算法和3-opt结合求解带有能力约束的VRP.东北大学学报, 1999, 20(3): 254-256.
[23]李军,郭强,刘建新.组合运输的优化调度.系统工程理论与实践, 2001, 21(2): 117-121.
[24]郎茂祥,胡思继.用混合遗传算法求解物流配送路径优化问题的研究.中国管理科学, 2002, 10(5): 51-56.
[25]邓爱民.城市物流配送系统优化研究: [武汉理工大学博士学位论文].武汉: 2005, 100-119.
[26]张潜,高立群.物流配送路径多目标优化的聚类-改进遗传算法.控制与决策, 2003, 18(4): 418-422.
[27]崔雪丽,马良,范炳全.车辆路径问题(VRP)的蚂蚁搜索算法.系统工程学报, 2004, 19(4): 418-422.
[28]黄红.基于GIS的物流配送系统路径优化的算法.计算机技术与发展, 2006, 16(8): 47-48.
[29]刘敬青.基于TransCAD的物流配送VRP解决方案.权威论坛, 2006, (12): 99-102.
[30]孙丽君,胡祥培,王征.车辆路径规划问题及其求解方法研究进展.系统工程, 2006, 24(11): 31-37.
[31]孙小年,陈幼林,杨东援.装卸一体化车辆路径问题的遗传算法研究.系统工程理论与实践, 2007, (2): 149-152.
[32] Jan Dethloff. Vehicle routing and reverse logistics: the vehicle routing problem with simultaneous delivery and pick-up. OR Spektrum, 2001, 23(12): 79-96.
[33] Lau HC, Liang Z. Pickup and delivery with time windows: algorithms and test case generation. Int J Artif Intell Tools, 2002, 11(1): 455–472.
[34]谢秉磊,李良,郭耀煌.求解配送\收集旅行商问题的模拟退火算法.系统工程理论方法应用, 2002, 11(3): 240-243.
[35]霍佳震,张磊.求解配送\收集旅行商问题的启发式算法.同济大学学报(自然科学版), 2006, 34(1): 134-138.
[36]郎茂祥.装卸混合车辆路径问题的模拟退火算法研究.系统工程学报, 2005, 10(5): 485-491.
[37]姜大立,杨西龙,杜文.车辆路径问题的遗传算法研究.系统工程理论与实践, 1999, 19(6): 40-45.
[38] Asvin Goel, Volker Gruhn. Large Neighborhood Search for rich VRP with multiple pickup and delivery locations. In: 18th Mini Euro Conference on VNS, 2005, 1-11.
[39] Mauro Dell’Amico, Giovanni Righini, Matteo Salani. A branch-and-price approach to the vehicle routing problemwith simultaneous distribution and collection. Transportion Science, 2006, 40(1): 235-247.
[40] J-F Chen and T-H Wu. Vehicle routing problem with simultaneous deliveries and pickups. Journal of the Operational Research Society, 2006, 57(14): 579-587.
[41] Carrabs F, Cordeau J-F, Laporte G. Variable neighbourhood search for the pickup and deliverytraveling salesman problem with LIFO loading. Informs Journal on Computing, 2007, 19(4): 618-632.
[42]蓝伯雄,张跃.求解装-卸载问题的概率式禁忌搜索算法.中国管理科学, 2004, 12(2): 66-72
[43] Ronald H.Ballou著,王晓东,胡瑞娟等译.企业物流管理-供应链的规划组织和控制.北京:机械工业出版社, 2005: 104-129.
[44]康立山,谢云,尤矢勇等.非数值并行计算,第一册.模拟退火算法.北京:科学出版社, 1997, 17-93.
[45] S.Kirkpatrick, C.D.Gelatt Jr., M.P.Vecchi. Optimization by simulated annealing. Science, 1983, 220(4598): 671-680
[46] D.S.Johnson, C.R.Aragon, L.A.Mc Geoch, et al. Optimization by simulated annealing: An experimental evaluation, Part I. AT&T Bell Laboratories, Murray Hill (NJ), 1987, 59-67.
[47] Nahar, S.Sahni, S.Shragowitz. Experiments with simulated annealing. In: Design Automation 22nd conference, 1985, 748-752.
[48] Christopher C.Skiscim, Bruce L.Golden. Optimization by simulated annealing: A preliminary computational study for the TSP. In: the 15th conference on Winter Simulation, 1983, 523-535.
[49] E.H.L. Aarts, J.H.M. Korst. Simulated annealing and Boltzmann Machines. Chichester: John Wiley and Sons, 1989, 90-93.
[50]郎茂祥.物流配送车辆调度问题的模型和算法研究: [北方交通大学博士学位论文].北京:北方交通大学交通运输学院运输管理工程系, 2002, 128-135.