适用于第三方冷链物流企业的车辆调度模型
|
摘要
随着社会经济的发展,人们对生鲜冷冻食品的需求越来越大。生鲜产品在生产、储存、运输和消费的过程中损耗率高达20%,尤其在城市的流通环节损失惊人；同时,零售商为了提高其销售水平,通常会对配送时间和配送质量提出限制性的要求；对配送商而言,在考虑时间窗限制的同时,还要考虑保证货物质量和降低运营成本。如何在降低物流成本的同时保证货物质量并达到客户的要求已经成为国内外许多理论及应用学者们关注的焦点。由于冷链配送中,配送任务重,技术要求高,许多超市委托第三方物流企业来进行日常的生鲜食品配送。第三方冷链物流企业为了追求配送利润的最大化、合理利用配送资源、降低配送生鲜冷冻食品的耗损,对现有的车辆调度提出了更高的要求。
理论上对第三方物流车辆调度的种类主要有带容量约束的车辆调度问题、多车型车辆调度问题、带时间窗的车辆调度问题、带回程运输的车辆调度问题、相容性约束车辆调度问题、不确定性车辆调度问题、车场开放车辆调度问题、多配送中心的车辆调度问题八种,主要研究方法有分支定界法、割平面法、动态规划法等精确算法和节约法、遗传算法、模拟退火算法、禁忌搜索算法等启发式算法。各种算法各有优缺点,鉴于超市数量不多且有增长的特性,本文选择易于扩展的节约法为基础进行算法研究和改善。
本文依托于北京市科学技术委员会绿色通道项目“北京市食品冷链物流关键技术研发与示范”课题,对调研的第三方冷链物流企业北京市东方友谊食品配送公司对普华超市各门店的物流配送做了车辆调度研究,在现有的平衡物流成本和满足客户需要的车辆调度模型基础上,进一步探索改进方案,为该物流配送提出新的车辆调度模型和方案。本文在对北京市这一特大型城市交通情况、冷链物流运输特别政策及硬件设施等基本情况的研究后,对需要的第三方冷链物流和车辆调度这两个相关理论进行了研究。然后提出了一种基于C-K节约算法的单货栈多商品多零售商冷藏车车辆调度模型并进行实例验证。
经验证,本文提出的基于C-K节约算法的单货栈多商品多零售商冷藏车车辆调度模型适用于第三方冷链物流企业的车辆调度,对不同商品的体积、质量的考虑,细化了车辆调度中考虑的因素,为第三方冷链物流企业商超配送提供了方法借鉴和指导。
With the social and economic development, the demand of fresh frozen foods is growing. Loss rate in the process of production, storage, transport and consumption of fresh products is up to20%, which is an alarming loss of circulation especially in the city. At the same time, retailers will ask for usual delivery time and delivery quality restrictive requirements in order to improve its level of sales. While, distributor, should also be considered to ensure the quality of the goods at the same time windows constraints, and reduce operating costs. How to reduce logistics costs as while as to ensure the quality of the goods and to meet customer requirements has become to the focus of many domestic and foreign theories and application scholars'attention. In cold chain, the distribution task is heavy, and the technique is demanding, so many supermarkets commission third-party logistics enterprises to carry out the daily fresh food distribution. Third-party cold chain logistics companies have a higher demand of the vehicle scheduling method in order to pursue the distribution of profit maximization, rational distribution of resources, reduce wear and tear of the distribution of fresh frozen foods.
Theoretically the main types of third-party logistics vehicle scheduling vehicle scheduling problem with capacity constraints, multi-model vehicle scheduling problem, vehicle scheduling problem with time windows, back to the way transportation vehicle scheduling problem, the compatibility constraints vehicle scheduling problem the uncertainty of the vehicle scheduling problem, the parking lots open vehicle scheduling problem, a distribution center for vehicle scheduling problem eight kinds, the main research method contains the exact algorithms and heuristic algorithms. The exact algorithms are Branch and Bound, Cutting Plane Method, Dynamic Programming, ect. While heuristic algorithms are Savings Algorithm, Genetic Algorithm, Simulated Annealing Algorithm, Tabu Search Algorithm, ect. Various heuristic algorithms have their own advantages and disadvantages, given a few number of supermarkets and the growth characteristics of the Conservation Act as the basis for the algorithm is easy to extend and improve.
This paper relies on the subject of "Beijing food cold chain logistics key technology R&D and demonstration" which is one of the Green Corridor projects held by Beijing Municipal Science and Technology Commission. Beijing Oriental Friendship Food Distribution Company and Puhua Supermarket are two companies surveyed in the subject. Beijing Oriental Friendship Food Distribution Company is a third-party cold-chain logistics enterprise and it offers Puhua supermarket stores'daily fresh food distribution. This paper does a research in vehicle routing models and proposes a new vehicle routing model and program for Beijing Oriental Friendship Food Distribution Company and Puhua Supermarket. In this paper, Beijing City's traffic, special policies of cold-chain logistics and transport and hardware facilities are studied. After the study, it comes to that two theories on third-party cold chain logistics and vehicle scheduling are needed. Then this paper proposes a saving algorithm based on C-K which is about single-warehouse multi-commodity multi-retailer vehicle routing model used by refrigerated trucks. Finally the model is instance validated.
Savings algorithm proposed in this paper is proven based on the C-K single-warehouse multi-commodity and multiple retailers refrigerated trucks, vehicle scheduling model for vehicle scheduling in third-party cold chain logistics enterprises, the volume of different commodities, quality considerations, and detailed vehicle scheduling factors considered in the super-distribution of third-party cold chain logistics companies to provide methods for reference and guidance.
理论上对第三方物流车辆调度的种类主要有带容量约束的车辆调度问题、多车型车辆调度问题、带时间窗的车辆调度问题、带回程运输的车辆调度问题、相容性约束车辆调度问题、不确定性车辆调度问题、车场开放车辆调度问题、多配送中心的车辆调度问题八种,主要研究方法有分支定界法、割平面法、动态规划法等精确算法和节约法、遗传算法、模拟退火算法、禁忌搜索算法等启发式算法。各种算法各有优缺点,鉴于超市数量不多且有增长的特性,本文选择易于扩展的节约法为基础进行算法研究和改善。
本文依托于北京市科学技术委员会绿色通道项目“北京市食品冷链物流关键技术研发与示范”课题,对调研的第三方冷链物流企业北京市东方友谊食品配送公司对普华超市各门店的物流配送做了车辆调度研究,在现有的平衡物流成本和满足客户需要的车辆调度模型基础上,进一步探索改进方案,为该物流配送提出新的车辆调度模型和方案。本文在对北京市这一特大型城市交通情况、冷链物流运输特别政策及硬件设施等基本情况的研究后,对需要的第三方冷链物流和车辆调度这两个相关理论进行了研究。然后提出了一种基于C-K节约算法的单货栈多商品多零售商冷藏车车辆调度模型并进行实例验证。
经验证,本文提出的基于C-K节约算法的单货栈多商品多零售商冷藏车车辆调度模型适用于第三方冷链物流企业的车辆调度,对不同商品的体积、质量的考虑,细化了车辆调度中考虑的因素,为第三方冷链物流企业商超配送提供了方法借鉴和指导。
With the social and economic development, the demand of fresh frozen foods is growing. Loss rate in the process of production, storage, transport and consumption of fresh products is up to20%, which is an alarming loss of circulation especially in the city. At the same time, retailers will ask for usual delivery time and delivery quality restrictive requirements in order to improve its level of sales. While, distributor, should also be considered to ensure the quality of the goods at the same time windows constraints, and reduce operating costs. How to reduce logistics costs as while as to ensure the quality of the goods and to meet customer requirements has become to the focus of many domestic and foreign theories and application scholars'attention. In cold chain, the distribution task is heavy, and the technique is demanding, so many supermarkets commission third-party logistics enterprises to carry out the daily fresh food distribution. Third-party cold chain logistics companies have a higher demand of the vehicle scheduling method in order to pursue the distribution of profit maximization, rational distribution of resources, reduce wear and tear of the distribution of fresh frozen foods.
Theoretically the main types of third-party logistics vehicle scheduling vehicle scheduling problem with capacity constraints, multi-model vehicle scheduling problem, vehicle scheduling problem with time windows, back to the way transportation vehicle scheduling problem, the compatibility constraints vehicle scheduling problem the uncertainty of the vehicle scheduling problem, the parking lots open vehicle scheduling problem, a distribution center for vehicle scheduling problem eight kinds, the main research method contains the exact algorithms and heuristic algorithms. The exact algorithms are Branch and Bound, Cutting Plane Method, Dynamic Programming, ect. While heuristic algorithms are Savings Algorithm, Genetic Algorithm, Simulated Annealing Algorithm, Tabu Search Algorithm, ect. Various heuristic algorithms have their own advantages and disadvantages, given a few number of supermarkets and the growth characteristics of the Conservation Act as the basis for the algorithm is easy to extend and improve.
This paper relies on the subject of "Beijing food cold chain logistics key technology R&D and demonstration" which is one of the Green Corridor projects held by Beijing Municipal Science and Technology Commission. Beijing Oriental Friendship Food Distribution Company and Puhua Supermarket are two companies surveyed in the subject. Beijing Oriental Friendship Food Distribution Company is a third-party cold-chain logistics enterprise and it offers Puhua supermarket stores'daily fresh food distribution. This paper does a research in vehicle routing models and proposes a new vehicle routing model and program for Beijing Oriental Friendship Food Distribution Company and Puhua Supermarket. In this paper, Beijing City's traffic, special policies of cold-chain logistics and transport and hardware facilities are studied. After the study, it comes to that two theories on third-party cold chain logistics and vehicle scheduling are needed. Then this paper proposes a saving algorithm based on C-K which is about single-warehouse multi-commodity multi-retailer vehicle routing model used by refrigerated trucks. Finally the model is instance validated.
Savings algorithm proposed in this paper is proven based on the C-K single-warehouse multi-commodity and multiple retailers refrigerated trucks, vehicle scheduling model for vehicle scheduling in third-party cold chain logistics enterprises, the volume of different commodities, quality considerations, and detailed vehicle scheduling factors considered in the super-distribution of third-party cold chain logistics companies to provide methods for reference and guidance.
引文
[1]吴秀敏.我国猪肉质量安全管理体系研究—基于四川消费者、生产者行为的实证分析[学位论文].杭州.浙江大学.2006.
[2]唐俊杰,刘忠宝,于媛媛.第三方冷链物流配送模式的建立和能耗分析[J].冷藏技术,2007年第一期：7-20.
[3]孙小婷.中国冷链物流模式选择与发展对策研究[学位论文].长春.东北农业大学.2011.
[4]De-la Fuente MV, Ros L. What to Do with Rejected Loads in the Agri-Food Chain [A]. In:International Conference on ENTER prize Information Systems [C]. Viana do Castelo, PORTUGAL, OCT 20-22,2010.109:251-260.
[5]Bogataj M, Bogataj L, Vodopivec R. Stability of perishable goods in cold logistic chains [A]. In:INTERNATIONAL JOURNAL OF PRODUCTION ECONOMICS[C]. Budapest, HUNGARY, AUG 20-25,2002,93-4:345-356.
[6]Abad E, Palacio F, Nuin M, ect. RFID smart tag for traceability and cold chain monitoring of foods:Demonstration in an intercontinental fresh fish logistic chain [J]. JOURNAL OF FOOD ENGINEERING, 2009,93 (4): 394-399.
[7]Miranda-de la Lama GC, Rivero L, Chacon G, ect. Effect of the pre-slaughter logistic chain on some indicators of welfare in lambs [J]. LIVESTOCK SCIENCE, 2010,128(1-3):52-59.
[8]汤晓艳,钱永忠.《我国肉类冷链物流状况及发展对策》[J].食品科学,2008,29(10)：656-660.
[9]杨光华,林朝朋,谢小良.《生鲜农产品冷链物流模式与对策研究》[J].广东农业科学,2009,6：200-203.
[10]邹毅峰,谢如鹤,邱祝强.中国易腐食品冷链物流现状分析及优化研究[J].食品安全,2008,29(12)：195-197.
[11]孟军齐.深圳冷链物流发展模式探讨[J].中国物流与采购,2009年,第10期：70-71.
[12]赵艳艳,张于贤HACCP体系在我国冷链物流管理中的运用及优化[J].安徽农业科学,2009,37(7)：3273-3274.
[13]赵艳艳.食品冷链物流软时窗配送模式优化研究[J].安徽农业科学,.2009。37(17)：8235--8238.
[14]高振娟.基于系统契合的大型零售商冷链物流模式革新[J].商业时代,2010年24期27-28.
[15]邹毅峰,谢如鹤,邱祝强.基于GO—FLOW法的荔枝冷链物流安全评价[J].工业工程,2008年第6期：47-49.
[16]Xiaohong XU, Hongjie Lan, Ruijiang Wang. Identification of Critical Control Points of the Food Cold Chain Logistic Process [A]. In:2010 International Conference on Logistics Systems and Intelligent Management [C]. Harbin, China, January 9, 2010 - January 10, 2010. 164-168.
[17]邓爱民,杨葱葱,傅志明.《基于可拓方法的第三方冷链物流企业评价研究》[J].财经理论与实践(双月刊),2010,31(166)：86-90.
[18]黄蜂权.《集成化食品冷链物流的绩效评价研究》[学位论文].北京：北京交通大学,2009.
[19]彭北青.第三方物流配送车辆路径问题模型及算法研究[博士论文].武汉.华中科技大学.2009
[20]李桃迎,陈燕.有工作时限和时间窗约束的车辆调度问题研究.第十七届中国过程控制会议论文集.江苏无锡.2006年.82-85.
[21]陈子侠.基于GIS物流配送线路优化与仿真.北京市.经济科学出版社.2007年
[22]吕雄伟.邮政物流车辆路径问题研究[博士论文].成都.西南交通大学.2008.
[23]何迪APTS下公交车辆区域调度问题研究[博士论文].成都：西南交通大学,2009.
[24]路琳.不确定信息车辆路径问题及其算法研究[博士论文].南京：南京航空航天大学,2007.
[25]刘青.冷藏车与保温车之异同——冷藏车保温车专题之五.商用汽车.2002年第2期：42.
[26]梁仲文,王国栋.冷藏车的春天来了——浅析《农产品冷链物流发展规划》出台后冷藏车的发展前景.商用汽车.2010年S6期：15-16.
[27]孙婧.第三方冷链物流企业物流系统的规划与评价研究[学位论文].合肥：安徽农业大学,2007.
[28]刘文龙、王昱琪、葛汝刚.第四方物流在我国发展的问题研究.物流科技.2006(11)：14-17.
[29]肖静,张东杰,刘子玉等.我国食品冷链物流管理体系构建研究[J].农机化研究,2008,7：13-17.
[30]陈萍.启发式算法及其在车辆路径问题中的应用[学位论文].北京.北京交通大学.2009.4-15.
[31]刘清,彭俊.中外车辆调度方法比较[J].交通企业管理,2009(5)：74-75.
[32]张建勇,郭耀煌,李军.一种具有模糊费用系数的VSP的修正C-W节约算法[J].西南交通大学学,2004年,第三期：281-284.
[33]王海丽,王勇,曾永长.带时间窗的易腐食品冷藏车辆配送问题[J].工业工程,2008年,5月：127-130.
[34]肖建辉.H公司车辆调度优化分析[学位论文].北京.北京交通大学.2008.34-38
[35]刘春全.基于消费者满意度的武汉市超市生鲜供应链管理优化研究[学位论文].武汉：华中农业大学,2008.
[36]李辉.苏果超市马群配送中心物流配送车辆调度问题研究[学位论文].南京.南京航空航天大学.2008.
[37]邵泽军.几类车辆调度问题的研究[学位论文].西安：西安电子科技大学,2009.
[38]朱辉.食品冷链物流配送管理研究[学位论文].上海：上海交通大学,2008.
[39]高义佳.基于复杂网络的冷链物流网络优化与应用研究[学位论文].青岛：中国海洋大学,2009.
[40]龚树生,梁怀兰.生鲜食品的冷链物流网络研究[J].中国流通经济,2006,2：7-9.
[41]兰洪杰.食品冷链物流系统协同对象与过程研究[J].中国流通经济,2009,2：20-23.
[42]刘佳,宋铁成,高飞等.无线车辆管理调度系统的设计与实现[J].电子工程师,2007,4：74-77.
[43]肖深茂.电子商务环境下北京市社区物流管理策略研究[学位论文].北京：北京信息科技大学,2008.
[44]刘长华,王忠.基于HGA的智能交通调度优化方法研究[J].武汉理工大学学报(交通科学与工程版),2010(8)：712-715.
[45]陈素敏.果蔬农产品冷链物流信息系统框架研究[学位论文].北京：北京物资学院,2006.
[46]郭绍君.全球统一标识系统在食品冷链中的应用研究[学位论文].北京：北京交通大学,2009.
[47]司京成.北京东方友谊食品配送公司发展战略研究[学位论文].北京：北京交通大学,2007.
[48]Chen Na, Shi Lei. Analysis of Quality Game Behavior for Cold-Chain Logistics Outsourcing [A]. In:Logistics Systems and Intelligent Management, 2010 International Conference on [C]. Harbin, China, 9-10 Jan. 2010. 202 - 206.
[2]唐俊杰,刘忠宝,于媛媛.第三方冷链物流配送模式的建立和能耗分析[J].冷藏技术,2007年第一期：7-20.
[3]孙小婷.中国冷链物流模式选择与发展对策研究[学位论文].长春.东北农业大学.2011.
[4]De-la Fuente MV, Ros L. What to Do with Rejected Loads in the Agri-Food Chain [A]. In:International Conference on ENTER prize Information Systems [C]. Viana do Castelo, PORTUGAL, OCT 20-22,2010.109:251-260.
[5]Bogataj M, Bogataj L, Vodopivec R. Stability of perishable goods in cold logistic chains [A]. In:INTERNATIONAL JOURNAL OF PRODUCTION ECONOMICS[C]. Budapest, HUNGARY, AUG 20-25,2002,93-4:345-356.
[6]Abad E, Palacio F, Nuin M, ect. RFID smart tag for traceability and cold chain monitoring of foods:Demonstration in an intercontinental fresh fish logistic chain [J]. JOURNAL OF FOOD ENGINEERING, 2009,93 (4): 394-399.
[7]Miranda-de la Lama GC, Rivero L, Chacon G, ect. Effect of the pre-slaughter logistic chain on some indicators of welfare in lambs [J]. LIVESTOCK SCIENCE, 2010,128(1-3):52-59.
[8]汤晓艳,钱永忠.《我国肉类冷链物流状况及发展对策》[J].食品科学,2008,29(10)：656-660.
[9]杨光华,林朝朋,谢小良.《生鲜农产品冷链物流模式与对策研究》[J].广东农业科学,2009,6：200-203.
[10]邹毅峰,谢如鹤,邱祝强.中国易腐食品冷链物流现状分析及优化研究[J].食品安全,2008,29(12)：195-197.
[11]孟军齐.深圳冷链物流发展模式探讨[J].中国物流与采购,2009年,第10期：70-71.
[12]赵艳艳,张于贤HACCP体系在我国冷链物流管理中的运用及优化[J].安徽农业科学,2009,37(7)：3273-3274.
[13]赵艳艳.食品冷链物流软时窗配送模式优化研究[J].安徽农业科学,.2009。37(17)：8235--8238.
[14]高振娟.基于系统契合的大型零售商冷链物流模式革新[J].商业时代,2010年24期27-28.
[15]邹毅峰,谢如鹤,邱祝强.基于GO—FLOW法的荔枝冷链物流安全评价[J].工业工程,2008年第6期：47-49.
[16]Xiaohong XU, Hongjie Lan, Ruijiang Wang. Identification of Critical Control Points of the Food Cold Chain Logistic Process [A]. In:2010 International Conference on Logistics Systems and Intelligent Management [C]. Harbin, China, January 9, 2010 - January 10, 2010. 164-168.
[17]邓爱民,杨葱葱,傅志明.《基于可拓方法的第三方冷链物流企业评价研究》[J].财经理论与实践(双月刊),2010,31(166)：86-90.
[18]黄蜂权.《集成化食品冷链物流的绩效评价研究》[学位论文].北京：北京交通大学,2009.
[19]彭北青.第三方物流配送车辆路径问题模型及算法研究[博士论文].武汉.华中科技大学.2009
[20]李桃迎,陈燕.有工作时限和时间窗约束的车辆调度问题研究.第十七届中国过程控制会议论文集.江苏无锡.2006年.82-85.
[21]陈子侠.基于GIS物流配送线路优化与仿真.北京市.经济科学出版社.2007年
[22]吕雄伟.邮政物流车辆路径问题研究[博士论文].成都.西南交通大学.2008.
[23]何迪APTS下公交车辆区域调度问题研究[博士论文].成都：西南交通大学,2009.
[24]路琳.不确定信息车辆路径问题及其算法研究[博士论文].南京：南京航空航天大学,2007.
[25]刘青.冷藏车与保温车之异同——冷藏车保温车专题之五.商用汽车.2002年第2期：42.
[26]梁仲文,王国栋.冷藏车的春天来了——浅析《农产品冷链物流发展规划》出台后冷藏车的发展前景.商用汽车.2010年S6期：15-16.
[27]孙婧.第三方冷链物流企业物流系统的规划与评价研究[学位论文].合肥：安徽农业大学,2007.
[28]刘文龙、王昱琪、葛汝刚.第四方物流在我国发展的问题研究.物流科技.2006(11)：14-17.
[29]肖静,张东杰,刘子玉等.我国食品冷链物流管理体系构建研究[J].农机化研究,2008,7：13-17.
[30]陈萍.启发式算法及其在车辆路径问题中的应用[学位论文].北京.北京交通大学.2009.4-15.
[31]刘清,彭俊.中外车辆调度方法比较[J].交通企业管理,2009(5)：74-75.
[32]张建勇,郭耀煌,李军.一种具有模糊费用系数的VSP的修正C-W节约算法[J].西南交通大学学,2004年,第三期：281-284.
[33]王海丽,王勇,曾永长.带时间窗的易腐食品冷藏车辆配送问题[J].工业工程,2008年,5月：127-130.
[34]肖建辉.H公司车辆调度优化分析[学位论文].北京.北京交通大学.2008.34-38
[35]刘春全.基于消费者满意度的武汉市超市生鲜供应链管理优化研究[学位论文].武汉：华中农业大学,2008.
[36]李辉.苏果超市马群配送中心物流配送车辆调度问题研究[学位论文].南京.南京航空航天大学.2008.
[37]邵泽军.几类车辆调度问题的研究[学位论文].西安：西安电子科技大学,2009.
[38]朱辉.食品冷链物流配送管理研究[学位论文].上海：上海交通大学,2008.
[39]高义佳.基于复杂网络的冷链物流网络优化与应用研究[学位论文].青岛：中国海洋大学,2009.
[40]龚树生,梁怀兰.生鲜食品的冷链物流网络研究[J].中国流通经济,2006,2：7-9.
[41]兰洪杰.食品冷链物流系统协同对象与过程研究[J].中国流通经济,2009,2：20-23.
[42]刘佳,宋铁成,高飞等.无线车辆管理调度系统的设计与实现[J].电子工程师,2007,4：74-77.
[43]肖深茂.电子商务环境下北京市社区物流管理策略研究[学位论文].北京：北京信息科技大学,2008.
[44]刘长华,王忠.基于HGA的智能交通调度优化方法研究[J].武汉理工大学学报(交通科学与工程版),2010(8)：712-715.
[45]陈素敏.果蔬农产品冷链物流信息系统框架研究[学位论文].北京：北京物资学院,2006.
[46]郭绍君.全球统一标识系统在食品冷链中的应用研究[学位论文].北京：北京交通大学,2009.
[47]司京成.北京东方友谊食品配送公司发展战略研究[学位论文].北京：北京交通大学,2007.
[48]Chen Na, Shi Lei. Analysis of Quality Game Behavior for Cold-Chain Logistics Outsourcing [A]. In:Logistics Systems and Intelligent Management, 2010 International Conference on [C]. Harbin, China, 9-10 Jan. 2010. 202 - 206.