×

Multi-commodity demand fulfillment via simultaneous pickup and delivery for a fast fashion retailer. (English) Zbl 1458.90157

Summary: This study addresses a multi-commodity many-to-many vehicle routing problem with simultaneous pickup and delivery (M-M-VRPSPD) for a fast fashion retailer in Singapore. Different from other widely studied pickup and delivery problems, the unique characteristics are: (1) collected products from customers are encouraged to be reallocated to fulfill demands of other customers; (2) it is multi-commodity and the number of involved commodities can be over 10,000. To solve this problem, we provide a nonvehicle-index arc-flow formulation and some strengthening strategies. Moreover, for large-scale instances, an adaptive memory programming based algorithm combined with techniques such as the regret insertion method for initializing the solution pool, the segment-based evaluation scheme, and advanced pool management method, is proposed. We test our algorithm on 66 real-world and 96 newly generated instances, and provide the results for future-use comparisons. The experiments on small-scale instances show that the proposed algorithm can quickly reach the optimality obtained by solving the mathematical formulation. In addition, the proposed algorithm is shown to perform well and stably on medium and large scale instances. Finally, we analyze some features of this problem, and find that relocation of commodities increases their utilization.

MSC:

90B06 Transportation, logistics and supply chain management
90C27 Combinatorial optimization
90C59 Approximation methods and heuristics in mathematical programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Abernathy, F. H.; Dunlop, J. T.; Hammond, J. H.; Weil, D., A Stitch in Time: Lean Retailing and the Transformation of Manufacturing-Lessons from the Apparel and Textile Industries, (1999), Oxford University Press
[2] Baldacci, R.; Bartolini, E.; Mingozzi, A., An exact algorithm for the pickup and delivery problem with time windows, Oper. Res., 59, 2, 414-426, (2011) · Zbl 1233.90058
[3] Benchimol, M.; Benchimol, P.; Chappert, B.; De La Taille, A.; Laroche, F.; Meunier, F.; Robinet, L., Balancing the stations of a self service “bike hire” system, RAIRO Oper. Res., 45, 01, 37-61, (2011) · Zbl 1222.90073
[4] Berbeglia, G.; Cordeau, J.-F.; Gribkovskaia, I.; Laporte, G., Static pickup and delivery problems: a classification scheme and survey, TOP, 15, 1, 1-31, (2007) · Zbl 1121.90001
[5] Bräysy, O., A reactive variable neighborhood search for the vehicle-routing problem with time windows, INFORMS J. Comput., 15, 4, 347-368, (2003) · Zbl 1238.90136
[6] Caro, F.; Martínez-de Albéniz, V., Fast fashion: business model overview and research opportunities, Retail Supply Chain Management, 237-264, (2015), Springer
[7] Chang, P.-C.; Huang, W.-H.; Zhang, Z.-Z., A puzzle-based genetic algorithm with block mining and recombination heuristic for the traveling salesman problem, J. Comput. Sci. Technol., 27, 5, 937-949, (2012)
[8] Chemla, D.; Meunier, F.; Calvo, R. W., Bike sharing systems: solving the static rebalancing problem, Discret. Optim., 10, 2, 120-146, (2013) · Zbl 1284.90040
[9] Dell’Amico, M.; Righini, G.; Salani, M., A branch-and-price approach to the vehicle routing problem with simultaneous distribution and collection, Transp. Sci., 40, 2, 235-247, (2006)
[10] Diana, M.; Dessouky, M. M., A new regret insertion heuristic for solving large-scale dial-a-ride problems with time windows, Transp. Res. Part B: Methodol., 38, 6, 539-557, (2004)
[11] Fredman, M. L.; Tarjan, R. E., Fibonacci heaps and their uses in improved network optimization algorithms, J. ACM, 34, 3, 596-615, (1987)
[12] Hansen, P.; Mladenovic, N., Variable neighborhood search : principles and applications, Eur. J. Oper. Res., 130, 3, 449-467, (2001) · Zbl 0981.90063
[13] Hernández-Pérez, H.; Rodríguez-Martín, I.; Salazar-González, J.-J., A hybrid heuristic approach for the multi-commodity pickup-and-delivery traveling salesman problem, Eur. J. Oper. Res., 251, 1, 44-52, (2016) · Zbl 1346.90124
[14] Hernández-Pérez, H.; Salazar-González, J.-J., A branch-and-cut algorithm for a traveling salesman problem with pickup and delivery, Discret. Appl. Math., 145, 1, 126-139, (2004) · Zbl 1058.90054
[15] Hernández-Pérez, H.; Salazar-González, J.-J., Heuristics for the one-commodity pickup-and-delivery traveling salesman problem, Transp. Sci., 38, 2, 245-255, (2004)
[16] Hernández-Pérez, H.; Salazar-González, J.-J., The one-commodity pickup-and-delivery traveling salesman problem: inequalities and algorithms, Networks, 50, 4, 258-272, (2007) · Zbl 1146.90056
[17] Hernández-Pérez, H.; Salazar-González, J.-J., The multi-commodity pickup-and-delivery traveling salesman problem, Networks, 63, 1, 46-59, (2014) · Zbl 1338.90340
[18] Imran, A.; Salhi, S.; Wassan, N. A., A variable neighborhood-based heuristic for the heterogeneous fleet vehicle routing problem, Eur. J. Oper. Res., 197, 2, 509-518, (2009) · Zbl 1159.90525
[19] Lim, A.; Zhang, Z.; Qin, H., Pickup and delivery service with manpower planning in hong kong public hospitals, Transp. Sci., 51, 2, 688-705, (2017)
[20] Lu, Q.; Dessouky, M., An exact algorithm for the multiple vehicle pickup and delivery problem, Transp. Sci., 38, 4, 503-514, (2004)
[21] Mladenović, N.; Urošević, D.; Ilić, A., A general variable neighborhood search for the one-commodity pickup-and-delivery travelling salesman problem, Eur. J. Oper. Res., 220, 1, 270-285, (2012) · Zbl 1253.90200
[22] Montané, F. A.T.; Galvão, R. D., A tabu search algorithm for the vehicle routing problem with simultaneous pick-up and delivery service, Comput. Oper. Res., 33, 3, 595-619, (2006) · Zbl 1077.90058
[23] Raviv, T.; Tzur, M.; Forma, I. A., Static repositioning in a bike-sharing system: models and solution approaches, EURO J. Transp. Logist., 2, 3, 187-229, (2013)
[24] Rochat, Y.; Taillard, E. D., Probabilistic diversification and intensification in local search for vehicle routing, J. Heuristics, 1, 1, 147-167, (1995) · Zbl 0857.90032
[25] Ropke, S.; Pisinger, D., An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows, Transp. Sci., 40, 4, 455-472, (2006)
[26] Salhi, S.; Nagy, G., A cluster insertion heuristic for single and multiple depot vehicle routing problems with backhauling, J. Oper. Res. Soc., 50, 10, 1034-1042, (1999) · Zbl 1054.90523
[27] Stenger, A.; Vigo, D.; Enz, S.; Schwind, M., An adaptive variable neighborhood search algorithm for a vehicle routing problem arising in small package shipping, Transp. Sci., 47, 1, 64-80, (2012)
[28] Subramanian, A.; Uchoa, E.; Ochi, L. S., A hybrid algorithm for a class of vehicle routing problems, Comput. Oper. Res., 40, 10, 2519-2531, (2013) · Zbl 1348.90132
[29] Subramanian, A.; Uchoa, E.; Pessoa, A. A.; Ochi, L. S., Branch-and-cut with lazy separation for the vehicle routing problem with simultaneous pickup and delivery, Oper. Res. Lett., 39, 5, 338-341, (2011) · Zbl 1235.90040
[30] Vidal, T.; Crainic, T. G.; Gendreau, M.; Lahrichi, N.; Rei, W.; Vehicle, P.; Problems, R., A hybrid genetic algorithm for multidepot and periodic vehicle routing problems, Oper. Res., 60, 3, 611-624, (2012) · Zbl 1260.90058
[31] Vidal, T.; Crainic, T. G.; Gendreau, M.; Prins, C., A unified solution framework for multi-attribute vehicle routing problems, Eur. J. Oper. Res., 234, 3, 658-673, (2014) · Zbl 1304.90004
[32] Zachariadis, E. E.; Kiranoudis, C. T., An open vehicle routing problem metaheuristic for examining wide solution neighborhoods, Comput. Oper. Res., 37, 12, 712-723, (2010) · Zbl 1175.90052
[33] Zachariadis, E. E.; Tarantilis, C. D.; Kiranoudis, C. T., A hybrid metaheuristic algorithm for the vehicle routing problem with simultaneous delivery and pick-up service, Expert Syst. Appl., 36, 2, 1070-1081, (2009)
[34] Zachariadis, E. E.; Tarantilis, C. D.; Kiranoudis, C. T., An adaptive memory methodology for the vehicle routing problem with simultaneous pick-ups and deliveries, Eur. J. Oper. Res., 202, 2, 401-411, (2010) · Zbl 1175.90345
[35] Zhang, Z.; Liu, M.; Lim, A., A memetic algorithm for the patient transportation problem, Omega (Westport), 54, 60-71, (2015)
[36] Zhang, Z.; Wei, L.; Lim, A., An evolutionary local search for the capacitated vehicle routing problem minimizing fuel consumption under three-dimensional loading constraints, Transp. Res. Part B: Methodol., 82, 20-35, (2015)
[37] Zhao, F.; Li, S.; Sun, J.; Mei, D., Genetic algorithm for the one-commodity pickup-and-delivery traveling salesman problem, Comput. Ind. Eng., 56, 4, 1642-1648, (2009)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.