Tabu Search for the Vehicle Routing Problem with Multiple Trips, Time Windows, and Simultaneous Delivery-Pickup

Authors

  • Suprayogi Suprayogi Institut Teknologi Bandung, Bandung
  • Yusuf Priyandari Universitas Sebelas Maret, Surakarta

:

https://doi.org/10.9744/jti.19.2.75-82

Keywords:

vehicle routing problem, multiple trips, time windows, simultaneous delivery-pickup, tabu search

Abstract

This paper discusses a vehicle routing problem with multiple trips, time windows, and simultaneous delivery-pickup (VRPMTTWSDP). This problem is a variant of the basic vehicle routing problem (VRP) including the following characteristics: multiple trips, time windows, and simultaneous delivery-pickup.  In this paper, a solution approach based on tabu search (TS) is proposed. In the proposed TS, the sequential insertion (SI) algorithm is used to construct an initial solution. A neighbor structure is generated by applying an operator order consisting of eleven operators of relocation, exchange, and crossover operators. A tabu solution code (TSC) method is applied as a tabu restriction mechanism. Computational experiments are carried out to examine the performance of the proposed TS using hypothetical instances. The performance of the proposed TS is compared to the local search (LS) and the genetic algorithm (GA). The comparison shows that the proposed TS is better in terms of the objective function value.

References

Taillard, É. D., Laporte, G. and Gendreau, M., Vehicle Routeing with Multiple Use of Vehicles, Journal of the Operational Research Society, 47 (8), 1996, pp. 1065-1070.

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.

Brandão, J. C. S. and Mercer, A., The Multi-Trip Vehicle Routing Problem, Journal of the Operational Research Society, 49 (8), 1998, pp. 799-805.

Zhao, Q. -H., Wang, S. -Y., Lai, K. K. and Xia, G. -P., A Vehicle Routing Problem with Multiple Use of Vehicles, Advanced Modeling and Optimization, 4 (3), 2002, pp. 31-40.

Petch, R. J. and Salhi, S., A Multi-Phase Constructive Heuristic for the Vehicle Routing Problem With Multiple Trips, Discrete Applied Mathematics, 133 (1-3), 2004, pp. 69-92.

Salhi, S. and R. J. Petch, A GA based heuristic for the vehicle routing problem with multiple trips, Journal of Mathematical Modelling and Algorithms, 6 (4), pp. 591-613, 2007.

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

Potvin, J. -Y. and Rousseau, M., Parallel Route Building Algorithm for the Vehicle Routing and Scheduling Problem with Time Windows, European Journal of Operational Research, 66 (3), 1993, pp. 331-340.

Kolen, A. W. J., Rinnoy-Kan, A. H. G., and Trienekens, H. W. J. M., Vehicle Routing with TimeWindows, Operations Research, 35 (2), 1987, pp. 266-273.

Savelsbergh, M. W. P. , The Vehicle Routing with Time Windows: Minimizing Route Duration, ORSA Journal on Computing, 4 (2), 1992, pp. 146-154.

Potvin, J. -Y., Kervahut, T., Garcia, B. -L. and Rosseau, J. -M., The Vehicle Routing Problem with Time Windows - Part I: Tabu Search, INFORM Journal on Computing, 8 (2), 1996. pp. 158-164.

Potvin, J. -Y. and Bengio, S., The Vehicle Routing Problem with Time Windows Part II: Genetic Search, INFORMS Journal on Computing, 8 (2), 1996, pp. 165-172.

Min, H., The Multiple Vehicle Routing Problem with Simultaneous Delivery and Pick-Up Point, Transportation Research, 23 A (5), 1989, pp. 377-386. .

Dethloff, J., Vehicle Routing and Reverse Logistics: The Vehicle Routing Problem with Simultaneous Delivery And Pick-Up, OR Spektrum, 23, 2001, pp. 79–96.

Dethloff, J., Relation between Vehicle Routing Problems: An Insertion Heuristic for the Vehicle Routing Problem with Simultaneous Delivery and Pick-Up applied to the Vehicle Routing Problem With Backhauls, Journal of the Operational Research Society, 53, 2002, pp. 115-118.

Tang Montané, F. A. and Galvão, R. G., A Tabu Search Algorithm for the Vehicle Routing Problem With Simultaneous Pick-Up and Delivery Service, Computers & Operations Research, 33 (3), 2006, pp. 595–619.

