物流车辆调度问题研究
|
摘要
交通运输是国民经济的动脉,它对社会经济发展和人民生活起着极为重要的作用。各种运输方式在日常运输营运管理工作中都要面对这样一个共同的问题,如何为其载运工具确定行驶路线及其时刻表,才能有效地运送各站点间的旅客和货物。运筹学界将此类问题统称为车辆路径问题。
随着市场竞争的日益加剧、世界经济一体化进程的加快和科学技术的飞速发展,许多企业已经把物流作为提高市场竞争能力和提升核心竞争能力的重要手段。作为实现物流合理化的重要内容和手段,研究车辆路径有助于企业降低物流成本,提高运作效率,全面提高顾客满意度。
车辆路径问题是运输组织优化中的核心问题。由于车辆路径问题将运筹学理论与生产实践紧密地结合在一起,近几十年取得了很多成果,因此被称为“最近几十年运筹学领域最成功的研究之一”。
本文通过收集国内外学者专家关于VRP研究的相关文献资料并对文献资料进行整理、分类,详细介绍VRP问题国内外的研究现状,对VRP的模型和算法进行了分析;通过对物流车辆调度的基本现状分析,得出现阶段我国物流车辆调度工作中存在的问题,说明解决VRP问题的必要性及现实意义;分析了物流车辆调度的影响因素,对各主要因素对VRP问题的影响情况分别做了分析,分析每个主要因素对VRP问题的模型和算法的影响情况;通过引入不完备信息系统理论,采用基于不完备信息系统的改进ROUSTIDA数据补齐算法,这样,在决策表不完备的情况下,可以使用该办法对决策表进行处理,使其中缺失的数据得到补齐,为物流车辆调度的最终决策提供科学的决策依据;通过对VRP问题、模型、算法和影响因素的分析后,提出对物流车辆调度系统开发的一些建议。
Transportation comprises a significant fraction of the national economy. In the routine work, various modes of transportation all face such a common problem: how to make routes and timetables for the vehicles that passengers and goods can be transported from one place to another efficiently. These problems are generally known as vehicle routing problems (VRP) in the circles of operations research.
With increasing intensification of marketing competition, step out of global integration, and speedy development of science and technology, many enterprises have been conscious that logistic is an important measure to improve the ability of market competition and exalt the ability of coral competition, Being an important approach to realize logistic rationalization, research on vehicle routing problems will help enterprise to reduce logistical cost, improve operation efficiency, and enhance customer satisfaction roundly.
It is clear that the vehicle routing problem is the key problem in the optimization of transportation operations. Because vehicle routing problems bridge theory of Operations Research and practice of production, they are named as one of the most successful areas in Operations Research in the past decades.
Based on many related literatures, this article summarized the research findings in Vehicle Routing Problems (VRP) both internal and external. Upon the description on VRP and analysis of the VRP Model and Algorithm, this article analyzed the factors that affect the vehicle dispatch in physical distribution and also their separate influences on the VPR Model and Algorithm. Plus the adding of the Incomplete Information System data filled arithmetic ROUSTIDA Algorithm , which replenish those absent datas of the influencing factors, offers scientific and integrated foundation to the vehicle dispatch in physical distribution. Some Countermeasures and suggestions were proposed on VPR system development at the end of this article.
随着市场竞争的日益加剧、世界经济一体化进程的加快和科学技术的飞速发展,许多企业已经把物流作为提高市场竞争能力和提升核心竞争能力的重要手段。作为实现物流合理化的重要内容和手段,研究车辆路径有助于企业降低物流成本,提高运作效率,全面提高顾客满意度。
车辆路径问题是运输组织优化中的核心问题。由于车辆路径问题将运筹学理论与生产实践紧密地结合在一起,近几十年取得了很多成果,因此被称为“最近几十年运筹学领域最成功的研究之一”。
本文通过收集国内外学者专家关于VRP研究的相关文献资料并对文献资料进行整理、分类,详细介绍VRP问题国内外的研究现状,对VRP的模型和算法进行了分析;通过对物流车辆调度的基本现状分析,得出现阶段我国物流车辆调度工作中存在的问题,说明解决VRP问题的必要性及现实意义;分析了物流车辆调度的影响因素,对各主要因素对VRP问题的影响情况分别做了分析,分析每个主要因素对VRP问题的模型和算法的影响情况;通过引入不完备信息系统理论,采用基于不完备信息系统的改进ROUSTIDA数据补齐算法,这样,在决策表不完备的情况下,可以使用该办法对决策表进行处理,使其中缺失的数据得到补齐,为物流车辆调度的最终决策提供科学的决策依据;通过对VRP问题、模型、算法和影响因素的分析后,提出对物流车辆调度系统开发的一些建议。
Transportation comprises a significant fraction of the national economy. In the routine work, various modes of transportation all face such a common problem: how to make routes and timetables for the vehicles that passengers and goods can be transported from one place to another efficiently. These problems are generally known as vehicle routing problems (VRP) in the circles of operations research.
With increasing intensification of marketing competition, step out of global integration, and speedy development of science and technology, many enterprises have been conscious that logistic is an important measure to improve the ability of market competition and exalt the ability of coral competition, Being an important approach to realize logistic rationalization, research on vehicle routing problems will help enterprise to reduce logistical cost, improve operation efficiency, and enhance customer satisfaction roundly.
It is clear that the vehicle routing problem is the key problem in the optimization of transportation operations. Because vehicle routing problems bridge theory of Operations Research and practice of production, they are named as one of the most successful areas in Operations Research in the past decades.
Based on many related literatures, this article summarized the research findings in Vehicle Routing Problems (VRP) both internal and external. Upon the description on VRP and analysis of the VRP Model and Algorithm, this article analyzed the factors that affect the vehicle dispatch in physical distribution and also their separate influences on the VPR Model and Algorithm. Plus the adding of the Incomplete Information System data filled arithmetic ROUSTIDA Algorithm , which replenish those absent datas of the influencing factors, offers scientific and integrated foundation to the vehicle dispatch in physical distribution. Some Countermeasures and suggestions were proposed on VPR system development at the end of this article.
引文
[1]张建勇.模糊信息条件下车辆路径问题研究[D].成都:西南交通大学管理系,2003
[2]王国胤.Rough集理论与知识获取[M].西安:西安交通大学出版社,2001.
[3]李军,郭耀煌.物流配送车辆优化调度理论与方法[M]北京:中国物资出版社,2001
[4]Balinski M,Quand R.On an integer program for a delivery problem[J].Operations Research,1962,12:300-304
[5]Eilon S,Watson-Gandy C DT,Christofides N.distribution management:mathematicalmodeling and practical analysis[M].London::Griffin,1971
[6]Gillett B,Miller L.A heuristic algorithm for the vehicle dispatch problem[J].Operations Research,1974,22:340-349
[7]Christofides N,Mingozzi A,Toth P Exact algorithms for the vehicle routing problem,based on spanning the shortest path relaxation[J].Mathematical programming,1981,20:255-282
[8]Fisher M L.Optimal solution of vehicle routing problems using minimum k-trees[J].Operation Research,1994,42(4):626-642
[9]Gendreau M,Hertz A,Laporte G A tabu search heuristic for the vehicle routing Problem[M].Montreal:Publication#777,Centre de recherche sur les transpors,1991
[10]Taillard E.Parallel interactive search method for vehicle routing problems[J].Networks,1993,23:661-673
[11]Lawrence S,Mohammad A.Parametric experimentation with a genetic algorithmic configuration for solving the vehicle routing problem[A].Proceedings-Annual Meeting of the Decision sciences Institute[C].Decis Scil Inst.1996.488-490
[12]Nicolas B,Pascal B Optimization by hybridization of a genetic algorithm with constraint satisfaction techniques[A].Proceedings of the IEEE Conference on Evolutionary Computation[C].1998
[13]张涛,王梦光.遗传算法和3-OPT结合求解带有能力约束的VRP[J].东北大学学报(自然科学版),1999.20(3):254-256)
[14]肖鹏等.车辆路径问题的单亲遗传算法[J].计算技术与自动化,2000.19(1):26-30
[15]李嘉等.一类特殊车辆路径问题(VRP)[J].东北大学学报(自然科学版),2001.22(3):245-248
[16]张丽萍,柴跃廷.车辆路径问题的改进遗传算法[J].系统工程理论与实践,2002.8:79-84
[17]方霞等:基于免疫算法的物流配送车辆路径优化问题研究.[J].土木工程学报,2003.36(7).43-46
[18]纪寿文等.货运车辆优化调度方法[J].公路交通科技,2003.6:109-112
[19]王正彬,杜文.考虑线路安排的物流配送方案模型及其算法研究[J].技术交流2003年第12期72-73
[20]陈湘州,黎志明,刘祖润一种改进的整数编码遗传算法在车辆路径优化问题中的应用[J].南方冶金学院学报,2004.25(1):36-41
[21]顾志康,李旭宏,徐家兵一种改进遗传算法在物流配送车辆调度中的应用研究[J].公路交通科技,2004.11:118-120
[22]章兢,周泉.基于免疫克隆算法的物流配送车辆路径优化研究[J].湖南大学学报(自然科学版),2004.31(5):54-58
[23]Psaraftis,H.,A Dynamic Programming Solution to the single.Many-to-many Immediate Request Dial-a-Ride Problem.Transportation Science 14(1980)130-154.
[24]Bodin L,Golden B.Classification in Vehicle Routing and Scheduling,Networks,1981,11:7-108
[25]Gendreau M.,Guertin F,Potvin J..Taillard E..Parallel tabu search for real-time vehicle routing and dispatching.Transportation Science,1999.33(4):381-390
[26]Perincherry V.,Kikuchi S二A fuzzy approach to the transshipment problem.In:B.M.Ayyub(ed.).Proceeding of ISUMA'90.The International Symposiumon Uncertainty Modelling and Analysis,IEEE Computer Press.Silver Spring
[27]Teodorovic D.,Pavkovic G.The fuzzy set theory approach to the vehicle routing problem when demand at nodes is uncertain.Fuzzy Set and Systems.1996.82:307-317
[28]Teodorovic D.,Radivojevic G.A fuzzy logic approach to dynamic Dial-A-Ride problem.Fuzzy Set and Systems.2000,116:23-33
[29]谢秉磊,李军,郭耀煌.有时间窗的非满载车辆调度问题的遗传算法[J].系统工程学报,2000.(3):76-80
[30]朗茂祥 装卸混合车辆路径问题的模拟退火算法研究[J].系统工程学报2005年10月
[31]贾永基,谷寒雨,席裕庚.一类货运车辆调度问题的混合禁忌搜索算法[J].信息与控制,2004.(6):151-155
[32]孙福春,宁滨,遗传算法在车辆调度问题中的应用[J].交通与计算机,2005.(2):19-24
[33]贾永基,谷寒雨,席裕庚.动态车辆调度系统的滚动时域调度算法(英文)[J].JOURNAL OF SOUTHEAST UNIVERSITY,2005.(1):67-71
[34]韩世通,朱晓宁,刘金华.基于混合优化算法的带时间窗的车辆调度问题求解研究[J].物流科技,2005.(6):65-69
[35]高麟,杜文基于蚁群系统算法的车辆路径问题研究[J]物流技术2005年06期
[36]郎茂祥.配送车辆调度问题诌议[J]物流技术2003年03期
[37]李军.有时间窗的车辆调度问题的网络启发式算法[J].系统工程,1999.(2):68-73
[38]李军,郭耀煌.有时间窗的非满载车辆调度问题的遗传算法[J].系统工程学报, 2000.(3):76-80
[39]何建敏,刘春林.限制期条件下应急车辆调度问题的模糊优化方法[J].控制与决策,2001.(3):63-67
[40]叶志坚,叶怀珍,周道平,易海燕多车型车辆路径问题算法[J]公路交通科技2005年5月
[41]张明善,唐小我.多车场满载货运车辆优化调度的网络流算法[J].系统工程理论方法应用,2002.(3):43-48
[42]杭省策,李怀祖多车场车流分配的广义指派模型极其分解算法[J]西安交通大学学报1997年12月第31卷第12期
[43]董媛媛等带回程的车辆运输路径优化及定价模型[J]现代交通技术2006年第4期
[44]郭伏,隆颖带时间回程取货的车辆路径问题的算法[J]东北大学学报2006年5月
[45]刘宏志、李慧兰、赵启兰多目标配送路线的合理选择物流科技[J]1999年第一期
[46]曾黄麟.粗集理论及其应用[M].重庆:重庆大学出版社,1996.
[47]李春生,尹旭日,陈世福.基于Rough集的规则学习研究.小型微型计算机系统[J],2001,22(8):982-984.
[48]郝先臣,张德干,高光来,等.数据挖掘工具和应用中的问题[J]东北大学学报,2001,22(2):183-186.
[49]张振华,刘文奇 一种基于可辨识矩阵与决策规则独立原则的缺损数据知识发现方法[J]计算机工程2002年10月
[2]王国胤.Rough集理论与知识获取[M].西安:西安交通大学出版社,2001.
[3]李军,郭耀煌.物流配送车辆优化调度理论与方法[M]北京:中国物资出版社,2001
[4]Balinski M,Quand R.On an integer program for a delivery problem[J].Operations Research,1962,12:300-304
[5]Eilon S,Watson-Gandy C DT,Christofides N.distribution management:mathematicalmodeling and practical analysis[M].London::Griffin,1971
[6]Gillett B,Miller L.A heuristic algorithm for the vehicle dispatch problem[J].Operations Research,1974,22:340-349
[7]Christofides N,Mingozzi A,Toth P Exact algorithms for the vehicle routing problem,based on spanning the shortest path relaxation[J].Mathematical programming,1981,20:255-282
[8]Fisher M L.Optimal solution of vehicle routing problems using minimum k-trees[J].Operation Research,1994,42(4):626-642
[9]Gendreau M,Hertz A,Laporte G A tabu search heuristic for the vehicle routing Problem[M].Montreal:Publication#777,Centre de recherche sur les transpors,1991
[10]Taillard E.Parallel interactive search method for vehicle routing problems[J].Networks,1993,23:661-673
[11]Lawrence S,Mohammad A.Parametric experimentation with a genetic algorithmic configuration for solving the vehicle routing problem[A].Proceedings-Annual Meeting of the Decision sciences Institute[C].Decis Scil Inst.1996.488-490
[12]Nicolas B,Pascal B Optimization by hybridization of a genetic algorithm with constraint satisfaction techniques[A].Proceedings of the IEEE Conference on Evolutionary Computation[C].1998
[13]张涛,王梦光.遗传算法和3-OPT结合求解带有能力约束的VRP[J].东北大学学报(自然科学版),1999.20(3):254-256)
[14]肖鹏等.车辆路径问题的单亲遗传算法[J].计算技术与自动化,2000.19(1):26-30
[15]李嘉等.一类特殊车辆路径问题(VRP)[J].东北大学学报(自然科学版),2001.22(3):245-248
[16]张丽萍,柴跃廷.车辆路径问题的改进遗传算法[J].系统工程理论与实践,2002.8:79-84
[17]方霞等:基于免疫算法的物流配送车辆路径优化问题研究.[J].土木工程学报,2003.36(7).43-46
[18]纪寿文等.货运车辆优化调度方法[J].公路交通科技,2003.6:109-112
[19]王正彬,杜文.考虑线路安排的物流配送方案模型及其算法研究[J].技术交流2003年第12期72-73
[20]陈湘州,黎志明,刘祖润一种改进的整数编码遗传算法在车辆路径优化问题中的应用[J].南方冶金学院学报,2004.25(1):36-41
[21]顾志康,李旭宏,徐家兵一种改进遗传算法在物流配送车辆调度中的应用研究[J].公路交通科技,2004.11:118-120
[22]章兢,周泉.基于免疫克隆算法的物流配送车辆路径优化研究[J].湖南大学学报(自然科学版),2004.31(5):54-58
[23]Psaraftis,H.,A Dynamic Programming Solution to the single.Many-to-many Immediate Request Dial-a-Ride Problem.Transportation Science 14(1980)130-154.
[24]Bodin L,Golden B.Classification in Vehicle Routing and Scheduling,Networks,1981,11:7-108
[25]Gendreau M.,Guertin F,Potvin J..Taillard E..Parallel tabu search for real-time vehicle routing and dispatching.Transportation Science,1999.33(4):381-390
[26]Perincherry V.,Kikuchi S二A fuzzy approach to the transshipment problem.In:B.M.Ayyub(ed.).Proceeding of ISUMA'90.The International Symposiumon Uncertainty Modelling and Analysis,IEEE Computer Press.Silver Spring
[27]Teodorovic D.,Pavkovic G.The fuzzy set theory approach to the vehicle routing problem when demand at nodes is uncertain.Fuzzy Set and Systems.1996.82:307-317
[28]Teodorovic D.,Radivojevic G.A fuzzy logic approach to dynamic Dial-A-Ride problem.Fuzzy Set and Systems.2000,116:23-33
[29]谢秉磊,李军,郭耀煌.有时间窗的非满载车辆调度问题的遗传算法[J].系统工程学报,2000.(3):76-80
[30]朗茂祥 装卸混合车辆路径问题的模拟退火算法研究[J].系统工程学报2005年10月
[31]贾永基,谷寒雨,席裕庚.一类货运车辆调度问题的混合禁忌搜索算法[J].信息与控制,2004.(6):151-155
[32]孙福春,宁滨,遗传算法在车辆调度问题中的应用[J].交通与计算机,2005.(2):19-24
[33]贾永基,谷寒雨,席裕庚.动态车辆调度系统的滚动时域调度算法(英文)[J].JOURNAL OF SOUTHEAST UNIVERSITY,2005.(1):67-71
[34]韩世通,朱晓宁,刘金华.基于混合优化算法的带时间窗的车辆调度问题求解研究[J].物流科技,2005.(6):65-69
[35]高麟,杜文基于蚁群系统算法的车辆路径问题研究[J]物流技术2005年06期
[36]郎茂祥.配送车辆调度问题诌议[J]物流技术2003年03期
[37]李军.有时间窗的车辆调度问题的网络启发式算法[J].系统工程,1999.(2):68-73
[38]李军,郭耀煌.有时间窗的非满载车辆调度问题的遗传算法[J].系统工程学报, 2000.(3):76-80
[39]何建敏,刘春林.限制期条件下应急车辆调度问题的模糊优化方法[J].控制与决策,2001.(3):63-67
[40]叶志坚,叶怀珍,周道平,易海燕多车型车辆路径问题算法[J]公路交通科技2005年5月
[41]张明善,唐小我.多车场满载货运车辆优化调度的网络流算法[J].系统工程理论方法应用,2002.(3):43-48
[42]杭省策,李怀祖多车场车流分配的广义指派模型极其分解算法[J]西安交通大学学报1997年12月第31卷第12期
[43]董媛媛等带回程的车辆运输路径优化及定价模型[J]现代交通技术2006年第4期
[44]郭伏,隆颖带时间回程取货的车辆路径问题的算法[J]东北大学学报2006年5月
[45]刘宏志、李慧兰、赵启兰多目标配送路线的合理选择物流科技[J]1999年第一期
[46]曾黄麟.粗集理论及其应用[M].重庆:重庆大学出版社,1996.
[47]李春生,尹旭日,陈世福.基于Rough集的规则学习研究.小型微型计算机系统[J],2001,22(8):982-984.
[48]郝先臣,张德干,高光来,等.数据挖掘工具和应用中的问题[J]东北大学学报,2001,22(2):183-186.
[49]张振华,刘文奇 一种基于可辨识矩阵与决策规则独立原则的缺损数据知识发现方法[J]计算机工程2002年10月