The Many-to-Many Vehicle Routing Problem with Cross-Docking
by Amalia Nikolopoulou, PhD, Research Fellow
In practical logistics applications, it is common for retailers located in urban areas to replenish their stock by receiving goods from multiple production warehouses located around the city limits. This situation emerges when a retailer receives different types of products from the same logistics provider, and not all of them are available at a single supplier location. Cross-docking is an alternative distribution strategy to typical warehousing distribution that regulates the flow of products from origins (production warehouses) to destinations (retailers), by maintaining little or no inventory at intermediated facilities called cross-docks. This is achieved via cargo consolidation operations with the potential of significant cost savings. Furthermore, the single visit requirement at the supplier and customer nodes is usually essential in practice to minimize the administrative, handling, and various types of setup costs and times (Tarantilis et al., 2011). Finally, recent pro-environmental city logistics initiatives are aligned with the use of cargo consolidation operations outside urban areas, in pursuit of dispatching lighter, greener, or even electric vehicles in the city to minimize the impact on the urban environment (Zachariadis et al., 2015).
A new generalized vehicle routing problem with cross-docking (VRPCD) has been introduced. Relevant studies in the VRPCD literature assume that every supplier is connected with only one customer (one-to-one VRPCD), while in most cases a common homogeneous fleet of vehicles is used for both inbound and outbound routes. Contrary, in the examined problem a many-to-many relationship between the suppliers and customers is considered, while different vehicle fleets are used to perform the pickup and delivery routes. An Adaptive Memory Programming method (Gounaris et al., 2014) has been developed to solve large instances found in practical applications. Key characteristic is the mechanism for identifying and selecting elite components from the reference solutions. Particularly, the proposed mechanism assigns scores to all possible subroutes with varying length and gradually selects those with the highest score in terms of solution cost or diversity. A Tabu Search algorithm coupled with new long term memory structures is applied as the main optimization block for improving the quality of the new provisional solutions generated throughout the search process. Using well-known benchmark data sets for the one-to-one VRPCD, the proposed method proved to be efficient and effective compared to the current state-of-the-art. Furthermore, new best solutions have been found, while the method scaled well with the problem size.
The proposed method has also been tested on new data sets with diverse features regarding the geographic distribution of the network nodes as well as the density of supplier-customer links. This set of results provided several new insights regarding the effect of these features on the total transportation costs. For example, the solution costs increased as the supplier-customer connection density increased. On the other hand, the solution costs decreased as the geographic distribution became more clustered and in particular for all cases with supplier participation ratio less than 30%. As far as the possibility of splitting requests is concerned, better -on average - costs were observed when the single visit requirement at each location was relaxed. More specifically, significant savings were observed when splitting of requests was allowed within clustered geographic distributions and high supplier participation ratio. Finally, more split requests were observed for the cases where supplier and customers were randomly distributed in a geographic region with large supplier-customer connection density.
Gounaris CE, Repoussis PP, Tarantilis CD, Wiesemann W and Floudas C (2014) An adaptive memory programming framework for the robust capacitated vehicle routing problem. Transportation Science (Article in Advance) http://dx.doi.org/10.1287/trsc.2014.0559.
Tarantilis CD, Stauropoulou F and Repoussis PP (2011) A template-based tabu search algorithm for the consistent vehicle routing problem. Expert Systems with Applications 39(4):4233-4239.
Zachariadis EE, Tarantilis CD and Kiranoudis CT (2015) The load-dependent vehicle routing problem and its pick-up and delivery extension. Transportation Research Part B: Methodological 71:158-18.
M A N A G E M E N T S C I E N C E L A B O R A T O R Y