Comparison Study of Neighborhood Structures in Local Search for Vehicle Routing Problem with Multiple Trips and Time Windows

Authors

  • Saskia Puspa Kenaka Institut Teknologi Bandung
  • Suprayogi Suprayogi Institut Teknologi Bandung

DOI:

https://doi.org/10.9744/jti.23.2.161-170

Keywords:

Vehicle Routing problem, multiple trips, time windows, local search, neighborhood structure

Abstract

This paper deals with the vehicle routing problem with multiple trips and time windows (VRPMTTW). The problem combines two features to the basic vehicle routing problem (VRP): multiple trips and time windows. The basic VRP and its variants fall into hard combinatorial optimization problems. Therefore, many heuristics have been developed to solve large problems. Local search (LS) is one of the heuristics using a neighborhood structure in order to find a better solution. This paper focuses on the comparative study of neighborhood structures applied in LS for the VRPMTTW. Two classes of neighborhood structures are compared: Tour-based and permutation-based neighborhood structures. The tour-based neighborhood structures are the neighborhoods in which the moves are performed on the solution represented by a set of tours. The permutation-based neighborhood structures are the neighborhood structures in which the moves are carried out on the solution represented by a permutation of customers. Comparing the performance of the neighborhood structures uses two responses: (1) relative improvement in the objective function value and (2) computation time. The first response is used to measure effectiveness, while the second is used as efficiency. Based on the computational experiment results, it is generally revealed that the permutation-based neighborhood structures used in LS are more effective than the tour-based neighbourhood structures. However, the permutation-based neighborhood structures are less efficient because they give higher computation times.

Author Biographies

Saskia Puspa Kenaka, Institut Teknologi Bandung

Faculty of Industrial Technology, Industrial System and Techno-Economics Research Group, Institut Teknologi Bandung, Jl. Ganesha 10, Bandung 40116 Indonesia

Suprayogi Suprayogi, Institut Teknologi Bandung

Faculty of Industrial Technology, Industrial System and Techno-Economics Research Group, Institut Teknologi Bandung, Jl. Ganesha 10, Bandung 40116 Indonesia

References

Fleischmann, B. The Vehicle Routing Problem with Multiple Use of the Vehicles, Working paper, Fachbereich Wirtschaftswissenschaften. Universität Hamburg, 1990.

Brandão, J. and Mercer, A., A Tabu Search Algorithm for the Multi-trip Vehicle Routing and Scheduling Problem, European Journal of Operational Research, 100(1), 1997, pp. 180–191.

Suprayogi, S., Algoritma Sequential Insertion untuk Memecahkan Vehicle Routing Problem dengan Multiple Trips dan Time Windows, Jurnal Teknik dan Manajemen Industri, 23(3), 2003, pp. 30–46.

Suprayogi, S., and Imawati, D., Algoritma Sequential Insertion dengan Forward dan Backward Pass untuk Memecahkan Vehicle Routing Problem with Multiple Trips and Time Windows, Jurnal Teknik dan Manajemen Industri, 25(1), 2005, pp. 41–54.

Suprayogi, S., Hardianto, A. and Yamato, H., Local Search and Genetic Algorithm Techniques for Solving Vehicle Routing Problem with Multiple Trips and Time Windows, in Proceedings of the 1st International Conference on Operations and Supply Chain Management, 2005, pp. J17–J24.

Suprayogi, S., Imawati, D., and Hardianto, A., Teknik Local Search untuk Pemecahan Vehicle Routing Problem with Multiple Trips and Time Windows, Jurnal Teknik dan Manajemen Industri, 27(2), 2007, pp. 57–75.

Azi, N., Gendreau, M., and Potvin, J.-Y., An Exact Algorithm for a Vehicle Routing Problem with Time Windows and Multiple Use of Vehicles, European Journal of Operational Research, 202(3), May 2010,pp. 756–763.

Macedo, R., Alves, C., Valério de Carvalho J. M., Clautiaux, F., and Hanafi, S., Solving the Vehicle Routing Problem with Time Windows and Multiple Routes Exactly using a Pseudo-Poly-nomial Model, European Journal of Operational Research, 214(3), Nov 2011, pp. 536–545.

Suprayogi, S., Hidayat, Y. A., and Imawati, D., Simulated Annealing untuk Pemecahan Masalah Rute dan Jadwal Kendaraan dengan Trip Maje-muk dan Jendela Waktu, in Proceedings of the 6th National Industrial Engineering Conference (NIEC-6), 2011, pp. 242–249.

Wang, Z., Liang, W., and Hu, X., A Metaheuristic Based on a Pool of Routes for the Vehicle Routing Problem with Multiple Trips and Time Windows, Journal of Operational Research Society, 65(1), Jan 2014, pp. 37–48.

Hernandez, F., Feillet, D., Giroudeau, R., and Naud, O., Branch-and-price Algorithms for the Solution of the Multi-trip Vehicle Routing Problem with Time Windows, European Journal of Operational Research, 249(2), Mar. 2016, pp. 551–559.

Cattaruzza, D., Absi, N., and Feillet, D., The Multi-trip Vehicle Routing Problem with Time Windows and Release Dates, Transportation Science, 50(2), May 2016, pp. 676–693.

Neira, D. A., Aguayo, M. M., de la Fuente, R., and Klapp, M. A., New Compact Integer Programming Formulations for the Multi-trip Vehicle Routing Problem with Time Windows, Compu¬ters & Industrial Engineering, 144, no. January 2019, p. 106399.

Suprayogi, S., and Mahaputra, M. S., Pemecahan Masalah Rute Kendaraan dengan Trip Majemuk, Jendela Waktu dan Pengantaran-Penjemputan Simultan Menggunakan Algoritma Genetika, J@ti Undip Jurnal Teknik Industri, 12(2), Jul 2017, p. 95.

Suprayogi, S., and Priyandari, Y., Tabu Search for the Vehicle Routing Problem with Multiple Trips, Time Windows, and Simultaneous Delivery-Pickup, Jurnal Teknik Industri, 19(2), 2017, pp. 75–82.

Ong, J. O., and Suprayogi, S., Vehicle Routing Problem with Backhaul, Multiple Trips and Time Window, Jurnal Teknik Industri, 13(1), 2011, pp. 1–10.

Suprayogi, S., Cahyono, R. T., and Lubis A. T., Multi-trip Vehicle Routing Problem with Backhauls and Time Windows, in Proceeding of the 9th International Conference on Operations and Supply Chain Management, 2019.

Solomon, M.M, Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints, Operational Research, 35(2), 1987, pp. 254–265.

Downloads

Published

2021-12-21

Issue

Section

Articles