基于邻域搜索的成品油多舱多目标配送路径优化算法研究

詹红鑫, 王旭坪, 孙自来, 何洪慧

系统工程理论与实践 ›› 2019, Vol. 39 ›› Issue (10) : 2660-2675.

PDF(1157 KB)
PDF(1157 KB)
系统工程理论与实践 ›› 2019, Vol. 39 ›› Issue (10) : 2660-2675. DOI: 10.12011/1000-6788-2017-0958-16
论文

基于邻域搜索的成品油多舱多目标配送路径优化算法研究

    詹红鑫1, 王旭坪1,2, 孙自来1, 何洪慧1
作者信息 +

Variable neighborhood search for the multi-objective multi-compartment optimization of refined products distribution

    ZHAN Hongxin1, WANG Xuping1,2, SUN Zilai1, HE Honghui1
Author information +
文章历史 +

摘要

针对成品油配送中多车型,多车舱的优化调度难题,综合考虑路径安排,舱位指派及车辆指派等决策.以配送成本最小,路径风险最小以及油品准时送达为目标,建立了成品油配送多目标路径优化模型.基于邻域搜索的基本思想,提出求解成品油配送多目标路径优化问题的MOVNS算法框架,并结合不同的可行解运行策略和比较准则,衍生出三类MOVNS算法(MOVNS-1、MOVNS-2、MOVNS-3).采用12组算例进行数值实验,结果表明,三种算法均能有效的求解配送模型,提升成品油多舱配送问题的解决效率;且MOVNS-2算法具有较强的局部搜索能力,MOVNS-3算法容易跳出局部最优;同时,考虑节点关联性的可行解构造策略和并行邻域搜索策略能够增强算法的寻优能力.

Abstract

Refined products distribution is an extension of the multi-compartment vehicle routing problem, which has to simultaneously consider the vehicle routing, the assignment of heterogonous trucks and loading policies of multi-compartment. An optimum model is developed with the objectives of minimizing the transport cost, the transport risk, and the time penalty cost. This article proposes a multi-objective variable neighborhood search (MOVNS) framework based on neighborhood search, which derive three MOVNS algorithms (MOVNS-1, MOVNS-2, MOVNS-3) when combined with different searching strategies and comparison criteria of feasible solutions. And extensive computational tests on 12 instances confirm the efficiency of the proposed algorithms. MOVNS-2 is equipped with stronger local search ability, and MOVNS-3 could avoid the poor local optimum effectively. Moreover, the route construction with relation degree between vertexes and the parallel search strategy can enhance the search ability of the algorithm.

关键词

成品油配送 / 车辆多舱 / 邻域搜索 / 多目标优化

Key words

refined products distribution / multi-compartment / VNS / multi-objective optimization

引用本文

导出引用
詹红鑫 , 王旭坪 , 孙自来 , 何洪慧. 基于邻域搜索的成品油多舱多目标配送路径优化算法研究. 系统工程理论与实践, 2019, 39(10): 2660-2675 https://doi.org/10.12011/1000-6788-2017-0958-16
ZHAN Hongxin , WANG Xuping , SUN Zilai , HE Honghui. Variable neighborhood search for the multi-objective multi-compartment optimization of refined products distribution. Systems Engineering - Theory & Practice, 2019, 39(10): 2660-2675 https://doi.org/10.12011/1000-6788-2017-0958-16
中图分类号: TP301.6   

参考文献

