This study presents a variant of the capacitated vehicle routing problem (CVRP), namely, the minimum cost vertex-disjoint path cover problem (MCVDPCP). In contrast to CVRP in which the vehicles start and end at the depot, vehicle routes in MCVDPCP involve a set of vertex-disjoint paths where a vehicle starts at a particular customer and finishes at another customer. Thus, MCVDPCP is defined to find a set of service paths to serve a set of customers with known geographical locations and demands; it aims to minimize the total of vehicle travel cost and vehicle activation cost. A hybrid approach that integrates variable neighborhood search (VNS) and tabu search (TS) is developed to solve the aforementioned problem. This algorithm presents the new concept of exploring a neighborhood solution by utilizing multi-neighborhood sets and applying the systematic changing neighborhood of VNS to modify a neighborhood set. TS is also incorporated into the algorithm to guide the search toward diverse regions. The proposed algorithm is tested on 14 instances of MCVDPCP, which are generated from well-known CVRP benchmark instances. Results indicate that the proposed algorithm efficiently solves MCVDPCP. Furthermore, a numerical experiment is performed on the problem using Taipei as the case study and considering the effects of vehicle capacity, maximum route duration, and demand variability.

This study presents a variant of the capacitated vehicle routing problem (CVRP), namely, the minimum cost vertex-disjoint path cover problem (MCVDPCP). In contrast to CVRP in which the vehicles start and end at the depot, vehicle routes in MCVDPCP involve a set of vertex-disjoint paths where a vehicle starts at a particular customer and finishes at another customer. Thus, MCVDPCP is defined to find a set of service paths to serve a set of customers with known geographical locations and demands; it aims to minimize the total of vehicle travel cost and vehicle activation cost. A hybrid approach that integrates variable neighborhood search (VNS) and tabu search (TS) is developed to solve the aforementioned problem. This algorithm presents the new concept of exploring a neighborhood solution by utilizing multi-neighborhood sets and applying the systematic changing neighborhood of VNS to modify a neighborhood set. TS is also incorporated into the algorithm to guide the search toward diverse regions. The proposed algorithm is tested on 14 instances of MCVDPCP, which are generated from well-known CVRP benchmark instances. Results indicate that the proposed algorithm efficiently solves MCVDPCP. Furthermore, a numerical experiment is performed on the problem using Taipei as the case study and considering the effects of vehicle capacity, maximum route duration, and demand variability.

