在线组建协作配送联盟中企业成本节约相对量估算方法研究
|
摘要
企业参与在线协作配送联盟的重要决策依据是成本的节约程度,但计算该信息需要求解2~N-1个(N为企业数)类似多配送中心车辆路径问题的复杂难题,且在线协作联盟组建允许计算的时间十分有限.本文针对该难题,提出了一种估算协作配送问题结果的快速方法.首先,基于合作博弈中经典成本分摊方法,证明得出了计算过程中采用估算方法的可行性;然后,基于Beardwood研究的包含n个点的旅行商问题最优解路径长度,会近似等于α(An)~(1/2)的结论(α为参数,A为n个点的分布面积),提出了能够根据各企业顾客位置、分布区域面积等信息,预估协作配送问题目标函数结果的方法;最后,分别采用本文方法和传统优化方法求解了大量的实例和算例.结果表明:本文提出的方法计算速度迅速且质量准确,与传统方法相比耗时几乎可以忽略不计,能够满足在线实时计算的要求;估算的企业节约成本相对量误差均在10%之内,并且问题规模越大误差越小.
The cost saving percentage is important to enterprises that make decision to participate in an online logistics distribution alliance. However, computing the information needs to optimize 2~N-1(N is the number of enterprise) complexity NP-hard problems being similar to multi-depot vehicle routing problem, and to allow very limited computation time. In this paper, a fast method is proposed to estimate the result of collaborative vehicle routing problem. Firstly, the feasibility of adopting the estimation method in allocating cost is proved. Secondly,based on Beardwood's research conclusions the method for estimating distribution distance of collaborative vehicle routing problem is developed, according to the number of customers, demand quantity and position of customers and depots of all enterprises in alliance. At last,some benchmark instances are designed based on actual investigation data. Then the method proposed in this paper and a three-phase optimization algorithm CSV(Cluster+Savings+Variable Neighborhood Search) used to solve the instances. The results demonstrate that the computational time of the estimation method is almost negligible compared with the CSV, which could meet the requirement of on-line real-time calculation, and the cost savings percentage deviation is within 10% for all instances. What's more, the bigger the problem, the smaller the deviation.
The cost saving percentage is important to enterprises that make decision to participate in an online logistics distribution alliance. However, computing the information needs to optimize 2~N-1(N is the number of enterprise) complexity NP-hard problems being similar to multi-depot vehicle routing problem, and to allow very limited computation time. In this paper, a fast method is proposed to estimate the result of collaborative vehicle routing problem. Firstly, the feasibility of adopting the estimation method in allocating cost is proved. Secondly,based on Beardwood's research conclusions the method for estimating distribution distance of collaborative vehicle routing problem is developed, according to the number of customers, demand quantity and position of customers and depots of all enterprises in alliance. At last,some benchmark instances are designed based on actual investigation data. Then the method proposed in this paper and a three-phase optimization algorithm CSV(Cluster+Savings+Variable Neighborhood Search) used to solve the instances. The results demonstrate that the computational time of the estimation method is almost negligible compared with the CSV, which could meet the requirement of on-line real-time calculation, and the cost savings percentage deviation is within 10% for all instances. What's more, the bigger the problem, the smaller the deviation.
引文
[1] Wang Y, Ma X, Li Z, et al. Profit distribution in collaborative multiple centers vehicle routing problem[J].Journal of Cleaner Production, 2017, 144:203-219.
[2] Flisberg P, Frisk M, Roennqvist M, et al. Potential savings and cost allocations for forest fuel transportation in Sweden:A country-wide study[J]. Energy, 2015, 85:353-365.
[3] Perez-Bernabeu E, Juan A A, Faulin J, et al. Horizontal cooperation in road transportation:A case illustrating savings in distances and greenhouse gas emissions[J]. International Transactions in Operational Research, 2015,22(3SI):585-606.
[4] Schopka K, Kopfer H. Pre-selection strategies for the collaborative vehicle routing problem with time windows[J].Dynamics in Logistics, 2017:231-242.
[5] Liu R, Jiang Z, Fung R Y K, et al. Two-phase heuristic algorithms for full truckloads multi-depot capacitated vehicle routing problem in carrier collaboration[J]. Computers and Operations Research, 2010(5):950-959.
[6] Tang Y L, Cai Y G, Yang J, et al. Collaborative vehicle routing problem for shuttle bus[J]. Application Research of Computers, 2014(12):3617-3620.
[7] Ferdinand F N, Kim Y J, Lee H K, et al. A study on collaborative pick-up and delivery routing problem of linehaul vehicles in express delivery services[J]. International Journal of Industrial Engineering,2014(6):376-383.
[8] Li J, Zhang J. A hybrid tabu search for Multi-Depots collaborative vehicle routing problem with simultaneous pickup and delivery[J]. Journal of Convergence Information Technology, 2012(21):416.
[9] Gothelundgren M, Jornsten K, Varbrand P. On the nucleolus of the basic vehicle routing game[J]. Mathematical Programming, 1996, 72(1):83-100.
[10] Mohri H, Watanabe T, Mori M, et al. Cost allocation on vehicle routing problem[J]. Journal of the Operations Research Society of Japan, 1997, 40(4):451-465.
[11] Engevall S, Gothe-Lundgren M, Varbrand P. The heterogeneous vehicle-routing game[J]. Transportation Science,2004, 38(1):71-85.
[12] Krajewska M A, Kopfer H. Collaborating freight forwarding enterprises—Request allocation and profit sharing[J]. OR Spectrum, 2006, 28(3):301-317.
[13] Krajewska M A, Kopfer H, Laporte G, et al. Horizontal cooperation among freight carriers:Request allocation and profit sharing[J]. Journal of the Operational Research Society, 2008, 59(11):1483-1491.
[14] Peng L, Yaohua W, Na X. Allocating collaborative profit in Less-than-Truckload carrier alliance[J]. Journal of Service Science and Management, 2010, 3(1):143-149.
[15] Caprara A, Letchford A N. New techniques for cost sharing in combinatorial optimization games[J]. Mathematical Programming, 2010, 124(1-2):93-118.
[16] Guajardo M, Ronnqvist M. A review on cost allocation methods in collaborative transportation[J]. International Transactions in Operational Research, 2016, 23(3):371-392.
[17] Shapley L S. Cores of convex games[J]. International Journal of Game Theory, 1971, 1(1):11-26.
[18] Schmeidler D. The nucleolus of a characteristic function game[J]. SIAM Journal on Applied Mathematics,1969,17(6):1163-1170.
[19] Shapley L S. A value for n-person games[J]. Contributions to the Theory of Games, 1953, 28:307-317.
[20]陈瑶,霍佳震.制造企业精益供应物流的整合优化与成本分摊问题——以汽车业为例[J].管理工程学报,2012, 26(3):55-63.Chen Y, Huo J Z. Integrated optimization and cost allocation of lean inbound logistics for the auto manufacturer[J]. Journal of Industrial Engineering an Engineering Management, 2012, 26(3):55-63.
[21]谭春桥,陈晓红.基于Choquet延拓n人模糊对策的Shapley值[J].管理科学学报,2010(2):24-32.Tan C Q, Chen X H. Shapley value for n-persons fuzzy games based on Choquet extension[J]. Journal of Management Sciences in China, 2010(2):24-32.
[22]李勇军,梁樑,凌六一.基于DEA联盟博弈核仁解的固定成本分摊方法研究[J].中国管理科学,2009(1):58-63.Li Y J, Liang L, Ling L Y. The methodological study of allocating the fixed cost based on the nucleolus in data envelopment analysis and cooperative game[J]. Chinese Journal of Management Science, 2009(1):58-63.
[23]陈雯,张强.模糊合作对策的shapley值[J].管理科学学报,2006, 9(5):50-55.Chen W, Zhang Q. Shapley value for fuzzy cooperative games[J]. Journal of Management Sciences in China,2006, 9(5):50-55.
[24]刘家利,马祖军.存在车辆租赁及共享且有时间窗的多配送中心开环VRP[J].系统工程理论与实践,2013, 33(3):666-675.Liu J L, Ma Z J. Multi-depot open vehicle routing problem with time windows based on vehicle leasing and sharing[J]. Systems Engineering—Theory Practice, 2013, 33(3):666-675.
[25]饶卫振,金淳,王新华,等.考虑道路坡度因素的低碳VRP问题模型与求解策略[J].系统工程理论与实践,2014, 34(8):2092-2105.Rao W Z, Jin C, Wang X H, et al. A model of low-carbon vehicle routing problem considering road gradient and its solving strategy[J]. Systems Engineering—Theory Practice, 2014, 34(8):2092-2105.
[26]殷脂,叶春明.多配送中心物流配送车辆调度问题的分层算法模型[J].系统管理学报,2014, 23(4):602-606.Yin Z, Ye C M. Study on the hierarchical model for multi-depot logistic vehicle scheduling problem[J]. Journal of Systems&Management, 2014, 23(4):602-606.
[27] Mancini S. A real-life multi depot multi period vehicle routing problem with a heterogeneous fleet:Formulation and adaptive large neighborhood search based matheuristic[J]. Transportation Research Part C—Emerging Technologies, 2016, 70(SI):100-112.
[28] MontoyarTorres J R, López Franco J, Nieto Isaza S, et al. A literature review on the vehicle routing problem with multiple depots[J]. Computers&Industrial Engineering, 2015, 79:115-129.
[29] Ploskas N, Athanasiadis I, Papathanasiou J, et al. A tangible collaborative decision support system for various variants of the vehicle routing problem[J]. Decision Support Systems V—Big Data Analytics for Decision Making, 2015:73-84.
[30] Beardwood J, Halton J H, Hammersley J M. The shortest path through many points[J]. Mathematical Proceedings of the Cambridge Philosophical Society, 1959, 55(4):299-327.
[31] Helsgaun K. An effective implementation of the Lin-Kernighan traveling salesman heuristic[J]. European Journal of Operational Research, 2000, 126(1):106-130.
[32] Karakatic S, Podgorelec V. A survey of genetic algorithms for solving multi depot vehicle routing problem[J].Applied Soft Computing, 2015, 27:519-532.
[2] Flisberg P, Frisk M, Roennqvist M, et al. Potential savings and cost allocations for forest fuel transportation in Sweden:A country-wide study[J]. Energy, 2015, 85:353-365.
[3] Perez-Bernabeu E, Juan A A, Faulin J, et al. Horizontal cooperation in road transportation:A case illustrating savings in distances and greenhouse gas emissions[J]. International Transactions in Operational Research, 2015,22(3SI):585-606.
[4] Schopka K, Kopfer H. Pre-selection strategies for the collaborative vehicle routing problem with time windows[J].Dynamics in Logistics, 2017:231-242.
[5] Liu R, Jiang Z, Fung R Y K, et al. Two-phase heuristic algorithms for full truckloads multi-depot capacitated vehicle routing problem in carrier collaboration[J]. Computers and Operations Research, 2010(5):950-959.
[6] Tang Y L, Cai Y G, Yang J, et al. Collaborative vehicle routing problem for shuttle bus[J]. Application Research of Computers, 2014(12):3617-3620.
[7] Ferdinand F N, Kim Y J, Lee H K, et al. A study on collaborative pick-up and delivery routing problem of linehaul vehicles in express delivery services[J]. International Journal of Industrial Engineering,2014(6):376-383.
[8] Li J, Zhang J. A hybrid tabu search for Multi-Depots collaborative vehicle routing problem with simultaneous pickup and delivery[J]. Journal of Convergence Information Technology, 2012(21):416.
[9] Gothelundgren M, Jornsten K, Varbrand P. On the nucleolus of the basic vehicle routing game[J]. Mathematical Programming, 1996, 72(1):83-100.
[10] Mohri H, Watanabe T, Mori M, et al. Cost allocation on vehicle routing problem[J]. Journal of the Operations Research Society of Japan, 1997, 40(4):451-465.
[11] Engevall S, Gothe-Lundgren M, Varbrand P. The heterogeneous vehicle-routing game[J]. Transportation Science,2004, 38(1):71-85.
[12] Krajewska M A, Kopfer H. Collaborating freight forwarding enterprises—Request allocation and profit sharing[J]. OR Spectrum, 2006, 28(3):301-317.
[13] Krajewska M A, Kopfer H, Laporte G, et al. Horizontal cooperation among freight carriers:Request allocation and profit sharing[J]. Journal of the Operational Research Society, 2008, 59(11):1483-1491.
[14] Peng L, Yaohua W, Na X. Allocating collaborative profit in Less-than-Truckload carrier alliance[J]. Journal of Service Science and Management, 2010, 3(1):143-149.
[15] Caprara A, Letchford A N. New techniques for cost sharing in combinatorial optimization games[J]. Mathematical Programming, 2010, 124(1-2):93-118.
[16] Guajardo M, Ronnqvist M. A review on cost allocation methods in collaborative transportation[J]. International Transactions in Operational Research, 2016, 23(3):371-392.
[17] Shapley L S. Cores of convex games[J]. International Journal of Game Theory, 1971, 1(1):11-26.
[18] Schmeidler D. The nucleolus of a characteristic function game[J]. SIAM Journal on Applied Mathematics,1969,17(6):1163-1170.
[19] Shapley L S. A value for n-person games[J]. Contributions to the Theory of Games, 1953, 28:307-317.
[20]陈瑶,霍佳震.制造企业精益供应物流的整合优化与成本分摊问题——以汽车业为例[J].管理工程学报,2012, 26(3):55-63.Chen Y, Huo J Z. Integrated optimization and cost allocation of lean inbound logistics for the auto manufacturer[J]. Journal of Industrial Engineering an Engineering Management, 2012, 26(3):55-63.
[21]谭春桥,陈晓红.基于Choquet延拓n人模糊对策的Shapley值[J].管理科学学报,2010(2):24-32.Tan C Q, Chen X H. Shapley value for n-persons fuzzy games based on Choquet extension[J]. Journal of Management Sciences in China, 2010(2):24-32.
[22]李勇军,梁樑,凌六一.基于DEA联盟博弈核仁解的固定成本分摊方法研究[J].中国管理科学,2009(1):58-63.Li Y J, Liang L, Ling L Y. The methodological study of allocating the fixed cost based on the nucleolus in data envelopment analysis and cooperative game[J]. Chinese Journal of Management Science, 2009(1):58-63.
[23]陈雯,张强.模糊合作对策的shapley值[J].管理科学学报,2006, 9(5):50-55.Chen W, Zhang Q. Shapley value for fuzzy cooperative games[J]. Journal of Management Sciences in China,2006, 9(5):50-55.
[24]刘家利,马祖军.存在车辆租赁及共享且有时间窗的多配送中心开环VRP[J].系统工程理论与实践,2013, 33(3):666-675.Liu J L, Ma Z J. Multi-depot open vehicle routing problem with time windows based on vehicle leasing and sharing[J]. Systems Engineering—Theory Practice, 2013, 33(3):666-675.
[25]饶卫振,金淳,王新华,等.考虑道路坡度因素的低碳VRP问题模型与求解策略[J].系统工程理论与实践,2014, 34(8):2092-2105.Rao W Z, Jin C, Wang X H, et al. A model of low-carbon vehicle routing problem considering road gradient and its solving strategy[J]. Systems Engineering—Theory Practice, 2014, 34(8):2092-2105.
[26]殷脂,叶春明.多配送中心物流配送车辆调度问题的分层算法模型[J].系统管理学报,2014, 23(4):602-606.Yin Z, Ye C M. Study on the hierarchical model for multi-depot logistic vehicle scheduling problem[J]. Journal of Systems&Management, 2014, 23(4):602-606.
[27] Mancini S. A real-life multi depot multi period vehicle routing problem with a heterogeneous fleet:Formulation and adaptive large neighborhood search based matheuristic[J]. Transportation Research Part C—Emerging Technologies, 2016, 70(SI):100-112.
[28] MontoyarTorres J R, López Franco J, Nieto Isaza S, et al. A literature review on the vehicle routing problem with multiple depots[J]. Computers&Industrial Engineering, 2015, 79:115-129.
[29] Ploskas N, Athanasiadis I, Papathanasiou J, et al. A tangible collaborative decision support system for various variants of the vehicle routing problem[J]. Decision Support Systems V—Big Data Analytics for Decision Making, 2015:73-84.
[30] Beardwood J, Halton J H, Hammersley J M. The shortest path through many points[J]. Mathematical Proceedings of the Cambridge Philosophical Society, 1959, 55(4):299-327.
[31] Helsgaun K. An effective implementation of the Lin-Kernighan traveling salesman heuristic[J]. European Journal of Operational Research, 2000, 126(1):106-130.
[32] Karakatic S, Podgorelec V. A survey of genetic algorithms for solving multi depot vehicle routing problem[J].Applied Soft Computing, 2015, 27:519-532.