Abstract: The vehicle routing problem (VRP) is a well-known combinatorial optimization issue in transportation and logistics network systems. There exist several limitations associated with the traditional VRP. Releasing the restricted conditions of traditional VRP has become a research focus in the past few decades. The vehicle routing problem with split deliveries and pickups (VRPSPDP) is particularly proposed to release the constraints on the visiting times per customer and vehicle capacity, that is, to allow the deliveries and pickups for each customer to be simultaneously split more than once. Few studies have focused on the VRPSPDP problem. In this paper we propose a two-stage heuristic method integrating the initial heuristic algorithm and hybrid heuristic algorithm to study the VRPSPDP problem. To validate the proposed algorithm, solomon benchmark datasets and extended solomon benchmark datasets were modified to compare with three other popular algorithms. A total of 18 datasets were used to evaluate the effectiveness of the proposed method. The computational results indicated that the proposed algorithm is superior to these three algorithms for VRPSPDP in terms of total travel cost and average loading rate.

求解集送货可拆分车辆路径问题的两阶段启发式方法

[1]Ai, T.J., Kachitvichyanukul, V., 2009. A particle swarm optimization for the vehicle routing problem with simultaneous pickup and delivery. Comput. Oper. Res., 36(5):1693-1702.

[2]Archetti, C., Savelsbergh, M.W.P., Speranza, M.G., 2008. To split or not to split: that is the question. Transp. Res. PT E-Logist. Transp., 44(1):114-123.

[3]Baldacci, R., Toth, P., Vigo, D., 2010. Exact algorithms for routing problems under vehicle capacity constraints. Ann. Oper. Res., 175(1):213-245.

[4]Çatay, B., 2010. A new saving-based ant algorithm for the vehicle routing problem with simultaneous pickup and delivery. Expert Syst. Appl., 37(10):6809-6817.

[5]Chen, A.L., Yang, G.K., Wu, Z.M., 2006. Hybrid discrete particle swarm optimization algorithm for capacitated vehicle routing problem. J. Zhejiang Univ.-Sci. A, 7(4):607-614.

[6]Chen, J.F., Wu, T.H., 2006. Vehicle routing problem with simultaneous deliveries and pickups. J. Oper. Res. Soc., 57(5):579-587.

[7]Chepuri, K., Homem-de-Mello, T., 2005. Solving the vehicle routing problem with stochastic demands using the cross-entropy method. Ann. Oper. Res., 134(1):153-181.

[8]de Oliveira, H.C.B., Vasconcelos, G.C., 2010. A hybrid search method for the vehicle routing problem with time windows. Ann. Oper. Res., 180(1):125-144.

[9]Dror, M., Trudeau, P., 1989. Savings by split delivery routing. Transp. Sci., 23(2):141-145.

[10]Gajpal, Y., Abad, P., 2009. An ant colony system (ACS) for vehicle routing problem with simultaneous delivery and pickup. Comput. Oper. Res., 36(12):3215-3223.

[11]Gulczynski, D., Golden, B., Wasil, E., 2010. The split delivery vehicle routing problem with minimum delivery amounts. Transp. Res. PT E-Logist. Transp., 46(5):612-626.

[12]Hennig, F., Nygreen, B., Christiansen, M., et al., 2012. Maritime crude oil transportation—a split pickup and split delivery problem. Eur. J. Oper. Res., 218(3):764-774.

[13]Ho, S.C., Haugland, D., 2004. A tabu search heuristic for vehicle routing problem with time windows and split deliveries. Comput. Oper. Res., 31(12):1947-1964.

[14]Hoff, A., Gribkovskaia, I., Laporte, G., et al., 2009. Lasso solution strategies for the vehicle routing problem with pickups and deliveries. Eur. J. Oper. Res., 192(3):755-766.

[15]Jin, M.Z., Liu, K., Bowden, R.O., 2007. A two-stage algorithm with valid inequalities for the split delivery vehicle routing problem. Int. J. Prod. Econ., 105(1):228-242.

[16]Lambert, S., Riopel, D., Abdul-Kader, W., 2011. A reverse logistics decisions conceptual framework. Comput. Ind. Eng., 61(3):561-581.

[17]Lee, C.G., Epelman, M.A., White, C.C.III, et al., 2006. A shortest path approach to the multiple-vehicle routing problem with pick-ups. Transp. Res. PT B-Method., 40(4):265-284.

