城市物流配送系统的LRP模型及其算法研究
|
摘要
电子商务的发展，产生了信息传递快速和物流反应缓慢的矛盾，为了解决这一矛盾，抽象的LRP优化问题被引入到城市物流配送系统优化中来。以往对LRP优化问题的研究大多是集中在单目标问题上，而且大多是停留在抽象理论的层次，这样不符合城市物流配送系统的特征。构建符合城市物流配送系统特征的多目标LRP，并研究其求解方法，是解决城市物流配送系统优化问题的必经之路。
本文研究了城市物流配送系统的特征，论述了城市物流配送调度可由LRP这一抽象的优化模型表示。经进一步的研究，发现城市物流配送系统LRP实质上是一个多目标混合整数规划问题。在构造这个模型的算法的时候，采用了两阶段法，把整个问题的求解分成两个阶段，对每个阶段采用启发式搜索算法来解决。为了解决算法中道路信息数据的调入问题，构建了数据的存储和调用方法，对其中两点距离的解决作了特别的说明。文章最后构建了一个模拟的城市物流配送系统，通过它实现了前面创建的模型、算法。
The inconsistency between information flow and logistics came into being while e-commerce having developed. In order to sloved this problem, the abstract LRP had been introduced to city logistics dispatch system. Over the past few decades, studies in LRP had aimed at single objective and abstract level, which could not reflect character of city logistics. Building a multiple objective LRP which reflect character of city logistics and sieving it use heuristic are means to slove city logistics dispatch problems.
The city logistics had been put forward in order to account for the transport dispatch problem in the city zone. The character of the city logistics information system had been analyzed at the beginning of this paper. Then, a truth that the city logistics delivery system dispatch problem could be expressed with the abstract LRP model had been pointed out. A multi-objective mixed integer programming model, which abstracted the city logistics delivery system LRP, had been presented. A two-phase heuristic had been introduced to solve the modle. The whole problem had been splied into two phases, and different heuristic methods had been introduced to each phase. A method of the data input and output has been introduced in order to solve the problem of the route information storage. At the same time, a method to calculate the distance of any two spots in the range of the logistics delivery had been presented. A simulated model had been worked out at the end of this paper.
本文研究了城市物流配送系统的特征，论述了城市物流配送调度可由LRP这一抽象的优化模型表示。经进一步的研究，发现城市物流配送系统LRP实质上是一个多目标混合整数规划问题。在构造这个模型的算法的时候，采用了两阶段法，把整个问题的求解分成两个阶段，对每个阶段采用启发式搜索算法来解决。为了解决算法中道路信息数据的调入问题，构建了数据的存储和调用方法，对其中两点距离的解决作了特别的说明。文章最后构建了一个模拟的城市物流配送系统，通过它实现了前面创建的模型、算法。
The inconsistency between information flow and logistics came into being while e-commerce having developed. In order to sloved this problem, the abstract LRP had been introduced to city logistics dispatch system. Over the past few decades, studies in LRP had aimed at single objective and abstract level, which could not reflect character of city logistics. Building a multiple objective LRP which reflect character of city logistics and sieving it use heuristic are means to slove city logistics dispatch problems.
The city logistics had been put forward in order to account for the transport dispatch problem in the city zone. The character of the city logistics information system had been analyzed at the beginning of this paper. Then, a truth that the city logistics delivery system dispatch problem could be expressed with the abstract LRP model had been pointed out. A multi-objective mixed integer programming model, which abstracted the city logistics delivery system LRP, had been presented. A two-phase heuristic had been introduced to solve the modle. The whole problem had been splied into two phases, and different heuristic methods had been introduced to each phase. A method of the data input and output has been introduced in order to solve the problem of the route information storage. At the same time, a method to calculate the distance of any two spots in the range of the logistics delivery had been presented. A simulated model had been worked out at the end of this paper.
引文
[1] 王之泰．城市物流研究探要．物流技术，1999，94(1) ：25-27
[2] Ellchi Taniguchi,Russell G Thompson,Tadashi Yamada,Ron Van Duin.City Logistics:network modelling and intelligent transport systems.PERGAMON,2001:2-3
[3] Gilbert Laporte. The vehicle routing problem : An overview of exact and approximate algorthms.European Journal of Operational Research, 1992,59 : 345-358
[4] Alant Murray, Ross A. Gerrard. Capacitated service and regional constraints in location-allocation modeling. Location Science, 1997, 5(2) : 103-118
[5] John Current, H. Min, D.A. Schilling. Multiobjective analysis of facility location decisions. European Journal of Operational Research, 1990, 49 : 295-307
[6] 汪寿阳，赵秋红，夏国平．集成物流管理系统中的定位--运输线路安排问题的研究． 管理科学学报，2000，3(2) ：69-75
[7] S. Salhi, G.K. Rand. The effect of ignoring routes when locating deports. European Journal of Operational Research, 1989, 39 : 150-156
[8] Maranzana F.E. On the location of supply points to minimize transport cost. Operational Research Quarterly, 1965,( 15) : 261-270
[9] M.H.J. Webb. Cost functions in the location of deports for multiple-delivery journeys. Operational Research Quarterly, 1968, (19) : 311-320
[10] N.Christofides, S.Eilton. An algorithm for the vehicle dispatching problem. Operational Research Quarterly, 1969, (20) : 309-318
[11] Leon Cooper. The Transportation-Location Problem. Operations Research, 1972, 20 : 94-108
[12] Leon Cooper. An efficient heuristic algorithm for the transportation-location problem. Journal of Regional Science, 1976, 16(3) : 309-315
[13] C.Watson-Gandy, P.Dohrn. Depot location with van salesman-A practical approach. Omega, 1973, 1(3) : 321-329
[14] I.Or, W.P.Pierskalla. A transportation, location-allocation model for regional blood banking. AIIE Transactions, 1979, 11(2) : 86-95
[15] Jacobson.S.k., Madsen. O.B.G.A comparative study of heuristics for a tow-level routing-location problem. European Journal of Operational Research, 1980, 5 : 378-387
[16] Laporte G.,Nobert Y. A exact algorithm for minimizing routing and operating costs in depot location . European Journal of Operational Research, 1981,6:224-226
[17] Hokey Min, Vaidyanathan Jayaraman, Rajesh Srivastava. Combined location-routing problems : A synthesis and future research direction. European Journal of Operational Research, 1998, 108:1-15
[18] I.Averbakh, O.Berman. Routing and location-routing p-delivery man problems on a path. Transportation Science, 1994, 28(2) : 162-166
[19] C.ReVelle, J.Cohon, D.Shobrys. Simultaneous siting and routing in the disposal of hazardous wastes. Transportation Science, 1991, 25(2) : 138-145
[20] G. Laporte, Y. Nobert, D.Arpin. An exact algorithm for solving a capacitated location-routing problem. Annals of Operations Research, 1986, 6: 293-310
[21] C.L.Stowers, U.S.Paleker. Location models with routing considerations for a single obnoxious facility. Transportation Science, 1993, 27(4): 350-362
[22] Rajesh Srivastava, W.C.Benton. The location-routing problem : considerations in physical distribution system design. Computers & Operations Research, 1990, 17: 427-435
[23] J.H.Bookbinder, K.E.Reece. Vehicle routing considerations in distribution system design. European Journal of Operational Research, 1988, 37: 204-213
[24] J.Perl, M.S.Daskin. A warehouse location-routing problem. Transportation Research, 1985, 19B(5): 381-396
[25] T.W. Chien. Heurristic procedures for practical-sized uncapacitated location-capacitated routing problems. Decision Sciences, 1993, 24(5): 995-1021
[26] P.H.Hansen, B.Hegedahl, S.Hjortk, B.Obel. A heuristic solution to the warehouse location-routing problem. European Journal of Operational Research, 1994, 76: 111-127
[27] R.I.phelps. Artificial Intelligence-An overview of Similarities with O.R. Journal of Operational Research Society, 1986, 37(1): 13-20
[28] 胡祥培，杨德礼．智能运筹学与动态系统实时优化控制．经济管理与社会科学前沿研究—2000年中国博士后学术大会经济管理与人文社会分会暨全国博士后第四届经济学管理学学术会议论文集，中国金融出版社，2000年10月出版：137-148
[29] Hu Xiangpei. A New Method on Knowledge Representation for Programming Model of Operational Research——Structured State-space Representation. Proceedings of the Second Russian-Chinese International Symposium On Management Science, Economic Education Press, Moscow, Russia, Oct. 1994
[30] 胡祥培，钱国明，胡运权．离散型动态规划模型的知识表示及其IBFS算法研究．哈尔滨工业大学学报，1996，3：119-126
[31] Gilbert Laporte, Francois Louveaux, He lene Mercure. Modles and exact solutions for a class of stochastic location-routing problems. European Journal of Operational Research, 1989, 39: 71-78
[32] J.Perl. A unified warehouse location-routing analysis. UMI Dissertation Information Service, 1983
[33] 李军，郭耀煌．物流配送车辆优化调度理论与方法。中国物资出版社，2001年6月出版
[34] 傅京孙，蔡自兴，徐光佑．人工智能及其应用．清华大学出版社，1987年9月出版
[2] Ellchi Taniguchi,Russell G Thompson,Tadashi Yamada,Ron Van Duin.City Logistics:network modelling and intelligent transport systems.PERGAMON,2001:2-3
[3] Gilbert Laporte. The vehicle routing problem : An overview of exact and approximate algorthms.European Journal of Operational Research, 1992,59 : 345-358
[4] Alant Murray, Ross A. Gerrard. Capacitated service and regional constraints in location-allocation modeling. Location Science, 1997, 5(2) : 103-118
[5] John Current, H. Min, D.A. Schilling. Multiobjective analysis of facility location decisions. European Journal of Operational Research, 1990, 49 : 295-307
[6] 汪寿阳，赵秋红，夏国平．集成物流管理系统中的定位--运输线路安排问题的研究． 管理科学学报，2000，3(2) ：69-75
[7] S. Salhi, G.K. Rand. The effect of ignoring routes when locating deports. European Journal of Operational Research, 1989, 39 : 150-156
[8] Maranzana F.E. On the location of supply points to minimize transport cost. Operational Research Quarterly, 1965,( 15) : 261-270
[9] M.H.J. Webb. Cost functions in the location of deports for multiple-delivery journeys. Operational Research Quarterly, 1968, (19) : 311-320
[10] N.Christofides, S.Eilton. An algorithm for the vehicle dispatching problem. Operational Research Quarterly, 1969, (20) : 309-318
[11] Leon Cooper. The Transportation-Location Problem. Operations Research, 1972, 20 : 94-108
[12] Leon Cooper. An efficient heuristic algorithm for the transportation-location problem. Journal of Regional Science, 1976, 16(3) : 309-315
[13] C.Watson-Gandy, P.Dohrn. Depot location with van salesman-A practical approach. Omega, 1973, 1(3) : 321-329
[14] I.Or, W.P.Pierskalla. A transportation, location-allocation model for regional blood banking. AIIE Transactions, 1979, 11(2) : 86-95
[15] Jacobson.S.k., Madsen. O.B.G.A comparative study of heuristics for a tow-level routing-location problem. European Journal of Operational Research, 1980, 5 : 378-387
[16] Laporte G.,Nobert Y. A exact algorithm for minimizing routing and operating costs in depot location . European Journal of Operational Research, 1981,6:224-226
[17] Hokey Min, Vaidyanathan Jayaraman, Rajesh Srivastava. Combined location-routing problems : A synthesis and future research direction. European Journal of Operational Research, 1998, 108:1-15
[18] I.Averbakh, O.Berman. Routing and location-routing p-delivery man problems on a path. Transportation Science, 1994, 28(2) : 162-166
[19] C.ReVelle, J.Cohon, D.Shobrys. Simultaneous siting and routing in the disposal of hazardous wastes. Transportation Science, 1991, 25(2) : 138-145
[20] G. Laporte, Y. Nobert, D.Arpin. An exact algorithm for solving a capacitated location-routing problem. Annals of Operations Research, 1986, 6: 293-310
[21] C.L.Stowers, U.S.Paleker. Location models with routing considerations for a single obnoxious facility. Transportation Science, 1993, 27(4): 350-362
[22] Rajesh Srivastava, W.C.Benton. The location-routing problem : considerations in physical distribution system design. Computers & Operations Research, 1990, 17: 427-435
[23] J.H.Bookbinder, K.E.Reece. Vehicle routing considerations in distribution system design. European Journal of Operational Research, 1988, 37: 204-213
[24] J.Perl, M.S.Daskin. A warehouse location-routing problem. Transportation Research, 1985, 19B(5): 381-396
[25] T.W. Chien. Heurristic procedures for practical-sized uncapacitated location-capacitated routing problems. Decision Sciences, 1993, 24(5): 995-1021
[26] P.H.Hansen, B.Hegedahl, S.Hjortk, B.Obel. A heuristic solution to the warehouse location-routing problem. European Journal of Operational Research, 1994, 76: 111-127
[27] R.I.phelps. Artificial Intelligence-An overview of Similarities with O.R. Journal of Operational Research Society, 1986, 37(1): 13-20
[28] 胡祥培，杨德礼．智能运筹学与动态系统实时优化控制．经济管理与社会科学前沿研究—2000年中国博士后学术大会经济管理与人文社会分会暨全国博士后第四届经济学管理学学术会议论文集，中国金融出版社，2000年10月出版：137-148
[29] Hu Xiangpei. A New Method on Knowledge Representation for Programming Model of Operational Research——Structured State-space Representation. Proceedings of the Second Russian-Chinese International Symposium On Management Science, Economic Education Press, Moscow, Russia, Oct. 1994
[30] 胡祥培，钱国明，胡运权．离散型动态规划模型的知识表示及其IBFS算法研究．哈尔滨工业大学学报，1996，3：119-126
[31] Gilbert Laporte, Francois Louveaux, He lene Mercure. Modles and exact solutions for a class of stochastic location-routing problems. European Journal of Operational Research, 1989, 39: 71-78
[32] J.Perl. A unified warehouse location-routing analysis. UMI Dissertation Information Service, 1983
[33] 李军，郭耀煌．物流配送车辆优化调度理论与方法。中国物资出版社，2001年6月出版
[34] 傅京孙，蔡自兴，徐光佑．人工智能及其应用．清华大学出版社，1987年9月出版