[1] El-Fallahi A, Prins C, Calvo R W. A memetic algorithm and a tabu search for the multi-compartment vehicle routing problem[J]. Computers & Operations Research, 2008, 35(5):1725-1741.
[2] Muyldermans L, Pang G. On the benefits of co-collection:Experiments with a multi-compartment vehicle routing algorithm[J]. European Journal of Operational Research, 2010, 206(1):93-103.
[3] Henke T, Speranza M G, Wäscher G. The multi-compartment vehicle routing problem with flexible compartment sizes[J]. European Journal of Operational Research, 2015, 246(3):730-743.
[4] 石磊. 危险货物道路运输事故统计分析及综合管理系统的建立[D].西安:长安大学, 2014.Shi L. Statistical analysis of dangerous goods road transportation accidents and the establishment of integrated management system[D]. Xi'an:Chang'an University, 2014.
[5] Cornillier F, Boctor F, Laporte G, et al. A heuristic for the multi-period petrol station replenishment problem[J]. European Journal of Operational Research, 2008, 191(2):295-305.
[6] Cornillier F, Boctor F, Renaud J. Heuristics for the multi-depot petrol station replenishment problem with time windows[J]. European Journal of Operational Research, 2012, 220(2):361-369.
[7] Cornillier F, Laporte G, Boctor F, et al. The petrol station replenishment problem with time windows[J]. Computers & Operations Research, 2009, 36(3):919-935.
[8] Boctor F, Renaud J, Cornillier F. Trip packing in petrol stations replenishment[J]. Omega, 2011, 39(1):86-98.
[9] Popovic D, Vidovic M, Radivojevic G. Variable neighborhood search heuristic for the inventory routing problem in fuel delivery[J]. Expert Systems with Applications, 2012, 39(18):13390-13398.
[10] 马义飞, 孙晓燕. 成品油二次配送调度优化模型及其遗传算法求解[J]. 运筹与管理, 2010, 19(6):73-78.Ma Y F, Sun X Y. Dispatching optimization model of second distribution of gasolin & diesel oil and solution based on genetic algorithm[J]. Operations Research and Management Science, 2010, 19(6):73-78.
[11] 李敏, 倪少权, 周凌, 等. 基于订单邻域的成品油二次配送中带时间窗车辆路径规划问题[J]. 计算机集成制造系统, 2015, 21(8):2158-2169.Li M, Ni S Q, Zhou L, et al. Vehicle routing problem with time windows of petroleum products distribution based on order neighborhood system[J]. Computer Integrated Manufacturing Systems, 2015, 21(8):2158-2169.
[12] 戴锡, 叶耀华, 吴勤旻, 等. 油品配送车辆路径问题的交互式求解方法[J]. 系统工程学报, 2009, 24(6):749-753.Dai X, Ye Y H, Wu Q M, et al. Interactively solving the vehicle routing problem for petroleum delivery[J]. Journal of Systems Engineering, 2009, 24(6):749-753.
[13] 张立峰, 易万里, 刘晓兰. 基于两阶段算法的大规模成品油二次配送优化[J]. 系统工程理论与实践, 2016, 36(11):2951-2963.Zhang L F, Yi W L, Liu X L. Two-stage optimization algorithm for large scale secondary petroleum product delivery planning[J]. Systems Engineering-Theory & Practice, 2016, 36(11):2951-2963.
[14] Zografos K G, Androutsopoulos K N. A heuristic algorithm for solving hazardous materials distribution problems[J]. European Journal of Operational Research, 2004, 152(2):507-519.
[15] Xie C, Waller S T. Optimal routing with multiple objectives:Efficient algorithm and application to the hazardous materials transportation problem[J]. Computer-Aided Civil and Infrastructure Engineering, 2012, 27(2):77-94.
[16] Das A, Mazumder T N, Gupta A K. Pareto frontier analyses based decision making tool for transportation of hazardous waste[J]. Journal of Hazardous Materials, 2012, 227-228:341-352.
[17] Jozefowiez N, Semet F, Talbi E G. Target aiming Pareto search and its application to the vehicle routing problem with route balancing[J]. Journal of Heuristics, 2007, 13(5):455-469.
[18] 杜卫卫, 姜立春, 刘付衍华. 基于交通流量的城市交叉口事故预测研究——以广州市为例[J]. 华东交通大学学报, 2009, 26(5):19-25.Du W W, Jiang L C, Liu F Y H, et al. Accident model prediction of urban intersection based on traffic flow-Taking Guangzhou as an example[J]. Journal of East China Jiaotong University, 2009, 26(5):19-25.
[19] Adibi M A, Zandieh M, Amiri M. Multi-objective scheduling of dynamic job shop using variable neighborhood search[J]. Expert Systems with Applications, 2010, 37(1):282-287.
[20] Liang Y C, Lo M H. Multi-objective redundancy allocation optimization using a variable neighborhood search algorithm[J]. Journal of Heuristics, 2010, 16(3):511-535.
[21] Verdegay J L. Evolutionary techniques for constrained optimization problems[C]//European Congress on Intelligent Techniques and Soft Computing, 1999:3997-4014.
[22] Zitzler E, Deb K, Thiele L. Comparison of multiobjective evolutionary algorithms:Empirical results[J]. Evolutionary Computation, 2000, 8(2):173-195.

基金

国家自然科学基金(71471025,71531002)
PDF(1157 KB)

619

Accesses

0

Citation

Detail

段落导航
相关文章

/