Abstract
We define the multiple-vehicle collection for processing problem (mCfPP) as a vehicle routing and scheduling problem in which items that accumulate at customer sites over time should be transferred by a series of tours to a processing facility. We show that this problem with the makespan objective (mCfPP(\(C_{\max }\))) is NP-hard using an approximation preserving reduction from a two-stage, hybrid flowshop scheduling problem. We develop a polynomial-time, constant-factor approximation algorithm to solve mCfPP(\(C_{\max }\)). The problem with a single site is analyzed as a special case with two purposes. First, we identify the minimum number of vehicles required to achieve a lower bound on the makespan, and second, we characterize the optimal makespan when a single vehicle is utilized.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Ahmadi, J.H., Ahmadi, R.H., Dasu, S., Tang, C.S.: Batching and scheduling jobs on batch and discrete processors. Oper. Res. 40, 750–763 (1992)
Cheng, T.C.E., Wang, G.: Batching and scheduling to minimize the makespan in the two-machine flowshop. IIE Trans. 30, 447–453 (1998)
Franca, P.M., Gendreau, M., Laporte, G., Müller, F.M.: The \(m\)-traveling salesman problem with minmax objective. Transp. Sci. 29, 267–275 (1995)
Frederickson, G.N., Hecht, M.S., Kim, C.E.: Approximation algorithms for some routing problems. SIAM J. Comput. 7, 178–193 (1978)
McDonald, J.J.: Vehicle scheduling—a case study. Oper. Res. Q. (1970–1977) 23, 433–444 (1972)
Revere, L.: Re-engineering proves effective for reducing courier costs. Bus. Process Manag. J. 10, 400–414 (2004)
Williamson, D.P., Shmoys, D.B.: The Design of Approximation Algorithms, Page Numbers. Cambridge University Press, New York (2010)
Yücel, E., Salman F.S., Gel E.S., Örmeci, E.L., Gel, A.: Optimizing specimen collection for processing in clinical testing laboratories. Eur. J. Oper. Res. (2012, accepted)
Acknowledgments
The authors would like to thank the anonymous reviewers for their valuable comments and suggestions to improve the quality of the paper.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Yücel, E., Salman, F.S., Örmeci, E.L. et al. A constant-factor approximation algorithm for multi-vehicle collection for processing problem. Optim Lett 7, 1627–1642 (2013). https://doi.org/10.1007/s11590-012-0578-1
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11590-012-0578-1