Author ORCID Identifier

https://orcid.org/0000-0002-5200-253X

Semester

Spring

Date of Graduation

2024

Document Type

Thesis

Degree Type

MS

College

Statler College of Engineering and Mineral Resources

Department

Industrial and Managements Systems Engineering

Committee Chair

Thorsten Wuest

Committee Member

John Saldanha

Committee Member

Zeyu Liu,

Abstract

Route determination for perishable products is complex due to its unique characteristics, such as limited shelf-life regulatory requirements, or possibility of getting damaged. This research investigates a novel problem of collecting raw milk from a rural network of dairy farms. The research problem is grounded in a real scenario of milk collection in West Virginia, USA. The milk in this scenario is produced by small farms incapable of realizing transportation economies of density out in mostly rural areas throughout the state. Maximum coverage area and milk processing overhead costs are used to identify suitable locations for intermediate milk collection centers or depots to store the milk to realize economies of density and reduce transportation costs. Each depot needs to be established within a certain maximum distance, for the refrigeration time of the multi-stop vehicle to not exceed the allowable time limit set to maintain the quality of the collected milk. This problem provides the unique opportunity to incorporate two separate classical optimization problems: the Set Covering Problem (SCP) (identifying depot locations) and the Traveling Salesman Problem (TSP) (routing). The SCP involves identifying the optimal number of service facilities required for the aggregation operations to maintain milk quality in transit. The TSP determines the most optimal route between farms and the depot. The milk collection problem requires solving both the SCP and TSP. However, the problem also becomes more difficult to solve when combining TSP constraints with the SCP. This study proposes a novel Mixed Integer Linear Programming (MILP) model to address this problem. The objective of the proposed model is to minimize the depot assignment cost, overhead cost of the depot, cleaning cost of the vehicle, and the vehicle distance traveled to reduce the fuel cost. The exact algorithm has been analyzed and we use sensitivity analyses to determine the model’s reliability and robustness to changes in the problem scenario. The model was tested for different scenarios for the dairy industry in West Virginia. However, it has to be noted that other applications can be developed for similar structured problems based on this study given the flexible working path created by the Application Programming Interface (API) of Google Maps. We evaluate the proposed model by comparing its result with the steepest ascent Hill climbing algorithm, a mathematical optimization problem in Artificial Intelligence (AI) and Nearest Neighbor heuristics. The two algorithms are compared regarding solution quality and computational efficiency to determine the better heuristic algorithm for the developed model. The Hill climbing algorithm has given significantly better results than the Nearest Neighbor heuristics. The Hill climbing algorithm ended up in near-optimal results with an efficient computational time. Further, the Multi-Vehicle Routing (MVR) model is analyzed for the transportation part of the model and found that MVR scenario shows the potential over other scenario (TSP-based) based on vehicle cycle time, still, there is a door to future research to incorporate the heterogeneous fleet and multi-depot constraints in the developed model.

Share

COinS