带回程取货的逆向物流车辆路径问题研究
|
摘要
随着世界经济的发展和科技的进步,物流产业正在世界范围内迅速发展,即使是长期受到学术界和企业界忽视的逆向物流也随着可持续发展理念的深入人心而成为社会日益关注的话题。然而在我国逆向物流的研究还处于初级阶段,尤其是关于带回程取货的逆向物流车辆路径问题(Vehicle Routing Problems withBackhauls,VRPB)的研究远未成熟。
VRPB问题是车辆路径问题(Vehicle Routing Problems,VRP)的延伸。VRPB问题不像VRP问题那样只考虑车辆运行中的单纯送货或者单纯取货过程,而是将送货与取货过程结合起来,同时实现送货和取货,更加节省运输成本。如何在逆向物流中经济合适地安排车辆的配送路径成为物流管理者面临的一个重要的问题决策。
本文首先介绍了逆向物流的内涵,通过对逆向物流和正向物流车辆路径问题进行比较,指出了逆向物流车辆路径问题的特点。在此基础上,通过对比,指出本文研究的取送交叉VRPB问题和取送无交叉VRPB问题的区别在于放松了取货客户必须在送货客户之后的约束,然后建立无时间窗VRPB问题模型及相关约束。通过对不同算法的比较,最终选择改进遗传算法并进行具体的算法设计,最后以算例进行了验证。
本文还针对物流行业的现状,在VRPB问题上增加了节点的服务时间窗限制,建立了带时间窗VRPB问题(Vehicle Routing Problems with Backhauls and TimeWindows,VRPBTW)模型及相关约束并使用最大-最小蚁群算法进行了具体的算法设计。最后通过对示例求得的结果比较,采用本文设计的算法所求结果优于文献结果,从而在实际中更加节省运输成本,实现了VRPBTW问题的优化。
With the rapid development of the world economy and modern technology, logistics industry is growing quickly all over the world. The reverse logistics which has been ignored by academia and business circle for a long time is gradually being paid attention to because of the implementing gradually thoroughly of sustainable development strategy. In our country the researches of the reverse logistics, particular in the Vehicle Routing Problems with Backhauls (VRPB) is at the threshold compared with foreign research results.
VRPB is the extension of the Vehicle Routing Problems (VRP) which serves only either linehaul customers or backhaul customers. VRPB can serve both linehaul customers and backhaul customers by a fleet of vehicles so that it can reduce the cost of the transportation. How to arrange proper route to cut the cost of logistics operations is a key problem that every logistics manager has to face.
Firstly, the paper introduces the definition of the reverse logistics, points the characteristic of the VRP in the reverse logistics through the comparison of the VRP in the logistics and the reverse logistics. On the basis of this, points that the VRPB which is used in this paper doesn't have the restriction that all backhauls have to be visited after all linehauls as the VRPB which all linehauls and backhauls aren't mixed. Then the VRPB mathematical model and special constraints are analyzed. The VRPB is solved by the improve Genetic Algorithms (GA) which is chose by the comparison of the different algorithms. Finally, illustration is given through a case study.
The paper adds a restriction of time windows on the VRPB on the basis of the reality of logistics industry, and then the Vehicle Routing Problems with Backhauls and Time Windows (VRPBTW) mathematical model and special constraints are analyzed and solved by the Max-Min Ant Colony Algorithms (MMACA). Finally, the results which are solved by the MMACA are better than the traditional algorithms on the example. Therefore, the MMACA can reduce the cost of the transportation in reality so as to realize the optimization of the VRPBTW.
VRPB问题是车辆路径问题(Vehicle Routing Problems,VRP)的延伸。VRPB问题不像VRP问题那样只考虑车辆运行中的单纯送货或者单纯取货过程,而是将送货与取货过程结合起来,同时实现送货和取货,更加节省运输成本。如何在逆向物流中经济合适地安排车辆的配送路径成为物流管理者面临的一个重要的问题决策。
本文首先介绍了逆向物流的内涵,通过对逆向物流和正向物流车辆路径问题进行比较,指出了逆向物流车辆路径问题的特点。在此基础上,通过对比,指出本文研究的取送交叉VRPB问题和取送无交叉VRPB问题的区别在于放松了取货客户必须在送货客户之后的约束,然后建立无时间窗VRPB问题模型及相关约束。通过对不同算法的比较,最终选择改进遗传算法并进行具体的算法设计,最后以算例进行了验证。
本文还针对物流行业的现状,在VRPB问题上增加了节点的服务时间窗限制,建立了带时间窗VRPB问题(Vehicle Routing Problems with Backhauls and TimeWindows,VRPBTW)模型及相关约束并使用最大-最小蚁群算法进行了具体的算法设计。最后通过对示例求得的结果比较,采用本文设计的算法所求结果优于文献结果,从而在实际中更加节省运输成本,实现了VRPBTW问题的优化。
With the rapid development of the world economy and modern technology, logistics industry is growing quickly all over the world. The reverse logistics which has been ignored by academia and business circle for a long time is gradually being paid attention to because of the implementing gradually thoroughly of sustainable development strategy. In our country the researches of the reverse logistics, particular in the Vehicle Routing Problems with Backhauls (VRPB) is at the threshold compared with foreign research results.
VRPB is the extension of the Vehicle Routing Problems (VRP) which serves only either linehaul customers or backhaul customers. VRPB can serve both linehaul customers and backhaul customers by a fleet of vehicles so that it can reduce the cost of the transportation. How to arrange proper route to cut the cost of logistics operations is a key problem that every logistics manager has to face.
Firstly, the paper introduces the definition of the reverse logistics, points the characteristic of the VRP in the reverse logistics through the comparison of the VRP in the logistics and the reverse logistics. On the basis of this, points that the VRPB which is used in this paper doesn't have the restriction that all backhauls have to be visited after all linehauls as the VRPB which all linehauls and backhauls aren't mixed. Then the VRPB mathematical model and special constraints are analyzed. The VRPB is solved by the improve Genetic Algorithms (GA) which is chose by the comparison of the different algorithms. Finally, illustration is given through a case study.
The paper adds a restriction of time windows on the VRPB on the basis of the reality of logistics industry, and then the Vehicle Routing Problems with Backhauls and Time Windows (VRPBTW) mathematical model and special constraints are analyzed and solved by the Max-Min Ant Colony Algorithms (MMACA). Finally, the results which are solved by the MMACA are better than the traditional algorithms on the example. Therefore, the MMACA can reduce the cost of the transportation in reality so as to realize the optimization of the VRPBTW.
引文
[1] Balinski M., Quand R.. On an integer program for a delivery problem[J]. Operations Research. 1962, 12: 300-304.
[2] Deif L., Bodin L. Extension of the Clarke and Wright algorithm for solving the vehicle routing problem with backhauling [J]. Proceedings of the Babson Conference on Software Uses in Transportation and Logistics Management. 1984: 75-96. [3] Clarke G., Wright J. W.. Scheduling of vehicles from a central depot to a number of deliver points [J]. Operations Research. 1964,12: 568-581.
[4] Goetschalckx M., Jacobs-Blecha C. The vehicle routing problem with backhauls [J], European Journal of Operational Research. 1989,42: 39-51.
[5] Toth P., Vigo D.. A heuristic algorithm for the symmetric and asymmetric vehicle routing problems with backhauls [J]. European Journal of Operational Research. 1999, 113(3): 528-544.
[6] Mingozzi A., Giorgi S., Baldacci R.. Exact method for the vehicle routing problem with backhauls [J]. Transportation Science. 1999, 33(3): 315-329.
[7] Golden B., Baker E., Alfaro J., Schaffer J.. The vehicle routing problem with backhauling: two approaches [J], Proceedings of the Twenty-First Annual Meeting of S.E.TIMS. 1985: 90-92.
[8] Casco D.O., Golden B.L, Wash E.A.. Vehicle routing with backhauls: models, algorithms, and case studies [J]. Vehicle Routing: Methods and Studies. 1988: 127-147.
[9] Salhi S., Nagy G. A cluster insertion heuristic for single and multiple depot vehicle routing problems with backhauling [J]. Journal of the Operational Research Society. 1999, 50: 1034-1042.
[10] Anne W., Said S.. An ant system algorithm for the vehicle routing problem with backhauls [J]. 4th Metaheuristics International Conference. 2001: 199-203.
[11] Thangiah S., Potvin J., and Sun T. Heuristic approaches to vehicle routing with backhauls and time windows [J]. Computers Operational Research. 1996, 23(11): 1043-1057.
[12] Kontoravdis G, Bard J.. Improved heuristics for the vehicle routing problem with time windows [J]. Working Paper, Operations Research Group, Department of Mechanical Engineering. The University of Texas, Austin. 1992.
[13] Potvin J., Kervahut T, Garcia B., Rousscau J.. The vehicle routing problem with time windows part I: tabu search [J]. INFORMS Journal on Computing. 1996, 8(2): 158-164.
[14]Solomon M..Algorithm for the vehicle routing and scheduling problem with time window constraint[J].Operations Research.1987,35:254-265.
[15]Duhamel C.,Potvin.,Jean-Yves.,Rousseau.,Jean-Marc..A tabu search heuristic for the vehicle routing problem with backhauls and time windows[J].Institute for Operations Research and Management Sciences,1997,49-59.
[16]吴泰熙,陈正芳,徐俊诚.含取货之车辆途程问题解法之研究[J].Journal of the Chinese Institute of Industrial Engineers,2003,20(6):651-665.
[17]隆颖.用遗传算法求解带回程取货的车辆路径问题[J].辽宁师专学报(自然科学版).2005,7(3):86-88.
[18]董媛媛,陶绪林,周晶.带回程的车辆运输路径优化及定价模型[J].现代交通技术.2006,4,42-45.
[19]尹传忠,卜雷,蒲云,赵宜.带回送和时间窗的车辆路径问题的模型及算法[J].西南交通大学学报.2006,41(3):290-295.
[20]霍佳震,张磊.求解配送收集旅行商问题的启发式算法[J].同济大学学报.2006,34(1):136-140.
[21]王发鸿,达庆利.逆向物流单车辆运输策略[J].东南大学学报.2006,36(1):156-160.
[22]郭伏,隆颖.带时窗回程取货的车辆路径问题的算法[J].东北大学学报.2006,27(5):575-578.
[23]M Dorigo.,V Maniezzo.,A Colorini..Distributed optirnization by ant colonies[J].Proceedings of the 1st European Conference on Artificial Life.1991,134-142.
[24]Gambardella L.M.,Dorigo M..Solving Symmetric and Asymmetric TSPs by Ant Colony [J].Proceedings of IEEE International Conference.1996.622-627
[25]吴庆洪,张继会,徐心和.有变异特征的蚁群算法[J].计算机研究与发展.1999,36(10):1240-1245.
[26]陈烨.带杂交算子的蚁群算法[J].计算机工程.2001,(12),74-76.
[27]王颖,谢剑英,一种自适应蚁群算法及其仿真研究[J].系统仿真学报.2002,14(1):31-33.
[28]Costa D.,Hertz A.,Dubuis O..Imbedding of a sequential algorithm within an evolutionary algorithm for coloring problem in graphs[J].Janu of heuristics.1989,20(1):105-128.
[29]Bilchev G,.Parmee I.C..Searching heavily constrained design spaces[J].In:Proc.of 22nd Int.Conf.Computer Aided Design.1995,230-235.
[30]魏平,熊伟清.用于一股函数优化的蚁群算法[J].宁波大学学报.2001,14(4):52-55.
[31]王长琼.逆向物流[M].北京:中国物资出版社.2007,157-161.
[32]Solomon M..On the Worst--Case Peformance of Some Heuristics for the Vehicle Routing and Scheduling Problem with Time Window Constraints[J].Network,1986,16:161-174.
[33]Mole R H.,S R Jameson..A sequential route-bulding algorithm employing a generalised savings criterion[J].Operational Research Quarterly.1976,27:503.
[34]Gillett B E.,Miller L R..A heuristic algorithm for the vehicle dispatch problem[J].Operations Research.1974,22:340-349.
[35]S.C.Ho.,D.Haugland..A tabu search heuristic for the vehicle routing problem with time windows and split deliveries[J].Computers & Operations Research.2004,31:1947-1964.
[36]W.Chiang.,R.Russell..Simulated Annealing metaheuristics for the vehicle with time windows[J].Annals of Operations Research.1996,63:3-27.
[37]Holland J H..Adaptation in Natural and Artificial System.MIT Press.1975.
[38]Arunkumar S.,Chocklingam T..Genetic search algorithms and their randomized operators [J].Computers Math.2003,12:91-100.
[39]段海滨.蚁群算法原理及其应用[M].北京:科学出版社.2005,24-39.
[40]T Stutzle.,H Hoos..Improvements on the Ant System:Introducing MAX-MIN ant system [J].In Proceedings of the International Conference on Artificial Neural Networks and Genetic Algorithms,Springer Verlag,Wien.1997,245-249.
[41]Thomas Stuztle..MAX-MIN Ant System[J].Elsevier Science,Nov,1999.
[42]孙明贵等.回收物流管理[M].北京:中国社会科学出版社.2005,5-20.
[43]杨浩.模型与算法[M].北京:北方交通大学出版社.2002,195-203.
[44]邢文训,谢金星.现代优化计算方法[M].北京:清华大学出版社.1999,140-180.
[45]李士勇.蚁群算法及其应用[M].黑龙江:哈尔滨工业大学出版社.2004,35-38.
[46]王新华.带时间窗的车辆路线问题研究[D].上海:同济大学硕士论文.2005,21-22.
[47]王之泰.新编现代物流学[M].北京:首都经济贸易大学出版社.2005,228-231.
[2] Deif L., Bodin L. Extension of the Clarke and Wright algorithm for solving the vehicle routing problem with backhauling [J]. Proceedings of the Babson Conference on Software Uses in Transportation and Logistics Management. 1984: 75-96. [3] Clarke G., Wright J. W.. Scheduling of vehicles from a central depot to a number of deliver points [J]. Operations Research. 1964,12: 568-581.
[4] Goetschalckx M., Jacobs-Blecha C. The vehicle routing problem with backhauls [J], European Journal of Operational Research. 1989,42: 39-51.
[5] Toth P., Vigo D.. A heuristic algorithm for the symmetric and asymmetric vehicle routing problems with backhauls [J]. European Journal of Operational Research. 1999, 113(3): 528-544.
[6] Mingozzi A., Giorgi S., Baldacci R.. Exact method for the vehicle routing problem with backhauls [J]. Transportation Science. 1999, 33(3): 315-329.
[7] Golden B., Baker E., Alfaro J., Schaffer J.. The vehicle routing problem with backhauling: two approaches [J], Proceedings of the Twenty-First Annual Meeting of S.E.TIMS. 1985: 90-92.
[8] Casco D.O., Golden B.L, Wash E.A.. Vehicle routing with backhauls: models, algorithms, and case studies [J]. Vehicle Routing: Methods and Studies. 1988: 127-147.
[9] Salhi S., Nagy G. A cluster insertion heuristic for single and multiple depot vehicle routing problems with backhauling [J]. Journal of the Operational Research Society. 1999, 50: 1034-1042.
[10] Anne W., Said S.. An ant system algorithm for the vehicle routing problem with backhauls [J]. 4th Metaheuristics International Conference. 2001: 199-203.
[11] Thangiah S., Potvin J., and Sun T. Heuristic approaches to vehicle routing with backhauls and time windows [J]. Computers Operational Research. 1996, 23(11): 1043-1057.
[12] Kontoravdis G, Bard J.. Improved heuristics for the vehicle routing problem with time windows [J]. Working Paper, Operations Research Group, Department of Mechanical Engineering. The University of Texas, Austin. 1992.
[13] Potvin J., Kervahut T, Garcia B., Rousscau J.. The vehicle routing problem with time windows part I: tabu search [J]. INFORMS Journal on Computing. 1996, 8(2): 158-164.
[14]Solomon M..Algorithm for the vehicle routing and scheduling problem with time window constraint[J].Operations Research.1987,35:254-265.
[15]Duhamel C.,Potvin.,Jean-Yves.,Rousseau.,Jean-Marc..A tabu search heuristic for the vehicle routing problem with backhauls and time windows[J].Institute for Operations Research and Management Sciences,1997,49-59.
[16]吴泰熙,陈正芳,徐俊诚.含取货之车辆途程问题解法之研究[J].Journal of the Chinese Institute of Industrial Engineers,2003,20(6):651-665.
[17]隆颖.用遗传算法求解带回程取货的车辆路径问题[J].辽宁师专学报(自然科学版).2005,7(3):86-88.
[18]董媛媛,陶绪林,周晶.带回程的车辆运输路径优化及定价模型[J].现代交通技术.2006,4,42-45.
[19]尹传忠,卜雷,蒲云,赵宜.带回送和时间窗的车辆路径问题的模型及算法[J].西南交通大学学报.2006,41(3):290-295.
[20]霍佳震,张磊.求解配送收集旅行商问题的启发式算法[J].同济大学学报.2006,34(1):136-140.
[21]王发鸿,达庆利.逆向物流单车辆运输策略[J].东南大学学报.2006,36(1):156-160.
[22]郭伏,隆颖.带时窗回程取货的车辆路径问题的算法[J].东北大学学报.2006,27(5):575-578.
[23]M Dorigo.,V Maniezzo.,A Colorini..Distributed optirnization by ant colonies[J].Proceedings of the 1st European Conference on Artificial Life.1991,134-142.
[24]Gambardella L.M.,Dorigo M..Solving Symmetric and Asymmetric TSPs by Ant Colony [J].Proceedings of IEEE International Conference.1996.622-627
[25]吴庆洪,张继会,徐心和.有变异特征的蚁群算法[J].计算机研究与发展.1999,36(10):1240-1245.
[26]陈烨.带杂交算子的蚁群算法[J].计算机工程.2001,(12),74-76.
[27]王颖,谢剑英,一种自适应蚁群算法及其仿真研究[J].系统仿真学报.2002,14(1):31-33.
[28]Costa D.,Hertz A.,Dubuis O..Imbedding of a sequential algorithm within an evolutionary algorithm for coloring problem in graphs[J].Janu of heuristics.1989,20(1):105-128.
[29]Bilchev G,.Parmee I.C..Searching heavily constrained design spaces[J].In:Proc.of 22nd Int.Conf.Computer Aided Design.1995,230-235.
[30]魏平,熊伟清.用于一股函数优化的蚁群算法[J].宁波大学学报.2001,14(4):52-55.
[31]王长琼.逆向物流[M].北京:中国物资出版社.2007,157-161.
[32]Solomon M..On the Worst--Case Peformance of Some Heuristics for the Vehicle Routing and Scheduling Problem with Time Window Constraints[J].Network,1986,16:161-174.
[33]Mole R H.,S R Jameson..A sequential route-bulding algorithm employing a generalised savings criterion[J].Operational Research Quarterly.1976,27:503.
[34]Gillett B E.,Miller L R..A heuristic algorithm for the vehicle dispatch problem[J].Operations Research.1974,22:340-349.
[35]S.C.Ho.,D.Haugland..A tabu search heuristic for the vehicle routing problem with time windows and split deliveries[J].Computers & Operations Research.2004,31:1947-1964.
[36]W.Chiang.,R.Russell..Simulated Annealing metaheuristics for the vehicle with time windows[J].Annals of Operations Research.1996,63:3-27.
[37]Holland J H..Adaptation in Natural and Artificial System.MIT Press.1975.
[38]Arunkumar S.,Chocklingam T..Genetic search algorithms and their randomized operators [J].Computers Math.2003,12:91-100.
[39]段海滨.蚁群算法原理及其应用[M].北京:科学出版社.2005,24-39.
[40]T Stutzle.,H Hoos..Improvements on the Ant System:Introducing MAX-MIN ant system [J].In Proceedings of the International Conference on Artificial Neural Networks and Genetic Algorithms,Springer Verlag,Wien.1997,245-249.
[41]Thomas Stuztle..MAX-MIN Ant System[J].Elsevier Science,Nov,1999.
[42]孙明贵等.回收物流管理[M].北京:中国社会科学出版社.2005,5-20.
[43]杨浩.模型与算法[M].北京:北方交通大学出版社.2002,195-203.
[44]邢文训,谢金星.现代优化计算方法[M].北京:清华大学出版社.1999,140-180.
[45]李士勇.蚁群算法及其应用[M].黑龙江:哈尔滨工业大学出版社.2004,35-38.
[46]王新华.带时间窗的车辆路线问题研究[D].上海:同济大学硕士论文.2005,21-22.
[47]王之泰.新编现代物流学[M].北京:首都经济贸易大学出版社.2005,228-231.