考虑卸载顺序约束的成品油二次配送车辆路径问题

研究考虑卸载顺序约束的成品油二次配送车辆路径问题,已知油库使用容量有限的多隔舱运输槽车为加油站配送多种类型的成品油,每个隔舱只能装载一种特定的油品,且装载到各个隔舱中的油品具有固定的卸载顺序.已知加油站对各种油品的需求量,假设每个加油站对同一种油品的需求只能由一辆车配送,考虑配送车辆的固定动用成本和运输成本,以总配送成本极小化为目标建立该问题的混合整数规划模型,并设计求解模型的自适应大邻域搜索启发式算法.利用不同规模的算例进行模拟计算与分析,从而验证算法的有效性.实验结果显示:对于小规模算例,大邻域搜索启发式算法能够以较高的概率得到全局最优解;对于中、大规模算例,大邻域搜索启发式算法可以在短时间内得到近似最优解,近似比不超过1.2.所提出的模型和算法可为石油公司制定成品油二次配送计划提供理论依据和决策支持.

Vehicle routing problem of refined oil secondary distribution considering unloading sequence constraints

The vehicle routing problem of refined oil secondary distribution with unloading sequence constraints is studied. Multi-compartment oil tankers with limited capacity are used to transport multi-types refined oil to gas stations from oil depot. Each compartment can load only one type of refined oil and the unloading sequence of each type of oil is fixed. Given the demand of each gas station for every type of refined oil, assuming that the demand for one type of refined oil from each gas station can only be served by one vehicle, to minimize the total costs including the fixed costs and transportation costs of the distribution vehicle, a mixed integer programming model is established, and a self-adaptive large neighborhood search heuristic(LNSH) algorithm is developed for solving the model. The effectiveness of the algorithm is verified by simulations and analysis on multiple scale of instances. The experimental results show that using the LNSH algorithm, the global optimal solutions of small size examples can be found with higher probobality; the approximate optimal solutions of middle and large scale examples can be obtained quickly, and the approximate ratio is no more than 1.2. The model and the algorithm can provide theoretical basis and decision support for oil companies to develop refined oil secondary distribution schedules.