SOLUÇÃO DO PROBLEMA DE ROTEAMENTO DE VEÍCULOS COM JANELA DE TEMPO VIA ITERATED GREEDY SEARCH
DOI:
https://doi.org/10.26512/ripe.v2i9.15042Abstract
Neste artigo ´e tratado o Problema de Roteamento de Veículos com Janela de Tempo. O objetivo é atender um conjunto de clientes geograficamente distribuídos com um número de veículos limitado. É considerado um único depósito, onde os veículos partem e retornam após visitar todos os clientes de sua respectiva rota. Há uma janela de tempo associada ao depósito, que indica seu peróodo de funcionamento, além de uma janela de tempo pertencente a cada cliente, que indica o intervalo de tempo para iniciar o atendimento. Todos os veículos possuem a mesma capacidade de carga e há uma demanda correspondente a cada cliente. O algoritmo proposto combina a meta-heurística Greedy Randomized Adaptive Search Procedure (GRASP) e a Push-Forward Insertion Heuristic (PFIH) para gerar a solução inicial e é aplicado uma busca local para refinar a solução gerada através da meta-heurística Variable Neighborhood Descent (VND). Posteriormente, esta solução é refinada pela meta-heurística Iterated Greedy Search (IGS) de forma iterativa. A análise de resultados consiste em comparar as 56 instâncias propostas por Solomon (1987) com os melhores resultados da literatura.
Keywords: Problema de Roteamento de Veículos com Janela de Tempo, GRASP, IGS, VND
Downloads
References
Blum, C., Puchinger, J., Raidl, G. R. and Roli, A. (2011). Hybrid metaheuristics in combinatorial optimization: A survey, Applied Soft Computing 11(6): 4135”“4151.
Chebbi, Olfa; Chaouachi, J. (2015). Multi-objective iterated greedy variable neighborhood search algorithm for solving a full-load automated guided vehicle routing problem with battery constraints, Electronic Notes in Discrete Mathematics 47.
Dantzig, G. B.; Ramser, J. H. (1959). The truck dispatching problem, Management Science 6.
Deng, Y., Xiang, J. and Ou, Z. (2013). Improvement of genetic algorithm for vehicle routing problems with time windows, Intelligent System Design and Engineering Applications (ISDEA), 2013 Third International Conference on, IEEE, pp. 866”“869.
Feo, T. and Resende, M. (1995). Greedy randomized adaptive search procedures, Journal of Global Optimization 6: 109”“133.
Hifi, M. and Wu, L. (2014). A hybrid metaheuristic for the vehicle routing problem with time windows, Control, Decision and Information Technologies (CoDIT), 2014 International Conference on, IEEE, pp. 188”“194.
Karabulut, Korhan; Fatih Tasgetiren, M. (2014). A variable iterated greedy algorithm for the traveling salesman problem with time windows, Information Sciences .
Mao, Y. and Deng, Y. (2010). Solving vehicle routing problem with time windows with hybrid evolutionary algorithm, 2010 Second WRI Global Congress on Intelligent Systems, Vol. 1, IEEE, pp. 335”“339.
Nucamendi, S., Cardona-Valdes, Y. and Angel-Bello Acosta, F. (2015). Minimizing customer’s waiting time in a vehicle routing problem with unit demands, Journal of Computer and Systems Sciences International 54(6): 866”“881.
Pierre, D. M. and Zakaria, N. (2014). Partially optimized cyclic shift crossover for multiobjective genetic algorithms for the multi-objective vehicle routing problem with timewindows,
Computational Intelligence in Multi-Criteria Decision-Making (MCDM), 2014
IEEE Symposium on, IEEE, pp. 106”“115.
Rodriguez, F. J., Lozano, M., Blum, C. and Garc´Ä±a-Mart´Ä±nez, C. (2013). An iterated greedy algorithm for the large-scale unrelated parallel machines scheduling problem, Computers & Operations Research 40.
Ruiz, L. F.-P. R. (2010). Iterated greedy local search methods for unrelated parallel machine scheduling, European Journal of Operational Research 207.
Sabar, N. R., Zhang, X. J. and Song, A. (2015). A math-hyper-heuristic approach for largescale vehicle routing problems with time windows, 2015 IEEE Congress on Evolutionary Computation (CEC), IEEE, pp. 830”“837.
Solomon,M. M. (1987). Algorithms for the vehicle routing and scheduling problems with time window constraints, Operations Research 35.
Sripriya, J., Ramalingam, A. and Rajeswari, K. (2015). A hybrid genetic algorithm for vehicle routing problem with time windows, Innovations in Information, Embedded and Communication Systems (ICIIECS), 2015 International Conference on, IEEE, pp. 1”“4.
St¨utzle, R. R. T. (2007). A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem, European Journal of Operational Research 177.
St¨utzle, R. R. T. (2008). An iterated greedy heuristic for the sequence dependent setup times flowshop problem with makespan and weighted tardiness objectives, European Journal of Operational Research 187.
Tasgetiren, M. F., Buyukdagli, O., Kızılay, D. and Karabulut, K. (2013). A populated iterated greedy algorithm with inver-over operator for traveling salesman problem, in B. K. Panigrahi,
P. N. Suganthan, S. Das and S. S. Dash (eds), Proceedings of the 4th International Conference on Swarm, Evolutionary, and Memetic Computing (SEMCCO 2013), Chennai, India, December 19-21, 2013, Springer International Publishing, pp. 1”“12.
Toth, P. and Vigo, D. (1998). Exact solution of the vehicle routing problem, Fleet management and logistics, Springer, pp. 1”“31.
Wang, C.-B. C. K.-P. (2009). Solving a vehicle routing problem with time windows by a decomposition technique and a genetic algorithm, Expert Systems with Applications 36.
Yang, Jun; Sun, H. (2015). Battery swap station location-routing problem with capacitated electric vehicles, Computers & Operations Research 55: 217”“232.
Yu, V. F. and Lin, S.-W. (2015). Iterated greedy heuristic for the time-dependent prize-collecting arc routing problem, Computers & Industrial Engineering 90: 54 ”“ 66.
Downloads
Published
How to Cite
Issue
Section
License
Given the public access policy of the journal, the use of the published texts is free, with the obligation of recognizing the original authorship and the first publication in this journal. The authors of the published contributions are entirely and exclusively responsible for their contents.
1. The authors authorize the publication of the article in this journal.
2. The authors guarantee that the contribution is original, and take full responsibility for its content in case of impugnation by third parties.
3. The authors guarantee that the contribution is not under evaluation in another journal.
4. The authors keep the copyright and convey to the journal the right of first publication, the work being licensed under a Creative Commons Attribution License-BY.
5. The authors are allowed and stimulated to publicize and distribute their work on-line after the publication in the journal.
6. The authors of the approved works authorize the journal to distribute their content, after publication, for reproduction in content indexes, virtual libraries and similars.
7. The editors reserve the right to make adjustments to the text and to adequate the article to the editorial rules of the journal.
