Saturday , April 27 2024

 Comparing Two Heuristic Local Search Algorithms for a
Complex Routing Problem

Pablo CABRERA-GUERRERO1*, Andrés MOLTEDO-PERFETTI2, Enrique CABRERA3, Fernando PAREDES4

1 Pontificia Universidad Católica de Valparaíso,
Av. Brasil 2241, Valparaíso, 2362807, Chile
pablo.cabrera@pucv.cl (* Corresponding author)
2 Escuela de Psicología, Universidad Santo Tomás,
Los Limonares 190, Viña del Mar, 2561694, Chile
andresmoltedo@santotomas.cl

3 CINFAV, Universidad de Valparaíso,
Blanco 951, Valparaíso, 2362905, Chile
enrique.cabrera@uv.cl
4 Escuela de Ingeniería Industrial, Universidad Diego Portales,
Manuel Rodríguez Sur 415, Santiago, 8370109, Chile
fernando.paredes@udp.clanjing

Abstract: Vehicle routing problems (VRP) have been widely studied in literature. Heuristics as well as exact algorithms have been applied to solve this kind of problems. In this study we approximately solve the VRP with simultaneous pickup and delivery and time windows by means of two well-known heuristics namely Tabu Search and Simulated Annealing. We compare the obtained results and then propose a restoration technique that allows both Tabu Search and Simulated Annealing to better explore the solution space. Results show that the proposed restoration technique allows both heuristic algorithms to obtain better results.

Keywords: Tabu Search, Simulated Annealing, Reverse Logistic, Restoration Techniques.

>>Full text
CITE THIS PAPER AS:
Pablo CABRERA-GUERRERO, Andrés MOLTEDO-PERFETTI, Enrique CABRERA, Fernando PAREDES, Comparing Two Heuristic Local Search Algorithms for a Complex Routing Problem, Studies in Informatics and Control, ISSN 1220-1766, vol. 25(4), pp. 411-420, 2016. https://doi.org/10.24846/v25i4y201602

  1. Introduction

Heuristic algorithms have been applied on a variety of problems in operations research and logistics for more than 50 years now. They have been shown to be very effective in dealing with complex problems that cannot be solved to optimality by traditional techniques such as mathematical programming. This is because mathematical programming methods often fail as the optimisation problem gets larger (i.e. more decision variables are involved).

Two well-known heuristic local search algorithms that have been applied on this kind of complex optimisation problems are Tabu Search [15] and Simulated Annealing [20, 21, 27]. In this paper we study the performance of these two heuristic algorithms when solving a complex problem arising in logistics called vehicle routing problem (VRP) with simultaneous pickup and delivery and time windows (VRPSPDTW).

Tabu Search algorithm has been used to approximately solve a range of combinatorial optimisation problems [5, 10, 23]. It has been shown to be a very simple, yet effective, method to approximately solve large and complex combinatorial optimisation problems such as the one we address in this paper. Just as Tabu Search, Simulated Annealing has also been considered to approximately solve a variety of optimisation problems (see for instance [3, 17, 24, 36]).

In this paper we implement both Tabu Search and Simulated Annealing algorithms and apply them on the VRPSPDTW. We then compare the results obtained by each technique.

One difficult we face when solving routing problems by means of local search algorithms is that neighbours of the current solution are often not feasible. Thus, we need to restore such neighbours so they become feasible. In this paper we propose a generic restoration strategy in the aim of making both local search algorithms to perform more efficiently. It is important to note that the restoration strategy we propose in this paper is directly applied on the local search algorithms. Thus, it can be seen as a generic strategy that can be included in any local search algorithm other than Tabu Search and Simulated Annealing.

This paper is organised as follows. In next section both Tabu Search and Simulated Annealing algorithms are described and their main features are highlighted. In Section 3 the VRPSPDTW problem we address in this paper is introduced. The mathematical formulation for this problem is presented at the end of this section. In Section 4 we introduce the restoration technique that is used within both heuristic algorithms. In Section 5 computational experiments performed in this paper are presented. In this section we discuss how the restoration technique helps both local search algorithms to better explore the solution space. Finally, in Section 6 some conclusions are drawn and future work is outlined.

