USING A GENETIC ALGORITHM TO SOLVE A VEHICLE ROUTING PROBLEM INVOLVING SIMULTANEOUS DELIVERIES AND PICKUPS WITH SPLIT LOADS AND TIME WINDOWS (A CASE STUDY FOR A SHIPPING COMPANY)

Background: This research addresses a Vehicle Routing Problem with Simultaneous Delivery and Pickup, Split Loads, and Time Windows (VRPSDPSLTW). In this research, the VRPSDPSLTW problem is adapted for Company X, a shipping company based in Surabaya. The main goal is to enhance the optimal utilization of vessel capacity in the field of shipping transportation and logistics. Little previous research has been done on VRPSDPSLTW at a shipping company. Methods: The optimization approach employed was the Genetic Algorithm (GA), which serves as a metaheuristic to effectively optimize vessel capacity utilization. The algorithm uses One Point Crossover and Swap Mutation operators and analyzes various mutation parameters to determine the best configuration. The GA was coded in R, and experiments were conducted to obtain the best parameter for the GA. Results: The research yielded several outcomes, including route plans, loaded and unloaded Twenty-Foot Equivalent Units (TEUs), travel times, and trip utility from the point of loading (POL) to the point of delivery (POD). In total, there were 85 port visits, surpassing the initial count of 35 ports. Some ports were visited multiple times, with the exception of Surabaya, which served as the home base for a fleet of 15 vessels. The average trip duration was approximately 35 days. Through experimentation, it was determined that employing 1,000 generations along with a mutation probability of 0.2 produces improved solutions. The Genetic Algorithm solution enhanced the average vessel capacity utilization, increasing it to 80.93%. This represents a significant 21.23% increase compared to the global average of 59.7% observed for similar vessel usage scenarios. Conclusions: Furthermore, through the introduction of novel route opportunities, the contributions of each vessel were effectively enhanced. This achievement resulted in an optimal average vessel capacity utilization that met the demand. The findings strongly advocate for the employment of the Genetic Algorithm, highlighting its potential to substantially improve vessel capacity utilization. Consequently, this approach has played a pivotal role in elevating the efficiency of transportation and logistics operations for Company X.