The collection and transportation of waste from an urban area is a significant topic for any municipality worldwide. If this process works under an orderly and efficient way, it will have positive effects such as environmental protection, public hygiene, fuel savings for the fleet of collection trucks and financial savings for the municipalities. A major issue of this operation is the total distance that the collection trucks need to cover in order to empty the bins of waste. For instance, in the USA it is estimated that more than 60,000 collection trucks [20] are used to execute routes of related operations on an annual basis. Moreover, the average annual distance  for every vehicle is estimated to be 40,000 kilometers [21]. Actually, this means that in USA more than 2,400,000,000 kilometers are covered annually to collect the accumulated tons of waste. This thesis proposes a solution for this important logistics problem by minimizing the covered distance (cost) for a fleet of collection trucks.

The following chapters present and propose methods for the collection and transportation of waste, which is a subprocess of Solid Waste Management (SWM). The approach followed in this thesis has been inspired by the Periodic Vehicle Routing Problem (PVRP). The objective  is to develop an appropriate model for a fleet of vehicles, which empties the bins of an urban area as necessary during a whole period of m days, minimizing the distance cost.

  To solve the PVRP mathematical model, two heuristic approaches have been developed: Heuristic Algorithm 1 (HA1) and Heuristic Algorithm 2 (HA2). HA1 involves simultaneously deciding which customers (bins of waste in our problem) will be served (emptied) in each day of the week, which vehicle will be used, and in which sequence. HA1 is a variant of the savings algorithm Clarke & Wright adapted to the characteristics of the PVRP model. More specifically, heuristic HA1 executes the Clarke & Wright method as many times as needed throughout the period until the number of visits (frequency) in each node is met.

Algorithm HA2 first decides which customers (bins of waste in our problem)  will be served (emptied) in each day of the week, by which vehicle and in which sequence. The characteristic of this algorithm is that it uses (empirical) classifications which minimize the total number of routes. More extensively, the algorithm first classifies the nodes according to their frequency and then assigns the nodes to days using PVRP. Secondly, Clarke & Wright is executed in each day of the period in order to route the assigned nodes.

In our model, algorithms HA1 and HA2 must follow three constraints which are associated with the schedule of visits, the capacity of the vehicle and the daily truck work-shift.

The schedule of visits is based on three parameters. First, a node must be visited as many times as its visiting frequency defines through the days of the set period. Secondly, every point cannot be visited more than once in a single day. Finally, if a point has frequency of more than one, it cannot not be visited in two consecutive days according to the Well Balance Schedule scenario (WBS). The WBS scenario is analyzed in the following paragraphs and its aim is to prevent waste overflowing from bins.

The constraints of capacity and time are made by the following two assumptions: Assumption 1: The capacity of a vehicle is measured in number of bins and computed as truck’s capacity = n bins * average waste amount per bin. 

Assumption 2: The shift of a vehicle is measured in a limited number of bins per shift and computed as truck’s work-shift = m bins * average evacuation time per bin.

The developed algorithms are initially shown in two small instances for a better understanding of the mathematical model. Eight applications with a range of 150 to 1400 nodes are then implemented 50 times each to compare both heuristics. In the last chapter, our PVRP inspired model is developed and solved for a practical case concerning the municipality of Chios. Finally, algorithms HA1 and HA2 are used in combination with the appropriate local search improvement heuristics for further reduction of the initial solution.