[18]Li, J.X., Chu, F., Chen, H.X., 2011. Coordination of split deliveries in one-warehouse multi-retailer distribution systems. Comput. Ind. Eng., 60(2):291-301.

[19]Liu, R., Xie, X.L., Augusto, V., et al., 2013. Heuristic algorithms for a vehicle routing problem with simultaneous delivery and pickup and time windows in home health care. Eur. J. Oper. Res., 230(3):475-486.

[20]Mitra, S., 2005. An algorithm for the generalized vehicle routing problem with backhauling. Asia Pac. J. Oper. Res., 22(2):153-169.

[21]Mitra, S., 2008. A parallel clustering technique for the vehicle routing problem with split deliveries and pickups. J. Oper. Res. Soc., 59(11):1532-1546.

[22]Montané, F.A.T., Galvão, R.D., 2006. A tabu search algorithm for the vehicle routing problem with simultaneous pick-up and delivery service. Comput. Oper. Res., 33(3):595-619.

[23]Moreno, L., de Aragão, M.P., Uchoa, E., 2010. Improved lower bounds for the split delivery vehicle routing problem. Oper. Res. Lett., 38(4):302-306.

[24]Mullaseril, P.A., Dror, M., Leung, J., 1997. Split-delivery routing heuristics in livestock feed distribution. J. Oper. Res. Soc., 48(2):107-116.

[25]Nanry, W.P., Barnes, J.W., 2000. Solving the pickup and delivery problem with time windows using reactive tabu search. Transp. Res. PT B-Method., 34(2):107-121.

[26]Nowak, M., Ergun, O., White, C.C.III, 2009. An empirical study on the benefit of split loads with the pickup and delivery problem. Eur. J. Oper. Res., 198(3):734-740.

[27]Özdamar, L., Demir, O., 2012. A hierarchical clustering and routing procedure for large scale disaster relief logistics planning. Transp. Res. PT E-Logist. Transp., 48(3):591-602.

[28]Rieck, J., Zimmermann, J., 2010. A new mixed integer linear model for a rich vehicle routing problem with docking constraints. Ann. Oper. Res., 181(1):337-358.

[29]Saberi, M., Verbas, İ.Ö., 2012. Continuous approximation model for the vehicle routing problem for emissions minimization at the strategic level. J. Transp. Eng., 138(11):1368-1376.

[30]Sheu, J.B., 2006. A novel dynamic resource allocation model for demand-responsive city logistics distribution operations. Transp. Res. PT E-Logist. Transp., 42(6):445-472.

[31]Sheu, J.B., 2008. Green supply chain management, reverse logistics and nuclear power generation. Transp. Res. PT E-Logist. Transp., 44(1):19-46.

[32]Solomon, M.M., 1987. Algorithms for the vehicle routing and scheduling problems with time window constraints. Oper. Res., 35(2):254-265.

[33]Subramanian, A., Drummond, L.M.A., Bentes, C., et al., 2010. A parallel heuristic for the vehicle routing problem with simultaneous pickup and delivery. Comput. Oper. Res., 37(11):1899-1911.

[34]Subramanian, A., Uchoa, E., Pessoa, A.A., et al., 2011. Branch-and-cut with lazy separation for the vehicle routing problem with simultaneous pickup and delivery. Oper. Res. Lett., 39(5):338-341.

[35]Wang, H.F., Chen, Y.Y., 2012. A genetic algorithm for the simultaneous delivery and pickup problems with time window. Comput. Ind. Eng., 62(1):84-95.

[36]Wang, Y., Ma, X.L., Wang, Y.H., et al., 2012. Location optimization of multiple distribution centers under fuzzy environment. J. Zhejiang Univ.-Sci. A (Appl. Phys. & Eng.), 13(10):782-798.

[37]Wang, Y., Ma, X.L., Lao, Y.T., et al., 2013. Vehicle routing problem: simultaneous deliveries and pickups with split loads and time windows. J. Transp. Res. Board, 2378:120-128.

[38]Wang, Y., Ma, X.L., Lao, Y.T., et al., 2014. A fuzzy-based customer clustering approach with hierarchical structure for logistics network optimization. Expert Syst. Appl., 41(2):521-534.

[39]Zhang, T., Chaovalitwongse, W.A., Zhang, Y.J., 2012. Scatter search for the stochastic travel-time vehicle routing problem with simultaneous pick-ups and deliveries. Comput. Oper. Res., 39(10):2277-2290.