PDF(1167 KB)
PDF(1167 KB)
PDF(1167 KB)
行驶时间延迟下配送车辆调度的干扰管理模型与算法
Disruption management model and algorithm for distribution vehicle scheduling problems under accidental travel time delay
针对行驶时间延迟下配送车辆调度的干扰管理问题,给出了车辆调度人员实际操作中的一系列"救援模式",并将其提炼为计算机可以理解并处理的形式化知识;按照车辆调度人员的"救援路线列举→救援路线选择"两阶段的思维方式,以顾客时间窗偏离程度最小化和配送成本最小化为目标,建立了问题的数学模型及其求解算法. 通过初步的实验,确定了算法的参数配置;在Solomon提出的标准算例上对算法的鲁棒性、求解结果的质量、以及求解性能等几项指标进行了测试及与文献算法的比较;最后对算法进行了实时化的处理. 实验结果表明,本文算法不仅达到了多目标优化的效果, 而且可以满足实时应用的要求.
Focused on the distribution vehicle scheduling problem under travel time delay, a series of rescue modes generalized from practical vehicle planners' experiences were presented and formulated to the extent that computers could understand and process. According to the vehicle planner's two-stage rescue idea of "routes generation → routes selection", a mathematical model with the aims of minimizing the deviation of customer time windows and minimizing the distribution cost was constructed for the problem, along with an algorithm. Based on some preliminary experiments, the combination of parameters' values in the algorithm was given. The robustness, the solution quality, and the efficiency of the algorithm were tested on Solomon's benchmark problems and a comparison with other algorithm in the literature was made. Finally, the algorithm was improved in the aspect of the real-time application. The experiment results show that the algorithm not only takes effect in the multi-objective optimization, but can meet the real-time application requirement.
行驶时间延迟 / 物流配送 / 干扰管理 / 救援模式 / 车辆路径问题 / 时间窗 {{custom_keyword}} /
travel time delay / distribution / disruption management / rescue mode / vehicle routing problem / time windows {{custom_keyword}} /
[1] Gao S, Chabini I. Optimal routing policy problems in stochastic time-dependent networks[J]. Transportation Research Part B, 2006, 40(2): 93-122.
[2] Zheng Y S, Liu B D. Fuzzy vehicle routing model with credibility measure and its hybrid intelligent algorithm[J]. Applied Mathematics and Computation, 2006, 176(2): 673-683.
[3] 刘长石, 赖明勇. 基于模糊聚类与车辆协作策略的随机车辆路径问题[J]. 管理工程学报, 2010, 24(2): 75-78.Liu C S, Lai M Y. The fuzzy clustering and vehicle coordination strategy to stochastic vehicle routing problem[J]. Journal of Industrial Engineering and Engineering Management, 2010, 24(2): 75-78.
[4] 曹二保, 赖明勇, 李董辉. 基于混合差分进化算法的模糊需求车辆路径问题[J]. 系统工程理论与实践, 2009, 29(2): 106-113.Cao E B, Lai M Y, Li D H. Vehicle routing problem with fuzzy demands based on hybrid differential evolution[J]. Systems Engineering — Theory & Practice, 2009, 29(2): 106-113.
[5] Li J Q, Mirchandani P B, Borenstein D. A Lagrangian heuristic for the real-time vehicle rescheduling problem[J]. Transportation Research Part E, 2009, 45(3): 419-433.
[6] Li J Q, Mirchandani P B, Borenstein D. The vehicle rescheduling problem: Model and algorithms[J]. Networks, 2007, 50(3): 211-229.
[7] Chen Z L, Xu H. Dynamic column generation for dynamic vehicle routing with time windows[J]. Transportation Science, 2006, 40(1): 74-88.
[8] 胡祥培, 丁秋雷, 张漪, 等. 干扰管理研究评述[J]. 管理科学, 2007, 20(2): 2-8.Hu X P, Ding Q L, Zhang Y, et al. A review on disruption management[J]. Journal of Management Sciences, 2007, 20(2): 2-8.
[9] 胡祥培, 张漪, 丁秋雷, 等. 干扰管理模型及其算法的研究进展[J]. 系统工程理论与实践, 2008, 28(10): 40-46.Hu X P, Zhang Y, Ding Q L, et al. Review on disruption management model and its algorithm[J]. Systems Engineering — Theory & Practice, 2008, 28(10): 40-46.
[10] Yu G, Qi X T. Disruption Management: Framework, Models and Applications[M]. Singapore: World Scientific Publishing Co Pte Ltd, 2004.
[11] Potivn J Y, Xu Y, Benyahia I. Vehicle routing and scheduling with dynamic travel times[J]. Computers & Operations Research, 2006, 33: 1129-1137.
[12] Huisman D, Freling R, Wagelmans A P M. A robust solution approach to the dynamic vehicle scheduling problem[J]. Transportation Science, 2004, 38(4): 447-458.
[13] 王明春, 高成修, 曾永廷. VRPTW的扰动恢复及其TABU SEARCH算法[J]. 数学杂志, 2006, 26(2): 231-236.Wang M C, Gao C X, Zeng Y T. Recovery of the VRPTW disruption and the Tabu Search algorithm[J]. Journal of Mathematics, 2006, 26(2): 231-236.
[14] 杨文超, 王征, 胡祥培, 等. 行驶时间延迟的物流配送干扰管理模型及算法[J]. 计算机集成制造系统, 2010, 16(2): 331-339.Yang W C, Wang Z, Hu X P, et al. Disruption management model and algorithm for urban distribution with travel time delay[J]. Computer Integrated Manufacturing Systems, 2010, 16(2): 331-339.
[15] Mu Q, Fu Z, Lysgaard J, et al. Disruption management of the vehicle routing problem with vehicle breakdown[J]. Journal of the Operational Research Society, 2011, 62(4): 742-749.
[16] Deb K, Agrawal S, Pratap A, et al. A fast elitist non-dominated sorting genetic algorithm for multi-objective optimisation: NSGA-II[C]// Proceedings of the 6th International Conference on Parallel Problem Solving from Nature, London, 2000.
[17] Solomon M. Solomon benchmark problems[EB/OL]. [2009-2-28]. http://www.idsia.ch/～luca/macs-vrptw/problems/welcome.htm.
国家自然科学基金(70801008, 71271037, 90924006); 国家杰出青年基金(70725004);中央高校基本科研业务费专项资金(DUT12JR09)
/
| 〈 |
|
〉 |
