Using mixed integer programming for solving the capacitated arc routing problem with vehicle/site dependencies with an application to the routing of residential sanitation collection vehicles

We present the Composite Approach for solving the Capacitated Arc Routing Problem with Vehicle/Site Dependencies (CARP-VSD). We also present two mixed integer programs, the Initial Fleet Mix Generator (IFM) and the Mathematical Programming Procedure (MPP), and a multi-criterion function called the Measure of Goodness. The IFM, MPP and Measure of Goodness are critical components of the Composite Approach. A key application area of the CARP-VSD is the routing of residential sanitation vehicles; throughout this paper, we derive parameters specific to this problem. In this paper, we describe the Composite Approach, the IFM, the MPP, the Measure of Goodness and work out several examples in detail.