物流配送调度系统的研究
|
摘要
近些年，物流作为“第三方利润的源泉”受到国内各行业的极大重视并得到了较大的发展，大量规模较大的生产企业，商业企业纷纷建立起配送中心向商品流通的效率发起挑战。与此同时，相当部分的大型运输、仓储和航运企业也开始朝向第三方物流经营。物流配送开始在我国迅速发展起来。如何在提高物流配送效率的同时降低成本成为一个重要的研究课题。
本文在对物流配送业务作详细介绍的基础上，针对配送运输管理决策中所需要考虑的核心问题—车辆调度问题VRP(Vehicle Routing and Scheduling Problem)的优化进行了研究。车辆调度问题主要内容是车辆分配和配送线路的生成。
本文研究工作主要包括以下几个方面：
在车辆调度问题中的车辆分配问题，本文首先分析了该问题。根据约束条件和优化目标，提出了该问题的一般数学模型，然后建立车辆数据库，提出了一种精度高、运算速度快、对初值要求小的新型调度算法对这个问题求解。
在车辆调度问题中的配送线路的生成问题上，首先分析了物流配送中运输线路的问题并建立了该问题的数学模型，发现合车送货可大大降低运输的成本。提出建立地理数据库用以存储配送区域的地理信息，大大减少生成配送计划的时间，并为运输线路的优化奠定基础。在地理数据库的基础上，单车配送可直接在地理数据库中查出配送线路，对于合车送货和有时间窗的配送线路生成问题采用一种启发式算法—蚂蚁算法进行优化。
针对物流配送的快速发展和计算机配送调度系统面临着的巨大应用前景，本文提出开发计算机配送调度系统的设想。根据实际物流配送业务中可能存在多种配送类型和形式，指出所开发的系统应能根据实际业务特点加入多种约束，进行灵活的优化调度处理。在所设想的基础上，以第三方物流配送企业为背景，对配送运输计算和优化调度系统进行了设计。根据以上的理论建立一套物流配送调度系统，文章的最后通过给出的实例证明了这套系统能大大节省生成计划的时间和降低配送的成本。
Recent years, logistics, taken as "third profit resource ", has been developing rapidly. Lots of physical distribution centers were 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, How to decrease distribution cost is concerned..
Elaboration on the knowledge of physical distribution, this paper attempts to take delivery routing and inventory as the core problem - VRP for further research.
On the vehicle assigning problem of VRP, analyze this problem in the logistics at first .Second , in term of the restrains and objective , the general mathematics model of this question is introduced, Set up vehicle data base and use a kind of new-type algorithms which is high accuracy , operation is fast to solve the problem .
On the vehicle routing problem of VRP, first, analyze this problem and mathematics model is introduced. Set up geographical data base in order to store the area's geographical information The geographical data base can reduce the time of making the logistics plan greatly .On the basis of geographical data base, delivery goods directly can find the routing of providing and deliver in the geographical data base directly, For delivers goods for the demand most with the vehicle at least and delivers goods with time restriction problems, optimize the routing with a kind of algorithms of intelligence -ant algorithms.
Because of the prosperous future of logistics development, the logistics dispatch system will be of great necessity. Base on practically and flexibility, primary design of the system is worked out in this paper.
本文在对物流配送业务作详细介绍的基础上，针对配送运输管理决策中所需要考虑的核心问题—车辆调度问题VRP(Vehicle Routing and Scheduling Problem)的优化进行了研究。车辆调度问题主要内容是车辆分配和配送线路的生成。
本文研究工作主要包括以下几个方面：
在车辆调度问题中的车辆分配问题，本文首先分析了该问题。根据约束条件和优化目标，提出了该问题的一般数学模型，然后建立车辆数据库，提出了一种精度高、运算速度快、对初值要求小的新型调度算法对这个问题求解。
在车辆调度问题中的配送线路的生成问题上，首先分析了物流配送中运输线路的问题并建立了该问题的数学模型，发现合车送货可大大降低运输的成本。提出建立地理数据库用以存储配送区域的地理信息，大大减少生成配送计划的时间，并为运输线路的优化奠定基础。在地理数据库的基础上，单车配送可直接在地理数据库中查出配送线路，对于合车送货和有时间窗的配送线路生成问题采用一种启发式算法—蚂蚁算法进行优化。
针对物流配送的快速发展和计算机配送调度系统面临着的巨大应用前景，本文提出开发计算机配送调度系统的设想。根据实际物流配送业务中可能存在多种配送类型和形式，指出所开发的系统应能根据实际业务特点加入多种约束，进行灵活的优化调度处理。在所设想的基础上，以第三方物流配送企业为背景，对配送运输计算和优化调度系统进行了设计。根据以上的理论建立一套物流配送调度系统，文章的最后通过给出的实例证明了这套系统能大大节省生成计划的时间和降低配送的成本。
Recent years, logistics, taken as "third profit resource ", has been developing rapidly. Lots of physical distribution centers were 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, How to decrease distribution cost is concerned..
Elaboration on the knowledge of physical distribution, this paper attempts to take delivery routing and inventory as the core problem - VRP for further research.
On the vehicle assigning problem of VRP, analyze this problem in the logistics at first .Second , in term of the restrains and objective , the general mathematics model of this question is introduced, Set up vehicle data base and use a kind of new-type algorithms which is high accuracy , operation is fast to solve the problem .
On the vehicle routing problem of VRP, first, analyze this problem and mathematics model is introduced. Set up geographical data base in order to store the area's geographical information The geographical data base can reduce the time of making the logistics plan greatly .On the basis of geographical data base, delivery goods directly can find the routing of providing and deliver in the geographical data base directly, For delivers goods for the demand most with the vehicle at least and delivers goods with time restriction problems, optimize the routing with a kind of algorithms of intelligence -ant algorithms.
Because of the prosperous future of logistics development, the logistics dispatch system will be of great necessity. Base on practically and flexibility, primary design of the system is worked out in this paper.
引文
[1] 李苏剑，常志明。MRP系统下的物流管理，企业物流，2000年第6期
[2] Koksalan M, Sural H,Kirca O.A location-distribution application for a beer company[J] .Europen Journal of Operational Reseatch, 1995,80:60-24
[3] AGNETIS A.Planning the routing mix in FASs to minimize total transportation time[J],International Journal of Flexible Manufacturing Systems, 1996,(2): 131-157.
[4] 叶杰刚著，配送；运行与发展，经济管理出版社，1999。132—198
[5] 宋华，胡左浩，现代物流与供应链管理，经济管理出版社
[6] 路成章，物流简论及公路运输业发展物流的策略，公路交通科技，1999年16卷增刊
[7] 王平，唐喜平，冯辉宗。物流配送车辆计划调度系统的设计与实现，计算机工程，第27卷，第9期
[8] 王平，胡向东 电子商务环境下的物流配送决策支持系统，计算机系统与应用，2001年10期
[9] 闻学伟，汝宜红。智能物流系统设计及应用，交通运输系统工程与信息，2002年第2卷第1期
[10] 朱志辉，李广文，分布式物流系统管理系统的研究，2001年第15卷第2期
[11] 唐孝飞，孙壮志，胡思继。物流配送决策系统的分析，北方交通大学学报，2002年26期
[12] 李军，郭辉煌，物流配送车辆优化调度理论与方法[M]．北京：中国物资出版社，2001
[13] Bertsimas.DJ.,Simchi-Levj. A new generation of vechile routing research :Robust Alogrithms Addressing Uncertainty .Operations Res. 1996.44(2):286-304
[14] 袁庆达，杜文，周再铃，带软时间窗的混和车队车辆路线问题的模型和算法研究，2001年第30卷，第4期
[15] 蔡延光，钱积新，孙优贤．带时间窗的多重运输调度问题的自适应 Tabu Search算法，系统工程理论与实践，2002年12期。
[16] 胡祥培，许智超，杨德礼，智能运筹学与动态系统实时优化控制，管理科学学报，第5卷第4期2002年8月
[17] 李军，车辆调度问题的分派启发式算法，系统工程理论与实践，1999年第1期
[18] 高培旺，唐忠旺，目标等值面切割定界法与割平面法组合求解整数规划，管理科学学报，第20卷第1期，2003年
[19] 蒲在毅，任建军，用标号实现单源最短路径问题的迪杰斯特(dijkstra)算法，四川示范学院学报(自然科学版)第24卷第1期，2003年3月
[20] Hiroshi KISE, Mingzhe LU, Guiyan H U, Tan LI, Heuristics for Improving Operational Performance of Permutation Circulation-type Vehicle Routing System, Journal of Xia men University(Natural Science),Vol 41 ,2002 Oct
[21] 陈晓伟，张悟移，耿继武，节约法在配送线路选择中的应用，昆明理工大学学报(理工版)，第28
卷第4期，2003年
[22] 蔡延光，钱积新，孙优贤，带时间窗的多重运输调度问题的自适应Tabu Search算法，系统工程理论与实践，第12期，2000年12月
[23] 蔡延光，钱积新，孙优贤，多重运输调度问题的分枝定界算法及界限估计，系统工程与电子技术，1998年第4期
[24] 蔡延光，钱积新，孙优贤，多重运输调度问题的模拟退火算法，系统工程理论与实践，第10期1998年
[25] DEMENULEMEESTER L,LAPORTE G,LOUEAUX FV,Optimal sequencing of skip collections and deliveries[J],Journal of the Operational Reserch Society., 1997,(1):57-64
[26] 王会云，论物流系统化的基本方法，物流技术，2000年第2期
[27] 候巧玲，浅谈物流／供应链管理系统，制造业自动化，2002年。
[28] 苏一旦，李桂。电子商务物流管理信息系统中的最优(佳)径算法研究，计算机工程与应用，2002年18期
[29] 梅绍祖，INTERNET与电子商务和物流，1998年第3卷第4期
[30] 忻斌建，汪镭，吴启迪，蚁群算法的研究现状和应用及蚂蚁智能体的硬件实现，同济大学学报，2002年，第30卷，第一期
[31] Dorgom M, Bonabeau E , Theraulaz GAnt Algorithm and stigmergy[J].Future Generation Computer Systems,2000,16(6):851-871
[32] Dorigo M, Caro G D ,Gambardella L M. Antalgorithms for discrete optimization[J].Artificial Life, 1999,5(2):137-172
[33] 马良，瓶颈TSP的蚂蚁系统优化，计算机工程，2001年，第27卷。第9期
[34] 白国仲，毛经中，C指派问题，系统工程理论与实践，2003年第3期
[35] 陈雄．李海刚，吴启迪，基于遗传算法的Job-shop调度问题研究，同济大学学报，第30卷第1期，2002年1月
[36] 马良 蒋馥，多目标旅行售货员问题的蚂蚁算法求解，系统工程理论方法应用，1999年，第8卷，第4期
[37] Li Layuan, Li Chunlin A Heuristic Algorithm for QoS Multicast Routing, Journal of System Engineering and Electronics, Vol,13,No,4,2002,pp,73-78
[38] 顾军华，侯向丹等，基于蚂蚁算法的QoS组播路由问题求解，河北工业大学学报，2002年，第31卷，第4期
[39] 马良，离散系统优化的蚂蚁算法研究[D]．上海交通大学管理学院，1999年
[40] 张维明．信息系统建模技术与应用[M]．北京：电子工业出版社，1997
[41] 朗茂祥．物流配送车辆调度问题的模型和算法研究[D]．北方交通大学学报，2002
[42] 吴自库，刘国柱，配送问题的数学模型及近似算法，青岛化工学院学报 1998，19(3)
[43] 陆锋等，基于层次空间推理的交通网络行车最优路径算法[J]，武汉测绘大学学报2000．18．4
[44] AGNETIS A.Planning the routing mix in FASs to minimize total transportation time[J],International
Journal of Flexible Manufacturing Systems, 1996,(2): 131-157.
[45] Barcia P, Jornsten K, Imporved Langrangean Decompostion:An Application to the Generalized Assignment Problem.Europen Jouranl of Operational Reserch,1990,46:84-92
[46] 高洪深．决策支持系统理论方法案例[M]．清华大学出版社，1996
[47] 孙劲光，“背包问题”算法设计及分析，辽宁工程技术大学学报(自然科学版)2002年4月
[48] 李娟，方平，周明，一种求解背包问题的混和遗传算法，南昌航空工业学院学报，1998年第3期
[49] 于秀霞，求解背包问题的新型算法，长春大学学报，12卷第2期
[50] Min H,Jayaram an V, Rajesh Srivastava R.Combined location problem:a synthesis and future research directions[J],Eourpean Journal of Operational Research, 1998,108:1-15
[51] 肖鹏，李茂军，张军平，叶涛，单亲遗传算法及其在物流配送系统中的应用
[52] 华宝玉，王雪峰，冯英浚，有时间窗约束单车型非满载车辆调度问题的遗传算法，哈尔滨商业大学学报(自然科学版)第18卷第6期
[53] 谢秉磊，李军，郭辉煌，有时间窗的非满载车辆调度问题的遗传算法，系统工程学报，2000年第15卷第3期
[54] 戴树贵，孙强，潘萌荣，带限制条件的多权最短路径近似算法，计算机工程，2003年第29卷，第7期
[55] 毕军，付梦鄞，张宇河，一种改进的蚁群算法求解最短路径问题，计算机工程与应用，2003年
[2] Koksalan M, Sural H,Kirca O.A location-distribution application for a beer company[J] .Europen Journal of Operational Reseatch, 1995,80:60-24
[3] AGNETIS A.Planning the routing mix in FASs to minimize total transportation time[J],International Journal of Flexible Manufacturing Systems, 1996,(2): 131-157.
[4] 叶杰刚著，配送；运行与发展，经济管理出版社，1999。132—198
[5] 宋华，胡左浩，现代物流与供应链管理，经济管理出版社
[6] 路成章，物流简论及公路运输业发展物流的策略，公路交通科技，1999年16卷增刊
[7] 王平，唐喜平，冯辉宗。物流配送车辆计划调度系统的设计与实现，计算机工程，第27卷，第9期
[8] 王平，胡向东 电子商务环境下的物流配送决策支持系统，计算机系统与应用，2001年10期
[9] 闻学伟，汝宜红。智能物流系统设计及应用，交通运输系统工程与信息，2002年第2卷第1期
[10] 朱志辉，李广文，分布式物流系统管理系统的研究，2001年第15卷第2期
[11] 唐孝飞，孙壮志，胡思继。物流配送决策系统的分析，北方交通大学学报，2002年26期
[12] 李军，郭辉煌，物流配送车辆优化调度理论与方法[M]．北京：中国物资出版社，2001
[13] Bertsimas.DJ.,Simchi-Levj. A new generation of vechile routing research :Robust Alogrithms Addressing Uncertainty .Operations Res. 1996.44(2):286-304
[14] 袁庆达，杜文，周再铃，带软时间窗的混和车队车辆路线问题的模型和算法研究，2001年第30卷，第4期
[15] 蔡延光，钱积新，孙优贤．带时间窗的多重运输调度问题的自适应 Tabu Search算法，系统工程理论与实践，2002年12期。
[16] 胡祥培，许智超，杨德礼，智能运筹学与动态系统实时优化控制，管理科学学报，第5卷第4期2002年8月
[17] 李军，车辆调度问题的分派启发式算法，系统工程理论与实践，1999年第1期
[18] 高培旺，唐忠旺，目标等值面切割定界法与割平面法组合求解整数规划，管理科学学报，第20卷第1期，2003年
[19] 蒲在毅，任建军，用标号实现单源最短路径问题的迪杰斯特(dijkstra)算法，四川示范学院学报(自然科学版)第24卷第1期，2003年3月
[20] Hiroshi KISE, Mingzhe LU, Guiyan H U, Tan LI, Heuristics for Improving Operational Performance of Permutation Circulation-type Vehicle Routing System, Journal of Xia men University(Natural Science),Vol 41 ,2002 Oct
[21] 陈晓伟，张悟移，耿继武，节约法在配送线路选择中的应用，昆明理工大学学报(理工版)，第28
卷第4期，2003年
[22] 蔡延光，钱积新，孙优贤，带时间窗的多重运输调度问题的自适应Tabu Search算法，系统工程理论与实践，第12期，2000年12月
[23] 蔡延光，钱积新，孙优贤，多重运输调度问题的分枝定界算法及界限估计，系统工程与电子技术，1998年第4期
[24] 蔡延光，钱积新，孙优贤，多重运输调度问题的模拟退火算法，系统工程理论与实践，第10期1998年
[25] DEMENULEMEESTER L,LAPORTE G,LOUEAUX FV,Optimal sequencing of skip collections and deliveries[J],Journal of the Operational Reserch Society., 1997,(1):57-64
[26] 王会云，论物流系统化的基本方法，物流技术，2000年第2期
[27] 候巧玲，浅谈物流／供应链管理系统，制造业自动化，2002年。
[28] 苏一旦，李桂。电子商务物流管理信息系统中的最优(佳)径算法研究，计算机工程与应用，2002年18期
[29] 梅绍祖，INTERNET与电子商务和物流，1998年第3卷第4期
[30] 忻斌建，汪镭，吴启迪，蚁群算法的研究现状和应用及蚂蚁智能体的硬件实现，同济大学学报，2002年，第30卷，第一期
[31] Dorgom M, Bonabeau E , Theraulaz GAnt Algorithm and stigmergy[J].Future Generation Computer Systems,2000,16(6):851-871
[32] Dorigo M, Caro G D ,Gambardella L M. Antalgorithms for discrete optimization[J].Artificial Life, 1999,5(2):137-172
[33] 马良，瓶颈TSP的蚂蚁系统优化，计算机工程，2001年，第27卷。第9期
[34] 白国仲，毛经中，C指派问题，系统工程理论与实践，2003年第3期
[35] 陈雄．李海刚，吴启迪，基于遗传算法的Job-shop调度问题研究，同济大学学报，第30卷第1期，2002年1月
[36] 马良 蒋馥，多目标旅行售货员问题的蚂蚁算法求解，系统工程理论方法应用，1999年，第8卷，第4期
[37] Li Layuan, Li Chunlin A Heuristic Algorithm for QoS Multicast Routing, Journal of System Engineering and Electronics, Vol,13,No,4,2002,pp,73-78
[38] 顾军华，侯向丹等，基于蚂蚁算法的QoS组播路由问题求解，河北工业大学学报，2002年，第31卷，第4期
[39] 马良，离散系统优化的蚂蚁算法研究[D]．上海交通大学管理学院，1999年
[40] 张维明．信息系统建模技术与应用[M]．北京：电子工业出版社，1997
[41] 朗茂祥．物流配送车辆调度问题的模型和算法研究[D]．北方交通大学学报，2002
[42] 吴自库，刘国柱，配送问题的数学模型及近似算法，青岛化工学院学报 1998，19(3)
[43] 陆锋等，基于层次空间推理的交通网络行车最优路径算法[J]，武汉测绘大学学报2000．18．4
[44] AGNETIS A.Planning the routing mix in FASs to minimize total transportation time[J],International
Journal of Flexible Manufacturing Systems, 1996,(2): 131-157.
[45] Barcia P, Jornsten K, Imporved Langrangean Decompostion:An Application to the Generalized Assignment Problem.Europen Jouranl of Operational Reserch,1990,46:84-92
[46] 高洪深．决策支持系统理论方法案例[M]．清华大学出版社，1996
[47] 孙劲光，“背包问题”算法设计及分析，辽宁工程技术大学学报(自然科学版)2002年4月
[48] 李娟，方平，周明，一种求解背包问题的混和遗传算法，南昌航空工业学院学报，1998年第3期
[49] 于秀霞，求解背包问题的新型算法，长春大学学报，12卷第2期
[50] Min H,Jayaram an V, Rajesh Srivastava R.Combined location problem:a synthesis and future research directions[J],Eourpean Journal of Operational Research, 1998,108:1-15
[51] 肖鹏，李茂军，张军平，叶涛，单亲遗传算法及其在物流配送系统中的应用
[52] 华宝玉，王雪峰，冯英浚，有时间窗约束单车型非满载车辆调度问题的遗传算法，哈尔滨商业大学学报(自然科学版)第18卷第6期
[53] 谢秉磊，李军，郭辉煌，有时间窗的非满载车辆调度问题的遗传算法，系统工程学报，2000年第15卷第3期
[54] 戴树贵，孙强，潘萌荣，带限制条件的多权最短路径近似算法，计算机工程，2003年第29卷，第7期
[55] 毕军，付梦鄞，张宇河，一种改进的蚁群算法求解最短路径问题，计算机工程与应用，2003年