REFERENCES

  1. AI, T. J., V. A. KACHITVICHYANUKUL, Particle Swarm Optimization for The Vehicle Routing Problem with Simultaneous Pickup and Delivery, Computers & Operations Research, vol. 36(5), 2009, pp. 1693-1702.
  2. ANGELELLI, E., R. MANSINI, The Vehicle Routing Problem with Time Windows and Simultaneous Pick-up and Delivery. Quantitative Approaches to Distribution Logistics and Supply Chain Management, Lecture Notes in Economics and Mathematical Systems, vol. 519, 2002, pp. 249-267.
  3. AREIBI, S., G. GREWAL, D. BANERJI, P. DU, Hierarchical FPGA Placement. Canadian Journal of Electrical and Computer Engineering, vol. 32(1), 2007, pp. 53-64.
  4. AVCI, M., S. TOPALOGLU, An Adaptive Local Search Algorithm for Vehicle Routing Problem with Simultaneous and Mixed Pickups and Deliveries. Computers & Industrial Engineering, vol. 83(C), 2015, pp. 15-29.
  5. BARANY, M., Z. TUZA, Circular Coloring of Graphs via Linear Programming and Tabu Search. Central European Journal of Operations Research, vol. 23(4), 2015, pp. 833-848
  6. BRAEKERS, K., K. RAMAEKERSA, I. V. NIEUWENHUYSEC, The Vehicle Routing Problem: State of the Art Classification and Review. Computers & Industrial Engineering, to be published.
  7. CABRERA, G., S. Roncagliolo, J. P. RIQUELME, C. CUBILLOS, R. SOTO, A Hybrid Particle Swarm Optimization-Simulated Annealing Algorithm for The Probabilistic Travelling Salesman Problem, Studies in Informatics and Control, vol. 21, 2012, pp. 49-58.
  8. CAO, E., M. LAI, An Improved Differential Evolution Algorithm for the Vehicle Routing Problem with Simultaneous Delivery and Pick-up Service, Proceedings of the 3rd International Conference on Natural Computation (ICNC), 2007, pp. 436-440.
  9. CHEN, J. F., T. H. WU, Vehicle Routing Problem with Simultaneous Deliveries and Pickups. Journal of the Operational Research Society, vol. 57, (5), 2006, pp 579-587.
  10. COSSI, A. M., J. R. S. MANTOVANI, Integrated Planning of Electric Power Distribution Networks. IEEE Latin American Transactions, vol 7(2), 2009, 203-210.
  11. DANTZIG, G. B., J. H. RAMSER, The Truck Dispatching Problem. Management Science, vol. 6(1), 1959, pp. 80-91.
  12. DETHLOFF, J., Vehicle Routing and Reverse Logistics: The Vehicle Routing Problem with Simultaneous Delivery and Pick-Up. OR-Spektrum, vol. 23(1), 2001, pp. 79-96.
  1. GAJPAL, Y., P. ABAD, An Ant Colony System (ACS) for Vehicle Routing Problem with Simultaneous Delivery and Pickup, Computers & Operations Research, vol. 36(1), 2009, pp. 3215-3223.
  2. GAN, X., Y. WANG, S. LI, B. NIU, Vehicle Routing Problem with Time Windows and Simultaneous Delivery and Pick-Up Service Based on MCPSO. Mathematical Problems in Engineering, vol. 2012, Article ID 104279, 2012, pp. 1-11. doi:10.1155/2012/104279.
  3. GLOVER, F., Artificial Intelligence, Heuristic Frameworks and Tabu Search. Managerial and Decision Economics, vol. 11(1), 1990, pp. 365-375.
  4. GOKSAL, F. P., I. Karaoglan, F. ALTIPARMAK, A Hybrid Discrete Particle Swarm Optimization for Vehicle Routing Problem with Simultaneous Pickup and Delivery. Computer and Industrial Engineering, vol. 65(1), 2013, pp. 39-53. doi: 10.1016/j.cie.2012.01.005.
  5. HIERMANN, G., M. PRANDSTETTER A. RENDL, J. PUCHINGER, G. R. RAIDL, Metaheuristics for Solving A Multimodal Home-Healthcare Scheduling Problem. Central European Journal of Operations Research, vol. 23(1), 2015, pp. 89-113.
  6. JOHNSON, F., J. VEGA, G. CABRERA, E. CABRERA, Ant Colony System for a Problem in Reverse Logistic, Studies in Informatics and Control, vol. 24(2), 2015, pp. 133-140.
  7. KASSEM, S., M. CHEN, Solving Reverse Logistics Vehicle Routing Problems WITH Time Windows. The International Journal of Advanced Manufacturing Technology, vol. 68(1), 2013, pp. 57–68, doi: 10.1007/s00170-012-4708-9.
  8. KIRKPATRICK, S., Optimization by Simulated Annealing: Quantitative Studies. Journal of Statistical Physics, vol. 34, no. 5-6, 1984, pp. 975-986.
  9. KIRKPATRICK, S., C. D. GELATT, M. P. VECCHI, Optimization by Simulated Annealing. Science, vol. 220, no. 4598, 1983, pp. 671-680.
  10. KOLEN, A. W. J., A. H. G. RINNOOY KAN, H. W. J. M. TRIENEKENS, Vehicle Routing with Time Windows. Operations Research, vol. 35(2), 1987, pp. 266-273.
  11. LAGOS, C., B. CRAWFORD, E. CABRERA, R. SOTO, J. M. RUBIO, F. PAREDES, Combining Tabu Search and Genetic Algorithms to Solve the Capacitated Multicommodity Network Flow Problem. Studies in Informatics and Control, vol. 23(3), 2014,pp. 265-276.
  12. LAGOS, C., B. CRAWFORD, R. SOTO, E. CABRERA, J. VEGA, F. JOHNSON, F. PAREDES, Improving Tabu Search Performance by Means of Automatic Parameter Tuning, Canadian Journal of Electrical and Computer Engineering, vol. 39(1), 2016, pp. 51-58.
  13. LIU, R., X. XIE, V. AUGUSTO, C. RODRIGUEZ, Heuristic Algorithms for a Vehicle Routing Problem with Simultaneous Delivery and Pickup and Time Windows in Home Healthcare. European Journal of Operational Research, vol. 230(3), 2013, pp. 475-486.
  14. LUNDY, M., A. MEES, Convergence of an Annealing Algorithm. Mathematical Programming, vol. 34(1), 1986, pp. 111-124.
  15. METROPOLIS, N., A. W. ROSENBLUTH, M. N. ROSENBLUTH, A. H. TELLER, E. TELLER, Equation of State Calculations by Fast Computing Machines. The Journal of Chemical Physics vol. 21(6), 1953, pp. 1087-1092.
  16. MIN, H. The Multiple Vehicle Routing Problem with Simultaneous Delivery and Pick-Up Points. Transportation Research Part A General 23(5), 1989, pp. 377-386.
  17. MLADENOVIĆ, N., P. HANSEN, Variable Neighborhood Search. Computers & Operations Research, vol. 24(11), 1997, pp. 1097-1100.
  18. NAGY, G., S. SALHI, Heuristic Algorithms For Single And Multiple Depot Vehicle Routing Problems With Pickups And Deliveries. European Journal of Operational Research, vol. 162(1), 2005, pp. 126-141.
  19. RIECK, J., J. ZIMMERMANN, Exact Solutions to the Symmetric and Asymmetric Vehicle Routing Problem with Simultaneous Delivery and Pick-Up. Business Research, vol. 6(1), 2013, pp. 77-92.
  20. RODRIGUEZ, D. A., A. C. OLIVERA, N. B. BRIGNOLE, Vehicle Routing for Public Transport with Adapted Simulated Annealing. Latin American Applied Research, vol. 44(3), 2014, 247-252.
  21. SOLOMON, M. M., Algorithms for the Vehicle Routing Problem with Time Windows. Transportation Science, vol. 29(2), 1995, pp. 156-166.
  22. SUBRAMANIAN, A., L. S. OCHI, New Lower Bounds for the Vehicle Routing Problem with Simultaneous Pickup and Delivery, Technical Report – RT 01/10, Universidade Federal Fluminense, Niteri-RJ, Brazil, 2010.
  23. TANG, F. A., R. D. GALVAO, A Tabu Search Algorithm for the Vehicle Routing Problem with Simultaneous Pick-Up and Delivery Service. Computers & Operations Research, vol. 33, 2006, pp. 595-619
  24. TOADER, F. A., A Hybrid Algorithm for Job Shop Scheduling Problem. Studies in Informatics and Control, vol. 24(2), 2015, pp. 171-180.
  25. WANG, C., F. ZHAO, D. MU, J. W. SUTHERLAND, Simulated Annealing for a Vehicle Routing Problem with Simultaneous Pickup-Delivery and Time Windows. Advances in Production Management Systems. Sustainable Production and Service Supply Chains, vol. 415(2), 2013, pp 170-177.
  26. WILHELM, M. R., T. L. WARD, Solving Quadratic Assignment Problems by Simulated Annealing, IIE Transactions, vol. 19(1), 1987, pp. 107-119.
  27. ZACHARIADIS, E., C. D. TARANTILIS, C. KIRANOUDIS, A Hybrid Metaheuristic Algorithm for the Vehicle Routing Problem with Simultaneous Delivery and Pick-Up Service. Expert Systems with Applications, vol. 36(2), 2009, pp. 1070-1081.
  28. ZHU, N., C. SHAO, Vehicle Routing Problem with Simultaneous Delivery and Pick-up Based on the Improved Genetic Algorithm, in Proc. of the 4th International Conference on Genetic and Evolutionary Computing (ICGEC), Shenzhen, China, 2010, pp. 312-316.

Designed by | ICI Bucharest
© Copyright 2024, All Rights Reserved