The capacitated arc routing problem with vehicle/site dependencies: An application of arc routing and partitioning

In this dissertation, we define and analyze a variant of the CARP called the Capacitated Are Routing Problem with Vehicle/Site Dependencies (CARP-VSD). The motivating example of the CARP-VSD that drives the analysis in this dissertation is residential solid waste collection. Typically, residential sanitation collection involves thousands of arcs and edges. Two key features of the CARP-VSD that separate this problem from other variants of the CARP are the following: (i) The vehicle fleet may have several different types of vehicles available for servicing the required arcs and edges in the network. (ii) Some of the arcs and edges may have restrictions that prohibit their service or traversal by certain vehicle classes.; We develop a composite approach for solving the CARP-VSD. The composite approach that we develop in this dissertation has solved CARP-VSD problems containing thousands of arcs and edges requiring service. The composite approach consists of two major procedures—the Vehicle Decomposition Algorithm (VDA), and a mathematical programming formulation (MPP).; A version of the VDA was implemented in Philadelphia and documented savings of over 12% were achieved.; A mathematical programming formulation (MPP) of the CARP-VSD is developed. The MPP is used to solve the partitioning of the arcs in the network that require service.; As part of the composite approach, we develop a cost model to evaluate different solutions. This cost model performs a tradeoff between capital and operating costs and is relatively unique in solving vehicle routing problems. The cost model is imbedded within the formulation of the MPP. (Abstract shortened by UMI.)...