Abstract
The one-commodity pickup-and-delivery travelling salesman problem is a well known combinatorial optimization problem applied in numerous practical situations. It consists of a set of customers dispersed on a geographical area and a vehicle with a predefined capacity that must not be exceeded. The vehicle starts from a depot, and should visit each customer only once then end at at the depot. The objective is to minimize the total length of the traveled path way. As the 1-PDTSP is known to be NP-hard, meta-heuristics perform well when generating solutions in a reasonable computation time. In this paper, we propose a hybrid-meta-heuristic Iterated Local search with Variable Neighborhood Descent (ILS-VND). In order to demonstrate the performance of the proposed approach in term of solution quality, we apply it on benchmark instances. Our approach is also applied in a real case on the city of Jendouba in the north west of Tunisia. The results are then highlighted in a cartographic format using Google Maps.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Hernandez-Perez, H., Salazar-Gonzalez, J.J.: Heuristics for the onecommodity pickup-and-delivery travelling salesman problem. Transportation Science 38, 245–255 (2004)
Zhao, F., Li, S., Sun, J., Mei, D.: Genetic algorithm for the one-commodity pickup-and-delivery travelling salesman problem. Computers & Industrial Engineering 56, 1642–1648 (2009)
Puchinger, J., Raidl, G.: Bringing order into the neighborhoods: relaxation guided variable neighborhood search. J. of Heuristics 14, 457–472 (2008)
Hernandez-Perez, H., Rodriguez-Martin, I., Salazar-Gonzalez, J.J.: A hybrid GRASP/VND heuristic for the one-commodity pickup-and-delivery travelling salesman problem. Computers & Operations Research 36, 1639–1645 (2009)
Mladenovic, N., Urosevic, D., Hanafi, S., Ilic, A.: A general variable neighborhood search for the one-commodity pickup-and-delivery travelling salesman problem. European Journal of Operational Research 220, 270–285 (2012)
Chalasani, P., Motwani, R.: Approximating capacitated routing and delivery problems. SIAM Journal on Computing 28, 2133–2149 (1999)
Parragh, S.N., Doerner, K.F., Hartl, R.F.: A survey on pickup and delivery problems. Part I: Transportation between customers and depot. Journal fur Betriebswirtschaft 58, 21–51 (2008)
Parragh, S.N., Doerner, K.F., Hartl, R.F.: A survey on pickup and delivery problems. Part II: Transportation between pickup and delivery locations. Journal fur Betriebswirtschaft 58, 81–117 (2008)
Faiz, S., Krichen, S., Inoubli, W.: A DSS based on GIS and Tabu search for solving the CVRP: The Tunisian case. The Egyptian Journal of Remote Sensing and Space Sciences 17, 105–110 (2014)
Geiger, M.J.: On heuristic search for the single machine total weighted tardiness problem- some theoretical insights and their empirical verification. EJOR 207(3), 1235–1243 (2010)
Talbi, E.-G.: Metaheuristics: From Design to Implementation
Lourenco, H.R., Martin, O., Stutzle, T.: Iterated Local Search, pp. 321–353. Kluwer Academic Publishers, Norwell (2002)
den Besten, M., Stützle, T., Dorigo, M.: Design of iterated local search algorithms: An example application to the single machine total weighted tardiness problem. In: Boers, E.J.W., et al. (eds.) EvoIASP 2001, EvoWorkshops 2001, EvoFlight 2001, EvoSTIM 2001, EvoCOP 2001, and EvoLearn 2001. LNCS, vol. 2037, pp. 441–452. Springer, Heidelberg (2001)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Yahyaoui, H., Krichen, S. (2015). A DSS Based on Hybrid Meta-Heuristic ILS-VND for Solving the 1-PDTSP. In: Rutkowski, L., Korytkowski, M., Scherer, R., Tadeusiewicz, R., Zadeh, L., Zurada, J. (eds) Artificial Intelligence and Soft Computing. ICAISC 2015. Lecture Notes in Computer Science(), vol 9120. Springer, Cham. https://doi.org/10.1007/978-3-319-19369-4_70
Download citation
DOI: https://doi.org/10.1007/978-3-319-19369-4_70
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-19368-7
Online ISBN: 978-3-319-19369-4
eBook Packages: Computer ScienceComputer Science (R0)