×

zbMATH — the first resource for mathematics

Waste collection vehicle routing problem with time windows. (English) Zbl 1113.90035
Summary: In this paper, we address a real life waste collection vehicle routing problem with time windows (VRPTW) with consideration of multiple disposal trips and drivers’ lunch breaks. Solomon’s well-known insertion algorithm is extended for the problem. While minimizing the number of vehicles and total traveling time is the major objective of vehicle routing problems in the literature, here we also consider the route compactness and workload balancing of a solution since they are very important aspects in practical applications. In order to improve the route compactness and workload balancing, a capacitated clustering-based waste collection VRPTW algorithm is developed. The proposed algorithms have been successfully implemented and deployed for the real life waste collection problems at Waste Management, Inc. A set of waste collection VRPTW benchmark problems is also presented in this paper.
Waste collection problems are frequently considered as arc routing problems without time windows. However, that point of view can be applied only to residential waste collection problems. In the waste collection industry, there are three major areas: commercial waste collection, residential waste collection and roll-on-roll-off. In this paper, we mainly focus on the commercial waste collection problem. The problem can be characterized as a variant of VRPTW since commercial waste collection stops may have time windows. The major variation from a standard VRPTW is due to disposal operations and driver’s lunch break. When a vehicle is full, it needs to go to one of the disposal facilities (landfill or transfer station). Each vehicle can, and typically does, make multiple disposal trips per day. The purpose of this paper is to introduce the waste collection VRPTW, benchmark problem sets, and a solution approach for the problem. The proposed algorithms have been successfully implemented and deployed for the real life waste collection problems of Waste Management, the leading provider of comprehensive waste management services in North America with nearly 26,000 collection and transfer vehicles.

MSC:
90B20 Traffic problems in operations research
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Sahoo S, Kim S, Kim B-I, Kraas B, Popov Jr. A. Routing optimization for waste management. Interfaces 2005;35(1):24-36.
[2] Golden, B.L.; Assad, A.A.; Wasil, E.A., Routing vehicles in the real world: applications in the solid waste, beverage, food, dairy, and newspaper industries, (), 245-286 · Zbl 1076.90546
[3] Solomon, M.M., Algorithms for the vehicle routing and scheduling problem with time window constraints, Operations research, 35, 2, 254-265, (1987) · Zbl 0625.90047
[4] Potvin, J.Y.; Rousseau, J.M., A parallel route building algorithm for the vehicle routing and scheduling problem with time windows, European journal of operations research, 66, 331-340, (1993) · Zbl 0775.90154
[5] Rochat, Y.; Taillard, E.D., Probabilistic diversification and intensification in local search for vehicle routing, Journal of heuristics, 1, 147-167, (1995) · Zbl 0857.90032
[6] Taillard, E.D.; Badeau, P.; Gendreau, M.; Guertin, F.; Potvin, J.Y., A tabu search heuristic for the vehicle routing problem with soft time windows, Transportation science, 31, 1, 170-186, (1997) · Zbl 0886.90070
[7] Taillard, E.D.; Laporte, G.; Gendreau, M., Vehicle routing with multiple use of vehicles, Journal of the operational research society, 47, 1065-1070, (1996) · Zbl 0864.90045
[8] Weigel, D.; Cao, B., Applying GIS and OR techniques to solve sears Technician-dispatching and home-delivery problems, Interfaces, 29, 1, 112-130, (1999)
[9] Tung, D.V.; Pinnoi, A., Vehicle routing-scheduling for waste collection in Hanoi, European journal of operational research, 125, 449-468, (2000) · Zbl 0967.90020
[10] Poot, A.; Kant, G.; Wagelmans, A.P.M., A savings based method for real-life vehicle routing problems, Journal of the operational research society, 53, 57-68, (2002) · Zbl 1138.90338
[11] Angelelli, E.; Speranza, M.G., The periodic vehicle routing problem with intermediate facilities, European journal of operational research, 137, 233-247, (2002) · Zbl 0998.90021
[12] Angelelli, E.; Speranza, M.G., The application of a vehicle routing model to a waste-collection problem: two case studies, Journal of the operational research society, 53, 944-952, (2002) · Zbl 1139.90396
[13] Teixeira, J.; Antunes, A.P.; Sousa, J.P., Recyclable waste collection planning—a case study, European journal of operational research, 158, 543-554, (2004) · Zbl 1056.90024
[14] Eisenstein, D.D.; Iyer, A.V., Garbage collection in Chicago: a dynamic scheduling model, Management science, 43, 7, 922-933, (1997) · Zbl 0890.90130
[15] Chang, N.-B.; Lu, H.Y.; Wei, Y.L., GIS technology for vehicle routing and scheduling in solid waste collection systems, Journal of environmental engineering, 123, 901-933, (1997)
[16] Mourao, M.C.; Almeida, M.T., Lower-bounding and heuristic methods for a refuse collection vehicle routing problem, European journal of operational research, 121, 420-434, (2000) · Zbl 0953.90008
[17] Cordeau, J.-F.; Desaulniers, G.; Desrosiers, J.; Solomon, M.M.; Soumis, F., VRP with time windows, (), 157-193 · Zbl 1076.90543
[18] Graham, R.L., An efficient algorithm for determining the convex hull of a finite planar set, Information processing letters, 1, 132-133, (1972) · Zbl 0236.68013
[19] Prins, C., A simple and effective evolutionary algorithm for the vehicle routing problem, Computers and operations research, 31, 1985-2002, (2004) · Zbl 1100.90504
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.