客户配送要求变动下的VRPSDP干扰管理优化
|
摘要
为解决客户配送要求变动对VRPSDP方案造成的干扰问题,从成本和服务时间两个方面,就干扰事件对原物流配送车辆路径方案造成的影响进行了干扰辨识分析.构建了VRPSDP干扰管理模型,并设计基于禁忌搜索的调度算法.从Solomon标准测试算例中随机抽取6组算例对模型和算法的有效性进行验证.结果显示,本文的干扰管理方案与传统的增派车辆和全局重调度方案相比较,广义总费用偏离有明显地降低,且本文方法能够在较短的时间内生成满意的物流配送车辆调度调整方案.
In order to handle the disruption caused by the changes of customer distribution requirement to the original plan of vehicle routing problem with simultaneous delivery and pickup(VRPSDP), this paper conducts the disruption identification analysis on the influence of the disruption event on the original logistics distribution vehicle routing scheme from three aspects of path, cost and service time. Therefore, the disruption management model with changes of customer distribution requirement is established. Then, a new dispatching method using tabu search algorithm is designed on the basis of the results of disruption identification. The randomly selected 6 samples from Solomon standard test verify the effectiveness of the model and algorithm. Experimental results show that the generalized total cost deviation is reduced obviously with the disruption management method given by this paper compared with the traditional adding vehicle or rescheduling method. And it could generate a satisfactory distribution vehicle schedule adjustment plan in a short time.
In order to handle the disruption caused by the changes of customer distribution requirement to the original plan of vehicle routing problem with simultaneous delivery and pickup(VRPSDP), this paper conducts the disruption identification analysis on the influence of the disruption event on the original logistics distribution vehicle routing scheme from three aspects of path, cost and service time. Therefore, the disruption management model with changes of customer distribution requirement is established. Then, a new dispatching method using tabu search algorithm is designed on the basis of the results of disruption identification. The randomly selected 6 samples from Solomon standard test verify the effectiveness of the model and algorithm. Experimental results show that the generalized total cost deviation is reduced obviously with the disruption management method given by this paper compared with the traditional adding vehicle or rescheduling method. And it could generate a satisfactory distribution vehicle schedule adjustment plan in a short time.
引文
[1]MIN H.The multiple vehicle routing problem with simultaneous delivery and pick-up points[J].Transportation Research Part A:General,1989,23(5):377-386.
[2]张亚明,李娜.基于精英单亲遗传算法的冷链物流VRP模型优化研究[J].数学的实践与认识,2016,46(4):87-96.[ZHANG Y M,LI N.Research on elite selection based partheno-genetic algorithm under optimized cold-chain logistics VRP model[J].Mathematics in Practice and Theory,2016,46(4):87-96.]
[3]丁秋雷.客户时间窗变化的物流配送干扰管理模型-基于行为的视角[J].中国管理科学,2015,23(5):89-97.[DING Q L.Model of disruption management for the change of time window based on human behavior in logistic disruption[J].Computer&Operations Research2015,23(5):89-97.]
[4]SCHYNS M.An ant colony system for responsive dynamic vehicle routing[J].European Journal o Operational Research,2015,245(3):704-718.
[5]ZHANG T,CHAOVALITWONGSE W A,ZHANG Y JScatter search for the stochastic travel-time vehicle routing problem with simultaneous pick-ups and deliveries[J].Computers&Operations Research,201239(10):2277-2290.
[6]王征,胡祥培,王旭坪.行驶时间延迟下配送车辆调度的干扰管理模型与算法[J].系统工程理论与实践2013,33(2):378-387.[WANG Z,HU X P,WANG X PDisruption management model and algorithm for distribution vehicle scheduling problems under accidental travel time delay[J].System Engineering Theory&Practice,2013,33(2):378-387.]
[7]杨华龙,叶迪,张倩,等.时间窗变动的车辆调度干扰管理模型与算法[J].运筹与管理,2017,26(10):56-64.[YANG H L,YE D,ZHANG Q,et al.Disruption management model and algorithm for vehicle scheduling with time window changes[J].Operations Research and Management Science,2017,26(10):56-64.]
[8]王旭坪,阮俊虎,孙自来,等.带回程取货车辆路径问题的干扰回复模型[J].系统工程学报,2013,28(5):608-616.[WANG X P,RUAN J H,SUN Z L,et al.Disruption recovery modal for vehicle routing problem with backhaul[J].Journal of Systems Engineering,2013,28(5):608-616.]
[9]王超,穆东.基于模拟退火算法求解VRPSPDTW问题[J].系统仿真学报,2014,26(11):2618-2623.[WANG C,MU D.Solving VRPSPDTW problem using simulated annealing algorithm[J].Journal of System Simulation,2014,26(11):2618-2623.]
[10]LAI M Y,LIU C S,TONG X J.A two-stage heuristic for pickup and delivery vehicle routing problem with time windows[J].Journal of Industrial&Management,2017,6(2):435-451.
[11]柴获,何瑞春,马昌喜,等.求解带硬时间窗车辆路径问题的改进UMDA算法[J].交通运输系统工程与信息,2016,16(2):176-182.[CHAI H,HE R C,MA C X,et al.A univariate marginal distribution algorithm hybridized with insertion heuristics for the vehicle routing problem with hard time windows[J].Journal of Transportation Systems Engineering and Information Technology,2016,16(2):176-182.]
[12]胡祥培,孙丽君,王雅楠.物流配送系统干扰管理模型研究[J].管理科学学报,2011,14(1):50-59.[HU X P,SUN L J,WANG Y N.A modal for disruption management in urban distribution systems[J].Journal of Management Sciences in China,2011,14(1):50-59.]
[2]张亚明,李娜.基于精英单亲遗传算法的冷链物流VRP模型优化研究[J].数学的实践与认识,2016,46(4):87-96.[ZHANG Y M,LI N.Research on elite selection based partheno-genetic algorithm under optimized cold-chain logistics VRP model[J].Mathematics in Practice and Theory,2016,46(4):87-96.]
[3]丁秋雷.客户时间窗变化的物流配送干扰管理模型-基于行为的视角[J].中国管理科学,2015,23(5):89-97.[DING Q L.Model of disruption management for the change of time window based on human behavior in logistic disruption[J].Computer&Operations Research2015,23(5):89-97.]
[4]SCHYNS M.An ant colony system for responsive dynamic vehicle routing[J].European Journal o Operational Research,2015,245(3):704-718.
[5]ZHANG T,CHAOVALITWONGSE W A,ZHANG Y JScatter search for the stochastic travel-time vehicle routing problem with simultaneous pick-ups and deliveries[J].Computers&Operations Research,201239(10):2277-2290.
[6]王征,胡祥培,王旭坪.行驶时间延迟下配送车辆调度的干扰管理模型与算法[J].系统工程理论与实践2013,33(2):378-387.[WANG Z,HU X P,WANG X PDisruption management model and algorithm for distribution vehicle scheduling problems under accidental travel time delay[J].System Engineering Theory&Practice,2013,33(2):378-387.]
[7]杨华龙,叶迪,张倩,等.时间窗变动的车辆调度干扰管理模型与算法[J].运筹与管理,2017,26(10):56-64.[YANG H L,YE D,ZHANG Q,et al.Disruption management model and algorithm for vehicle scheduling with time window changes[J].Operations Research and Management Science,2017,26(10):56-64.]
[8]王旭坪,阮俊虎,孙自来,等.带回程取货车辆路径问题的干扰回复模型[J].系统工程学报,2013,28(5):608-616.[WANG X P,RUAN J H,SUN Z L,et al.Disruption recovery modal for vehicle routing problem with backhaul[J].Journal of Systems Engineering,2013,28(5):608-616.]
[9]王超,穆东.基于模拟退火算法求解VRPSPDTW问题[J].系统仿真学报,2014,26(11):2618-2623.[WANG C,MU D.Solving VRPSPDTW problem using simulated annealing algorithm[J].Journal of System Simulation,2014,26(11):2618-2623.]
[10]LAI M Y,LIU C S,TONG X J.A two-stage heuristic for pickup and delivery vehicle routing problem with time windows[J].Journal of Industrial&Management,2017,6(2):435-451.
[11]柴获,何瑞春,马昌喜,等.求解带硬时间窗车辆路径问题的改进UMDA算法[J].交通运输系统工程与信息,2016,16(2):176-182.[CHAI H,HE R C,MA C X,et al.A univariate marginal distribution algorithm hybridized with insertion heuristics for the vehicle routing problem with hard time windows[J].Journal of Transportation Systems Engineering and Information Technology,2016,16(2):176-182.]
[12]胡祥培,孙丽君,王雅楠.物流配送系统干扰管理模型研究[J].管理科学学报,2011,14(1):50-59.[HU X P,SUN L J,WANG Y N.A modal for disruption management in urban distribution systems[J].Journal of Management Sciences in China,2011,14(1):50-59.]