农资连锁经营配送车辆实时调度优化模型与算法研究
|
摘要
连锁经营的产生和发展主要是在城市范围内,关于城市连锁经营物流配送理论和技术的研究也取得了较多的成果。如今,随着市场化在农村范围的深入,加之城市连锁经营市场竞争的升级,使得国内众多企业纷纷进军村镇农资连锁经营市场。但是目前针对农资连锁经营物流配送理论的研究却十分落后于快速发展的实践需要。因此,进行面向村镇的农资连锁经营物流配送理论和技术的研究具有重要的理论和现实意义。
论文分析了农资连锁经营物流配送的特性,提出了农资连锁经营配送车辆合理调度的目标和约束；深入研究了农资连锁经营配送车辆调度优化问题的构成要素,并系统描述了车辆调度优化问题的分类及特点；分析了农资连锁经营配送的需求量小、需求点分散、运输条件差以及到货时间弹性强等特征,并定义了反映需求量变化或路径调整而发生的惩罚成本变量,建立了配送需求发生变化时车辆实时调度优化模型；模型求解中,从静态车辆调度和动态线路优化两方面,设计了基于遗传算法的静态车辆调度的求解方法,基于最近插入法和禁忌搜索算法的动态线路优化调整方法；最后以金色谷农资超市管理有限公司为例,进行了实例应用与分析,验证了本文所构建模型和算法的科学、合理性,以及研究成果的理论和实际应用价值。
Chain operation comes from cities originally, both theory and practice about it have sufficiently developed, there are many findings on theory and technique of logistic distribution of chain operation facing city. In recent years, the fact that increasing development of marketing in countryside and market competition's upgrade of chain operation makes many overseas and domestic corporations exploit market of countryside chain operation. But the theory research on logistic distribution of chain operation facing countryside fully doesn't follow practice demand. So, it makes important theory and realism significance to do research on theory and technique of logistic distribution of chain operation facing main towns.
The thesis analyses characteristics of agricultural resource chain operation logistic distribution, proposes reasonable vehicle scheduling objectives and constraints of agricultural resource chain operation logistic distribution. The paper intensively studies constitute elements of vehicle scheduling problem in agricultural resource chain operation, and systematically describe the classification and characteristics of vehicle scheduling problem. The paper establishes vehicle real-time scheduling optimization model when the demands of farm shop change after delivery is beginning, considers the characteristics of agricultural resource chain operation such as:the demand of farm shop is small, the farm shop scattered, poor transportation situation and weak time window requirement, and considers penalty cost in the objective function when the failure distribution caused. Among the model solution, author divides the problem into two parts which are static vehicle scheduling problem and dynamic vehicle scheduling problem. The paper constructs genetic algorithm to solve static vehicle scheduling problem. When ameliorating route, the paper considers using recent insertion and tabu search algorithm. In the last part, the author puts the method in JSG Agricultural resource Supermarket Management Ltd, and confirms that the designed model and algorithm are scientific, reasonable method, which has theoretical and practical value.
论文分析了农资连锁经营物流配送的特性,提出了农资连锁经营配送车辆合理调度的目标和约束；深入研究了农资连锁经营配送车辆调度优化问题的构成要素,并系统描述了车辆调度优化问题的分类及特点；分析了农资连锁经营配送的需求量小、需求点分散、运输条件差以及到货时间弹性强等特征,并定义了反映需求量变化或路径调整而发生的惩罚成本变量,建立了配送需求发生变化时车辆实时调度优化模型；模型求解中,从静态车辆调度和动态线路优化两方面,设计了基于遗传算法的静态车辆调度的求解方法,基于最近插入法和禁忌搜索算法的动态线路优化调整方法；最后以金色谷农资超市管理有限公司为例,进行了实例应用与分析,验证了本文所构建模型和算法的科学、合理性,以及研究成果的理论和实际应用价值。
Chain operation comes from cities originally, both theory and practice about it have sufficiently developed, there are many findings on theory and technique of logistic distribution of chain operation facing city. In recent years, the fact that increasing development of marketing in countryside and market competition's upgrade of chain operation makes many overseas and domestic corporations exploit market of countryside chain operation. But the theory research on logistic distribution of chain operation facing countryside fully doesn't follow practice demand. So, it makes important theory and realism significance to do research on theory and technique of logistic distribution of chain operation facing main towns.
The thesis analyses characteristics of agricultural resource chain operation logistic distribution, proposes reasonable vehicle scheduling objectives and constraints of agricultural resource chain operation logistic distribution. The paper intensively studies constitute elements of vehicle scheduling problem in agricultural resource chain operation, and systematically describe the classification and characteristics of vehicle scheduling problem. The paper establishes vehicle real-time scheduling optimization model when the demands of farm shop change after delivery is beginning, considers the characteristics of agricultural resource chain operation such as:the demand of farm shop is small, the farm shop scattered, poor transportation situation and weak time window requirement, and considers penalty cost in the objective function when the failure distribution caused. Among the model solution, author divides the problem into two parts which are static vehicle scheduling problem and dynamic vehicle scheduling problem. The paper constructs genetic algorithm to solve static vehicle scheduling problem. When ameliorating route, the paper considers using recent insertion and tabu search algorithm. In the last part, the author puts the method in JSG Agricultural resource Supermarket Management Ltd, and confirms that the designed model and algorithm are scientific, reasonable method, which has theoretical and practical value.
引文
[1]张理,李蕴姝.物流管理导论[M].北京：清华大学出版社,北京交通大学出版社,2009.
[2]张海燕.连锁企业的配送管理[M].北京：中国物资出版社,2002.
[3]丁立言,张铎.物流基础[M].北京：清华大学出版社,2000.
[4]陆强华.连锁经营[M].北京：中国工人出版社,2001.
[5]叶魁.加拿大、美国农资考察报告[J].农资科技,2002(1)：26-28.
[6]惠良.美国农资配送渠道变革[J].物流时代,2005(18)：64-65.
[7]李军,郭耀煌.物流配送车辆优化调度理论与方法[M].北京：中国物资出版社2001.
[8]Michael R.Swihart and Jason D.Papastavrou.A stochastic and dynamic model for the single-vehicle pick-up and delivery problem [J]. European Journal of Operational Research, 1999,114:447-464.
[9]Alan Slater. Specification for a dynamic vehicle routing and scheduling system[J], International Journal of Transport Management,2002,1:29-40.
[10]Gianpaolo Ghiani, Francesca Guerriero, Gilbert Laporte and Roberto Musmanno. Real-time vehicle routing:Solution concepts, algorithms and parallel computing strategies [J]. European Journal of Operational Research,2003,151 (1):1-11.
[11]Ruben Ruiz, Concepcion Maroto and Javier Alcaraz. A decision support system for a real vehicle routing problem [J]. European Journal of Operational Research,2004,153 (3):593-606.
[12]Huey-Kuo Chen,Che F.Hsueh,Mei-Shiang Chang.The real-time time-dependent vehicle routing problem [J].Transportation Research Part E,2006,42:383-408.
[13]Jean-Yves Potvin, Ying Xu and Ilham Benyahia. Vehicle routing and scheduling with dynamic travel times [J]. Computers & Operations Research,2006,33 (4):1129-1137.
[14]Miguel Andres Figliozzi, Hani S. Mahmassani and Patrick Jaillet. Pricing in Dynamic Vehicle Routing Problems [J], Transportation Science,2007,41(3):302-318.
[15]Lian-sheng Tang, Wen-ming Cheng, Ze-qiang Zhang, and Jian Liang. Vehicle Routing Problem with Travel Time Reliability Constrain [J]. ASCE Conf. Proc,2007:246-300.
[16]Deniz Tu'rsel Eliiyi, Arslan Ornek. A vehicle scheduling problem with fixed trips and time limitations[J]. Int.J.Production Economics,2009,117:150-161.
[17]Jing-Quan Li, Pitu B. Mirchandani, Denis Borenstein. Real-time vehicle rerouting problems with time windows [J]. European Journal of Operational Research,2009,194:711-727.
[18]蒋华江,宋瑛.城乡统筹视角下重庆农村商贸体系的构建[J].商业时代,2009,(32)
[19]刘文杰.我国农业发展连锁经营的必要性和对策研究[D].天津财经大学,2006.
[20]吴长莹.农资连锁经营模式在中国农资营销中的应用研究[D].西南财经大学,2007.
[21]徐云.农村物流中心若干关键问题研究[D].武汉理工大学,2008.
[22]顾掌根,王国峰.创新农业发展业态的探讨[J].中国农学通报,2009,25(21)：375-378.
[23]谢秉磊,郭耀煌,郭强.动态车辆路径问题现状与展望[J].系统工程理论方法与应用,2002,11(2)：116-120.
[24]肖增敏,李军.动态网络车辆路径问题：研究现状及展望[J].系统工程,2004,22(7)
[25]张建勇,李军,郭耀煌.模糊需求信息条件下的实时动态车辆调度问题研究[J].管理工程学 报,2004,18(4)
[26]刘云霞.动态车辆调度问题分析及算法设计[D].成都：西南交通大学,2006.
[27]王江晴,康立山.动态网络环境下的实时路径评估模型[J].计算机工程及应用,2006,42(32)：226-228.
[28]高林杰.交通网络动态路径求解并行仿真算法研究与实现[D].长春：吉林大学,2006.
[29]柯昌正.动态车辆调度问题研究与应用[D].北京：北京交通大学,2006.
[30]郎茂祥.用单亲遗传算法求解配送车辆调度问题的研究[J].交通与计算机,2006,24(1)
[31]郎茂祥.装卸混合车辆路径问题的模拟退火算法研究[J].系统工程学报,2005,20(5)
[32]郎茂祥,胡思继.车辆路径问题的禁忌搜索算法研究[J].管理工程学报,2004,18(1)
[33]赵辉,全雄文,孙光伟,杨鹏.ITS和GPS系统下车辆实时调度问题的研究[J].计算机工程与应用,2007,43(23).
[34]刘士新,冯海兰.动态车辆路径问题的优化方法[J].东北大学学报,2008,29(4)
[35]潘登,郑应平,陆小芳.避免车辆路径拥塞的动态蚁群算法[J].计算机工程,2008,34(5)
[36]李铭,李旭宏.公交枢纽内多线路车辆实时调度优化方法研究[J].公路交通科技,2006,23(6).
[37]高勇.海防部队应急车辆调度问题的优化模型研究[D].长沙：国防科技大学,2009.
[38]施朝春,王旭,葛显龙.带有时间窗的多配送中心的车辆调度问题研究[J].计算机工业与应用,2009,45(34).
[39]马华伟,左春荣,杨善林.多时间窗车辆调度问题建模与求解[J].系统工程学报,2009,24(5)
[40]于洋,刘刚,丁宁.实时信息下除雪车辆优化调度分析[J].科学技术与工程,2009,9(19).
[41]路萍,于书举,胡祺.基于位势法的农资供需匹配解决方案[J].计算机工程与应用,2003(30)：223-226.
[42]马守忠.农村物流的瓶颈制约与发展对策研究[J].中国市场,2007(6)：38.
[43]徐天亮.运输与配送[M].北京：中国物资出版社,2002.
[44]Dimitris J.B,David S.A new Generation of vehicle routing research[J].Survey, Expository and Tutorial,1995,44 (2):286-303.
[45]Luis G.A result on projection for the vehicle routing problem[J].European Journal of Operational Research,1995 (85):610-624.
[46]《运筹学》教材编写组.运筹学[M].北京：清华大学出版社,2003.
[47]Solomon,M. Algorithms for the vehicle routing and scheduling problems with time window constraints[J]. Operations Research,1987,35:254-265.
[48]王小平,曹立明.遗传算法理论、应用与软件实现[M].西安：西安交通大学出版社,2002.
[49]杨浩.模型与算法[M].北京：北方交通大学出版社,2002.
[50]郎茂祥.配送车辆优化调度模型与算法研究[M].北京：电子工业出版社,2009.
[51]贾永基.车辆调度问题优化算法研究[D].上海：上海交通大学,2004.
[52]郭鸣凤.动态环境下车辆调度问题研究[D].上海：同济大学,2006.
[53]王永亮,袁振洲.多配送中心单向车辆调度问题的模型与禁忌搜索算法的研究[J].物流技术,2008,27(2).
[54]陈萍.启发式算法及其在车辆路径问题中的应用[D].北京：北京交通大学,2009.
[55]魏晓明.基于禁忌搜索算法求解带时间窗的定位路线研究[D].西安：长安大学,2009.
[2]张海燕.连锁企业的配送管理[M].北京：中国物资出版社,2002.
[3]丁立言,张铎.物流基础[M].北京：清华大学出版社,2000.
[4]陆强华.连锁经营[M].北京：中国工人出版社,2001.
[5]叶魁.加拿大、美国农资考察报告[J].农资科技,2002(1)：26-28.
[6]惠良.美国农资配送渠道变革[J].物流时代,2005(18)：64-65.
[7]李军,郭耀煌.物流配送车辆优化调度理论与方法[M].北京：中国物资出版社2001.
[8]Michael R.Swihart and Jason D.Papastavrou.A stochastic and dynamic model for the single-vehicle pick-up and delivery problem [J]. European Journal of Operational Research, 1999,114:447-464.
[9]Alan Slater. Specification for a dynamic vehicle routing and scheduling system[J], International Journal of Transport Management,2002,1:29-40.
[10]Gianpaolo Ghiani, Francesca Guerriero, Gilbert Laporte and Roberto Musmanno. Real-time vehicle routing:Solution concepts, algorithms and parallel computing strategies [J]. European Journal of Operational Research,2003,151 (1):1-11.
[11]Ruben Ruiz, Concepcion Maroto and Javier Alcaraz. A decision support system for a real vehicle routing problem [J]. European Journal of Operational Research,2004,153 (3):593-606.
[12]Huey-Kuo Chen,Che F.Hsueh,Mei-Shiang Chang.The real-time time-dependent vehicle routing problem [J].Transportation Research Part E,2006,42:383-408.
[13]Jean-Yves Potvin, Ying Xu and Ilham Benyahia. Vehicle routing and scheduling with dynamic travel times [J]. Computers & Operations Research,2006,33 (4):1129-1137.
[14]Miguel Andres Figliozzi, Hani S. Mahmassani and Patrick Jaillet. Pricing in Dynamic Vehicle Routing Problems [J], Transportation Science,2007,41(3):302-318.
[15]Lian-sheng Tang, Wen-ming Cheng, Ze-qiang Zhang, and Jian Liang. Vehicle Routing Problem with Travel Time Reliability Constrain [J]. ASCE Conf. Proc,2007:246-300.
[16]Deniz Tu'rsel Eliiyi, Arslan Ornek. A vehicle scheduling problem with fixed trips and time limitations[J]. Int.J.Production Economics,2009,117:150-161.
[17]Jing-Quan Li, Pitu B. Mirchandani, Denis Borenstein. Real-time vehicle rerouting problems with time windows [J]. European Journal of Operational Research,2009,194:711-727.
[18]蒋华江,宋瑛.城乡统筹视角下重庆农村商贸体系的构建[J].商业时代,2009,(32)
[19]刘文杰.我国农业发展连锁经营的必要性和对策研究[D].天津财经大学,2006.
[20]吴长莹.农资连锁经营模式在中国农资营销中的应用研究[D].西南财经大学,2007.
[21]徐云.农村物流中心若干关键问题研究[D].武汉理工大学,2008.
[22]顾掌根,王国峰.创新农业发展业态的探讨[J].中国农学通报,2009,25(21)：375-378.
[23]谢秉磊,郭耀煌,郭强.动态车辆路径问题现状与展望[J].系统工程理论方法与应用,2002,11(2)：116-120.
[24]肖增敏,李军.动态网络车辆路径问题：研究现状及展望[J].系统工程,2004,22(7)
[25]张建勇,李军,郭耀煌.模糊需求信息条件下的实时动态车辆调度问题研究[J].管理工程学 报,2004,18(4)
[26]刘云霞.动态车辆调度问题分析及算法设计[D].成都：西南交通大学,2006.
[27]王江晴,康立山.动态网络环境下的实时路径评估模型[J].计算机工程及应用,2006,42(32)：226-228.
[28]高林杰.交通网络动态路径求解并行仿真算法研究与实现[D].长春：吉林大学,2006.
[29]柯昌正.动态车辆调度问题研究与应用[D].北京：北京交通大学,2006.
[30]郎茂祥.用单亲遗传算法求解配送车辆调度问题的研究[J].交通与计算机,2006,24(1)
[31]郎茂祥.装卸混合车辆路径问题的模拟退火算法研究[J].系统工程学报,2005,20(5)
[32]郎茂祥,胡思继.车辆路径问题的禁忌搜索算法研究[J].管理工程学报,2004,18(1)
[33]赵辉,全雄文,孙光伟,杨鹏.ITS和GPS系统下车辆实时调度问题的研究[J].计算机工程与应用,2007,43(23).
[34]刘士新,冯海兰.动态车辆路径问题的优化方法[J].东北大学学报,2008,29(4)
[35]潘登,郑应平,陆小芳.避免车辆路径拥塞的动态蚁群算法[J].计算机工程,2008,34(5)
[36]李铭,李旭宏.公交枢纽内多线路车辆实时调度优化方法研究[J].公路交通科技,2006,23(6).
[37]高勇.海防部队应急车辆调度问题的优化模型研究[D].长沙：国防科技大学,2009.
[38]施朝春,王旭,葛显龙.带有时间窗的多配送中心的车辆调度问题研究[J].计算机工业与应用,2009,45(34).
[39]马华伟,左春荣,杨善林.多时间窗车辆调度问题建模与求解[J].系统工程学报,2009,24(5)
[40]于洋,刘刚,丁宁.实时信息下除雪车辆优化调度分析[J].科学技术与工程,2009,9(19).
[41]路萍,于书举,胡祺.基于位势法的农资供需匹配解决方案[J].计算机工程与应用,2003(30)：223-226.
[42]马守忠.农村物流的瓶颈制约与发展对策研究[J].中国市场,2007(6)：38.
[43]徐天亮.运输与配送[M].北京：中国物资出版社,2002.
[44]Dimitris J.B,David S.A new Generation of vehicle routing research[J].Survey, Expository and Tutorial,1995,44 (2):286-303.
[45]Luis G.A result on projection for the vehicle routing problem[J].European Journal of Operational Research,1995 (85):610-624.
[46]《运筹学》教材编写组.运筹学[M].北京：清华大学出版社,2003.
[47]Solomon,M. Algorithms for the vehicle routing and scheduling problems with time window constraints[J]. Operations Research,1987,35:254-265.
[48]王小平,曹立明.遗传算法理论、应用与软件实现[M].西安：西安交通大学出版社,2002.
[49]杨浩.模型与算法[M].北京：北方交通大学出版社,2002.
[50]郎茂祥.配送车辆优化调度模型与算法研究[M].北京：电子工业出版社,2009.
[51]贾永基.车辆调度问题优化算法研究[D].上海：上海交通大学,2004.
[52]郭鸣凤.动态环境下车辆调度问题研究[D].上海：同济大学,2006.
[53]王永亮,袁振洲.多配送中心单向车辆调度问题的模型与禁忌搜索算法的研究[J].物流技术,2008,27(2).
[54]陈萍.启发式算法及其在车辆路径问题中的应用[D].北京：北京交通大学,2009.
[55]魏晓明.基于禁忌搜索算法求解带时间窗的定位路线研究[D].西安：长安大学,2009.