Volume 1 : Issue 1

Optimum Routes for Multiple Petrol Station Replenishment Problems

Authors : S. A. MirHassani,A.Dolatnezhad



In the Multiple Petrol Station Replenishment Problem with Time Window (MPSRPTW), the aim is to plan, schedule and manage truck fleet to deliver petroleum products to petrol stations. In this article, an algorithm was proposed to solve the MPSRPTW, in which feasible trips were obtained by solving a routing problem on a set of sub-graphs. The sub-graphs were small graphs of original graph that played an important role in reducing time requirement for generating feasible trips. Moreover, an improvement algorithm was proposed that generated a restricted set of feasible trips when the number of stations was huge. Based on the restricted set, a trip selection model proposed to produce near-optimal solution. Computational experience confirms that the proposed algorithm was able to achieve a near-optimal solution in a reasonable time by using this set of feasible trips. Finally, the approach was evaluated on a set of randomly generated problem and a real case with 42 stations arising in Eastern Quebec.