基于场景动态度的两级配送路径问题
|
摘要
针对城市配送过程中出现的交通限行和需求不确定性等问题,将配送周期划分为初始配送阶段和动态补货阶段,路径中包含枢纽型物流中心、配送型物流中心和客户,研究其共同构成的两级车辆配送路径优化问题.考虑到问题的动态性,提出前摄性需求配额策略及响应性补货策略,构建基于场景动态度的两级动态车辆路径问题数学模型.设计融合扫描算子的禁忌搜索算法,完成车辆初始阶段的配送路径优化;根据场景动态度,设计修复/更新性动态客户的响应策略,快速响应动态需求.最后,通过仿真算例验证模型和算法的有效性,实验结果表明,所提出的设计策略能够有效降低动态客户对低动态度应用场景初始路径的干扰,并简化高动态度场景下的路径优化复杂度.
Aiming at the problems such as traffic limitation and demand uncertainty in the process of city distribution, this paper divides the distribution process into initial stage and dynamic replenishment stage, and studies the optimization of the two-echelon dynamic vehicle routing of the hub logistics center, the distribution logistics center and customers. Taking into account the dynamic events, this paper proposes a proactive demand quota strategy and a responsive replenishment strategy, and establishes the mathematical model of the two-echelon dynamic vehicle routing problem in dynamic circumstance. A tabu search algorithm based on a fusion scan operator is designed to optimize the delivery route in the initial stage. Meanwhile, according to the scene dynamic degree, this paper raises a repair/update dynamic customer response strategy to respond quickly to the dynamic demand. Finally, a simulation example is given to illustrate, the effectiveness of the proposed model and algorithm. The experimental results demonstrate that the proposed scheduling strategy can effectively reduce the dynamic client interference on the initial path of low-dynamism scenario and simplify the path optimization complexity of high-dynamism scenarios.
Aiming at the problems such as traffic limitation and demand uncertainty in the process of city distribution, this paper divides the distribution process into initial stage and dynamic replenishment stage, and studies the optimization of the two-echelon dynamic vehicle routing of the hub logistics center, the distribution logistics center and customers. Taking into account the dynamic events, this paper proposes a proactive demand quota strategy and a responsive replenishment strategy, and establishes the mathematical model of the two-echelon dynamic vehicle routing problem in dynamic circumstance. A tabu search algorithm based on a fusion scan operator is designed to optimize the delivery route in the initial stage. Meanwhile, according to the scene dynamic degree, this paper raises a repair/update dynamic customer response strategy to respond quickly to the dynamic demand. Finally, a simulation example is given to illustrate, the effectiveness of the proposed model and algorithm. The experimental results demonstrate that the proposed scheduling strategy can effectively reduce the dynamic client interference on the initial path of low-dynamism scenario and simplify the path optimization complexity of high-dynamism scenarios.
引文
[1]麻存瑞,柏赟,赵欣苗.快递配送车辆路径优化研究[J].交通运输系统工程与信息,2017,17(4):182-187.(Ma C R,Bai Y,Zhao X M.Vehicle routing optimization on express distribution[J].J of Transportation Systems Engineering and Information Technology,2017,17(4):182-187.)
[2]叶威惠,张飞舟.真实路况下的快递配送路径优化研究[J].计算机工程与科学,2017,39(8):1530-1537.(Ye W H,Zhang F Z.Express distribution route optimization under real-time road condition[J].Computer Engineering and Science,2017,39(8):1530-1537.)
[3]Nagy G,Salhi S.Location-routing:Issues,models and methods[J].European J of Operational Research,2007,177(2):649-672.
[4]Rahmani Y,Cherifkhettaf W R,Oulamara A.The two-echelon multi-products location-routing problem with pickup and delivery:Formulation and heuristic approaches[J].Int J of Production Research,2014,54(4):1-21.
[5]Liu R,Tao Y,Hu Q,et al.Simulation-based optimisation approach for the stochastic two-echelonlogistics problem[J].Int J of Production Research,2017,55(1):1-15.
[6]王道平,徐展,杨岑.基于两阶段启发式算法的物流配送选址-路径问题研究[J].运筹与管理,2017,26(4):70-75.(Wang D P,Xu Z,Yang C.Study on location-routing problem of logistics distribution based on two-stage heuristic algorithm[J].Operations Research and Management Science,2017,26(4):70-75.)
[7]Escobar J W,Linfati R,Baldoquin M G,et al.Agranular variable tabu neighborhood search for the capacitated location-routing problem[J].Transportation Research Part B,2014,67(9):344-356.
[8]Jepsen M,Spoorendonk S,Ropke S.A branch-and-cut algorithm for the symmetric two-echelon capacitated vehicle routing problem[J].Transportation Science,2013,47(9):23-37.
[9]Feliu J G,Perboli G,Tadei R,et al.The two-echelon capacitated vehicle routing problem[J].Working Papers,2008,45(3):364-380.
[10]孙华丽,王循庆,薛耀锋.应急定位一路径的模糊机会约束规划模型[J].统计与决策,2012(7):45-48.(Sun H L,Wang X Q,Xue Y F.Fuzzy chance constrained programming model for emergency location and one path[J].Statistics&Decision,2012(7):45-48.)
[11]Adulyasak Y,Cordeau J F,Jans R.Formulations and branch-and-cut algorithms for multivehicle production and inventory routing problems[J].Informs J on Computing,2014,26(1):103-120.
[12]Yuan B,Liu R,Jiang Z.A branch-and-price algorithm for the home health care scheduling and routing problem with stochastic service times and skill requirements[J].Int J of Production Research,2015,53(24):7450-7464.
[13]Janne Huiskonen.Service parts management:Demand forecasting and inventory control[J].Production Planning&Control,2011,25(6):489-494.
[14]穆东,王超,王胜春.基于并行模拟退火算法求解时间依赖型车辆路径问题[J].计算机集成制造系统,2015,21(6):1626-1636.(Mu D,Wang C,Wang S C.Solving TDVRP based on parallel-simulated annealing algorithm[J].Computer Integrated Manufacturing Systems,2015,21(6):1626-1636.)
[15]Cordeau J,Gendreau M,Laporte G.A tabu search heuristic for periodic and multi-depot vehicle routing problems[J].Networks,2015,30(2):105-119.
[16]王茜,吉清凯,胡祥培.多车型多车槽VRP的混合导引反应式禁忌搜索算法[J].管理工程学报,2016,30(3):179-187.(Wang Q,Ji Q K,Hu X P.A hybrid guided reactive tabu search for heterogeneous fixed fleet multi-compartment vehicle routing problem[J].J of Industrial Engineering and Engineering Management,2016,30(3):179-187.)
[17]代颖,马祖军.应急物流系统中的随机定位-路径问题[J].系统管理学报,2012,21(2):212-217.(Dai Y,Ma Z J.Stochastic location-routing problem in emergency logistics systems[J].J of Systems&Management,2012,21(2):212-217.)
[18]李明燏,梁丽萍,鲁燕霞.基于改进禁忌搜索算法的车辆路径问题模型[J].公路交通科技,2017,34(10):108-114.(Li M J,Liang L P,Lu Y X.A model of vehicle routing problem based on improved tabu search algorithm[J].J of Highway and Transportation Research and Development,2017,34(10):108-114.)
[19]Alonso F,Alvarez M J,Beasley J E.A tabu search algorithm for the periodic vehicle routing problem with multiple vehicle trips and accessibility restrictions[J].J of the Operational Research Society,2008,59(7):963-976.
[20]Maischberger M.A parallel iterated tabu search heuristic for vehicle routing problems[J].Computers&Operations Research,2012,39(9):2033-2050.
[21]Larsen A.The dynamic vehicle routing problem[D].Kongens Lyngby:Department of Mathematical Modelling,Technical University of Denmark,2000.
[2]叶威惠,张飞舟.真实路况下的快递配送路径优化研究[J].计算机工程与科学,2017,39(8):1530-1537.(Ye W H,Zhang F Z.Express distribution route optimization under real-time road condition[J].Computer Engineering and Science,2017,39(8):1530-1537.)
[3]Nagy G,Salhi S.Location-routing:Issues,models and methods[J].European J of Operational Research,2007,177(2):649-672.
[4]Rahmani Y,Cherifkhettaf W R,Oulamara A.The two-echelon multi-products location-routing problem with pickup and delivery:Formulation and heuristic approaches[J].Int J of Production Research,2014,54(4):1-21.
[5]Liu R,Tao Y,Hu Q,et al.Simulation-based optimisation approach for the stochastic two-echelonlogistics problem[J].Int J of Production Research,2017,55(1):1-15.
[6]王道平,徐展,杨岑.基于两阶段启发式算法的物流配送选址-路径问题研究[J].运筹与管理,2017,26(4):70-75.(Wang D P,Xu Z,Yang C.Study on location-routing problem of logistics distribution based on two-stage heuristic algorithm[J].Operations Research and Management Science,2017,26(4):70-75.)
[7]Escobar J W,Linfati R,Baldoquin M G,et al.Agranular variable tabu neighborhood search for the capacitated location-routing problem[J].Transportation Research Part B,2014,67(9):344-356.
[8]Jepsen M,Spoorendonk S,Ropke S.A branch-and-cut algorithm for the symmetric two-echelon capacitated vehicle routing problem[J].Transportation Science,2013,47(9):23-37.
[9]Feliu J G,Perboli G,Tadei R,et al.The two-echelon capacitated vehicle routing problem[J].Working Papers,2008,45(3):364-380.
[10]孙华丽,王循庆,薛耀锋.应急定位一路径的模糊机会约束规划模型[J].统计与决策,2012(7):45-48.(Sun H L,Wang X Q,Xue Y F.Fuzzy chance constrained programming model for emergency location and one path[J].Statistics&Decision,2012(7):45-48.)
[11]Adulyasak Y,Cordeau J F,Jans R.Formulations and branch-and-cut algorithms for multivehicle production and inventory routing problems[J].Informs J on Computing,2014,26(1):103-120.
[12]Yuan B,Liu R,Jiang Z.A branch-and-price algorithm for the home health care scheduling and routing problem with stochastic service times and skill requirements[J].Int J of Production Research,2015,53(24):7450-7464.
[13]Janne Huiskonen.Service parts management:Demand forecasting and inventory control[J].Production Planning&Control,2011,25(6):489-494.
[14]穆东,王超,王胜春.基于并行模拟退火算法求解时间依赖型车辆路径问题[J].计算机集成制造系统,2015,21(6):1626-1636.(Mu D,Wang C,Wang S C.Solving TDVRP based on parallel-simulated annealing algorithm[J].Computer Integrated Manufacturing Systems,2015,21(6):1626-1636.)
[15]Cordeau J,Gendreau M,Laporte G.A tabu search heuristic for periodic and multi-depot vehicle routing problems[J].Networks,2015,30(2):105-119.
[16]王茜,吉清凯,胡祥培.多车型多车槽VRP的混合导引反应式禁忌搜索算法[J].管理工程学报,2016,30(3):179-187.(Wang Q,Ji Q K,Hu X P.A hybrid guided reactive tabu search for heterogeneous fixed fleet multi-compartment vehicle routing problem[J].J of Industrial Engineering and Engineering Management,2016,30(3):179-187.)
[17]代颖,马祖军.应急物流系统中的随机定位-路径问题[J].系统管理学报,2012,21(2):212-217.(Dai Y,Ma Z J.Stochastic location-routing problem in emergency logistics systems[J].J of Systems&Management,2012,21(2):212-217.)
[18]李明燏,梁丽萍,鲁燕霞.基于改进禁忌搜索算法的车辆路径问题模型[J].公路交通科技,2017,34(10):108-114.(Li M J,Liang L P,Lu Y X.A model of vehicle routing problem based on improved tabu search algorithm[J].J of Highway and Transportation Research and Development,2017,34(10):108-114.)
[19]Alonso F,Alvarez M J,Beasley J E.A tabu search algorithm for the periodic vehicle routing problem with multiple vehicle trips and accessibility restrictions[J].J of the Operational Research Society,2008,59(7):963-976.
[20]Maischberger M.A parallel iterated tabu search heuristic for vehicle routing problems[J].Computers&Operations Research,2012,39(9):2033-2050.
[21]Larsen A.The dynamic vehicle routing problem[D].Kongens Lyngby:Department of Mathematical Modelling,Technical University of Denmark,2000.
© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号 地址：北京市海淀区学院路29号 邮编：100083 电话：办公室：(+86 10)66554848；文献借阅、咨询服务、科技查新：66554700 |