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.15042Resumo
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
Referências
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
Publicado
Como Citar
Edição
Seção
Licença
Autores que publicam nesta revista concordam com os seguintes termos:
Autores mantém os direitos autorais e concedem à revista o direito de primeira publicação, sendo o trabalho simultaneamente licenciado sob a Creative Commons Attribution License o que permite o compartilhamento do trabalho com reconhecimento da autoria do trabalho e publicação inicial nesta revista.
Autores têm autorização para assumir contratos adicionais separadamente, para distribuição não-exclusiva da versão do trabalho publicada nesta revista (ex: publicar em repositório institucional ou como capítulo de livro), com reconhecimento de autoria e publicação inicial nesta revista.
Autores têm permissão e são estimulados a publicar e distribuir seu trabalho online (ex: em repositórios institucionais ou na sua página pessoal) a qualquer ponto antes ou durante o processo editorial, já que isso pode gerar alterações produtivas, bem como aumentar o impacto e a citação do trabalho publicado.
