The petrol station replenishment problem (PSRP) refers to the process of transporting petroleum products from oil depots to petrol stations via tank trucks. It mainly consists of two parts: allocating petroleum products to tank trucks and planning the travel route of each truck. In this study, we examine a new variant of PSRP by considering a multi-depot vehicle routing problem with open inter-depot routes (MDVRPOI). Each depot can act as an intermediate replenishment facility, and each truck can be reloaded at any depot any number of times within the working period. Moreover, trucks can end their routes at any depot instead of making a long empty drive to the start depot. The trucks are heterogeneous with multiple load-specific compartments. We formulate the problem as a mixed-integer linear programming (MILP) model. Given the problem’s complexity, a tabu-based adaptive large neighborhood search (T-ALNS) algorithm is proposed, which integrates the tabu search approach into ALNS to solve the problem effectively. The T-ALNS executes multiple problem-tailored destroy/repair operators on the station, trip, and route levels. A local search procedure with problem-specific operators and an adaptive strategy is further embedded into T-ALNS. We use the real data of an oil company in China to evaluate our algorithm. Computational results show that our T-ALNS significantly outperforms the CPLEX solver and other algorithms in terms of solution quality and computation time. Further, it realizes an average reduction in transportation cost of about 45% compared to the company’s actual strategy.

This paper aims to study a new form of facility layout problem, in which the building has already been constructed and the specific room layout inside has been determined. Unlike the traditional facility layout problem, what we take into account is how to assign a certain number of rooms to a given number of departments with the purpose of maximizing the utilization rate of the rooms. This is equivalent to minimizing the total difference value between the extra area of different departments after satisfying their required area, thus reducing the space waste. To solve this special combinatorial optimization problem, we develop a Mixed-Integer Linear Programming (MILP) model. The model is solved using commercial software CPLEX12.6. Computational results on several randomly generated instances demonstrate the effectiveness of the proposed approach.