摘要
针对应急救援物资紧缺难以满足所有需求的情形,以单个需求点最大缺货量最小、车辆运输费用最小为双目标,建立从配送中心到分发点再到需求点的两级配送路径选择模型,设计复杂性为O(n~3)的近似算法GA进行求解,证明算法近似比的上下界并讨论影响因素,用数值验证算法GA的近似比接近于1,表明算法GA具有较好的性能。最后以雅安灾区配送实例验证模型和算法的有效性。
Emergency relief supply dispatching is an important issue after the sudden disaster. For the practical case that emergency rescue materials are in short supply and cannot meet the needs of all demand points, a multi-objective Two-Echelon emergency relief supply dispatching vehicle routing model which is the nonlinear programming model is built to find an optimal solution with the aim of minimizing both the maximum shortage of each demand point and total distribution cost. Then, an approximation algorithm GA is designed with the time complexity O(n~3), the upper and lower bounder of the approximation ratio is analyzed and the approximation ratio is measured by instances. The approximation ratio which closes to 1 means that the approximation performance of the algorithm is better. Further, the influencing factors of the approximate ratio is analyzed, along with the finding that the more of the number of satellites, the supplies in the depot and the capacity of primary vehicles and secondary vehicles, the less of the number of customers, the better of the algorithm effectiveness. Finally, by comparing the results of the algorithm GA with the results of genetic algorithm, the effectiveness of the algorithm GA is proved.
作者
苏兵
周佳其
LIN Guohui
姬浩
徐阳
SU Bing;ZHOU Jia-qi;LIN Guo-hui;JI Hao;XU Yang(School of Economics and Management,Xi’an Technological University,Xi’an 710021,China;Computing Science,University of Alberta,Edmonton T6G 2E8,Canada;Research Center for Science and Technology Innovation in Military and Civilian Integration of Shaanxi’s Colleges and Universities,Xi’an 710021,China)
出处
《中国管理科学》
CSSCI
CSCD
北大核心
2022年第8期155-163,共9页
Chinese Journal of Management Science
基金
国家社会科学基金资助项目(20XGL023)。
关键词
两级配送路径
近似算法
应急救援物资配送
优化
Two-Echelon Vehicle Routing
approximation algorithms
emergency relief supply dispatching
optimization
