Truck scheduling for solid waste collection in the City of Porto Alegre, Brazil
AbstractThis paper considers a truck scheduling problem in the context of solid waste collection in the City of Porto Alegre, Brazil. The problem consists of designing "good" daily truck schedules over a set of previously defined collection trips, on which the trucks collect solid waste in fixed routes and empty loads in one of several operational recycling facilities in the system. These facilities are managed by cooperatives whose members are poor and not part of the mainstream economy. The main objective is to minimize the total operating and fixed truck costs. We show that the problem can be modeled as a special case of the single-depot vehicle scheduling problem, which is polynomially solvable. However, due to the social benefits of the solid waste program, it is desirable to obtain balanced assignments of collection trips unloading their cargo at the recycling facilities. We prove that the truck scheduling problem considering balanced unloading is NP-hard. A heuristic approach, incorporating an auction algorithm and a dynamic penalty method, is designed to acquire a good solution. Finally, computational experiments are conducted on real data. The results show that the heuristic approach simultaneously reduces total costs and balances the number of trips assigned to each recycling facility.
Download InfoIf you experience problems downloading a file, check if you have the proper application to view it first. In case of further problems read the IDEAS help page. Note that these files are not on the IDEAS site. Please be patient as the files may be large.
Bibliographic InfoArticle provided by Elsevier in its journal Omega.
Volume (Year): 36 (2008)
Issue (Month): 6 (December)
Contact details of provider:
Web page: http://www.elsevier.com/wps/find/journaldescription.cws_home/375/description#description
Please report citation or reference errors to , or , if you are the registered author of the cited work, log in to your RePEc Author Service profile, click on "citations" and make appropriate adjustments.:
- Marshall L. Fisher & R. Jaikumar & Luk N. Van Wassenhove, 1986. "A Multiplier Adjustment Method for the Generalized Assignment Problem," Management Science, INFORMS, vol. 32(9), pages 1095-1103, September.
- Bokinge, Ulf & Hasselstrom, Dick, 1980. "Improved vehicle scheduling in public transport through systematic changes in the time-table," European Journal of Operational Research, Elsevier, vol. 5(6), pages 388-395, December.
- Lorena, Luiz Antonio N. & Narciso, Marcelo G., 1996. "Relaxation heuristics for a generalized assignment problem," European Journal of Operational Research, Elsevier, vol. 91(3), pages 600-610, June.
- Kirca, Omer & Erkip, Nesim, 1988. "Selecting transfer station locations for large solid waste systems," European Journal of Operational Research, Elsevier, vol. 35(3), pages 339-349, June.
- Mauro Dell'Amico & Matteo Fischetti & Paolo Toth, 1993. "Heuristic Algorithms for the Multiple Depot Vehicle Scheduling Problem," Management Science, INFORMS, vol. 39(1), pages 115-125, January.
- Donald D. Eisenstein & Ananth. V. Iyer, 1997. "Garbage Collection in Chicago: A Dynamic Scheduling Model," Management Science, INFORMS, vol. 43(7), pages 922-933, July.
- Tung, Dang Vu & Pinnoi, Anulark, 2000. "Vehicle routing-scheduling for waste collection in Hanoi," European Journal of Operational Research, Elsevier, vol. 125(3), pages 449-468, September.
- Adlakha, Veena & Kowalski, Krzysztof & Lev, Benjamin, 2010. "A branching method for the fixed charge transportation problem," Omega, Elsevier, vol. 38(5), pages 393-397, October.
- Salazar-González, Juan-José, 2014. "Approaches to solve the fleet-assignment, aircraft-routing, crew-pairing and crew-rostering problems of a regional carrier," Omega, Elsevier, vol. 43(C), pages 71-82.
- Izabel Cristina Carvalho de Oliveira & Henrique Dantas Neder & Niemeyer Almeida Filho, 2010. "Impactos Sociais Da Expansão Do Programa De Biocombustíveis Sobre O Estado De Minas Gerais," Anais do XIV Seminário sobre a Economia Mineira [Proceedings of the 14th Seminar on the Economy of Minas Gerais], in: Anais do XIV Seminário sobre a Economia Mineira [Proceedings of the 14th Seminar on the Economy of Minas Gerais] Cedeplar, Universidade Federal de Minas Gerais.
- Overholts II, Dale L. & Bell, John E. & Arostegui, Marvin A., 2009. "A location analysis approach for military maintenance scheduling with geographically dispersed service areas," Omega, Elsevier, vol. 37(4), pages 838-852, August.
- Belien, Jeroen & De Boeck, Liesje & Van Ackere, Jonas, 2011. "Municipal Solid Waste Collection Problems: A Literature Review," Working Papers 2011/34, Hogeschool-Universiteit Brussel, Faculteit Economie en Management.
If references are entirely missing, you can add them using this form.