A heuristic solution method for node routing based solid waste collection problems
Tóm tắt
This paper considers a real world waste collection problem in which glass, metal, plastics, or paper is brought to certain waste collection points by the citizens of a certain region. The collection of this waste from the collection points is therefore a node routing problem. The waste is delivered to special sites, so called intermediate facilities (IF), that are typically not identical with the vehicle depot. Since most waste collection points need not be visited every day, a planning period of several days has to be considered. In this context three related planning problems are considered. First, the periodic vehicle routing problem with intermediate facilities (PVRP-IF) is considered and an exact problem formulation is proposed. A set of benchmark instances is developed and an efficient hybrid solution method based on variable neighborhood search and dynamic programming is presented. Second, in a real world application the PVRP-IF is modified by permitting the return of partly loaded vehicles to the depots and by considering capacity limits at the IF. An average improvement of 25% in the routing cost is obtained compared to the current solution. Finally, a different but related problem, the so called multi-depot vehicle routing problem with inter-depot routes (MDVRPI) is considered. In this problem class just a single day is considered and the depots can act as an intermediate facility only at the end of a tour. For this problem several instances and benchmark solutions are available. It is shown that the algorithm outperforms all previously published metaheuristics for this problem class and finds the best solutions for all available benchmark instances.
Tài liệu tham khảo
Alegre, J., Laguna, M., Pacheco, J.: Optimizing the periodic pick-up of raw materials for a manufacturer of auto parts. Eur. J. Oper. Res. 179, 736–746 (2007)
Angelelli, E., Speranza, M.: The application of a vehicle routing model to a waste-collection problem: two case studies. J. Oper. Res. Soc. 53(9), 944–952 (2002a)
Angelelli, E., Speranza, M.G.: The periodic vehicle routing problem with intermediate facilities. Eur. J. Oper. Res. 137(2), 233–247 (2002b)
Archetti, C., Speranza, M.: Vehicle routing in the 1-skip collection problem. J. Oper. Res. Soc. 55(7), 717–727 (2004)
Baptista, S., Oliveira, R., Zuquete, E.: A period vehicle routing case study. Eur. J. Oper. Res. 139(2), 220–229 (2002)
Beasley, J.: Route-first cluster-second methods for vehicle routing. Omega 11(4), 403–408 (1983)
Beltrami, E., Bodin, L.: Networks and vehicle routing for municipal waste collection. Networks 4(1) (1974)
Bodin, L., Mingozzi, A., Baldacci, R., Ball, M.: The rollon-rolloff vehicle routing problem. Transp. Sci. 34(3), 271 (2000)
Christofides, N., Beasley, J.: The period routing problem. Networks 14(2), 237–256 (1984)
Clarke, G., Wright, J.W.: Scheduling of vehicles from a central depot to a number of delivery points. Oper. Res. 12, 568–581 (1964)
Cordeau, J., Gendreau, M., Laporte, G.: A tabu search heuristic for periodic and multi-depot vehicle routing problems. Networks 30(2), 105–119 (1998)
Crevier, B., Cordeau, J., Laporte, G.: The multi-depot vehicle routing problem with inter-depot routes. Eur. J. Oper. Res. 176(2), 756–773 (2007)
Croes, G.: A method for solving traveling salesman problems. Oper. Res. 6, 791–812 (1958)
Eisenstein, D., Iyer, A.: Garbage collection in Chicago: a dynamic scheduling model. Manag. Sci. 43(7), 922–933 (1997)
Gelatt, S., Vecchi, M.: Optimization by simulated annealing. Science 220(4598), 671–680 (1983)
Golden, B., Assad, A., Wasil, E.: Routing vehicles in the real world: Applications in the solid waste, beverage, food, dairy and newspaper industry. In: Toth, P., Vigo, D. (eds.) The Vehicle Routing Problem, pp. 245–286. SIAM, Philadelphia (2001)
Hansen, P., Mladenovic, N.: Variable neighborhood search: Principles and applications. Eur. J. Oper. Res. 130, 449–467 (2001)
Hemmelmayr, V., Doerner, K., Hartl, R.: A variable neighborhood search heuristic for periodic routing problems. Eur. J. Oper. Res. 195(3), 791–802 (2009)
Kindervater, G.A.P., Savelsbergh, M.: Vehicle routing: Handling edges exchanges windows. In: Aarts, E., Lenstra, J. (eds.) Local Search in Combinatorial Optimization. Wiley, Chichester (1997)
Kulcar, T.: Optimizing solid waste collection in Brussels. Eur. J. Oper. Res. 90(1), 71–77 (1996)
Lacomme, P., Prins, C., Ramdane-Cherif, W.: Evolutionary algorithms for periodic arc routing problems. Eur. J. Oper. Res. 165(2), 535–553 (2005)
Lin, S.: Computer solutions of the traveling salesman problem. Bell Syst. Tech. J. 44, 2245–2269 (1965)
Mourão, M., Almeida, M.: Lower-bounding and heuristic methods for a refuse collection vehicle routing problem. European Journal of Operational Research 121(2), 420–434 (2000)
Mourão, M., Amado, L.: Heuristic method for a mixed capacitated arc routing problem: A refuse collection application. European Journal of Operational Research 160(1), 139–153 (2005)
Potvin, J., Rousseau, J.: An exchange heuristic for routeing problems with time windows. J. Oper. Res. Soc. 1433–1446 (1995)
Prins, C.: A simple and effective evolutionary algorithm for the vehicle routing problem. Comput. Oper. Res. 31(12), 1985–2002 (2004)
Prins, C., Bouchenoua, S.: A memetic algorithm solving the VRP, the CARP and general routing problems with nodes, edges and arcs. In: Recent Advances in Memetic Algorithms, pp. 65–85 (2005)
Tarantilis, C., Zachariadis, E., Kiranoudis, C.: A hybrid guided local search for the vehicle-routing problem with intermediate replenishment facilities. INFORMS J. Comput. 20(1), 154 (2008)
Teixeira, J., Antunes, A., de Sousa, J.: Recyclable waste collection planning—a case study. European Journal of Operational Research 158(3), 543–554 (2004)
Tung, D., Pinnoi, A.: Vehicle routing–scheduling for waste collection in Hanoi. Eur. J. Oper. Res. 125(3), 449–468 (2000)