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

Júnior César Bonafim, Pedro Munari

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.


Texto completo:

PDF

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.




DOI: https://doi.org/10.5540/03.2021.008.01.0413

Apontamentos

  • Não há apontamentos.


SBMAC - Sociedade de Matemática Aplicada e Computacional
Edifício Medical Center - Rua Maestro João Seppe, nº. 900, 16º. andar - Sala 163 | São Carlos/SP - CEP: 13561-120
 


Normas para publicação | Contato