模糊需求下多中心开放式车辆路径优化
|
摘要
针对模糊需求下多中心及开放式三重约束的车辆路径问题,运用三角模糊数表征模糊需求,根据可信性理论设置决策保守程度值刻画决策者的风险偏好,对多中心约束采用"先路径后分组"的策略,在此基础上建立了相应的数学模型;设计了两阶段禁忌搜索算法进行求解,算法第1阶段求解包含全部客户的旅行商问题,以此作为算法第2阶段的初始解,并采用合适的编码方式来保证算法两个阶段解兼容。通过算例实验表明,所使用的三角模糊数能够有效地对模糊需求进行定量刻画,随机模拟算法则能在计算机中对模糊需求进行模拟。所设计的两阶段禁忌搜索算法的第1阶段能够显著提升算法整体的求解质量。决策者的决策保守程度对配送总成本影响很大,过于保守或过于冒险均不能获得较好的路径安排方案,决策保守程度值为0.6时的模型求解效果最好,所提算法能够在可接受时间内对该类问题进行有效求解。
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 1 st phase of the algorithm,and the best solution of the 1 st phase would be used as the initial solution at the 2 nd 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 1 st 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.
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 1 st phase of the algorithm,and the best solution of the 1 st phase would be used as the initial solution at the 2 nd 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 1 st 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.
引文
[1]ARAS N,AKSEN D,TEKIN M T.Selective multi-depot vehicle routing problem with pricing[J].Transportation Research Part C:Emerging Technologies,2011,19(5):866-884.
[2]AFSHAR-NADJAFI B,AFSHAR-NADJAFI A.A constructive heuristic for time-dependent multi-depot vehicle routing problem with time-windows and heterogeneous fleet[J].Journal of King Saud University:Engineering Sciences,2014,29(1):29-34.
[3]WANG Zheng,ZHANG Jun,WANG Xuping.A modified variable neighborhood search algorithm for the multi depot vehicle routing problem with time windows[J].Chinese Journal of Management Science,2011,19(2):99-109(in Chinese).[王征,张俊,王旭坪.多车场带时间窗车辆路径问题的变邻域搜索算法[J].中国管理科学,2011,19(2):99-109.]
[4]YU Bin,JIN Penghuan,YANG Zhongzhen.Two-stage heuristic algorithm for multi-depot vehicle routing problem with time windows[J].Systems Engineering-Theory&Practice,2012,32(8):1793-1800(in Chinese).[于滨,靳鹏欢,杨忠振.两阶段启发式算法求解带时间窗的多中心车辆路径问题[J].系统工程理论与实践,2012,32(8):1793-1800.]
[5]OLIVEIRA F B D,ENAYATIFAR R,SADAEI H J,et al.A cooperative coevolutionary algorithm for the multi-depot vehicle routing problem[J].Expert Systems with Applications:An International Journal,2016,43(C):117-130.DOI:10.1016/j.eswa.2015.08.030.
[6]YU B,YANG Z Z,XIE J X.A parallel improved ant colony optimization for multi-depot vehicle routing problem[J].Journal of the Operational Research Society,2011,62(1):183-188.
[7]YU V F,JEWPANYA P,REDI A A N P.Open vehicle routing problem with cross-docking[J].Computers&Industrial Engineering,2016,94:6-17.
[8]ATEFI R,SALARI M,COELHO L C,et al.The open vehicle routing problem with decoupling points[J].European Journal of Operational Research,2017,265(1):316-327.
[9]爦EVKLI A Z,GLER B.A multi-phase oscillated variable neighbourhood search algorithm for a real-world open vehicle routing problem[J].Applied Soft Computing,2017,58:128-144.
[10]LPEZ-SNCHEZ A D,HERNNDEZ-DAZ A G,VIGOD,et al.A multi-start algorithm for a balanced real-world open vehicle routing problem[J].European Journal of Operational Research,2014,238(1):104-113.
[11]ERBAO C,MINGYONG L.A hybrid differential evolution algorithm to vehicle routing problem with fuzzy demands[J].Journal of Computational&Applied Mathematics,2009,231(1):302-310.
[12]SHI Y,BOUDOUH T,GRUNDER O.A hybrid genetic algorithm for a home health care routing problem with time window and fuzzy demand[J].Expert Systems with Applications,2016,72(4):160-176.
[13]CAO Erbao,LAI Mingyong.The open vehicle routing problem with fuzzy demands[J].Expert Systems with Applications,2010,37(3):2405-2411.
[14]GHAFFARI-NASAB N,AHARI S G,GHAZANFARI M.A hybrid simulated annealing based heuristic for solving the location-routing problem with fuzzy demands[J].Scientia Iranica,2013,20(3):919-930.
[15]KUO R J,ZULVIA F E,SURYADI K.Hybrid particle swarm optimization with genetic algorithm for solving capacitated vehicle routing problem with fuzzy demand-a case study on garbage collection system[J].Applied Mathematics&Computation,2012,219(5):2574-2588.
[16]ZHANG Xiaonan,FAN Houming.Optimization and realtime adjustment for vehicle routing problem with fuzzy demand[J].Journal of Shanghai Jiaotong University,2016,50(1):124-139(in Chinese).[张晓楠,范厚明.模糊需求车辆路径优化及实时调整[J].上海交通大学学报,2016,50(1):124-139.]
[17]LI Xing.Credibility theory[M]//Uncertainty and Operations Research:Credibilistic Programming.Berlin,Germany:Springer-Verlag,2013:1-29.
[18]GLOVER F.Future paths for integer programming and links to artificial intelligence[J].Computers&Operations Research,1986,13(5):533-549.
[19]JIA Hongmei,LI Yang,DONG Bo,et al.An improved tabu search approach to vehicle routing problem[J].Procedia-Social and Behavioral Sciences,2013,96:1208-1217.
[20]SILVESTRIN P V,RITT M.An iterated tabu search for the multi-compartment vehicle routing problem[J].Computers&Operations Research,2017,81:192-202.
[21]XIONG Hao,YAN Huili.A three-phase tabu search heuristic for the split delivery vehicle routing problem[J].Systems Engineering-Theory&Practice,2015,35(5):1230-1235(in Chinese).[熊浩,鄢慧丽.需求可拆分车辆路径问题的三阶段禁忌算法[J].系统工程理论与实践,2015,35(5):1230-1235.]
[22]BULHES T,HM H,MARTINELLI R,et al.The vehicle routing problem with service level constraints[J].European Journal of Operational Research,2018,265(2):544-558.
[2]AFSHAR-NADJAFI B,AFSHAR-NADJAFI A.A constructive heuristic for time-dependent multi-depot vehicle routing problem with time-windows and heterogeneous fleet[J].Journal of King Saud University:Engineering Sciences,2014,29(1):29-34.
[3]WANG Zheng,ZHANG Jun,WANG Xuping.A modified variable neighborhood search algorithm for the multi depot vehicle routing problem with time windows[J].Chinese Journal of Management Science,2011,19(2):99-109(in Chinese).[王征,张俊,王旭坪.多车场带时间窗车辆路径问题的变邻域搜索算法[J].中国管理科学,2011,19(2):99-109.]
[4]YU Bin,JIN Penghuan,YANG Zhongzhen.Two-stage heuristic algorithm for multi-depot vehicle routing problem with time windows[J].Systems Engineering-Theory&Practice,2012,32(8):1793-1800(in Chinese).[于滨,靳鹏欢,杨忠振.两阶段启发式算法求解带时间窗的多中心车辆路径问题[J].系统工程理论与实践,2012,32(8):1793-1800.]
[5]OLIVEIRA F B D,ENAYATIFAR R,SADAEI H J,et al.A cooperative coevolutionary algorithm for the multi-depot vehicle routing problem[J].Expert Systems with Applications:An International Journal,2016,43(C):117-130.DOI:10.1016/j.eswa.2015.08.030.
[6]YU B,YANG Z Z,XIE J X.A parallel improved ant colony optimization for multi-depot vehicle routing problem[J].Journal of the Operational Research Society,2011,62(1):183-188.
[7]YU V F,JEWPANYA P,REDI A A N P.Open vehicle routing problem with cross-docking[J].Computers&Industrial Engineering,2016,94:6-17.
[8]ATEFI R,SALARI M,COELHO L C,et al.The open vehicle routing problem with decoupling points[J].European Journal of Operational Research,2017,265(1):316-327.
[9]爦EVKLI A Z,GLER B.A multi-phase oscillated variable neighbourhood search algorithm for a real-world open vehicle routing problem[J].Applied Soft Computing,2017,58:128-144.
[10]LPEZ-SNCHEZ A D,HERNNDEZ-DAZ A G,VIGOD,et al.A multi-start algorithm for a balanced real-world open vehicle routing problem[J].European Journal of Operational Research,2014,238(1):104-113.
[11]ERBAO C,MINGYONG L.A hybrid differential evolution algorithm to vehicle routing problem with fuzzy demands[J].Journal of Computational&Applied Mathematics,2009,231(1):302-310.
[12]SHI Y,BOUDOUH T,GRUNDER O.A hybrid genetic algorithm for a home health care routing problem with time window and fuzzy demand[J].Expert Systems with Applications,2016,72(4):160-176.
[13]CAO Erbao,LAI Mingyong.The open vehicle routing problem with fuzzy demands[J].Expert Systems with Applications,2010,37(3):2405-2411.
[14]GHAFFARI-NASAB N,AHARI S G,GHAZANFARI M.A hybrid simulated annealing based heuristic for solving the location-routing problem with fuzzy demands[J].Scientia Iranica,2013,20(3):919-930.
[15]KUO R J,ZULVIA F E,SURYADI K.Hybrid particle swarm optimization with genetic algorithm for solving capacitated vehicle routing problem with fuzzy demand-a case study on garbage collection system[J].Applied Mathematics&Computation,2012,219(5):2574-2588.
[16]ZHANG Xiaonan,FAN Houming.Optimization and realtime adjustment for vehicle routing problem with fuzzy demand[J].Journal of Shanghai Jiaotong University,2016,50(1):124-139(in Chinese).[张晓楠,范厚明.模糊需求车辆路径优化及实时调整[J].上海交通大学学报,2016,50(1):124-139.]
[17]LI Xing.Credibility theory[M]//Uncertainty and Operations Research:Credibilistic Programming.Berlin,Germany:Springer-Verlag,2013:1-29.
[18]GLOVER F.Future paths for integer programming and links to artificial intelligence[J].Computers&Operations Research,1986,13(5):533-549.
[19]JIA Hongmei,LI Yang,DONG Bo,et al.An improved tabu search approach to vehicle routing problem[J].Procedia-Social and Behavioral Sciences,2013,96:1208-1217.
[20]SILVESTRIN P V,RITT M.An iterated tabu search for the multi-compartment vehicle routing problem[J].Computers&Operations Research,2017,81:192-202.
[21]XIONG Hao,YAN Huili.A three-phase tabu search heuristic for the split delivery vehicle routing problem[J].Systems Engineering-Theory&Practice,2015,35(5):1230-1235(in Chinese).[熊浩,鄢慧丽.需求可拆分车辆路径问题的三阶段禁忌算法[J].系统工程理论与实践,2015,35(5):1230-1235.]
[22]BULHES T,HM H,MARTINELLI R,et al.The vehicle routing problem with service level constraints[J].European Journal of Operational Research,2018,265(2):544-558.