Scatter search para problemas de roteirização de veículos com frota heterogênea, janelas de tempo e entregas fracionadas
Scatter search for heterogeneous fleet vehicle routing problems with time windows and split deliveries
Belfiore, Patrícia Prado; Yoshizaki, Hugo Tsugunobu Y.
http://dx.doi.org/10.1590/S0103-65132006000300008
Prod, vol.16, n3, p.455-469, 2006
Resumo
Este trabalho estuda a implementação da metaheurística scatter search (SS) em um problema real de roteirização de veículos com frota heterogênea, janelas de tempo e entregas fracionadas. No problema de roteirização de veículos com entregas fracionadas, cada cliente pode ser abastecido por mais de um veículo. O problema é baseado em um único centro de distribuição, a demanda de cada cliente pode ser maior que a capacidade dos veículos e, além das restrições de janelas de tempo, há também as restrições de capacidade dos veículos e acessibilidade (alguns clientes não podem ser atendidos por alguns veículos). Os modelos foram aplicados em um dos maiores grupos varejistas brasileiros, que abastece 519 clientes distribuídos em 12 estados brasileiros. Os resultados mostraram melhorias no caso real da empresa, reduzindo em até 8% o custo total da operação.
Palavras-chave
Problema de roteirização de veículos, frota heterogênea, janelas de tempo, entregas fracionadas
Abstract
This work studies the implementation of heuristics and scatter search (SS) metaheuristic in a real heterogeneous fleet vehicle routing problem with time windows and split deliveries (HFVRPTWSD) in Brazil. In the vehicle routing problem with time windows and split deliveries (VRPSD) each client can be supplied by more than one vehicle. The problem is based in a single depot, the demand of each client can be greater than the vehicles capacity and beyond the time windows constraints, and there are also vehicle capacity and accessibility constraints (some customers cannot be served by some vehicles). The models were applied in one of the biggest retail market in Brazil that has 519 stores distributed in 12 Brazilian states. Results showed improvements over current solutions in a real case, reducing up to 8% the total cost of the operation.
Keywords
Vehicle routing problem, heterogeneous fleet, time windows, split delivers
References
ARCHETTI, C.; MANSINI, M.; SPERANZA, M. G. Complexity and Reducibility of the Skip Delivery Problem. Transportation Science, v. 39, n. 2, p. 182-187, 2005.
ARCHETTI, C.; SAVELSBERGH, M. W. P.; SPERANZA, M. G. Worst-Case Analysis of Split Delivery Routing Problems. Transportation Science, v. 40, n. 2, p. 226-234, 2006.
ARCHETTI, C.; SPERANZA, M. G.; HERTZ, A. A Tabu Search Algorithm for the Split Delivery Vehicle Routing Problem. Transportation Science, v. 40, n. 1, p. 64-73, 2006.
BELENGUER, J. M.; MARTINEZ, M. C.; MOTA, E. A Lower Bound for the Split Delivery Vehicle Routing Problem. Operations Research, v. 48, n. 5, p. 801-810, 2000.
CAMPOS, V.; GLOVER, F.; LAGUNA, M.; MARTÍ, R. An Experimental Evaluation of a Scatter Search for the Linear Ordering Problem. Journal of Global Optimization, v. 21, n. 4, p. 397-414, 2001.
CAMPOS, V.; LAGUNA, M.; MARTÍ, R. Context-independent scatter and tabu search for permutation problems. INFORMS Journal on Computing, v. 17, n. 1, p. 111-122, 2005.
CORBERÁN, A.; FERNÁNDEZ, E.; LAGUNA, M.; MARTÍ, R. Heuristic solutions to the problem of routing school buses with multiple objectives. Journal of the Operational Research Society, v. 53, n. 4, p. 427-435, 2002.
DESROCHERS, M.; VERHOOG, T. W. A new heuristic for the fleet size and mix vehicle routing problem. Computers & Operations Research, v. 18, n. 3, p. 263-274, 1991.
DROR, M.; TRUDEAU, P. Savings by Split Delivery Routing. Transportation Science, v. 23, n. 2, p. 141-145, 1989.
DROR, M.; TRUDEAU, P. Split Delivery Routing. Naval Research Logistics, v. 37, p. 383-402, 1990.
DROR, M.; LAPORTE, G.; TRUDEAU, P. Vehicle routing with split deliveries. Discrete Applied Mathematics, v. 50, n. 3, p. 229-254, 1994.
DULLAERT, W.; JANSSENS, G. K.; SORENSEN, K.; VERNIMMEN, B. New heuristics for the Fleet Size and Mix Vehicle Routing Problem with Time Windows. Journal of Operational Research Society, v. 53, p. 1232-1238, 2002.
FEO, T. A.; RESENDE, M. G. C. A probabilistic heuristic for a computationally difficult set covering problem. Operations Research Letters, v. 8, n. 2, p. 67-71, 1989.
FRIZZELL, P. W.; GIFFIN, J. W. The bounded split delivery vehicle routing problem with grid network distances. Asia Pacific Journal of Operational Research, v. 9, n. 1, p. 101-106, 1992.
FRIZZELL, P. W.; GIFFIN, J. W. The Split Delivery Vehicle Scheduling Problem with Time Windows and Grid Network Distances. Computers & Operations Research, v. 22, n. 6, p. 655-667, 1995.
GENDREAU, M.; LAPORTE, G.; MUSARAGANYI, C.; TAILLARD, E. D. A tabu search heuristic for the heterogeneous fleet vehicle routing problem. Computers & Operations Research, v. 26, n. 12, p. 1153-1173, 1999.
GLOVER, F. A Template for Scatter Search and Path Relinking. In: Artificial Evolution, Lecture Notes in Computer Science 1363, Hao, J.-K., E. Lutton, E. Ronald, M. Schoenauer, D. Snyers (Eds.), Springer-Verlag, p. 13-54, 1998.
GOLDEN, B. L.; ASSAD, A.; LEVY, L.; GHEYSENS, F. The fleet size and mix vehicle routing problem. Computers & Operations Research, v. 11, n. 1, p. 49-65, 1984.
HO, S. C.; HAUGLAND, D. A A tabu search heuristic for the vehicle routing problem with time windows and split deliveries. Computers & Operations Research, v. 31, n. 2, p. 1947-1964, 2004.
JAIN, A. S.; MEERAN, S. A multi-level hybrid framework applied to the general flow-shop scheduling problem. Computers & Operations Research, v. 29, n. 13, p. 1873-1901, 2002.
LAGUNA, M.; MARTÍ, R. Experimental Testing of Advanced Scatter Search Designs for Global Optimization of Multimodal Functions. Journal of Global Optimization, v. 33, n. 2, p. 235-255, 2005.
LENSTRA, J. K.; RINNOOY KAN, A. H. G. Complexity of Vehicle and Scheduling Problems. Networks, v. 11, n. 2, p. 221-227, 1981.
LIU, F. H.; SHEN, S. Y. The fleet size and mix vehicle routing problem with time windows. Journal of the Operational Research Society, v. 50, n. 7, p. 721-732, 1999.
MARTÍ, R.; LOURENÇO, H.; LAGUNA, M. Assigning proctors to exams with scatter search. In: Computing Tools for Modeling, Optimization and Simulation, Laguna, M.; Velaverde, J.L.G. (Eds.), Kluwer Academia Publishers, p. 215-227, 2000.
MARTÍ, R.; LAGUNA, M.; CAMPOS, V. Scatter search vs genetic algorithms: an experimental evaluation permutation problems. In: Metaheuristic Optimization via Adaptive memory and evolution: Tabu search and scatter search, Rego, C.; Alidaee, B. (Eds.), Kluwer Academic Publishers, p. 263-285, 2005.
MULLASERIL, P. A.; DROR, M.; LEUNG, J. Split-delivery Routing Heuristics in Livestock Feed Distribution. Journal of the Operational Research Society, v. 48, n. 2, p. 107-116, 1997.
REGO, C.; LEÃO, P. A Scatter Search Tutorial for Graph-Based Permutation Problems. Hearin Center for Enterprise, University of Mississipi, HCES-10-00, USA, 2000. In: Metaheuristic Optimization via Memory and Evolution: Tabu Search and Scatter Search, Rego, C; Alidaee, B. (Eds.), Kluwer Academic Publishers, p. 1-24, 2005.
ROCHAT, Y.; SEMET, F. A Tabu Search Approach for Delivering Pet Food and Flour in Switzerland. Journal of the Operational Research Society, v. 45, n. 11, p. 1233-1246, 1994.
ROCHAT, Y.; TAILLARD, E. D. Probabilistic Diversification and Intensification in Local Search for Vehicle Routing. Journal of Heuristics, v. 1, n. 1, p. 147-167, 1995.
SALHI, S.; RAND, G. K. Incorporating vehicle routing into the vehicle fleet composition problem. European Journal of Operational Research, v. 66, n. 3, p. 313-330, 1993.
SOLOMON, M. M. Algorithms for the Vehicle Routing and Scheduling Problems with Time Windows Constraints. Operations Research, v. 35, n. 2, p. 254-265, 1987.
SOLOMON, M. M.; DESROSIERS, J. Time Window Constrained Routing and Scheduling Problem. Transportation Science, v. 22, n. 1, p. 1-13, 1988.
TAILLARD, É. D. A heuristic column generation method for the heterogeneous fleet vehicle routing problem. RAIRO - Operations Research, v. 33, n.1, p. 1-14, 1999.
TARANTILIS, C. D.; KIRANOUDIS, C. T.; VASSILIADIS, V. S. A threshold accepting metaheuristic for the heterogeneous fixed fleet vehicle routing problem. European Journal of Operational Research, v. 152, n. 1, p. 148-158, 2004.
YAMASHITA, D. S.; ARMENTANO, V. A.; LAGUNA, M. Scatter Search for Project scheduling with resource availability cost. European Journal of Operational Research, v. 169, n. 2, p. 623-637, 2006.
WASSAN, N. A.; OSMAN, I. H. Tabu search variants for the mix fleet vehicle routing problem. Journal of the Operational Research Society, v. 53, p. 768-782, 2002.
Facebook
Google+
Twitter
LinkedIn
Mendeley
StumbleUpon
CiteULike
Reddit
Email