Suprayogi, Algoritma Sequential Insertion untuk Memecahkan Masalah Vehicle Routing Problem dengan Multiple Trips dan Time Windows, Jurnal Teknik dan Manajemen Industri, 23 (3), 2003, pp. 21-36.

Suprayogi 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, Hardianto, A., and Yamato, H., Local Search and Genetic Algorithm Techniques for Solving Vehicle Routing Problem with Multiple Trips and Time Windows, Proceedings of International Conference on Operations and Supply Chain Management, Bali, Indonesia, 2005.

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, 2010, pp. 756–763.

Suprayogi, Hidayat, Y. A. and Imawati, D., Simulated Annealing untuk Pemecahan Masalah Rute dan Jadwal Kendaraan dengan Trip Majemuk dan Jendela Waktu, Proceedings of 6th National Industrial Engineering Conference 2011, Surabaya, Indonesia, 2011.

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

Hernandez, F., Feillet, D., Giroudeau, R. and Naud, O., A New Exact Algorithm to Solve the Multi-Trip Vehicle Routing Problem with Time Windows and Limited Duration, 4QR, 12, 2014, pp. 235-259.

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), 2016, p. 551–559.

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

Mingyong, L. and Erbao, C. An Improved Differential Evolution Algorithm for Vehicle Routing Problem with Simultaneous Pickups and Deliveries and Time Windows, Engineering Applications of Artificial Intelligence, 23 (2), 2010, pp. 188–195.

Fan, J., The Vehicle Routing Problem with Simultaneous Pickup and Delivery based on Customer Satisfaction, Procedia Engineering, 15, 2011, pp. 5284-5289.

Wang, H. -F. and Chen, Y. Y., A Genetic Algorithm for the Simultaneous Delivery and Pickup Problems with Time Windows, Computers & Industrial Engineering, 62 (1), 2012, pp. 84–95.

Liu, R., Xie, X., Augusto V. and Rodriguez, R., Heuristic Algorithms for a Vehicle Routing Problem with Simultaneous Delivery and Pickup and Time Windows in Home Health Care, European Journal of Operational Research, 230 (3), 2013, pp. 475–486.

Avci, M. and Topaloglu, S., An Adaptive Local Search Algorithm for Vehicle Routing Problem with Simultaneous and Mixed Pickups and Deliveries, Computers & Industrial Engineering, 83, 2015, pp. 15–29.

Wang, C., Mu, D., Zhao, F. and Sutherland, J. W., A Parallel Simulated Annealing Method for the Vehicle Routing Problem with Simultaneous Pickup–Delivery and Time Windows, Computers & Industrial Engineering, 83, 2015, pp. 111–122.

Suprayogi and Priyandari, Y., Algoritma Sequential Insertion untuk Memecahkan Vehicle Routing Problem dengan Multiple Trips, Time Windows dan Simultaneous Pickup Delivery, Performa, 7 (1), 2008, pp. 88-96.

Suprayogi dan Priyandari, Y., Vehicle Routing Problem with Multiple Trips, Time Windows, and Simultaneous Delivery and Pickup Services, Proceedings of Asia Pacific Industrial Engineering and Management Systems Conference, Kitakyushu, Japan, 2009.

Suprayogi 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), 2017, pp. 95-104.

Glover, F., Tabu Search - Part I, ORSA Journal on Computing, 1 (3), 1989, pp. 190-206.

Glover, F., Tabu Search - Part II, ORSA Journal on Computing, 2 (1), 1990, pp. 4-32.

Wassan, N. A. and Osman, I. H., Tabu Search Variant for the Mix Fleet Vehicle Routing Problem, Journal of the Operational Research Society, 53 (7), 2002, pp. 768-782.

Downloads

Published

2018-01-08

How to Cite

[1]
S. Suprayogi and Y. Priyandari, “Tabu Search for the Vehicle Routing Problem with Multiple Trips, Time Windows, and Simultaneous Delivery-Pickup”, Jurnal Teknik Industri: Jurnal Keilmuan dan Aplikasi Teknik Industri, vol. 19, no. 2, pp. 75-82, Jan. 2018.

Most read articles by the same author(s)

1 2 > >>