摘要
协作配送问题是典型的组合优化合作博弈问题,也可称为协作车辆路径问题,其核心问题之一是确定公平合理的成本分摊方案.其中核仁解由于具有唯一性和公平性等特点,是成本分摊领域中公认的科学分摊方案.本文提出了一种近似求解协作配送问题核仁解的方法.首先分析证明了当顾客位置分布均匀,从理论上协作配送成本分摊问题会是凸博弈问题,然后,基于凸博弈的核仁解会等同于预内核解的理论,提出了一个能够求解凸博弈问题核仁解的迭代逼近算法(approximate iterative algorithm,AIA),分析了AIA算法的复杂度为O(n~42~n),为此又提出了AIA的有效提速策略,可将AIA的复杂度降低至多项式.最后,通过求解协作配送算例和实例,验证了本文AIA算法能够准确求解得到协作配送成本分摊问题的核仁解,提出的求解策略能有效的减少求解耗时,并且得到的最终结果与实际核仁解的平均偏差不到0.02%,更重要的是AIA能够用于求解所有凸博弈问题的核仁解.
The collaborative distribution problem is a typical combined optimization cooperative game problem,and is named the collaborative vehicle routing problem.One of its core problems is to determine a fair and reasonable cost sharing plan.Among them,the nucleolus solution is a recognized scientific allocation plan in the field of cost sharing because of its uniqueness and fairness.This paper proposes a method to approximate the nucleolus solution of collaborative distribution problem.Firstly,the paper proves the cost allocation of collaborative vehicle routing problem will theoretically be a convex game problem when the location of the customer is evenly distributed.Based on the theory that the nucleolus solution will be equivalent to the prekernel solution in convex game problems,an approximate iterative algorithm(AIA)is proposed to get the nucleolus solution of convex game problems.The complexity of AIA is O(n~42~n),and then the paper proposes two effective speed-up strategies of AIA,which reduce the complexity of AIA to polynomial level.Finally,by solving the cooperative distribution examples,it is verified that the AIA algorithm in this paper can accurately solve the nucleolus solution of the collaborative distribution cost allocation problem.The proposed solution can effectively reduce the time-consuming of calculation.And the average deviation between the final result of AIA and the actual nucleolus solution is less than 0.02%.More importantly,AIA can be used to get the nucleolus solution in all convex games.
引文
[1]Gansterer M,Hartl R F.Collaborative vehicle routing:A survey[J].European Journal of Operational Research,2018(1):1-12.
[2]Fernandez E,Roca-Riu M,Speranza M G.The shared customer collaboration vehicle routing problem[J].European Journal of Operational Research,2018,265(3):1078-1093.
[3]Wang Y,Zhang J,Assogba K,et al.Collaboration and transportation resource sharing in multiple centers vehicle routing optimization with delivery and pickup[J].Knowledge-Based Systems,2018,160:296-310.
[4]Wang Y,Zhang S,Assogba K,et al.Economic and environmental evaluations in the two-echelon collaborative multiple centers vehicle routing optimization[J].Journal of Cleaner Production,2018,197(1):443-461.
[5]刘家利,马祖军.存在车辆租赁及共享且有时间窗的多配送中心开环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.
[6]Defryn C,Sorensen K,Cornelissens T.The selective vehicle routing problem in a collaborative environment[J].European Journal of Operational Research,2016(2):400-411.
[7]Von Neumann J,Morgenstern O.Theory of games and economic behavior[M].Princeton University Press,1944.
[8]Schmeidler D.The nucleolus of a characteristic function game[J].SIAM Journal on Applied Mathematics,1969,17(6):1163-1170.
[9]Baiou M,Barahona F.On the nucleolus of shortest path games[J].Algorithmic Game Theory,2017:55-66.
[10]Farsani E A,Abyaneh H A,Abedi M,et al.A novel policy for LMP calculation in distribution networks based on loss and emission reduction allocation using nucleolus theory[J].IEEE Transactions on Power Systems,2016(1):143-152.
[11]刘家财,李登峰,胡勋锋.区间值最小二乘核仁解及在供应链合作利益分配中的应用[J].中国管理科学. 2017,25(12):78-87.Li J C,Li D F,Hu X F.Interval-Valued least square nucleolus and its application in cooperative profit allocation of supply chain[J].Chinese Journal of Management Science,2017,25(12):78-87.
[12]Gow S H,Thomas L C.Interchange fees for bank ATM networks[J].Naval Research Logistics,1998,45(4):407-417.
[13]Albizuri M J,Echarri J M,Zarzuelo J M.A non-cooperative mechanism yielding the nucleolus of airport problems[J].Group Decision and Negotiation,2018,27(1):153-163.
[14]Kohlberg E.The nucleolus as a solution of a minimization problem[J].SIAM Journal on Applied Mathematics,1972,23(1):34-39.
[15]Owen G.A note on the nucleolus[J].International Journal of Game Theory,1974,3(2):101-103.
[16]Maschler M,Peleg B,Shapley L S.Geometric properties of the kernel,nucleolus,and related solution concepts[J].Mathematics of Operations Research,1979(4):303-338.
[17]Dragan I.A procedure for finding the nucleolus of a cooperative N person game[J].Zeitschrift fiir Operations Research,1981(5):119-131.
[18]Behringer F A.A simplex based algorithm for the lexicographically extended linear maxmin problem[J].European Journal of Operational Research,1981(3):274-283.
[19]Fromen B.Reducing the number of linear programs needed for solving the nucleolus problem of N-person game theory[J].European Journal of Operational Research,1997,98(3):626-636.
[20]Potters J A M,Reijnierse J H,Ansing M.Computing the nucleolus by solving a prolonged simplex algorithm[J].Mathematics of Operations Research,1996,21(3):757-768.
[21]Solymosi T,Raghavan T E S.An algorithm for finding the nucleolus of assignment games[J].International Journal of Game Theory,1994(2):119-143.
[22]Sankaran J K.On finding the nucleolus of an N-person cooperative game[J].International Journal of Game Theory,1991(4):329-338.
[23]Puerto J,Perea F.Finding the nucleolus of any N-person cooperative game by a single linear program[J].Computers&Operations Research,2013,40(10):2308-2313.
[24]Nguyen T,Thomas L.Finding the nucleoli of large cooperative games[J].European Journal of Operational Research,2016,248(3):1078-1092.
[25]Chardaire P.The core and nucleolus of games:A note on a paper by Gothe-Lundgren et al[J].Mathematical Programming,2001,90(1):147-151.
[26]Guajardo M,Jornsten K.Common mistakes in computing the nucleolus[J].European Journal of Operational Research,2015,241(3):931-935.
[27]Faigle U,Kern W,Kuipers J.On the computation of the nucleolus of a cooperative game[J].International Journal of Game Theory,2001,30(1):79-98.
[28]Leng M,Parlar M.Analytic solution for the nucleolus of a three-player cooperative game[J].Naval Research Logistics Quarterly,2010,57(7):667-672.
[29]Zhang Q,Yang Z,Gui B,Coalitional game with fuzzy payoffs and credibilistic nucleolus[J].Journal of Intelligent&Fuzzy Systems,2017,32(1):1-9.
[30]Lin J,Zhang Q. The least square B-nucleolus for fuzzy cooperative games[J].Journal of Intelligent&Fuzzy Systems,2016,30(1):279-289.
[31]Lin J,Zhang Q.The L-nucleolus and I-Shapley value for cooperative games under incomplete information[J].Transactions of Beijing Institute of Technology,2015(7):767-770.
[32]Hu C,Tsay M,Yeh C.A study of the nucleolus in the nested cost-sharing problem:Axiomatic and strategic perspectives[J].Games and Economic Behavior,2018:82-98.
[33]Sziklai B,Fleiner T,Solymosi T.On the core and nucleolus of directed acyclic graph games[J].Mathematical Programming,2017(1-2):243-271.
[34]Beardswood J,Hammersley J M.The shortest path through many points[J].Proceedings of the Cambridge Philosophical Society,1959,55:299-327.
[35]Helsgaun K.An effective implementation of the Lin-Kernighan traveling salesman heuristic[J].European Journal of Operational Research,2000,126:106-130.
[36]Stearns R E.Convergent transfer schemes for N-person games[J].Transactions of the American Mathematical Society,1968,134(3):449-459.
[37]Sakawa M,Nishizaki I,Uemura Y.Fuzzy programming and profit and cost allocation for a production and transportation problem[J].European Journal of Operational Research,2001,131(1):1-15.
[38]Krus L,Bronisz P.Cooperative game solution concepts to a cost allocation problem[J].European Journal of Operational Research,2000,122(2):258-271.
[39]SatyaRamesh P,Radhakrishna C.Use of cooperative game theory concepts for loss allocation in multiple transaction electricity markets[J].Journal of Electrical Systems,2009,5(1):6.
[40]Oh S C,Shin J.A semantic e-kanban system for network-centric manufacturing:Technology,scale-free convergence,value and cost-sharing considerations[J].International Journal of Production Research,2012,50(19):5292-5316.
[41]Lemaire J.Cooperative game theory and its insurance applications[J].Astin Bulletin,1991,21(1):17-40.
