物流配送车辆调度优化研究
|
摘要
物流配送是物流活动中直接与消费者相连的环节。在物流的各项成本中，配送成本占了相当高的比例。配送车辆调度的合理与否对配送速度、成本、效益影响很大，特别是多用户配送车辆调度的确定更为复杂。采用科学、合理的方法来进行配送车辆调度，是物流配送中非常重要的一项活动。因此，车辆调度问题(Vehicle Scheduling Problem，简记VSP)成为众多学者竟相研究的热门话题。在高度发展的商业社会中，特别是随着Internet的普及和电子商务的发展，消费者对时间的要求越来越严格，以往的到货“日”已转换成到货“时”。
VSP是一个典型的NP-难题，高效的精确算法存在的可能性不大，启发式算法虽能快速求解大型问题，但对解的质量没有保证。近些年来，人们在用遗传算法解决现实中的各种组合优化问题上进行了探索，如在生产调度问题中的应用，但在车辆调度问题中的应用才刚刚开始。有专家断言遗传算法是用来解决NP完全问题和NP难题的趋势。
本论文主要对有时间窗的非满载VSP和供应商管理库存(Vendor Managed Inventory，简记VMI)管理思想下的VSP进行了研究。
对于有时间窗的非满载VSP问题，将货运量约束和时间窗约束转化为目标约束，建立了VSP模型，使用最大保留交叉、交叉率和变异率的自适应调整等技术，设计了给予自然数编码的可同时处理软、硬时间窗约束的遗传算法，实验分析取得了较好的结果。本论文丰富了遗传算法在组合优化中的应用，为继续深入研究VSP、JOB—SHOP和物流配送车辆调度优化的计算机实现等打下基础。
对于VMI下的VSP问题，可以看作上述VSP的问题的延伸。本文分析了VMI对于供应链物流配送系统优化的作用。在VMI管理方式下，存在库存和配送运输可以集成起来进一步优化配送系统成本这一实际情况。接着对此问题建立了数学模型和迭代优化算法，实例证明该模型和算法能够起到较好的效果。
武汉理工大学硕士学位论文
物流配送车辆调度优化，是物流配送优化中关键的一环，也是电子商务活
动不可缺少的内容。对货运车辆进行调度优化，可以提高物流经济效益、实现
物流科学化。对货运车辆调度优化理论与方法进行系统研究是物流集约化发展、
建立现代调度指挥系统、发展智能交通运输系统和开展电子商务的基础。目前，
问题的形式已有很大发展，该问题以不仅仅局限于汽车运输领域，在水运、
航空、通讯、电力、工业管理、计算机应用等领域也有一定的应用，其算法
已用于航空乘务员轮班安排、轮船公司运送货物经过港口与货物安排的优化
设计、交通车线路安排、生产系统中的计划与控制等多种组合优化问题。
Logistic distribution is an operation linking with consumer directly ,and takes account for considerable proportion in variable costs in logistics. The planning of vehicle scheduling in distribution will be take great effect on the efficiency ,cost ,and benefit, especially in distributing for multi consumers. A scientific and reasonable method to vehicle scheduling is an important operation in logistic distribution. So,vehicle scheduling problem had become focus of many scholars to study. In the developed commercial society . With popularization of internet and development of electronic commerce, requirement of comsumer for delivery time is higher and higher so that delivery day formerly had rum to delivery hour now.
VSP is a typical strong NP- hard problem,high effective exact algorithm is immposible to it. Heuristic Algorithm can resolve large-scale problem,but cannot ensure the quality of the resolution. Recently, genetic algorithm has been tyied to resolve variable combinatorial optimization problems, such as job scheduling problem,but but has began just now in VSP. Some people assert that genetic algorithm has tended to NP-had problem.
This paper attempts to take VSP with time window and VSP in VMI as the tow core problems for further research.
On the VSP with time window,while the restraints of capacity and time windows are changed into object restraints,a mathematic model is established.We use technique such as maximum preserved crossover and selfadaptability change of probability of crossover and mutation,and design genetic algorithm on nature number,which can deal with soft and hard time windows.The excellent solutions are obtained in the application.
VSP in VMI may be looked as the stretch of the VSP above. On the VSP in VMI,this paper analyses the contribution of the optimization of logistic distribution's system.Being aimed at looking for the optimal distribution policy.this paper put delivery routing and inventory into consideration jointly,and brings forward an mathematic model and its algorithm.Consequently,results from the case proved the availability of the model and its algorithm.
VSP is both a pivotal tache in logistic distribution optimization and indispensable in electronic commerce.It can increase logistic economic benefit and realize logistic rationalization.The systemic study on the theory and method of VSP is the base on the growth of logistic intensivism ,the establishment of modem chain of command,the development of ITS and EC.Now,the problem is not only applied to the field of auto transportation,but also to ship avigation communication electricity industry management computer application etc.The algorithm has been applied into many combinatorial optimization problems such as the trainman's shift arrangement in avigation the optimization design of cargo arrangement in ship company . traffic routing arrangement and the plan and control in the production system.
VSP是一个典型的NP-难题，高效的精确算法存在的可能性不大，启发式算法虽能快速求解大型问题，但对解的质量没有保证。近些年来，人们在用遗传算法解决现实中的各种组合优化问题上进行了探索，如在生产调度问题中的应用，但在车辆调度问题中的应用才刚刚开始。有专家断言遗传算法是用来解决NP完全问题和NP难题的趋势。
本论文主要对有时间窗的非满载VSP和供应商管理库存(Vendor Managed Inventory，简记VMI)管理思想下的VSP进行了研究。
对于有时间窗的非满载VSP问题，将货运量约束和时间窗约束转化为目标约束，建立了VSP模型，使用最大保留交叉、交叉率和变异率的自适应调整等技术，设计了给予自然数编码的可同时处理软、硬时间窗约束的遗传算法，实验分析取得了较好的结果。本论文丰富了遗传算法在组合优化中的应用，为继续深入研究VSP、JOB—SHOP和物流配送车辆调度优化的计算机实现等打下基础。
对于VMI下的VSP问题，可以看作上述VSP的问题的延伸。本文分析了VMI对于供应链物流配送系统优化的作用。在VMI管理方式下，存在库存和配送运输可以集成起来进一步优化配送系统成本这一实际情况。接着对此问题建立了数学模型和迭代优化算法，实例证明该模型和算法能够起到较好的效果。
武汉理工大学硕士学位论文
物流配送车辆调度优化，是物流配送优化中关键的一环，也是电子商务活
动不可缺少的内容。对货运车辆进行调度优化，可以提高物流经济效益、实现
物流科学化。对货运车辆调度优化理论与方法进行系统研究是物流集约化发展、
建立现代调度指挥系统、发展智能交通运输系统和开展电子商务的基础。目前，
问题的形式已有很大发展，该问题以不仅仅局限于汽车运输领域，在水运、
航空、通讯、电力、工业管理、计算机应用等领域也有一定的应用，其算法
已用于航空乘务员轮班安排、轮船公司运送货物经过港口与货物安排的优化
设计、交通车线路安排、生产系统中的计划与控制等多种组合优化问题。
Logistic distribution is an operation linking with consumer directly ,and takes account for considerable proportion in variable costs in logistics. The planning of vehicle scheduling in distribution will be take great effect on the efficiency ,cost ,and benefit, especially in distributing for multi consumers. A scientific and reasonable method to vehicle scheduling is an important operation in logistic distribution. So,vehicle scheduling problem had become focus of many scholars to study. In the developed commercial society . With popularization of internet and development of electronic commerce, requirement of comsumer for delivery time is higher and higher so that delivery day formerly had rum to delivery hour now.
VSP is a typical strong NP- hard problem,high effective exact algorithm is immposible to it. Heuristic Algorithm can resolve large-scale problem,but cannot ensure the quality of the resolution. Recently, genetic algorithm has been tyied to resolve variable combinatorial optimization problems, such as job scheduling problem,but but has began just now in VSP. Some people assert that genetic algorithm has tended to NP-had problem.
This paper attempts to take VSP with time window and VSP in VMI as the tow core problems for further research.
On the VSP with time window,while the restraints of capacity and time windows are changed into object restraints,a mathematic model is established.We use technique such as maximum preserved crossover and selfadaptability change of probability of crossover and mutation,and design genetic algorithm on nature number,which can deal with soft and hard time windows.The excellent solutions are obtained in the application.
VSP in VMI may be looked as the stretch of the VSP above. On the VSP in VMI,this paper analyses the contribution of the optimization of logistic distribution's system.Being aimed at looking for the optimal distribution policy.this paper put delivery routing and inventory into consideration jointly,and brings forward an mathematic model and its algorithm.Consequently,results from the case proved the availability of the model and its algorithm.
VSP is both a pivotal tache in logistic distribution optimization and indispensable in electronic commerce.It can increase logistic economic benefit and realize logistic rationalization.The systemic study on the theory and method of VSP is the base on the growth of logistic intensivism ,the establishment of modem chain of command,the development of ITS and EC.Now,the problem is not only applied to the field of auto transportation,but also to ship avigation communication electricity industry management computer application etc.The algorithm has been applied into many combinatorial optimization problems such as the trainman's shift arrangement in avigation the optimization design of cargo arrangement in ship company . traffic routing arrangement and the plan and control in the production system.
引文
[1] 现代物流管理课题组编．运输与配送管理．广州：广东经济出版社，2002，10
[2] 丁立言，张铎等．物流企业管理．北京：清华大学出版社，1999
[3]马建平等．现代物流配送管理．广州：中山大学出版社，2001
[4] 宋华等．现代物流与供应链管理．北京：经济管理出版社，2000
[5] 骆温平．第三方物流．上海：上海社会科学院出版社，2001
[6] 丁立言，张铎．物流系统工程．北京：清华大学出版社，1999
[7] 李建民．VMI在库存管理中的应用．综合运输，2002，(5)
[8] 何明苛等．现代配送中心：推动流通创新的趋势．北京：中国商业出版社，1997
[9] 郭耀煌等．货运优化调度模型及算法．西南地区运筹学学术会议．昆明，1990
[10] 郭耀煌等．车辆优化调度问题的研究现状评述．西南交通大学学报，1995，Vol．30，No．4
[11] 郭耀煌．安排城市卡车行车线路的一种新算法．系统工程学报，1989，No2
[12] 郭耀煌．复杂道路网上货运卡车的优化调度．西南交通大学学报，1988，No．4
[13] 李军等．加强区域物流运输科学调度研究．中国交通研究与探索．北京：人民交通出版社，1999
[14] 张震．城市货运汽车营运组织最优化的理论与方法．管理工程学报，1995，Vol．9，No．3
[15] 胡怀邦等．现代物流管理学．广州：中山大学出版社，2001
[16] 姜大力等．车辆路径问题的遗传算法研究．系统工程理论与实践，1999．Vol．18，p40—45
[17] 张薰华等．交通经济学．上海：上海社会科学院出版社，1998
[18] 郭耀煌等．货运调度的一种序列优化算法．汽车运输研究，1994，Vol．11，No．3
[19] 常发亮等．物资配送中心的物流调度与优化研究．高技术通讯，1997．12．
[20] 郭耀煌等．一种派车算法．运筹与决策．成都：成都科技大学出版社，1992
[21] 纪树新等．车间作业调度遗传算法中的交叉算子的研究．控制与决策，1998，Vol．18．No．2
[22] 李军．车辆调度问题的分派启发式算法．系统工程理论与实践，1999，Vol．17，No．2
[23] 陈惠开．网络——网络流．北京：人民邮电出版社，1992
[24] 富尔兹L．R．组合最优化．北京：上海翻译出版社
[25] 李大卫等．遗传算法在有时间窗车辆路径问题上的应用．系统工程理论与实践，1999，19(8)
[26] 田丰等．图与网络流理论．北京：科学出版社，1987
[27] 王树禾．图论及其算法．合肥：中国科学技术大学出版社
[28] 玄光男等．遗传算法与工程设计．北京：科技出版社，2000
[29] 席裕庚等．遗传算法综述．控制理论与应用，1999，No．6
[30] 王熙法等．遗传算法与遗传规划．北京：冶金出版社，1996
[31]陈国良等．遗传算法及其应用．北京：中国邮电出版社，1996
[32]陈恩红．遗传算法的若干理论问题研究．软件学报，1997，增刊
[33]李军等．基于自然数编码的模式理论研究．西南交通大学学报，2000，Vol．35，No．1
[34]孙艳丰等．遗传算法在优化问题中的应用研究进展．控制理论与决策，1996，Vol．11，No．
[35]Glden B.L.Introduction to Recent Advances in Vehicle Routing Methods.Transportation Planning Models,1984
[35]Cesar Rego.A Subpath Ejection Method for The Vehicle Routing Routing Problem.Manegement Science , I998,Vol.44,No.10
[36]Cattrysse D.ete..Set Partitioning and column Generation Heuristics for Capacitated Dynamic Lotsizing.European Journal of Operational Research, 1999, Vol.46
[37]Fiechter.A parallel tabu search algorithm for large traveling salesman problem.Discrete Application Mathematics,1994,Vol.51
[38]Goldberg D E .Alleles, loci, and the traveling salesman problem.Second Int.Conf.on Genetic Algorithms and their Applications,1985
[39]Dejong K A.Analysis of the behavior of a class of genetic adaptive systems.Ph.D.thesis.Univ.of Michigan.Ann Arbir, Mich.1975
[40]Christofides N.The Vehicle Routing Problem.Combinatorial Optimization.Johnly Wiley, New York,1979
[41]Pureza V M.Vehicle Routing Problem via Tabu Search Metaheuristies.Publication CRT-747,Centre de Recherche sur les Transports, Montreal,1991
[42]Held,M.& R.Karp, "The Traveling salesman problem and minimum spanning trees",Operations Research,1970,18,1138-1162.
[43]Kolen,A.W.J,Rinnooy Kan,A.H.G. and Trienkens,H.W.J.M, "Vehicle routing and scheduling with time windows",Operations research,1987, 35(2)
[44]Solomon,M.M., "Vehicle routing and scheduling with time windows constrains:models and algorithms"Ph.D.dissertation,Dept of decision sciences,University of Pennsylvania,1983.
[45]Gillett,B.& Miller, L., "A heuristic algorithm for the vehicle dispatch problem",Operation research,1974, 22,340-349
[46]Mole,R.H.& Jameson,S.R., "A study of permulation crossover operators on the traveling salesman problem",Genetic algorithms and their appliacation:proceeding of second Int.Conf. on Genetic algorithms, 1976,224-230.
[47]Clarke,G & Wright,J.W., "Scheduling vehicles from a center delivery deport to a number of delivery points",Operation research quarterly,1964,12,568-581.
[2] 丁立言，张铎等．物流企业管理．北京：清华大学出版社，1999
[3]马建平等．现代物流配送管理．广州：中山大学出版社，2001
[4] 宋华等．现代物流与供应链管理．北京：经济管理出版社，2000
[5] 骆温平．第三方物流．上海：上海社会科学院出版社，2001
[6] 丁立言，张铎．物流系统工程．北京：清华大学出版社，1999
[7] 李建民．VMI在库存管理中的应用．综合运输，2002，(5)
[8] 何明苛等．现代配送中心：推动流通创新的趋势．北京：中国商业出版社，1997
[9] 郭耀煌等．货运优化调度模型及算法．西南地区运筹学学术会议．昆明，1990
[10] 郭耀煌等．车辆优化调度问题的研究现状评述．西南交通大学学报，1995，Vol．30，No．4
[11] 郭耀煌．安排城市卡车行车线路的一种新算法．系统工程学报，1989，No2
[12] 郭耀煌．复杂道路网上货运卡车的优化调度．西南交通大学学报，1988，No．4
[13] 李军等．加强区域物流运输科学调度研究．中国交通研究与探索．北京：人民交通出版社，1999
[14] 张震．城市货运汽车营运组织最优化的理论与方法．管理工程学报，1995，Vol．9，No．3
[15] 胡怀邦等．现代物流管理学．广州：中山大学出版社，2001
[16] 姜大力等．车辆路径问题的遗传算法研究．系统工程理论与实践，1999．Vol．18，p40—45
[17] 张薰华等．交通经济学．上海：上海社会科学院出版社，1998
[18] 郭耀煌等．货运调度的一种序列优化算法．汽车运输研究，1994，Vol．11，No．3
[19] 常发亮等．物资配送中心的物流调度与优化研究．高技术通讯，1997．12．
[20] 郭耀煌等．一种派车算法．运筹与决策．成都：成都科技大学出版社，1992
[21] 纪树新等．车间作业调度遗传算法中的交叉算子的研究．控制与决策，1998，Vol．18．No．2
[22] 李军．车辆调度问题的分派启发式算法．系统工程理论与实践，1999，Vol．17，No．2
[23] 陈惠开．网络——网络流．北京：人民邮电出版社，1992
[24] 富尔兹L．R．组合最优化．北京：上海翻译出版社
[25] 李大卫等．遗传算法在有时间窗车辆路径问题上的应用．系统工程理论与实践，1999，19(8)
[26] 田丰等．图与网络流理论．北京：科学出版社，1987
[27] 王树禾．图论及其算法．合肥：中国科学技术大学出版社
[28] 玄光男等．遗传算法与工程设计．北京：科技出版社，2000
[29] 席裕庚等．遗传算法综述．控制理论与应用，1999，No．6
[30] 王熙法等．遗传算法与遗传规划．北京：冶金出版社，1996
[31]陈国良等．遗传算法及其应用．北京：中国邮电出版社，1996
[32]陈恩红．遗传算法的若干理论问题研究．软件学报，1997，增刊
[33]李军等．基于自然数编码的模式理论研究．西南交通大学学报，2000，Vol．35，No．1
[34]孙艳丰等．遗传算法在优化问题中的应用研究进展．控制理论与决策，1996，Vol．11，No．
[35]Glden B.L.Introduction to Recent Advances in Vehicle Routing Methods.Transportation Planning Models,1984
[35]Cesar Rego.A Subpath Ejection Method for The Vehicle Routing Routing Problem.Manegement Science , I998,Vol.44,No.10
[36]Cattrysse D.ete..Set Partitioning and column Generation Heuristics for Capacitated Dynamic Lotsizing.European Journal of Operational Research, 1999, Vol.46
[37]Fiechter.A parallel tabu search algorithm for large traveling salesman problem.Discrete Application Mathematics,1994,Vol.51
[38]Goldberg D E .Alleles, loci, and the traveling salesman problem.Second Int.Conf.on Genetic Algorithms and their Applications,1985
[39]Dejong K A.Analysis of the behavior of a class of genetic adaptive systems.Ph.D.thesis.Univ.of Michigan.Ann Arbir, Mich.1975
[40]Christofides N.The Vehicle Routing Problem.Combinatorial Optimization.Johnly Wiley, New York,1979
[41]Pureza V M.Vehicle Routing Problem via Tabu Search Metaheuristies.Publication CRT-747,Centre de Recherche sur les Transports, Montreal,1991
[42]Held,M.& R.Karp, "The Traveling salesman problem and minimum spanning trees",Operations Research,1970,18,1138-1162.
[43]Kolen,A.W.J,Rinnooy Kan,A.H.G. and Trienkens,H.W.J.M, "Vehicle routing and scheduling with time windows",Operations research,1987, 35(2)
[44]Solomon,M.M., "Vehicle routing and scheduling with time windows constrains:models and algorithms"Ph.D.dissertation,Dept of decision sciences,University of Pennsylvania,1983.
[45]Gillett,B.& Miller, L., "A heuristic algorithm for the vehicle dispatch problem",Operation research,1974, 22,340-349
[46]Mole,R.H.& Jameson,S.R., "A study of permulation crossover operators on the traveling salesman problem",Genetic algorithms and their appliacation:proceeding of second Int.Conf. on Genetic algorithms, 1976,224-230.
[47]Clarke,G & Wright,J.W., "Scheduling vehicles from a center delivery deport to a number of delivery points",Operation research quarterly,1964,12,568-581.