Multi-commodity demand fulfillment via simultaneous pickup and delivery for a fast fashion retailer

Abstract

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.