Ai, T. J., & Kachitvichyanukul, V. (2009). Particle swarm optimization and two solution representations for solving the capacitated vehicle routing problem. Comput. Ind. Eng., 56(1), 380-387. doi: 10.1016/j.cie.2008.06.012
Belhaiza, S., Hansen, P., & Laporte, G. (2014). A hybrid variable neighborhood tabu search heuristic for the vehicle routing problem with multiple time windows. Computers & Operations Research, 52, 269-281. doi: 10.1016/j.cor.2013.08.010
Brandão, 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, B., Hartl, R. F., & Strauss, C. (1999). An improved ant System algorithm for thevehicle Routing Problem. Annals of Operations Research, 89, 319-328.
Christofides, N., Mingozzi, A., & Toth, P. (1979). Combinatorial Optimization. Chichester, UK: John Wiley & Sons.
Clarke, G., & Wright, J. W. (1964). Scheduling of Vehicles from a Central Depot to a Number of Delivery Points. Operations Research, 12(4), 568-581. doi: doi:10.1287/opre.12.4.568
Cordeau, J.-F., Gendreau, M., Hertz, A., Laporte, G., & Sormany, J.-S. (2005). New heuristics for the vehicle routing problem: Springer.
Cordeau, J.-F., & Laporte, G. (2001). A tabu search algorithm for the site dependent vehicle routing problem with time windows. Infor, 39(3), 292-298.
Cordeau, J.-F., Laporte, G., & Mercier, A. (2001). A unified tabu search heuristic for vehicle routing problems with time windows. Journal of the Operational Research Society, 52(8), 928-936.
Cordeau, J.-F., Laporte, G., Savelsbergh, M. W. P., & Vigo, D. (2007). Chapter 6 Vehicle Routing. 14, 367-428. doi: 10.1016/s0927-0507(06)14006-2
Cordeau, J.-F., & Maischberger, M. (2012). A parallel iterated tabu search heuristic for vehicle routing problems. Computers & Operations Research, 39(9), 2033-2050. doi: 10.1016/j.cor.2011.09.021
Dantzig, G. B., & Ramser, J. H. (1959). The Truck Dispatching Problem.
Dhahri, A., Zidi, K., & Ghedira, K. (2014). Variable Neighborhood Search based Set Covering ILP Model for the Vehicle Routing Problem with Time Windows. Procedia Computer Science, 29, 844-854. doi: 10.1016/j.procs.2014.05.076
Escobar, J. W., Linfati, R., Baldoquin, M. G., & Toth, P. (2014). A Granular Variable Tabu Neighborhood Search for the capacitated location-routing problem. Transportation Research Part B-Methodological, 67, 344-356. doi: DOI 10.1016/j.trb.2014.05.014
Eskandarpour, M., Nikbakhsh, E., & Zegordi, S. H. (2014). Variable neighborhood search for the bi-objective post-sales network design problem: A fitness landscape analysis approach. Computers & Operations Research, 52, 300-314. doi: 10.1016/j.cor.2013.06.002
Favaretto, D., Moretti, E., & Pellegrini, P. (2007). Ant colony system for a VRP with multiple time windows and multiple visits. Journal of Interdisciplinary Mathematics, 10(2), 263-284. doi: 10.1080/09720502.2007.10700491
Fisher, M. L., & Jaikumar, R. (1981). A generalized assignment heuristic for vehicle routing. Networks, 11(2), 109-124.
Fung, R. Y., Liu, R., & Jiang, Z. (2013). A memetic algorithm for the open capacitated arc routing problem. Transportation Research Part E: Logistics and Transportation Review, 50, 53-67.
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
Gendreau, M., Laporte, G., Musaraganyi, C., & Taillard, E. D. (1999). A tabu search heuristic for the heterogeneous fleet vehicle routing problem. Computers & Operations Research, 26(12), 1153-1173. doi: Doi 10.1016/S0305-0548(98)00100-2
Gillett, B. E., & Miller, L. R. (1974). A Heuristic Algorithm for the Vehicle-Dispatch Problem. Operations Research, 22(2), 340-349. doi: doi:10.1287/opre.22.2.340
Glover, F. (1986). Future paths for integer programming and links to artificial intelligence. Computers & Operations Research, 13(5), 533-549.
Glover, F., & Laguna, M. (2007). Principles of tabu search.
Hansen, P., & Mladenovic, N. (2001). Variable neighborhood search: Principles and applications. European Journal of Operational Research, 130(3), 449-467. doi: Doi 10.1016/S0377-2217(00)00100-4
Ho, S. C., & Gendreau, M. (2006). Path relinking for the vehicle routing problem. Journal of heuristics, 12(1-2), 55-72.
Jarboui, B., Derbel, H., Hanafi, S., & Mladenović, N. (2013). Variable neighborhood search for location routing. Computers & Operations Research, 40(1), 47-57. doi: 10.1016/j.cor.2012.05.009
Kocatürk, F., & Özpeynirci, Ö. (2014). Variable neighborhood search for the pharmacy duty scheduling problem. Computers & Operations Research, 51, 218-226. doi: 10.1016/j.cor.2014.06.001
Kytöjoki, J., Nuortio, T., Bräysy, O., & Gendreau, M. (2007). An efficient variable neighborhood search heuristic for very large scale vehicle routing problems. Computers & Operations Research, 34(9), 2743-2757.
Laporte, G. (1992). The vehicle routing problem: An overview of exact and approximate algorithms. European Journal of Operational Research, 59(3), 345-358.
Laporte, G. (2007). What you should know about the vehicle routing problem. Naval Research Logistics, 54(8), 811-819. doi: 10.1002/nav.20261
Li, F., Golden, B., & Wasil, E. (2007). The open vehicle routing problem: Algorithms, large-scale test problems, and computational results. Computers & Operations Research, 34(10), 2918-2930. doi: 10.1016/j.cor.2005.11.018
Li, J.-q., Pan, Q.-k., & Liang, Y.-C. (2010). An effective hybrid tabu search algorithm for multi-objective flexible job-shop scheduling problems. Computers & Industrial Engineering, 59(4), 647-662. doi: 10.1016/j.cie.2010.07.014
Li, J.-q., Pan, Q.-k., & Wang, F.-t. (2014). A hybrid variable neighborhood search for solving the hybrid flow shop scheduling problem. Applied Soft Computing, 24, 63-77. doi: 10.1016/j.asoc.2014.07.005
Lin, C., 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
Lin, S.-W., Vincent, F. Y., & Chou, S.-Y. (2009). Solving the truck and trailer routing problem based on a simulated annealing heuristic. Computers & Operations Research, 36(5), 1683-1692.
Mester, D., & Bräysy, O. (2007). Active-guided evolution strategies for large-scale capacitated vehicle routing problems. Computers & Operations Research, 34(10), 2964-2975.
Mladenovic, N., & Hansen, P. (1997). Variable neighborhood search. Computers & Operations Research, 24(11), 1097-1100. doi: Doi 10.1016/S0305-0548(97)00031-2
Osman, I. (1993). Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem. Annals of Operations Research, 41(4), 421-451. doi: 10.1007/BF02023004
Peng, B., Lü, Z., & Cheng, T. C. E. (2015). A tabu search/path relinking algorithm to solve the job shop scheduling problem. Computers & Operations Research, 53, 154-164. doi: http://dx.doi.org/10.1016/j.cor.2014.08.006
Pirim, H., Eksioglu, B., & Bayraktar, E. (2008). Tabu Search: a comparative study: INTECH Open Access Publisher.
Pisinger, D., & Ropke, S. (2007). A general heuristic for vehicle routing problems. Computers & Operations Research, 34(8), 2403-2435.
Potvin, J.-Y., & Naud, M.-A. (2011). Tabu search with ejection chains for the vehicle routing problem with private fleet and common carrier. Journal of the Operational Research Society, 62(2), 326-336.
Rego, C., & Roucairol, C. (1996). A Parallel Tabu Search Algorithm Using Ejection Chains for the Vehicle Routing Problem. In I. Osman & J. Kelly (Eds.), Meta-Heuristics (pp. 661-675): Springer US.
Rochat, Y., & Taillard, É. D. (1995). Probabilistic diversification and intensification in local search for vehicle routing. Journal of heuristics, 1(1), 147-167.
Sariklis, D., & Powell, S. (2000). A heuristic method for the open vehicle routing problem. Journal of the Operational Research Society, 51(5), 564-573.
Syslo, M. M., Deo, N., & Kowalik, J. S. (1983). Discrete optimization algorithms: with pascal programs: Courier Dover Publications.
Szeto, W. Y., Wu, Y., & Ho, S. C. (2011). An artificial bee colony algorithm for the capacitated vehicle routing problem. European Journal of Operational Research, 215(1), 126-135. doi: 10.1016/j.ejor.2011.06.006
Taillard, É. (1993). Parallel iterative search methods for vehicle routing problems. Networks, 23(8), 661-673.
Tao, Y., & Wang, F. (2015). An effective tabu search approach with improved loading algorithms for the 3L-CVRP. Computers & Operations Research, 55, 127-140. doi: http://dx.doi.org/10.1016/j.cor.2013.10.017
Ting, C.-K., Li, S.-T., & Lee, C. (2003). On the harmonious mating strategy through tabu search. Information Sciences, 156(3-4), 189-214. doi: 10.1016/s0020-0255(03)00176-2
Toth, P., & Vigo, D. (2002). The vehicle routing problem. Philadelphia: Society for Industrial and Applied Mathematics.
Wassan, N. A., & Osman, I. H. (2002). Tabu search variants for the mix fleet vehicle routing problem. Journal of the Operational Research Society, 768-782.
Wei, L., Zhang, Z., Zhang, D., & Lim, A. (2015). A variable neighborhood search for the capacitated vehicle routing problem with two-dimensional loading constraints. European Journal of Operational Research. doi: 10.1016/j.ejor.2014.12.048
Xia, W., & Wu, Z. (2005). An effective hybrid optimization approach for multi-objective flexible job-shop scheduling problems. Computers & Industrial Engineering, 48(2), 409-425. doi: http://dx.doi.org/10.1016/j.cie.2005.01.018
Xu, J., & Kelly, J. P. (1996). A network flow-based tabu search heuristic for the vehicle routing problem. Transportation Science, 30(4), 379-393.
Yu, S., Ding, C., & Zhu, K. (2011). A hybrid GA–TS algorithm for open vehicle routing optimization of coal mines material. Expert Systems with Applications, 38(8), 10568-10573. doi: http://dx.doi.org/10.1016/j.eswa.2011.02.108
Yurtkuran, A., & Emel, E. (2010). A new hybrid electromagnetism-like algorithm for capacitated vehicle routing problems. Expert Systems with Applications, 37(4), 3427-3433.
Zhang, G., Shao, X., Li, P., & Gao, L. (2009). An effective hybrid particle swarm optimization algorithm for multi-objective flexible job-shop scheduling problem. Computers & Industrial Engineering, 56(4), 1309-1318. doi: http://dx.doi.org/10.1016/j.cie.2008.07.021