Abstract: For vehicle routing problem with constrains of fuzzy demand,multi-depot and open distribution,the triangular fuzzy number was utilized to characterize the fuzzy demand of customers.According to the fuzzy credibility theory,the decision conservative degree value was used to depict the decision maker's risk preference,and the grouping after path strategy was adopted for the multi-center constraint.The corresponding mathematic model was constructed on the base of above-mentioned assume.Then a two phase tabu search algorithm was designed to solve the problem,and the traveling salesman problem which contained all customers of open multi-depot vehicle routing problem with fuzzy demand was solved in the 1st phase of the algorithm,and the best solution of the 1st phase would be used as the initial solution at the 2nd phase.Therefore,an appropriate encoding method was adopted to guarantee the compatibility in the two phases computing of algorithm.The results showed that the triangular fuzzy number could be used to characterize the fuzzy demand of customers effectively,and the stochastic simulation algorithm could realize its simulation in computer;the 1st phase of the two phase tabu search algorithm could significantly improve the overall solution quality of the algorithm;the decision conservative degree value of decision maker had great influence on the total distribution cost that too conservative or too risky setting of the value couldn't get a better route arrangement,and the algorithm would get the best result when the value set to 0.6;the proposed algorithm could effectively solve the problem in an acceptable time.

Key words: open vehicle routing problem, multi-depot, fuzzy demand, tabu search algorithm

摘要： 针对模糊需求下多中心及开放式三重约束的车辆路径问题,运用三角模糊数表征模糊需求,根据可信性理论设置决策保守程度值刻画决策者的风险偏好,对多中心约束采用“先路径后分组”的策略,在此基础上建立了相应的数学模型;设计了两阶段禁忌搜索算法进行求解,算法第1阶段求解包含全部客户的旅行商问题,以此作为算法第2阶段的初始解,并采用合适的编码方式来保证算法两个阶段解兼容。通过算例实验表明,所使用的三角模糊数能够有效地对模糊需求进行定量刻画,随机模拟算法则能在计算机中对模糊需求进行模拟。所设计的两阶段禁忌搜索算法的第1阶段能够显著提升算法整体的求解质量。决策者的决策保守程度对配送总成本影响很大,过于保守或过于冒险均不能获得较好的路径安排方案,决策保守程度值为0.6时的模型求解效果最好,所提算法能够在可接受时间内对该类问题进行有效求解。

关键词: 开放式车辆路径优化, 多中心, 模糊需求, 禁忌搜索算法