Loading and vehicle routing problem with cross-docking: a mathematical formulation

A lot of pressure is put on logistic distribution system in order to satisfy highly impatient customers that expect, if not require, fast deliveries. The supply chain should be reactive on one hand, but also keep costs as low as possible. One way of achieving this goal is to make use of cross-docking, which is a technique that aims at reducing inventory and picking costs and shortening the shipping cycle.

Cross-docks differ from standard distribution centers by having no inventory, but allowing for goods consolidation between the suppliers and the customers. Cross-docking comes initially from industry, and it seems that Wal-Mart was one of the first retailers to implement this technique in the late 1980s. In more detail, the cross-docking system is composed of a network of locations, associated to suppliers and customers, as well as a (set of) cross-dock facility(ies). Inbound trucks collect goods from the suppliers, and bring them back to a cross-dock where they are unloaded at an input dock. Goods are then sorted and consolidated according to their destination. Next, the goods are loaded into outbound trucks at an output dock, and the trucks then deliver them to the customers.

While many aspects of the cross-docking may be optimized, we focus here on the routing and loading aspects. Over the past 15 years, many papers studied the Capacitated Vehicle Routing Problem with Cross-Docking (CVRP-CD). Basically, the VRP-CD can be seen as two interdependent VRPs (one for the suppliers and one for the customers) with temporal constraints associated to the goods arrival at the cross-dock. The key element of efficient cross-docking lies in the synchronization of the inbound trucks arriving at the facility and the outbound trucks that leave to visit the customers. However, the loading aspect in the context of cross-docking has been barely studied, but never with the whole distribution network (inbound echelon, consolidation, and outbound echelon). This problem can be regarded as a 3-dimensional Loading CVRP-CD (3L-CVRP-CD).

This work proposes a mathematical formulation for the 3L-CVRP-CD, considering that the goods cannot be stocked in the cross-dock and that specific temporal constraints should be added to ensure the synchronization of the two echelons. The objective function is to minimize transportation costs. Regarding the packing constraints, we consider geometric and stability constraints, and in particular the multi-drop constraint and its pickup counterpart, the multi-load. This mathematical formulation was implemented and tested on toy instances, in order to validate the model and identify the instance size limit that a standard Branch-and-Bound algorithm (CPLEX) is able to solve.