Solving a Complex Waste Collection Routing Problem with Intermediate Disposals

Abstract

Solid waste collection is one of the most complex logistical problems facing any municipality. In recent years, increased fuel prices and operational costs, environmental and health concerns, and the growing regulation burden have caused waste collection companies, both municipal and private, to optimize their collection routes. According to various studies (Bhat, 1996; Teixeira et al., 2004; Tavares et al., 2009), transportation costs represent between 70 and 80% of all operational costs in waste collection. Therefore, even small improvements in the collection routes may lead to substantial savings, which directly affect household fees, municipal budgets and the companies’ bottom lines. We consider a complex waste collection problem, which can be described as follows. The residents of a certain region dispose of recyclable waste, which is collected using a fixed heterogeneous fleet of vehicles with different volume and weight capacities, fixed costs, unit distance running costs and hourly driver wage rates. Each tour starts and ends at one of several depots, not necessarily the same, and is a sequence of collections followed by disposals at the available recycling plants, which can be visited when and as necessary. Depots in our case are not vehicle housing locations, but only physical points where a tour may start and/or end, and vehicles are in no way bound to specific depots. There is a mandatory disposal just before the end of a tour, i.e. a tour terminates with an empty vehicle. We consider time windows on recycling plants and collection points, and a maximum tour duration, which is interrupted by a rest period after a certain interval of continuous work. Moreover, due to the particularities of different collection areas, there are occasional accessibility constraints. Mountainous terrain and narrow streets, for example, are impassable by big collector trucks. The above description is an extension of the vehicle routing problem with intermediate facilities (VRP-IF) of Kim et al. (2006) and the multi-depot vehicle routing problem with

inter-depot routes (MDVRPI) of Crevier et al. (2007). The framework of the former includes a temporal aspect with time windows and a driver break, which are missing in the latter. Another difference is that in the MDVRPI depots and intermediate facilities coincide; thus a vehicle need not be emptied before returning to the depot. Both frameworks consider a homogeneous fleet, fixed in the case of the MDVRPI, and a single origin/destination depot. Several authors (Ombuki-Berman et al., 2007; Benjamin, 2011; Buhrkal et al., 2012 in the case of the VRP-IF; Tarantilis et al., 2008; Hemmelmayr et al., 2013 in the case of the MDVRPI) have worked on synthetic instances of these problems. A real-world case study is presented in Buhrkal et al. (2012). Solution techniques focus on various heuristics and no fully exact method has been applied to either version of the problem. A hybrid set partitioning algorithm was developed by Crevier et al. (2007). Given the heterogeneous nature of our fleet, another relevant problem is the heterogeneous fixed fleet vehicle routing problem (HFFVRP) proposed by Taillard (1996) and tackled by numerous other authors. What makes the HFFVRP more challenging compared to the homogeneous fleet VRP and the vehicle fleet mix problem (VFMP) is that tour improvement heuristics require periodically finding a new assignment of vehicles to tours, which is both time consuming and also difficult given the limited number of heterogeneous vehicles. Our problem is modeled as a mixed binary linear program, which minimizes the number of tours and their spatial and temporal costs. The model introduces several new features to the VRP-IF and the MDVRPI, such as a realistic cost-based objective function, multiple depots, a fixed heterogeneous fleet, accessibility restrictions, and a rest period that is not restricted by a time window but depends on when the vehicle started its tour. Moreover, we include a relocation term in the objective function, which incentivizes, rather than enforcing, the vehicle to return to the depot it started from—a situation mimicking our case study, which includes a large rural and peri-urban region. Therefore, tours may be longer than in the case of an urban environment and it may not always be optimal for a vehicle to return to its origin point at the end of the tour. We assess the model’s performance on randomly generated data sets with various characteristics and investigate classes of valid inequalities and exact elimination rules to speed up the branch-and-bound process. We also develop a variable neighborhood search (VNS) heuristic designed specifically for the problem. In addition to the classical swap, 2-opt and reinsert operators, we implement trip swapping and reinsertion within and between tours, where a trip is a part of a tour between two disposal operations. The performance of the VNS is evaluated by comparison to the optimal solution on small and medium-sized instances of up to 30 collection points, with and without time windows. With a maximum runtime of 30 sec. and an optimality gap consistently under 5%, we proceed to apply the VNS to real-world instances with several tens to a few hundred collection points operated by a waste collection company based in France. Currently, the company is logging its tours as well as the total amount of collected material during each tour. Thus, in the near future we will be able to assess the global performance of the VNS on real-world instances as well as the solution’s added value to the company. The developed algorithm will be integrated in a web-service application to be used by tour planners. Future research will focus on the extension of the algorithm to include container level prediction and inventory management with dynamic container visit schedules.