OPTIMIZATION OF MULTI-TRIP VEHICLE ROUTING PROBLEM WITH TIME WINDOWS USING GENETIC ALGORITHM

Yusuf Priyo Anggodo, Amalia Kartika Ariyani, Muhammad Khaerul Ardi, Wayan Firdaus Mahmudy

Abstract


This research studied the application of multitrip vehicle routing problem with time windows (VRPTW) on the problems of the tourist routes in Banyuwangi. The problems of ordinary VRPTW has only one route to the finish line that will be targeted with specific time limits while the multi-trip VRPTW has several tourist routes and one central point as the reference point for determining the route of the tour as well as the deadline for each tour. Genetic algorithm used to solve this problem because it can overcome the problem of combinatorial effectively and efficiently, moreover it can reach solutions globally so that it can produce the optimum solution. Chromosome on the Genetic Algorithm represents the permutation of the overall tour. After decoding there are three chromosome segments created, where each segment represents a visit of tourist attractions in one day. This research provides the optimal result i.e. a solution route with the shortest commute time and a fast computing time so it is very helpful in determining the route of the tourist trips with the closest mileage based on their places to stay (centre point).

Full Text:

PDF

References


BAI, Y., ZHOU, Y., ZHANG, Y. & YANG, M. 2015. Study of multi-vehicle routing problem with time window. International Symposium on Operations Research and its Applications in engineering, technology and management (ISORA), 21-24 August, Louyang, China.

CHUNGYU, R. & XIAOBO, W. 2010. Research on multi-vehicle and multi-depot vehicle routing problem with time windows electronic commerce. IEEE International Conference on Artficial Intelligence and Compputation Intelligence (AICI), 23-24 October, Sanya, China.

GEN, M. & CHENG, R. 2000. Genetic Algorithm and Engineering Optimization. John Wiley & Sons, Inc., New York.

GHOSEIRI, K. & GHANNADPOUR, S. F. 2010. Multi-objective vehicle routing problem with time windows using goal programming and genetic algorithm. Applied Soft Computing, 10, 1096-1107.

HENG, K. K., NGUYEN, Q. C., SIWEI, J., TAN, P. S., GUPTA, A., DA, B. & ONG, Y. S. 2016. Application of route flexibility in data-starved vehicle routing problem with time windows. IEEE Congress on Evolutionary Computation (CEC), 25-29 July, Beijing, China.

HOLLAND, J. H. 1975. Adaptation in natural and artificial systems. University of Michigan Press, ANN Arbor, MI, USA, hhtp://books.google.com/books?id=YE5RAAAAMAAJ.

KARAKATIC, S. & PODGORELEC, V. 2015. A survey of genetic algorithms for solving multi depot vehicle routing problem. Applied Soft Computing, 27, 519-532.

KUMAR, S. N. & PANNEERSELVAM, R. 2015. A time-dependent vehicle routing problem with time windows for e-commerce supplier site pickups using genetic algorithm. Intelligent Information Management, 7, 181-194.

MAHMUDY, W. F., MARIAN, R. M. & LUONG, L. H. 2013. Modeling and optimization of part tye selection and loading problems in flexible manufacturing system using real coded genetic algorithms. International Journal of Electrical, Computer Electronics and Communication Engineering, Vol. 7, No. 4, 251-260.

MAHMUDY, W. F. 2015. ‘Dasar-Dasar Algoritma Evolusi’. Program Teknologi Informasi dan Ilmu Komputer (PTIIK), Universitas Brawijaya. Malang.

MAHMUDY, W. F. 2014. Improved simulated annealing for optimization of vehicle routing problem with time windows (VRPTW). Kursor, vol. 7, no. 3, pp. 109-116.

NOVITASARI, D., CHOLISSODIN, I. & MAHMUDY, W. F. 2016. Hybridizing PSO with SA for optimizing SVR applied to software effort estimation. TELKOMNIKA, Vol. 14, No. 1, 245-253

PIERRE, D. M. & ZAKARIA, N. 2016. Stochastic partially optimized cyclic shift crossover for multi-objective genetic algorithms for the vehicle routing problem with time-windows. Applied Soft Computing, 3838, 14-28.

PRIANDANI, N. D & MAHMUDY, W. F. 2015. ‘Optimasi travelling salesman problem with time windows (TSP-TW) pada penjadwalan paket rute wisata di pulau Bali menggunakan algoritma genetika’. Seminar Teknologi Informasi Indonesia (SESINDO), Institut Teknologi Sepuluh Nopember (ITS), Surabaya, 2-3 Nov., pp. 259-266.

URSANI, Z., DARYL, E., CORNFORTH, D. & STOCKER, R. 2011. Localized genetic algorithm for vehicle routing problem with time windows. Applied Soft Computing, 11, 5375-5390.

WANG, Y., MA, X., XU, M., LIU, Y. & WANG, Y. 2015. Two-echelon logistics distribution region partitioning problem based on hybrid swarm optimization-genetic algorithm. Expert Systems with Applications, 42, 5019-5031




DOI: http://dx.doi.org/10.21776/ub.jeest.2017.003.02.4

Refbacks

  • There are currently no refbacks.


Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 International License.