Optimization of ship routing using hybrid genetic algorithm / Ismail

Vehicle Routing Problem (VRP) relates to the problem of providing optimum service with a fleet of vehicles to customers. It is a combinatorial optimization problem. The objective is usually to maximize the profit of the operation. However, for public transportation owned and operated by government, accessibility takes priority over profitability. Accessibility usually reduces profit, while increasing profit tends to reduce accessibility. In this research, we look at how accessibility can be increased without penalizing the profitability. This requires the determination of routes with minimum fuel consumption, maximum number of ports of call and maximum load factor satisfying a number of pre-determined constraints, i.e. hard and soft constraints. The hard constraints are travel time, travel distance and the restriction that a route must contain at least one fuel port. Soft constraints concerns with ship draft and load factor. To solve this problem, we propose a hybrid genetic algorithm (hybrid GA). A chromosome in the proposed hybrid GA consists of some sub-chromosomes and each sub-chromosome consists of Q-arm, P-arm and two centromere. The initial population is generated randomly for the centromere while Q-arm and P-arm are generated by the nearest neighbor. An improvement procedure is proposed to increase the performance of the hybrid GA. The improvement procedure ensures a chromosome with the best fitness is carried forward into the next generation. To evaluate the algorithm, three experiments are carried out. The first experiment is to investigate performance of the hybrid GA algorithm over 11 benchmarks. The results from this experiment show that the hybrid GA has better performance compared to the general GA, the PELNI method and the heuristic algorithm. The second experiment is to generate routes using three algorithms discussed in the research. The results shows that the best routes are generated by the hybrid GA followed by the general GA while the PELNI method shows the worst performance. The best and the worst fitness of the best solution in the second experiment were recorded. It is used to study the performance of the hybrid GA when compared to the general GA. The third experiment is to generate optimum routes when the number of vehicle used is minimized. The result of the experiments show that the hybrid GA performance better than the other algorithms