物流配送中双向运输车辆路径优化问题研究
|
摘要
近年来，物流配送作为“第三方利润的源泉”受到国内各行业的极大重视并得到了较大发展，大量规模较大的生产企业、商业企业纷纷建立起配送中心向商品流通的高效率化发起挑战，与此同时，相当部分的大型运输、仓储和航运企业也开始朝向第三方物流经营。物流配送开始在我国迅速兴起。如何在提高物流配送效率的同时降低成本成为一个重要的研究课题，运输作为物流配送中的重要环节，首当其冲成为节约成本的对象。
此外，物流企业要想在激烈的市场竞争中立于不败之地，必须具备自己的核心竞争力。物流配送是物流中一个重要的、直接与消费者相连的环节，而配送系统中车辆路径优化，是竞争力的直接表现。
本文共分为五章。前两章内容是为问题的研究与解决作铺垫。第三章和第四章是本文的重点，也是创新点的聚集之处。第一章从概念的角度阐述了物流配送的产生和发展以及物流配送系统的需求，并由此引申出物流配送系统中运输路径优化问题。第二章从理论的角度讲述物流配送系统中双向运输路径优化算法，并对引起双向运输的逆向物流进行了分类和系统论述。第三章以物流配送中运输信息化为线索，分析了运输优化系统的构成、功能以及其在物流配送系统中的位置，并对与运输系统相关的数据库进行设计——基本数据的结构设计和电子地图数据库的设计。针对中小企业实现信息化成本高的现实，本文还提出了采用ASP优化车辆路径的建议。第四章以物流配送系统双向运输路径优化模型构建为目标，首先用双向运输路径优化问题混合整数模型来更进一步分析DPVRPTW，接下来将C—W节约法进行了改进，使其更适合于解决带时间窗双向运输问题。第五章进行了模型的验证，利用案例来说明和验证算法的可行性。
由于双向运输路径优化问题属于复杂问题，所以在此文中选择节约法，并对该方法进行了改进使得其可以快速地解决双向运输且具有时间窗约束的路径优化问题。
针对物流配送发展和计算机运输优化系统面临着的巨大应用前景，本文提出
开发计算机运输优化系统的设想。根据实际物流配送业务中可能存在的多种约束，
进行了灵活的优化处理，介绍了该系统中主要的模块功能及其实现方法。
In recent years, logistics, taken as "the third profit resource", has been taken seriously and been developing rapidly. Lots of physical distribution centers are established to improve the efficiency of goods flow by large factories and commercial firms. Meanwhile, considerable sum of transportation corporations, storage enterprises and shipping companies are taking on business of third party logistics. The distribution business is now flourishing in my country. How to low distribution cost is concerned. Transportation is the key part of the logistics distribution, so decline of transportation cost is focused on.
Furthermore, to remain invincible in the intense market competition, logistics enterprises are supposed to have their own core strengths and competitiveness. VRP is a crucial and direct link with customs in the entire logistics, whereas, the optimization of vehicle planning of the distribution system is a key segment of the whole optimization system, which directly reflects the nucleus competitiveness of the enterprises
This dissertation consists of five chapters. Chapter 1 and Chapter 2 are taken as matting for the next chapters, Chapter 3 and Chapter 4 is the key parts and the novelty points. Chapter 5 is about the validation of module.
Chapter 1 analyzes the coming into being and developing of logistics distribution and the demand of logistics distribution system in terms of concepts, and introduces VRP. In terms of theories, chapter 2 presents the arithmetic of DPVRP. Then it detailedly classifies and tells reverse logistics that causes DPVRP. Chapter 3 uses transportation informationizing as a clue, explains the structure and functions of the system, formulates the design of database, which includes the basic data structure and electronic map database. At the goal of building module chapter 4 firstly introduces the mixed-integer module to show DPVRPTW, secondly improves C-W saving metric
method to solve DPVRPTW. Chapter 5 makes use of real cases to validate arithmetic above.
Delivery and pick-up vehicle routing problem is complex so we choose saving matrix method ,and improve on it to make sure that we can quickly search the solution of DPVRP with time window.
Because of development of logistics distribution and prospect of computer-aided transportation optimization system application, this dissertation gives an assumption to design computer-aided transportation optimization system. And according to some restrictions that maybe occur during real operation of logistics distribution, the author deals with the problem flexibly, and explains the main modules.
此外，物流企业要想在激烈的市场竞争中立于不败之地，必须具备自己的核心竞争力。物流配送是物流中一个重要的、直接与消费者相连的环节，而配送系统中车辆路径优化，是竞争力的直接表现。
本文共分为五章。前两章内容是为问题的研究与解决作铺垫。第三章和第四章是本文的重点，也是创新点的聚集之处。第一章从概念的角度阐述了物流配送的产生和发展以及物流配送系统的需求，并由此引申出物流配送系统中运输路径优化问题。第二章从理论的角度讲述物流配送系统中双向运输路径优化算法，并对引起双向运输的逆向物流进行了分类和系统论述。第三章以物流配送中运输信息化为线索，分析了运输优化系统的构成、功能以及其在物流配送系统中的位置，并对与运输系统相关的数据库进行设计——基本数据的结构设计和电子地图数据库的设计。针对中小企业实现信息化成本高的现实，本文还提出了采用ASP优化车辆路径的建议。第四章以物流配送系统双向运输路径优化模型构建为目标，首先用双向运输路径优化问题混合整数模型来更进一步分析DPVRPTW，接下来将C—W节约法进行了改进，使其更适合于解决带时间窗双向运输问题。第五章进行了模型的验证，利用案例来说明和验证算法的可行性。
由于双向运输路径优化问题属于复杂问题，所以在此文中选择节约法，并对该方法进行了改进使得其可以快速地解决双向运输且具有时间窗约束的路径优化问题。
针对物流配送发展和计算机运输优化系统面临着的巨大应用前景，本文提出
开发计算机运输优化系统的设想。根据实际物流配送业务中可能存在的多种约束，
进行了灵活的优化处理，介绍了该系统中主要的模块功能及其实现方法。
In recent years, logistics, taken as "the third profit resource", has been taken seriously and been developing rapidly. Lots of physical distribution centers are established to improve the efficiency of goods flow by large factories and commercial firms. Meanwhile, considerable sum of transportation corporations, storage enterprises and shipping companies are taking on business of third party logistics. The distribution business is now flourishing in my country. How to low distribution cost is concerned. Transportation is the key part of the logistics distribution, so decline of transportation cost is focused on.
Furthermore, to remain invincible in the intense market competition, logistics enterprises are supposed to have their own core strengths and competitiveness. VRP is a crucial and direct link with customs in the entire logistics, whereas, the optimization of vehicle planning of the distribution system is a key segment of the whole optimization system, which directly reflects the nucleus competitiveness of the enterprises
This dissertation consists of five chapters. Chapter 1 and Chapter 2 are taken as matting for the next chapters, Chapter 3 and Chapter 4 is the key parts and the novelty points. Chapter 5 is about the validation of module.
Chapter 1 analyzes the coming into being and developing of logistics distribution and the demand of logistics distribution system in terms of concepts, and introduces VRP. In terms of theories, chapter 2 presents the arithmetic of DPVRP. Then it detailedly classifies and tells reverse logistics that causes DPVRP. Chapter 3 uses transportation informationizing as a clue, explains the structure and functions of the system, formulates the design of database, which includes the basic data structure and electronic map database. At the goal of building module chapter 4 firstly introduces the mixed-integer module to show DPVRPTW, secondly improves C-W saving metric
method to solve DPVRPTW. Chapter 5 makes use of real cases to validate arithmetic above.
Delivery and pick-up vehicle routing problem is complex so we choose saving matrix method ,and improve on it to make sure that we can quickly search the solution of DPVRP with time window.
Because of development of logistics distribution and prospect of computer-aided transportation optimization system application, this dissertation gives an assumption to design computer-aided transportation optimization system. And according to some restrictions that maybe occur during real operation of logistics distribution, the author deals with the problem flexibly, and explains the main modules.
引文
[1]范玉妹，刘胜富．多源多汇运输系统的多目标规划模型[J]．物流技术与应用，1998年第3卷第1期，26—29．
[2]唐立新．旅行商问题(TSP)的改进遗传算法[J]．东北大学学报(自然科学版)，1999年20期：40-42．
[3]钱颂迪．运筹学[M]．清华大学出版社，1997年．
[4]姜大立，杨西龙，杜文，周贤伟．车辆路径问题的遗传算法研究[J]．系统工程理论与实践，1999年19(6)．
[5]李军．有时间窗的车辆路线安排问题的启发式算法[J]．系统工程，1996年114(5)．
[6]魏明，高成修，胡润洲．一种带时间窗和容量约束的车辆路线问题及其tabu search算法[J]．运筹与管理，2002年第十一卷第三期．
[7]王永庆．人工智能原理和方法[M]．西安交通大学出版社，1998年．
[8]王嘉霖，张蕾丽．物流系统工程[M]．中国物资出版社，1990年．
[9]周明，孙淑栋．遗传算法原理及应用[M]．国防工业出版社，2000年．
[10]姜福川，吕传红．基于节约法在优化配送路线的研究[J]．辽宁工程技术大学学报，2003年9月．
[11]何景华．共同配送—配送物流发展的新趋势[J]．世界海运，2001年10月．
[12]韩伯棠．管理运筹学[M]．高等教育出版社，2000年．
[13]运筹学教材编写组．运筹学[M]．清华大学出版社，2000年．
[14]上海现代物流人才培训中心．现代物流管理[M]．上海人民出版社，2001年．
[15]张小国，王庆，万德钧．基于电子地图的路径最优算法研究[J]．中国惯性技术学报，2001年3月．
[16]蔡忠亮．基于电子地图的超媒体数据模型研究[J]．武汉大学学报信息科学版，2001年10月．
[17]唐孝飞，孙壮志，胡思继．物流配送决策支持系统的分析[J]．北方交通大学学报，2003年第5期．
[18]李云，王平．共同配送体系结构[J]．重庆邮电学院学报(自然科学版)，2002年第2期．
[19]陈勇，刘飞，王平．基于信息技术的敏捷物流配送系统[J]．物流技术，2003年第3期．
[20]郭成．GPS在物流配送中的运用分析[J]．中国储运，2002年第1期．
[21]蒋梦莉．电子商务货物配送系统解决方案[J]．现代电子技术，2002年第11期．
[22]李金苹．现代物流配送系统的运输优化调度方案[J]．物流技术，2002年第5期．
[23]蔡希贤，夏士智．物流合理化的数量方法[M]．华中工学院出版社，1985年．
[24]李军．物流配送车辆优化调度理论与方法[M]．中国物资出版社，2001年6月．
[25]丁立言，张铎主编．物流系统工程[M]．清华大学出版社，1999年．
[26]丁立言，张铎主编．物流管理[M]．清华大学出版社，1999年．
[27]夏静．现代物流配送的车辆优化调度模型及应用[D]．北京：北京理工大学载运工具运用工程专业，2003年．
[28]安涛．智能车辆调度系统研究及工程实现[D]．北京：北京航空航天大学精密仪器及机械专业，2002年．
[29]孟小平．物流配送及其运输调度优化研究[D]．大连：大连海事大学交通运输规划与管理专业，2001年．
[30]王艳艳．物流配送系统中车辆装运的优化研究[D]．济南：山东大学机械电子专业，2002年．
[31]李建哲．基于多层C／S模型连锁配送与储运管理系统的设计及实现[D]．西安：西安建筑科技大学计算机应用专业，2000年．
[32]杨杰．电子商务活动的物流配送模型研究[D]．济南：山东大学运筹与控制
论专业，2001年．
[33]Gary Hardenburg. Logistics Control and Information Support [J]. Autotestcon Proceedings 2000 IEEE Sept. 2000 Pages: 40-42.
[34]Anily .The vehicle-routing problem with delivery and back-haul options. Naval Research Logistics 43: 415- 434.
[35]Bodin L.D., Golden B.L., Assad A.A., Ball M., Routing and Scheduling of Vehicles and Crews[J]: The State of Art, Computers &Operations Research, 1983, No. 10, Pages:63-211.
[36]Kohl N, Madsen O B G. An optimization algorithm for the vehicle routing problem with time windows based on Lagrangian relaxation [J]. Operations Research, 1997, 45; 395-406.
[37]Desrochers M, Desroiers J, Solomon M. A new optimization algorithm for the vehicle routing problem with time windows[J]. Operations Research, 1992,40; 342-354.
[38]Mosheiov. The traveling salesman problem with pick-up and delivery. European Journal of Operational Research 79: 299-310.
[39]Min H, Javaram an V, Rajesh Srivastava R. Combined location-routing problems: a synthesis and future research directions [J]. European Journal of Operational Research, 1998,108; 1-15.
[40]Kim N-H, Rim S-C, Min B-D (1997). A heuristic algorithm for vehicle routing problem with backhauls. International Journal of Management Science 3: 1-14.
[41]Min H (1989). The multiple vehicle routing problems with simultaneous delivery and pickup points. Transportation Research-A 23A: 377- 386.
[42]Salhi S, NagyG(1999).A cluster insertion heuristic for single and multiple depot vehicle routing problems with backhauling. Journal of the Operational Research Society 50:1034-1042.
[43]Dumas Y, Desrosiers J, Soumis F (1991). The pickup and delivery problem with time windows. European Journal of Operational Research 54:7-22.
[44]Fleischmann M, Bloemhof-Ruwaard JM, Dekker R, van der Laan E, van Nunen JAEE, van Wassenhove LN (1997) Quantitative models for reverse logistics: A review. European Journal of Operational Research 103:1 -17.
[45]Bodin L. A taxonomies structure for vehicle routing and scheduling problems [J]. Computers and Urban Society, 1975,1; 11-29.
[46]H. Kokubugata. H. Itoyama and H. Kawashima. (2001)Vehicle Routing Methods for City Logistics Operation[J]. Preprint for IF AC Symposium on Transportation Systems:755-766.
[47]Assad A A. Modeling and Implementation Issues in Vehicle Routing: Method and Studies in Management Science and System[M]. 1998.
[48]Fleischmann M, Bloemhof-Ruwaard JM, Dekker R, van der Laan E, van Nunen JAEE, VanWassenhove LN (1997) Quantitative models for reverse logistics: A review. European Journal of Operational Research 103:1-17.
[2]唐立新．旅行商问题(TSP)的改进遗传算法[J]．东北大学学报(自然科学版)，1999年20期：40-42．
[3]钱颂迪．运筹学[M]．清华大学出版社，1997年．
[4]姜大立，杨西龙，杜文，周贤伟．车辆路径问题的遗传算法研究[J]．系统工程理论与实践，1999年19(6)．
[5]李军．有时间窗的车辆路线安排问题的启发式算法[J]．系统工程，1996年114(5)．
[6]魏明，高成修，胡润洲．一种带时间窗和容量约束的车辆路线问题及其tabu search算法[J]．运筹与管理，2002年第十一卷第三期．
[7]王永庆．人工智能原理和方法[M]．西安交通大学出版社，1998年．
[8]王嘉霖，张蕾丽．物流系统工程[M]．中国物资出版社，1990年．
[9]周明，孙淑栋．遗传算法原理及应用[M]．国防工业出版社，2000年．
[10]姜福川，吕传红．基于节约法在优化配送路线的研究[J]．辽宁工程技术大学学报，2003年9月．
[11]何景华．共同配送—配送物流发展的新趋势[J]．世界海运，2001年10月．
[12]韩伯棠．管理运筹学[M]．高等教育出版社，2000年．
[13]运筹学教材编写组．运筹学[M]．清华大学出版社，2000年．
[14]上海现代物流人才培训中心．现代物流管理[M]．上海人民出版社，2001年．
[15]张小国，王庆，万德钧．基于电子地图的路径最优算法研究[J]．中国惯性技术学报，2001年3月．
[16]蔡忠亮．基于电子地图的超媒体数据模型研究[J]．武汉大学学报信息科学版，2001年10月．
[17]唐孝飞，孙壮志，胡思继．物流配送决策支持系统的分析[J]．北方交通大学学报，2003年第5期．
[18]李云，王平．共同配送体系结构[J]．重庆邮电学院学报(自然科学版)，2002年第2期．
[19]陈勇，刘飞，王平．基于信息技术的敏捷物流配送系统[J]．物流技术，2003年第3期．
[20]郭成．GPS在物流配送中的运用分析[J]．中国储运，2002年第1期．
[21]蒋梦莉．电子商务货物配送系统解决方案[J]．现代电子技术，2002年第11期．
[22]李金苹．现代物流配送系统的运输优化调度方案[J]．物流技术，2002年第5期．
[23]蔡希贤，夏士智．物流合理化的数量方法[M]．华中工学院出版社，1985年．
[24]李军．物流配送车辆优化调度理论与方法[M]．中国物资出版社，2001年6月．
[25]丁立言，张铎主编．物流系统工程[M]．清华大学出版社，1999年．
[26]丁立言，张铎主编．物流管理[M]．清华大学出版社，1999年．
[27]夏静．现代物流配送的车辆优化调度模型及应用[D]．北京：北京理工大学载运工具运用工程专业，2003年．
[28]安涛．智能车辆调度系统研究及工程实现[D]．北京：北京航空航天大学精密仪器及机械专业，2002年．
[29]孟小平．物流配送及其运输调度优化研究[D]．大连：大连海事大学交通运输规划与管理专业，2001年．
[30]王艳艳．物流配送系统中车辆装运的优化研究[D]．济南：山东大学机械电子专业，2002年．
[31]李建哲．基于多层C／S模型连锁配送与储运管理系统的设计及实现[D]．西安：西安建筑科技大学计算机应用专业，2000年．
[32]杨杰．电子商务活动的物流配送模型研究[D]．济南：山东大学运筹与控制
论专业，2001年．
[33]Gary Hardenburg. Logistics Control and Information Support [J]. Autotestcon Proceedings 2000 IEEE Sept. 2000 Pages: 40-42.
[34]Anily .The vehicle-routing problem with delivery and back-haul options. Naval Research Logistics 43: 415- 434.
[35]Bodin L.D., Golden B.L., Assad A.A., Ball M., Routing and Scheduling of Vehicles and Crews[J]: The State of Art, Computers &Operations Research, 1983, No. 10, Pages:63-211.
[36]Kohl N, Madsen O B G. An optimization algorithm for the vehicle routing problem with time windows based on Lagrangian relaxation [J]. Operations Research, 1997, 45; 395-406.
[37]Desrochers M, Desroiers J, Solomon M. A new optimization algorithm for the vehicle routing problem with time windows[J]. Operations Research, 1992,40; 342-354.
[38]Mosheiov. The traveling salesman problem with pick-up and delivery. European Journal of Operational Research 79: 299-310.
[39]Min H, Javaram an V, Rajesh Srivastava R. Combined location-routing problems: a synthesis and future research directions [J]. European Journal of Operational Research, 1998,108; 1-15.
[40]Kim N-H, Rim S-C, Min B-D (1997). A heuristic algorithm for vehicle routing problem with backhauls. International Journal of Management Science 3: 1-14.
[41]Min H (1989). The multiple vehicle routing problems with simultaneous delivery and pickup points. Transportation Research-A 23A: 377- 386.
[42]Salhi S, NagyG(1999).A cluster insertion heuristic for single and multiple depot vehicle routing problems with backhauling. Journal of the Operational Research Society 50:1034-1042.
[43]Dumas Y, Desrosiers J, Soumis F (1991). The pickup and delivery problem with time windows. European Journal of Operational Research 54:7-22.
[44]Fleischmann M, Bloemhof-Ruwaard JM, Dekker R, van der Laan E, van Nunen JAEE, van Wassenhove LN (1997) Quantitative models for reverse logistics: A review. European Journal of Operational Research 103:1 -17.
[45]Bodin L. A taxonomies structure for vehicle routing and scheduling problems [J]. Computers and Urban Society, 1975,1; 11-29.
[46]H. Kokubugata. H. Itoyama and H. Kawashima. (2001)Vehicle Routing Methods for City Logistics Operation[J]. Preprint for IF AC Symposium on Transportation Systems:755-766.
[47]Assad A A. Modeling and Implementation Issues in Vehicle Routing: Method and Studies in Management Science and System[M]. 1998.
[48]Fleischmann M, Bloemhof-Ruwaard JM, Dekker R, van der Laan E, van Nunen JAEE, VanWassenhove LN (1997) Quantitative models for reverse logistics: A review. European Journal of Operational Research 103:1-17.