基于遗传算法的成品油二次配送车辆路径问题研究  

Study on the Vehicle Routing Problem of Refined Oil Secondary Distribution Based on Genetic Algorithm

作　　者：李珍萍[1] 胡娩霞 吴凌云[2] LI Zhen-ping;HU Wan-xia;WU Ling-yun(School of Information, Beijing Wuzi University, Beijing 101149, China;Academy of Mathematics and System Science, Chinese Academy of Sciences, Beijing 100190, China)

机构地区：[1]北京物资学院信息学院,北京101149 [2]中国科学院数学与系统科学研究院,北京100190

出　　处：《数学的实践与认识》2018年第9期189-198,共10页Mathematics in Practice and Theory

基　　金：国家自然科学基金(71771028,71540028);2018年北京市属高校高水平教师队伍建设支持计划创新团队;2016年北京高等学校高水平人才交叉培养“实培计划”项目毕业设计(科研类)

摘　　要：研究了加油站需求已知前提下带时间窗的具有满隔舱运输约束的多车型成品油二次配送车辆路径问题．首先以总费用极小化为目标建立了具有满载运输约束的多车型成品油二次配送车辆路径问题的混合整数规划模型，其中总费用包括动用车辆的固定费用、车辆的运输费用、以及不满足时间窗约束的等待成本和惩罚成本等．然后基于成品油二次配送车辆路径问题的特点设计了求解模型的遗传算法，通过对车辆和加油站分别采用自然数编码方式、解码时考虑约束条件等策略有效避免了不可行解的产生．最后利用一个实际案例进行了模拟计算，结果显示根据方法得到的配送方案明显优于实际中凭经验得到的配送方案，总配送成本大约降低了9％．模型和算法为制订成品油二次配送方案提供了决策依据．The vehicle routing problem of refined oil secondary distribution with known demand of gas stations, time window constraints and full compartment transport constraints is investigated. A mixed integer programming model is established to minimize the total cost with constraints of full load transportation of multiple type vehicles. The total cost includes the fixed costs of the vehicle used, the transportation costs, the waiting costs and penal costs for the vehicles not satisfying the time window constraints. Base on the characteristics of the problem, a genetic algorithm is designed to solve the model. By adopting the natural number coding scheme for the vehicle and the gas station, and the decoding strategy considering the constraints, the developed Mgorithm is effective to avoid the generation of infeasible solutions. The simulation is conducted on a real case, the results show that the distribution scheme obtained by this method is obviously superior to the actual distribution scheme, and the total distribution cost is reduced by about 9%. The model and algorithm of this paper provide the decision reference for formulating the secondary distribution scheme of refined oil.

关 键 词：成品油二次配送 车辆路径问题 混合整数规划模型 遗传算法 

分 类 号：TE834[石油与天然气工程—油气储运工程] TP18[自动化与计算机技术—控制理论与控制工程]