在线组建协作配送联盟中企业成本节约相对量估算方法研究

An estimation method for computing cost saving percentage of distribution enterprises in collaborative environment:Used for forming collaborative distribution coalition on-line

企业参与在线协作配送联盟的重要决策依据是成本的节约程度,但计算该信息需要求解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 2N-1 (N is the number of enterprise) complexity NP-hard problems being similar to multi-depot vehicle routing problem, and to allows 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 an 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.