EUVIMEDAtrasti EUVIMED
Crossref

A flow‐based model for the multivehicle covering tour problem with route balancing

Cristina Teruko Ota, Diego Jacinto Fiorotto, Carla Taviane Lucke da Silva Ghidini, Washington Alves de Oliveira

International Transactions in Operational Research · 2024-09 · 31 (5) · 2930-2955

DOI: 10.1111/itor.13399 ↗

At a glance

Journal article in International Transactions in Operational Research, published online on 2023-11-06. Written by Cristina Teruko Ota and 3 co-authors. Cited 8 times so far (Crossref); 55 references. Funded by: Fundação de Amparo à Pesquisa do Estado de São Paulo, Fundo de Apoio ao Ensino, à Pesquisa e Extensão, Universidade Estadual de Campinas, Conselho Nacional de Desenvolvimento Científico e Tecnológico.

SantraukaBibliografiniai duomenysCiteRelated studies

Abstract (original language)

This paper introduces a new flow‐based mathematical formulation for the multivehicle covering tour problem. This problem determines a set of vehicle routes for the available fleet; therefore, the total distance traveled is minimal. In the proposed mathematical formulation, each vertex represents a location of interest, and these vertices belong to three sets: vertices that can be visited; vertices that must be visited; and vertices that must be covered, in the sense that each vertex must be close to a visited vertex in a route. The proposed formulation aims to find solutions with balanced routes (all the routes with an equal or similar number of visited nodes) and extends the previous formulations proposed in the literature by considering a two‐index vehicle flow formulation with a decision variable to find the balanced routes. It constitutes an NP‐hard integer programming problem based on a two‐commodity flow model, which is solved by applying the branch‐and‐cut and biased random‐key genetic algorithms. This paper reports computational results for some adapted instances from TSPLIB to evaluate the efficiency of the proposed model. The computational results validate the branch‐and‐cut and genetic algorithms, whereby the latter performs better in large‐size instances with reduced computational runtime. Finally, the used approaches obtained competitive solutions compared to the literature.

Funding

  • Fundação de Amparo à Pesquisa do Estado de São Paulo
  • Fundo de Apoio ao Ensino, à Pesquisa e Extensão, Universidade Estadual de Campinas
  • Conselho Nacional de Desenvolvimento Científico e Tecnológico

Cite

APA

Ota, C. T., Fiorotto, D. J., Ghidini, C. T. L. D. S., & Oliveira, W. A. D. (2024). A flow‐based model for the multivehicle covering tour problem with route balancing. International Transactions in Operational Research, 31(5), 2930-2955. https://doi.org/10.1111/itor.13399

Vancouver

Ota CT, Fiorotto DJ, Ghidini CTLDS, Oliveira WAD. A flow‐based model for the multivehicle covering tour problem with route balancing. International Transactions in Operational Research. 2024;31(5):2930-2955. doi:10.1111/itor.13399

BibTeX
@article{Ota2024,
  author = {Ota, Cristina Teruko and Fiorotto, Diego Jacinto and Ghidini, Carla Taviane Lucke da Silva and Oliveira, Washington Alves de},
  title = {A flow‐based model for the multivehicle covering tour problem with route balancing},
  journal = {International Transactions in Operational Research},
  year = {2024},
  volume = {31},
  number = {5},
  pages = {2930--2955},
  doi = {10.1111/itor.13399}
}
Start for free →