TRUCK ROUTING PROBLEM IN DISTRIBUTION OF GASOLINE TO GAS STATIONS

Open Access
Author:
Janakiraman, Swagath
Graduate Program:
Industrial Engineering
Degree:
Master of Science
Document Type:
Master Thesis
Date of Defense:
None
Committee Members:
  • Arunachalam Ravindran, Thesis Advisor
Keywords:
  • Mixed Linear Integer Programming
  • Vehicle Routing
  • MATLAB
Abstract:
This thesis aims at finding a daily routing plan for a fleet of vehicles delivering gasoline to gas stations for an oil company, satisfying all the system constraints. Main constraints include vehicle capacity constraints, customer demand constraints and distance travel limit. The fleet of vehicles starts from an installation (single depot) and tries to cover the maximum number of deliveries on their way without violating the vehicle capacity constraints. All the customers are visited only once and the vehicles then return back to the installation after delivering the gasoline to the gas stations. The mathematical problem is a multiple traveling salesman problem, which is computationally hard to solve. In this thesis, the problem is first formulated and solved as a Mixed Linear Integer Programming (MILP) problem. We show that this approach is not practical for larger problems, since the optimal algorithm can take more than 10 hours to solve even a small problem with just 10 customer locations. Hence, we develop an intelligent heuristics approach to solve large problems in few seconds. The heuristics method implemented in MATLAB, not only minimizes the total distance travelled by the fleet of vehicles, but also uses fewer number of trucks in comparison with the optimal method to deliver the gasoline. We compare the solution effectiveness of the heuristics with the optimal solution obtained by MILP. We then apply the heuristic method to an actual case study involving gasoline delivery to 120 gas stations and discuss its solution effectiveness.