In the minimum cost vertex–disjoint path cover problem (MCVDPCP), each vehicle serves customers directly from its location without having to start from or return to a depot. The aim of the MCVDPCP is to minimize the total vehicle travel cost without violating the vehicle capacity constraint and the maximum tour length. An application of the problem can be found in companies hiring freelance workers to serve customers to reduce operational costs. In this study, we propose a particle swarm optimization algorithm for solving the MCVDPCP with an aim at obtaining better results than the previous study.

In the minimum cost vertex–disjoint path cover problem (MCVDPCP), each vehicle serves customers directly from its location without having to start from or return to a depot. The aim of the MCVDPCP is to minimize the total vehicle travel cost without violating the vehicle capacity constraint and the maximum tour length. An application of the problem can be found in companies hiring freelance workers to serve customers to reduce operational costs. In this study, we propose a particle swarm optimization algorithm for solving the MCVDPCP with an aim at obtaining better results than the previous study.

Ai, T. J., & Kachitvichyanukul, V. (2009). Particle swarm optimization and two solution representations for solving the capacitated vehicle routing problem. Computers & Industrial Engineering, 56(1), 380-387. doi:10.1016/j.cie.2008.06.012
Augerat, P., Belenguer, J. M., Benavent, E., Corberan, A., Naddef, D., & Rinaldi, G. (1995). Computational Results with a Branch-and-Cut Code for the Capacitated Vehicle Routing Problem. Retrieved from Grenoble, France.
Autor, D. M. (2011). Securing the Pharmaceutical Supply Chain. Retrieved from http://www.fda.gov/NewsEvents/Testimony/ucm271073.htm
Baker, B. M., & Ayechew, M. A. (2003). A genetic algorithm for the vehicle routing problem. Computers & Operations Research, 30, 787–800.
Bell, J. E., & McMullen P. R. (2004). Ant colony optimization techniques for the vehicle routing problem. Advanced Engineering Informatics, 18, 41-48.
Berger, J., & Barkaoui, M. (2003). A new hybrid genetic algorithm for the capacitated vehicle routing problem. Journal of the Operational Research Society, 54, 1254–1262.
Brandao, J. (2004). A tabu search algorithm for the open vehicle routing problem. European Journal of Operational Research, 157(3), 552-564. doi:10.1016/S0377-2217(03)00238-8
Bullnheimer, R., Hartl, F., & Strauss, C. (1999). An improved ant system algorithm for the vehicle routing problem. Annals of Operations Research, 89, 319–328.
Chen, A. L., Yang, G. K., & Z.M, W. (2006). Hybrid discrete particle swarm optimization algorithm for capacitated vehicle routing problem. Journal of Zhejiang University SCIENCE A, 7(4), 607-614.
Christofides, N., Mingozzi, A., & Toth, P. (1979). Combinatorial Optimization. Chichester, UK: John Wiley & Sons.
Cordeau, J. F., Laporte, G., Savelsbergh, M. W. P., & Vigo, D. (2007). Vehicle RoutingHandbook in OR & MS (Vol. 14): Elsevier B. V.
Dantzig, G. B., & Ramser, J. H. (1959). The Truck Dispatching Problem. Management Science, 6(1), 80-91.
Engelbrecht, A. P. (2007). Computational Intelligence: An Introduction, 2nd Edition: John Wiley and Sons.
Fu, Z., Eglese, R. and Li, L.Y.O. (2005). A new tabu search heuristic for the open vehicle
routing problem. J. of the Opl Res. Soc., 56, 267–274.
Fu, Z., Eglese, R. and Li, L.Y.O. (2006). Corrigendum to ‘A new tabu search heuristic for
the open vehicle routing problem’. J. of the Opl Res. Soc., 57, 1018.
Gendreau, M., Hertz, A., & Laporte, G. (1994). A Tabu Search Heuristic for the Vehicle-Routing Problem. Management Science, 40(10), 1276-1290. doi:DOI 10.1287/mnsc.40.10.1276
Goksal, F. P., Karaoglan, I., & Altiparmak, F. (2013). A hybrid discrete particle swarm optimization for vehicle routing problem with simultaneous pickup and delivery. Computers & Industrial Engineering, 65(1), 39-53. doi:10.1016/j.cie.2012.01.005
Halim, C. (2015). Minimum Cost Vertex-Disjoint Path Cover Problem. (Master of Business Administration), National Taiwan University of Science and Technology, Taiwan.
Kennedy, J., & Eberhart, R. (1995). Particle swarm optimization. 1995 Ieee International Conference on Neural Networks Proceedings, Vols 1-6, 1942-1948. doi:Doi 10.1109/Icnn.1995.488968
Kim, B. I., & Son, S. J. (2012). A probability matrix based particle swarm optimization for the capacitated vehicle routing problem. Journal of Intelligent Manufacturing, 23(4), 1119-1126. doi:10.1007/s10845-010-0455-7
Kuckelhaus, M., & Terhoeven, M. (2013). Key Logistics Trends in Life Sciences 2020+. Retrieved from Germany:
Laporte, G. (1992). The Vehicle Routing Problem: an Overview of exact and approximate algorithms. European Journal of Operation Research, 59, 345-358.
Laporte, G., Nobert, Y., & Taillefer, S. (1987). A Branch-and-Bound Algorithm for the Asymmetrical Distance-Constrained Vehicle Routing Problem. Mathematical Modelling, 9(12), 857-868.
Lenstra, J. K., & Kan, A. H. G. (1981). Complexity of vehicle routing and scheduling problems. Networks, 11(221-227).
Letchford, A., Lysgaard, J., & Eglese, R. W. (2007). A branch-and-cut algorithm for the
capacitated open vehicle routing problem. Journal of Operation Research Society,
58, 1624–1651.
Li, F., Golden, B., and Wasil, E. (2006). The open vehicle routing problem: algorithms, large-scale test problems, and computational results. Computers & Operations Research, 37(4), 712-723.
Lin, C. H., Choy, K. L., Ho, G. T. S., Chung, S. H., & Lam, H. Y. (2014). Survey of Green Vehicle Routing Problem: Past and future trends. Expert Systems with Applications, 41(4), 1118-1138. doi:10.1016/j.eswa.2013.07.107
Marinakis, Y., Marinaki, M., & Dounias, G. (2010). A hybrid particle swarm optimization algorithm for the vehicle routing problem. Engineering Applications of Artificial Intelligence, 23, 463–472.
MirHassani, S. A., & Abolghasemi, N. (2011). A particle swarm optimization algorithm for open vehicle routing problem. Expert Systems with Applications, 38(9), 11547-11551. doi:10.1016/j.eswa.2011.03.032
Osman, I. H. (1993). Metastrategy Simulated Annealing and Tabu Search Algorithms for the Vehicle Routing Problem. Annals of Operation Research, 41, 421-451.
Repoussis, P., Tarantilis, C., & Ioannou, G. (2007). An Evolutionary Algorithm for the Open Vehicle Routing Problem with Time Windows. In Pereira, F. Baptista, Tavares, & Jorge (Eds.), Bio-inspired Algorithms for the Vehicle Routing Problem: Springer.
Sariklis, D., & Powell, S. (2000). A heuristic method for the open vehicle routing problem. Journal of the Operational Research Society, 51(5), 564-573.
Sariklis, D., & Powell, S. (2007). A heuristic method for the open vehicle routing
problem. Journal of Operation Research Society, 51, 355–367.
Syslo, M. M., Deo, N., & Kowalik, J. S. (1983). Discrete optimization algorithms: with pascal programs.: Courier Dover Publications.
Toth, V., & Vigo, D. (2002). The Vehicle Routing Problem: Society for Industrial and Applied Mathematics.
Xu, S. H., Liu, J. P., Zhang, F. H., Wang, L., & Sun, L. J. (2015). A Combination of Genetic Algorithm and Particle Swarm Optimization for Vehicle Routing Problem with Time Windows. Sensors, 15.