A HEURISTIC FOR THE SOLUTION OF VEHICLE ROUTING PROBLEMS WITH TIME WINDOWS AND MULTIPLE DUMPING SITES IN WASTE COLLECTION

Resumen

Municipalities have to collect the waste of households at least once a week. Households place their generated waste, which is stored in either bins or bags, on the designated days in front of their properties where waste collection vehicles can then collect the waste. This process is highly repetitive and performed throughout the year, therefore even a small improvement in waste collection and vehicle routing can lead to significant savings. The waste collection vehicle routing problem with time windows (WCVRPTW) differs from the traditional VRPTW by that the waste collecting vehicles must empty their load at disposal sites.
We present a solution to a real world WCVRPTW in a residential waste collection environment with more than 750 requesters per problem instance. In our application private homes are grouped to street segments and are partitioned into disjoint clusters with known capacity afterwards. During clustering the items with shortest assigning paths from centroids are grouped together. The summation of grouped items should not exceed the capacity of each cluster. All clusters have uniform capacity. In addition we suggest a heuristic that solves the routing problem. Each vehicle can, and typically does, make multiple disposal trips per day. A constructive heuristic that is capable of solving the problem is developed and tested, created to improve waste collection in residential areas.
KEYWORDS: Capacitated Clustering, Waiting Time, Extended Savings Algorithm, Municipal Management.
MSC: 90B06