Um estudo de impactos do roteamento dinâmico de veículos em atividades de prestação de serviço
A study of impacts of dynamic vehicle routing on services production activities
Pureza, Vitoria; Lazarin, Daniel França
http://dx.doi.org/10.1590/S0103-65132010005000042
Prod, vol.20, n4, p.589-600, 2010
Resumo
Neste trabalho, é analisado o impacto da utilização de métodos de roteamento dinâmico de veículos em ambientes de prestação de serviço, onde a satisfação dos prazos de atendimento do cliente é prioritária. Com esse objetivo, é proposta uma heurística construtiva/desconstrutiva, que, quando acionada por um módulo de despacho de veículos, elabora rotas em tempo real. O impacto da aplicação da heurística é medido frente a outros métodos, utilizando-se conjuntos de instâncias geradas aleatoriamente, com base em dados fornecidos por uma empresa do setor de bebidas do interior do Estado de São Paulo. Os resultados indicam benefícios substanciais em termos de nível de serviço oferecido.
Palavras-chave
Roteamento de veículos dinâmico. Otimização combinatória. Métodos heurísticos.
Abstract
In this paper we evaluate the impacts resulting from the incorporation of dynamic vehicle routing and scheduling in service production systems where due dates for service are a priority issue. We propose a constructive/deconstructive heuristic, which is activated by a dispatcher module in order to obtain routes in real time. The relative impact of the heuristic application to other methods is analyzed by means of sets of randomly generated instances, based on the data supplied by a drinks company in São Paulo State. The results indicate significant gains in terms of service level.
Keywords
Dynamic vehicle routing. Combinatorial optimization. Heuristics.
References
BELL, W. J. et al. Improving the distribution of industrial gases with an on- line computerized routing and scheduling optimizer. Interfaces, v. 13, n. 6, p. 4- 23, 1983.
BERTSIMAS, D. J.; JAILLET, P.; ODONI, A. A priori optimization. Operations Research, v. 38, n. 6, p. 1019- 1033, 1990.
BERTSIMAS, D. J.; van RYZIN, G. A stochastic and dynamic vehicle routing problem in the euclidean plane. Operations Research, v. 39, n. 4, p. 601- 614, 1991.
BERTSIMAS, D. J.; SIMCHI- LEVI, D. A new generation of vehicle routing research: robust algorithms, addressing uncertainty. Operations Research, v. 44, n. 2, p. 286- 304, 1996.
BODIN, L. D. et al. Routing and scheduling of vehicle and crews: the state of the art. Computers and Operations Research, v. 10, n. 2, p. 63- 211, 1983.
BRANKE, J. et al. Waiting strategies for dynamic vehicle routing. Transportation Science, v. 39, n. 3, p. 298- 312, 2005.
BROWN, G. G. et al. Real- Time, Wide Area Dispatch of Mobil Tank Trucks. Interfaces, v. 17, n. 1, p. 107- 120, 1987.
CRAINIC, T. G.; DEJAX, P.; GENDREAU, M. Modeling the container fleet management problem using a stochastic programming approach. Operational Research 90, v. 18, p. 473- 486, 1991.
FLEISCHMANN, B.; GNUTZMANN, S.; SANDVOß, E. Dynamic vehicle routing based on online traffic information. Transportation Science, v. 38, n. 4, p. 420- 433, 2004.
GENDREAU, M. et al. Neighborhood search heuristics for a dynamic vehicle dispatching problem with pick- ups and deliveries. Transportation Research Part C, v. 14, n. 3, p. 157- 174, 2006.
GENDREAU, M. et al. Parallel tabu search for real- time vehicle routing and dispatching. Transportation Science, v. 33, n. 4, p. 381- 390, 1999.
GENDREAU, M.; LAPORTE, G.; SÉGUIN, R. Stochastic Vehicle Routing. European Journal of Operational Research, v. 88, p. 3- 12, 1996.
GENDREAU, M.; LAPORTE, G.; SEMET, F. A dynamic model and parallel tabu search heuristic for real- time ambulance relocation. Parallel Computing, v. 27, n. 12, p. 1641- 1653, 2001.
GENDREAU, M.; LAPORTE, G.; SEMET, F. Solving an ambulance location model by tabu search. Location Science, v. 5, n. 2, p. 75- 88, 1997.
GHIANI, G. et al. Real- time vehicle routing: solution concepts, algorithms and parallel computing strategies. European Journal of Operational Research, v. 151, n. 1, p. 1- 11, 2003.
GHIANI, G.; MANNI, E.; QUARANTA, A.; TRIKI, C. Anticipatory algorithms for same- day courier dispatching. Transportation Research Part E: Logistics and Transportation Review, v. 45, n. 1, p. 96- 106, 2009.
HVATTUM, L. M.; LØKKETANGEN, A.; LAPORTE, G. Solving a dynamic and stochastic vehicle routing problem with a sample scenario hedging heuristic. Transportation Science, v. 40, n. 4, p. 421- 438, 2006.
ICHOUA, S.; GENDREAU, M.; POTVIN, J. Y. Exploiting knowledge about future demands for real- time vehicle dispatching. Transportation Science, v. 40, n. 2, p. 211- 225, 2006.
KILBY, P.; PROSSER, P.; SHAW, P. Dynamic VRPs: a study of scenarios. Scotland: University of Strathclyde, 1998. Technical Report APES- 06- 1998.
LARSEN, A. The dynamic vehicle routing. 2000. Thesis (Phd) - Department of Mathematical Modeling - IMM, Technical University of Denmark – DTU, Denmark, 2000.
LARSEN, A.; MADSEN, O. B. G.; SOLOMON, M. M. The a priori dynamic traveling salesman problem with time windows. Transportation Science, v. 38, n. 4, p. 459- 472, 2004.
MADSEN, O. B. G.; RAVN, H. F.; RYGAARD, J. M. A heuristic algorithm for a dial- a- ride problem with time- windows, multiple capacities, and multiple objectives. Annals of Operations Research, v. 60, n. 1, p. 193- 208, 1995.
MITROVI'C- MINI'C, S.; LAPORTE, G. Waiting strategies for the dynamic pickup and delivery problem with time windows. Transportation Research Part B, v. 38, n. 7, p. 635- 655, 2004.
MONTEMANNI, R. et al. Ant colony system for a dynamic vehicle routing problem. Journal of Combinatorial Optimization, v. 10, n. 4, p. 327- 343, 2005.
PSARAFTIS, H. N. Dynamic vehicle routing: status and prospects. Annals of Operations Research, v. 61, n. 1, p. 143- 164, 1995.
PUREZA, V.; LAPORTE, G. Waiting and buffering strategies for the dynamic pickup and delivery problem with time windows. Information Systems and Operational Research, v. 46, n. 3, p. 165- 175, 2008.
SOLOMON, M. M. Algorithms for the vehicle routing and scheduling problem with time window constraints. Operations Research, v. 35, n. 2, p. 254- 265, 1987.
Facebook
Google+
Twitter
LinkedIn
Mendeley
StumbleUpon
CiteULike
Reddit
Email