考虑时空距离的成品油多舱配送路径优化研究

The optimization research of refined oil multi-compartment distribution route considering temporal-spatial distance

成品油多舱配送问题是传统VRP问题在油品物流领域的一个典型应用,除了具有基本VRP问题的求解复杂性之外,还具有基于油品配送情景的复杂性特征,求解难度较大。针对这类问题,本文设计了一种考虑订单时空距离的两阶段启发式算法(STVNS算法)。首先引入时空距离的概念并通过订单时空聚类获得初始解,之后运用变邻域搜索算法进行再优化,同时设计了在配送过程中的扰动恢复策略,最后通过若干算例验证了算法的有效性。研究表明,相较于传统变邻域搜索算法,考虑配送订单时空距离的初始解以及针对多舱配送特点构造的邻域搜索结构均能大幅提高模型求解质量,加快算法收敛速度。此外,结合STVNS算法的扰动恢复策略能够在满足加油站需求的同时,有效减少成本支出。

Refined oil logistics can be divided into two stages.The first stage refers to the process by which the refined oil is transported to the depot from oil refineries.The second stage is the distribution from depot to gas stations or customers.The latter is located at the end of the entire oil supply chain and is essential for improving efficiency and reducing operating costs.In terms of the second stage,the vehicle scheduling problem is the key issue that determines the rationalization of refined oil secondary distribution.In China,most vehicles used in refined oil secondary distribution are single cabin tankers with small and medium– sized,which can only supply one kind of product once and has small delivery quantity.Especially in the peak season,the vehicle must go back and forth between the gas station and oil depot which seriously reduce the distribution efficiency.Therefore,the domestic refined oil vehicles are mostly compartmentalized vehicles,which have large loading capacity and could transport a variety of oil at the same time.It has obvious advantage especially when there are many gas stations but little demand.The refined oil secondary distribution can be abstracted as vehicle routing problem(VRP).In addition to the complexity of VRP,it has the complexity of oil distribution which includes multiple yards,multiple warehouses,multiple products,multiple shipping spaces,multiple vehicle types,return empty,carrying the load balance and nonlinear discontinuous cost function and so on.Currently,there are few literatures on VRP considering oil distribution.First of all,existing literatures focused on the distribution optimization of single type oil product,which seldom considered the influence of the heterogeneous vehicle and the multi-oil product on the distribution plan.It is especially short of related research on multi-compartment distribution and modeling without fully considering the influence of compartmental factors on distribution decisions.Secondly,in the process of modeling most researchers only consider the space distance between oil depot,distribution center and gas stations.The time window is just as the constraint condition.But due to the different distribution time window,it is clear that those gas stations with narrow space distance may not meet the time constraint,and can not be arranged in a path with narrow time window as well.In addition,the existing studies of vehicle scheduling disruption management are seldom in allusion to the oil distribution and mainly focus on the disturbance measurement and the fast recovery algorithm.For multi-compartment distribution,each class may be responsible for more than one gas station with different tasks,which requires a wide range of distribution and high precision.During the distribution,there will occur a variety of unexpected situations such as vehicle damage,time window changes and especially the demand changes.Currently,the distribution model is gradually converted from passive distribution to active distribution.Once the demand forecasting meets an error,the distribution centers need to increase a delivery order temporarily and adjust the original distribution program to complete the normal supply.Therefore,it is important to further investigate whether the oil products distribution route optimization or disturbance recovery vehicle scheduling.In summary,we design a two-phase approach considering temporal-spatial distance(STVNS).Firstly,we employ space-time clustering to obtain initial solutions,followed by applying VNS and disturbance recovery strategy to gain optimization.Finally,several numerical examples are presented to demonstrate the effectiveness of the proposed algorithm.The results show that the initial solution that considered temporal-spatial distance as well as neighborhood structures based on multi-compartment distribution can greatly improve the quality of the model solution,and accelerate the algorithm convergence speed.In addition,combined with the STVNS algorithm,the disturbance recovery strategy can effectively reduce the cost while meeting the demand of gas stations.