VARIABLE NEIGHBORHOOD SEARCH HEURISTIC FOR A NEW VARIANT OF THE FULL TRUCKLOAD ROUTING PROBLEM IN LIQUEFIED PETROLEUM GAS REPLENISHMENT

In this paper we address a new variant of the full truck load routing problem (FTVRP) arising in the liquefied petroleum gas (LPG) industry. The objective consists of determining a schedule of daily supply which minimizes the gas transportation cost and the additional purchase costs. First, we formulate the problem as a mixed-integer linear programming model. Then, a variable neighborhood search (VNS) metaheuristic is proposed to speed up the solution procedure and to generate good feasible solutions. In the proposed VNS, The initial solution is generated using a Greedy Algorithm by selecting the most beneficial nodes. Moreover, the developed local search is based on two different mechanisms: improving solution based on the transportation cost and based on the additional purchasing cost. A set of real datasets is selected in a way that reflects the real-life company situation and used to assess the performance of the proposed VNS. Computational results of large-scale test instances show that the proposed VNS performs well and can be efficiently used to solve the problem.