Comparison of GA-Shift Neighbourhood Mutation and GA-Pairs Exchange Mutation with Multi Cut Point Crossover in Solving RICH-VRP

ismail ismail, Sanusi Sanusi, Pratiwi Hendro Wahyudiono, Nurdiana Daeng Pawawo

Abstract


This research was focused on a heterogeneous fleet of passenger ships to solve multi depot by using genetic algorithm (GA) to solve combinatorial problem i.e. vehicle routing problem (VRP). The objective of this study is to compare the roulette wheel selection, multi cut point crossover, and shift neighbourhood mutation with roulette wheel selection, multi cut point crossover, and pairs exchange mutation to minimize the sum of the fuel consumption travelled, the cost for violations of the ship draft and sea depth, and penalty cost for violations of the load factor; maximize number port of call; and maximize load factor. Problem solving in this study is how to generate feasible route combinations for rich VRP that meets all the requirements with optimum solution. Route generated by roulette wheel selection, multi cut point crossover, and shift neighbourhood mutation could decrease fuel consumption about 19.4350% compared to roulette wheel selection, multi cut point crossover, and pairs exchange mutation about 18.6738%.


Full Text:

PDF

References


A. Mungwattana, K. Soonpracha and T. Manisri, ”A Practical Case Study of a Heterogeneous Fleet VRP with Various Constraints”. Proceedings of the 2016 International Conference on Industrial Engineering and Operations Management, pp.948-957, 2016.

A. Pessoa, E. Uchoa and M. Poggi de Aragão, “A Robust Branch-Cut-and-Price Algorithm for the Heterogeneous Fleet Vehicle Routing Problem,” Network, vol.54, pp.167–177. 2009.

A. Subramanian, P. H. V. Penna, E. Uchoa and L. S. Ochi, “A hybrid algorithm for the Heterogeneous Fleet Vehicle Routing Problem,” European Journal of Operational Research, vol.221, pp.285–295, 2012

B. Nag, B. L. Golden, and A. Assad, “Vehicle Routing with Site Dependencies,” Vehicle routing: methods and studies, pp.149–159, 1988.

C. D. Tarantilis, C. T. Kiranoudis, and V. S. Vassiliadis, “A List-Based Threshold Accepting Metaheuristic for the Heterogeneous Fixed Fleet Vehicle Routing Problem,” Journal of the Operational Research Society, vol.54, pp.65–71, 2003.

C. D. Tarantilis, C. T. Kiranoudis and V. S. Vassiliadis, “A Threshold Accepting Metaheuristic for The Heterogeneous Fixed Fleet Vehicle Routing Problem,” Journal of the Operational Research Society, vol.152, pp.148–158, 2004

C. Prins, “Efficient Heuristics for the Heterogeneous Fleet Multi Trip VRP with Application to a Large-Scale Real Case,” Journal of Mathematical Modelling and Algorithms, vol.1, pp. 135–150, 2002.

C. Prins, “Two Memetic Algorithms for Heterogeneous Fleet Vehicle Routing Problems,” Eng.Appl.Artif.Intell. vol.22, pp.916–928, 2009

E. Choi and D. W. Tcha, “A Column Generation Approach to the Heterogeneous Fleet Vehicle Routing Problem,” Computers and Operations Research, vol. 34, pp.2080–2095, 2007.

E. D. Taillard, “A Heuristic Column Generation Method for the Heterogeneous Fleet VRP,” RAIRO, vol.33, pp. 1–14, 1996.

E. Volna, ”Genetic Algorithm for the VRP,” Proceeding of International Conference of Numerical Analysis and Applied Mathematics ICNAAM 2015, vol. 4. pp.120002.1 – 120002.

F. Li, B. L. Golden, and E. Wasil, “A Record-to-Record Travel Algorithm for Solving the Heterogeneous Fleet Vehicle Routing Problems,” Computers and Operations Research, vol.34, pp.2734–2742, 2007

G. B. Dantzig and J. H. Ramser, “The Truck Dispatching Problem,” Management Science, vol. 6, pp.80-91, 1959.

