Our work examines this collection step in the plastic waste management supply chain, which can be formulated as capacitated arc routing problems (CARPs). Here, we represent the street networks travelled by waste collection vehicles using a graph G=(N,A), where N is the set of nodes and A is the set of arcs. The nodes can represent street intersections or point facilities (the most common case is a node which represents the depot from which collection vehicles depart from and return to). The arcs represent the streets of the network, with each arc allowing travel in one direction only. Some of these arcs will have associated demand, representing streets requiring curbside recycling pickup, while others may have no demand but can be travelled (this is referred to as ‘deadheading’). Two-way streets, in which a vehicle can travel in either direction and still collect waste from both sides, are represented by two directed arcs in the graph. We solve the CARP to find the optimal set of routes by which a given fleet of vehicles (either homogeneous or heterogeneous in composition) collects all demand from required arcs while minimizing total traversal and service costs. These costs can be calculated as a function of time or distance.
The CARP was first proposed by Golden and Wong2 in 1981, and it has been studied in many variants since. We introduce a new formulation for the basic CARP problem which has comparable performance to the baseline CARP formulation proposed by Gouveia3 on commonly used benchmarks. CARP formulations typically only track if arcs are serviced or deadheaded, and do not give information on the order of traversal or service. The key feature of our formulation is a 5-index binary Y(n1,n2,n3,n4,k), which determines if arc (n1,n2) is served directly before arc (n3,n4) by vehicle type k. Knowing the order of service allows us to trace the route in its entirety and track the cumulative demand collected along the route, which is represented in the formulation by the flow variable F(n1,n2,n3,n4,k).
As each route in the solution can be defined solely by the sequence of links between the depot and serviced arcs, we do not need to use the vehicle index k to distinguish individual routes from each other. Instead, the index k gives information on the vehicle type used to travel a given route. This means our formulation is agnostic to vehicle fleet size, as the model size only grows if more vehicle types are considered. This opens the possibility of investigating how different vehicle types affect the routing problem without significantly increasing the model size.
To avoid exponential numbers of the Y(n1,n2,n3,n4,k) binaries, we only define them over a pre-determined set L, which contains the set of permissible links between successively serviced arcs. We can take advantage of the set L to reduce the size of the model and solve larger problem instances. For example, we can limit the routes to only service arcs sequentially if the shortest path between them is less than some maximum distance applied uniformly to all arcs. Going a step further, inspired by the principles of the path-scanning heuristic4, we might only allow links from an arc to arcs for which the shortest path between them is less than the length of the xth-shortest path possible.
We also demonstrate that we can easily extend our formulation to include design decisions regarding where to locate depots. These problems are known as location arc routing problems (LARPs). We propose a novel method of representing LARPs which uses a ‘tagging’ system built into the flow variables to enforce ‘return-to-facility’ (RtF) constraints, which ensure each vehicle route returns to the depot it departed from. In this system, a ‘tag’ unique to each depot node is added to all flows leaving from that depot. These ‘tags’ have magnitudes which are a multiple of the vehicle capacity and are carried through the flow variables associated with the route leaving that depot. When the route returns to a depot, the depot ‘untags’ the incoming flows by subtracting its unique ‘tag’. Once ‘untagged’, all flows entering a depot must be within 0 and the vehicle capacity. Only by returning to the depot it departed from can a route satisfy this constraint.
Our ‘tagging’ method means we do not need to add a depot index to flow and binary variables, or add constraints with separate binaries assigning arcs to depots, as is often done in literature 5–7. In this way, our model does not increase dramatically in size with the inclusion of location decisions. Our formulation can solve several benchmark LARP instances to optimality in times comparable to some heuristics, and can solve both single and multiple depot problems.
To reduce pollution and energy usage in the plastic recycling life cycle, we must also take care to design collection routes to be fuel-efficient. We can easily incorporate environmental objectives through a cost per ton-distance which represents the increased fuel cost (and corresponding pollution) associated with the increasing vehicle weight along a waste collection route. Our formulation already tracks the cumulative demand throughout the route, and therefore introducing an environmental objective will not necessitate modification of the formulation.
We present case studies to demonstrate the applicability of our formulation to different arc routing problems seen in waste collection, as well as a computational study to show the efficiency of our formulation.
References