IDEAS home Printed from
   My bibliography  Save this article

Truck scheduling for solid waste collection in the City of Porto Alegre, Brazil


  • Li, Jing-Quan
  • Borenstein, Denis
  • Mirchandani, Pitu B.


This 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.

Suggested Citation

  • Li, Jing-Quan & Borenstein, Denis & Mirchandani, Pitu B., 2008. "Truck scheduling for solid waste collection in the City of Porto Alegre, Brazil," Omega, Elsevier, vol. 36(6), pages 1133-1149, December.
  • Handle: RePEc:eee:jomega:v:36:y:2008:i:6:p:1133-1149

    Download full text from publisher

    File URL:
    Download Restriction: Full text for ScienceDirect subscribers only

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    1. 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.
    2. 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.
    3. 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.
    4. 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.
    5. 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.
    6. 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.
    7. 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.
    Full references (including those not matched with items on IDEAS)


    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.

    Cited by:

    1. 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.
    2. 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.
    3. 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.
    4. Kowalski, Krzysztof & Lev, Benjamin & Shen, Wenjing & Tu, Yan, 2014. "A fast and simple branching algorithm for solving small scale fixed-charge transportation problem," Operations Research Perspectives, Elsevier, vol. 1(1), pages 1-5.
    5. Ramos, Tânia Rodrigues Pereira & Gomes, Maria Isabel & Barbosa-Póvoa, Ana Paula, 2014. "Planning a sustainable reverse logistics system: Balancing costs with environmental and social concerns," Omega, Elsevier, vol. 48(C), pages 60-74.
    6. 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.
    7. Huang, Shan-Huen & Lin, Pei-Chun, 2015. "Vehicle routing–scheduling for municipal waste collection system under the “Keep Trash off the Ground” policy," Omega, Elsevier, vol. 55(C), pages 24-37.
    8. 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.


    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:jomega:v:36:y:2008:i:6:p:1133-1149. See general information about how to correct material in RePEc.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Dana Niculescu). General contact details of provider: .

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service hosted by the Research Division of the Federal Reserve Bank of St. Louis . RePEc uses bibliographic data supplied by the respective publishers.