Formulação p-step para o problema de caminho mínimo com restrições de recursos

Autores

  • Júnior César Bonafim Universidade Federal de São Carlos
  • Pedro Munari Universidade Federal de São Carlos

DOI:

https://doi.org/10.5540/03.2021.008.01.0413

Resumo

Neste  artigo,  aborda-se  o  problema  de  caminho  elementar  com  restrições  de  recursos (RCESPP, do inglês resource-constrained elementary shortest path problem) que, al ́em de formular diversas situações reais importantes, ocorre comumente como subproblema na resolução de outros problemas clássicos de otimiza ̧c ̃ao combinatória.  Por exemplo, em formulações do roteamento de veículos cujas variáveis de decis ̃ao se relacionam a rotas factíveis, comumente resolvidos pela técnica de gera ̧c ̃ao de colunas, tais rotas s ̃ao obtidas pela resolução do RCESPP. Recentemente, foram introduzidas novas formulações para problemas de roteamento de veículos com base em variáveis que estão relacionadas a caminhos parciais de comprimento p, chamados p-steps.  Tais formulações têm mostrado limitantes mais fortes em relação `as formulações tradicionais com variáveis baseadas em um único arco e, portanto, tem o potencial de beneficiar métodos de solução que dependem dessa característica.  O objetivo deste trabalho é propor formulações p-step para a modelagem do RCESPP, dado que ainda n ̃ao foram usadas nesse contexto, explorando propriedades e características especiais do problema.  Experimentos computacionais com instâncias da literatura foram realizados de modo a comparar o desempenho das formulações propostas em relação à formulação tradicional, considerando diferentes valores dep.

Downloads

Não há dados estatísticos.

Referências

Boland, N., Dethridge, J., Dumitrescu, I. Accelerated label setting algorithms for the elemen-tary resource constrained shortest path problem.Operations Research Letters, 34:58-68, 2006.DOI: 10.1016/j.orl.2004.11.011.

Da, J., Zheng, L., Tang, X. A polyhedral study of the elementary shortest path problemwith resource constraints.Lecture Notes in Computer Science, 10572 LNCS:79-93, 2017. DOI:10.1007/978-3-319-68496-36.

Dollevoet, T., Munari, P., Spliet, R. A p-step Formulation for the Capacitated Vehicle RoutingProblem. n. 2014, 2020.

Dror, M. Note on the Complexity of the Shortest Path Models for Column Generation inVRPTW.Operations Research, 42:977-978, 1994. DOI: 10.1287/opre.42.5.977.

Feillet, D. et al. An exact algorithm for the elementary shortest path problem with resourceconstraints: Application to some vehicle routing problems.Networks, 44:216-229, 2004. DOI:10.1002/net.20033.

Jepsen, M., Petersen, B., Spoorendonk, S. A branch-and-cut algorithm for the elementaryshortest path problem with a capacity constraint. Department of Computer Science, Universityof Copenhagen, n. 08/01, 2008.

Munari, P., Dollevoet, T., Spliet, R. A generalized formulation for vehicle routing problems.n. 1, p. 1-19, 2017.

Pugliese, L. D. P., Guerriero, F. A survey of resource constrained shortest path problems:Exact solution approaches.Networks, 62:183-200, 2013. DOI: 10.1002/net.21511.

Righini, G., Salani, M. Symmetry helps: Bounded bi-directional dynamic programming for theelementary shortest path problem with resource constraints.Discrete Optimization, 3:255-273,2006. DOI: 10.1016/j.disopt.2006.05.007.

Righini, G., Salani, M. New dynamic programming algorithms for the resource constrainedelementary shortest path problem.Networks, 51:155-170, 2008. DOI: 10.1002/net.20212.

Solomon, M. M. Vehicle routing and scheduling with time window constraints: Models andAlgorithms. Tese de Doutorado, University of Pennsylvania, 1983.

Toth, P., Vigo, D.Vehicle routing: problems, methods, and applications. 3a edi ̧c ̃ao. Societyfor Industrial and Applied Mathematics, Philadelphia, 2014.

Downloads

Publicado

2021-12-20

Edição

Seção

Trabalhos Completos