Abstract
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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Assad, A. and B. Golden. (1995). “Arc Routing Methods and Applications.” In M.O. Ball et al. (eds.), Handbooks in Operations Research and Management Science, Vol. 8, pp. 375–483.
Bodin, L., B. Golden, A. Assad, and M. Ball. (1983). “Routing and Scheduling of Vehicles and Crews: The State of the Art.” Computers and Operations Research, 10, 65–211.
Bodin, L. and S. Kursh. (1978). “A Computer-Assisted System for the Routing and Scheduling of Street Sweepers.” Operations Research, 26, 525–537.
Bodin, L., D. Rosenfield, and A. Kydes. (1978). “UCOST, A Micro Approach to the Transit Planning Problem.” Journal of Urban Analysis, 15, 47–69.
Bodin, L., D. Rosenfield, and A. Kydes. (1981). “Scheduling and Estimation Techniques for Transportation Planning.” Computers and Operations Research, 8, 25–38.
Dror, M, (ed.)., (2000). ARC ROUTING: Theory, Solutions, and Applications. Kluwer Academic Publishers.
Eiselt, H., M. Gendreau, and G. G. Laporte. (1995a). “Arc Routing Problems, Part I: The Chinese Postman Problem.” Operations Research, 43, 231–242.
Eiselt, H., M. Gendreau, and G. G. Laporte. (1995b). “Arc Routing Problems, Part II: The Rural Postman Problem.” Operations Research, 43, 399–414.
Golden, B., A. Assad, and E. Wasil. (2002). “Routing Vehicles in the Real World: Applications in the Solid Waste, Beverage, Food, Dairy and Newspaper Industries.” Chapter 10 of The Vehicle Routing Problem In P. Toth and D. Vigo (eds.), SIAM Monograph on Discrete Mathematics and Applications pp. 243–286.
Sniezek, J. (2001). “The Capacitated Arc Routing Problem with Vehicle/Site Dependencies: An Application of Arc Routing and Partitioning.” Ph.D. Dissertation, University of Maryland, College Park, Md. 20742.
Sniezek, J., L. Bodin, L. Levy, and M. Ball. (2002). “Capacitated Arc Routing Problem with Vehicle-Site Dependencies: The Philadelphia Experience.” Chapter 11 of The Vehicle Routing Problem, In P. Toth and D. Vigo (eds.), SIAM Monograph on Discrete Mathematics and Applications, pp. 287–308.
Toth, P., D. Vigo (eds.) (2002). “The Vehicle Routing Problem.” SIAM Monograph on Discrete Mathematics and Applications.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Sniezek, J., Bodin, L. 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. Ann Oper Res 144, 33–58 (2006). https://doi.org/10.1007/s10479-006-0006-y
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10479-006-0006-y