H. Bae and I. Moon, ”Multi-depot VRP with time windows considering delivery and installation vehicles”. Applied Mathematical Modelling, vol.40. pp. 6536–6549, 2016

H. C. W. Lau, T. M. Chan, W. T. Tsui, and W. K. Pang, “Application of Genetic Algorithms to Solve the Multi Depot Vehicle Routing Problem,” Transactions on Automation Science and Engineering, vol. 7, pp. 383-392. 2010.

H. Kocha, T. Henke, and G. Wäscher, ”A Genetic Algorithm for the multi-compartment VRP with flexible compartment sizes.” Working paper no. 4. Faculty of economics and management, universität magdeburg, 2016.

H. Yaman, “Formulations and Valid Inequalities for the Heterogeneous Vehicle Routing Problem,” Mathematical Programming, vol. 106, pp. 365–390, 2006.

I. C. Choi, S. I. Kim and H. S. Kim, “A Genetic Algorithm with a Mixed Region Search for the Asymmetric Travelling Salesman Problem,” Computers and Operations Research, vol.30, pp. 773–786, 2003

I. M. Chao, B. Golden , and E. Wasil, “A Computational Study of a New Heuristic for the Site-Dependent Vehicle Routing Problem,” INFOR, vol.37, pp.319-355, 1999.

I. Yusuf, M. S. Baba and N. Iksan, “Applied Genetic Algorithm for Solving Rich VRP”, Applied Artificial Intelligence, Vol. 28, No.10, pp.957-991, 2014.

J. Brandão, “A Tabu Search Algorithm for The Heterogeneous Fixed Fleet Vehicle Routing Problem, ”Computers and Operations Research, vol.38, pp.140–151, 2011

J. F. Cordeau and G. Laporte, “A Tabu Search Algorithm for the Site Dependent Vehicle Routing Problem with Time Windows,” INFOR, vol. 39, pp.292-300, 2001

L. S. Ochi, D. S. Viana, L. Drummond, and A. O. Victor, “A Parallel Evolutionary Algorithm for the Vehicle Routing Problem with Heterogeneous Fleet,” Future Generation Computation System, vol.14, pp.285–292, 1998.

M. Gendreau, G. Laporte, C. Musaraganyi and E. D. Taillard, “A Tabu Search Heuristic for the Heterogeneous Fleet Vehicle Routing Problem,” Computers and Operations Research, vol.26, pp.1153–1173, 1999.

N. E. A. Ghani, S. R. Shariff and S. M. Zahari, ”An alternative algorithm for VRP with time windows for daily deliveries,” Advances in Pure Mathematics,pp.342-350, 2016.

P. H. V. Penna, A. Subramanian, and L. S. Ochi, “An Iterated Local Search Heuristic for the Heterogeneous Fleet Vehicle Routing Problem,” Journal of Heuristics, 2011.

R. Dondo and J. Cerdá, “A Cluster-Based Optimization Approach for the Multi-Depot Heterogeneous Fleet Vehicle Routing Problem With Time Window,” European Journal of Operational Research, vol.176, pp.1478-1507, 2007.

S. Basu, R. S. Gajulapalli, and D. Ghosh, “Implementing Tabu Search to Exploit Sparsity in ATSP Instances,” Indian Institute of Management, W.P,2008.

S. N. Kumar and R. Panneerselvam, ”Development of an efficient Genetic Algorithm for the time dependent VRP with time windows”. American Journal of Operations Research. vol.7. pp.1-25, 2017.

X. Li, P. Tian, and Y. P. Aneja, “An Adaptive Memory Programming Metaheuristic For the Heterogeneous Fixed Fleet Vehicle Routing Problem,” Transport. Res.Pt.E, vol.46, pp.1111–1127, 2010.

Y. Nagata and O. Bräysy, “Edge Assembly-Based Memetic Algorithm for the Capacitated Vehicle Routing Problem,” Networks, vol.54, pp. 205–215, 2009.


Refbacks

  • There are currently no refbacks.