Milk Run Design and Optimization in Logistics Operations
E-commerce logistics is about effectively managing the multiple stages of a shipment’s journey from its manifestation to delivery. This process includes network design, warehouse and inventory management, supply/demand management, vehicle fleet allocation and scheduling, etc. This blog discusses a key aspect of this process known as network design. In particular, we discuss vehicle configurations and routes of milk runs, a key distribution concept in logistics as elaborated later. E-commerce distribution network is designed through multiple type of facilities and often uses the hub-spoke model for transportation of goods for better efficiency (Verma et al., 2023). Two major types of facilities are (i) hubs and (ii) distribution centers (DCs), where the DCs act as spokes. These facilities are collectively known as nodes (Sachdeva et al., 2022). These facilities are connected to each other through line hauls and milk runs. Hub to hub connections happen through large sized vehicles through a concept known as line hauls that enable consolidation of load at hubs for better efficiency. The hubs are connected to DCs through milk runs. A milk run starts and ends at the hub and covers a set of DCs to deliver the bags containing the shipments. The term “milk run” comes from the dairy industry in which several milkmen collect milk from a single milk processing firm, deliver milk bottles to customers and return back to the processing firm (Brar and Saini, 2011). The objective of a milk run is to ensure that the supplied milk remains fresh and helps avoid/reduce overstocking at the processing firm.
E-commerce operations are complex and a shipment passes through several facilities during its journey from the origin to the consignee. The shipment journey consists of three miles, namely:
(i) First mile: where the field executive picks up the manifested shipments from several pickup centres and sends them to the origin hub for processing. Here, the shipments are bagged as per their destination, thereby facilitating movement of bags thereafter.
(ii) Middle mile: which is responsible for transportation of bags from the origin hub to the destination hub and then to the DCs.
(iii) Last mile: that aids the shipment delivery to the consignees from the DCs after debagging the shipments.
As mentioned before, the middle mile is classified into two parts: line hauls and milk runs. The aim of this article is to present a mathematical model to optimize the milk runs for a hub. Milk run design for a hub is a case of capacitated vehicle routing problem (CVRP). This problem seeks to minimize the total travel distance (or sometimes total travel time) by all the vehicles and adheres to the available vehicle configurations (Caric and Gold, 2008). In the CVRP, multiple vehicles depart from a destination side hub, deliver bags to its designated DCs and return back to the hub.
Modelling Details
This blog illustrates a CVRP which is an optimization of distribution of bags from a hub to multiple DCs. The following are the features, assumptions and operational constraints of the model:
1. The inbound load at each DC is known.
2. The location of the hub and all DCs are available.
3. The vehicle fleet is heterogeneous (vehicles with different capacities).
4. Vehicles of specific capacities cannot cover more than a certain distance due to operational constraints.
5. Vehicles of specific capacities cannot cover certain DCs due to narrow road and traffic congestion near these DCs.
6. There is an upper limit on the number of DCs that can be covered by each
vehicle.
7. Some pairs of DCs should be covered consecutively due to operational
requirements.
8. Some pairs of DCs cannot be covered consecutively due to damaged road
between them.
9. The distance matrix between the nodes is assumed to be symmetric.
This optimization problem is described as a complete undirected graph. The network consists of a hub and N DCs. The notations are given next.
G = (V, E) represents the graph, V = {0, 1, . . . , N} is the set of nodes (node
‘0’ is the hub, while {1, . . . , N} are the DCs) and E = {(i, j) : i, j∈ V} is the
set of edges. There are M vehicles, T = {1, . . . , M} is the set of vehicles. Q_t
represents the vehicle capacity; total distance travelled by this vehicle should not exceed D_t and it can cover a maximum of H_t DCs on its route where t ∈ T . The origin destination distance matrix is symmetric, that is, distance between two nodes i and j is d_i,j and d_i,j = d_j,i. Each DC j∈ V with demand l_j must be served by a single vehicle. We assume that the demand at a DC is less than or equal to the capacity of the largest sized vehicle that can potentially serve this DC. Otherwise, the additional demand is served by creating a separate node at the same location. As given in (5), we assume that B is a set of tuple {(v’,t’), . . . } where DC v’, v’∈ V cannot be covered by the vehicle t’, t’∈ T. Additionally as per (7), suppose P be a set of tuples each having a DC pair such that P = {(i, j), . . .} and each tuple of DC pair must be covered in that order. Further, as stated in (8), let us assume a set of tuple of pairs of DCs R = {(i, j), . . .} such that DCs in each tuple (i, j) cannot be covered consecutively.
The objective function seeks to minimize the total distance travelled by all the vehicles. The decision variables associated with this integer programming problem are x^t_i,j , ∀ i, j∈ V , t∈ T , where
Let u_i be an auxiliary variable such that u_i >= 0, ∀ i∈ V\{0}. This auxiliary variable will be used in the subtour elimination constraints in the formulation.
Constraints
The vehicle routing problem has the following constraints which can be broadly grouped in four categories. These are explained subsequently with reference to the equations given in the mathematical model.
Flow balance constraints: These are three sets of constraints that ensure flow of the vehicles inbound/outbound to/from different nodes in the network. Specifically, equation (2) states that the number of incoming/outgoing edges to/from a node are equal and hence, ensures a round trip to the hub. Equations (3) and (4) ensure exactly one incoming edge into each DC and one outgoing edge from each DC.
Vehicle characteristic constraints: These set of three constraints ensure that each vehicle adheres to its designed capacity, travel distance and maximum number of DCs that can be covered by them. In particular, the total load delivered by each vehicle to all its designated DCs is within the designed vehicle capacity as ensured by equation (5). Equation (6) ensures that a vehicle does not travel for than its designated distance in the round trip. Equation (7) guarantees that each vehicle does not cover more than its intended number of DCs. We subtract one edge since each vehicle starts and ends at the hub.
Route constraints: These sets of four constraints help consider the DC specific characteristics in the milk run routing problem. There is a set of unserviced DC-vehicle pairs such that these vehicles cannot serve the given DC due to narrow roads. Equations (8) and (9) together ensure that no such vehicle can be incoming/outgoing to/from these DCs if it exist in this unserviced DC-vehicle pair set. Similarly, equation (10) is the DC pair constraint that means two DCs must be covered consecutively. Contrarily, damaged road constraint (Equation 11) ensures that two DCs cannot be covered consecutively.
Subtour elimination constraints: A subtour in our problem is any cycle formed between the DCs without the hub being a part of this cycle. Equations (12), (13) and (14) together ensure no subtour formation in the final solution (Oncan et al., 2009). These are based on the Miller-Tucker-Zemlin (MTZ) formulation. These constraints eliminate the subtours by ordering the nodes with the help of auxiliary variables that ensure no node is covered more than once. Consider an example with three nodes 1,2 and 3 which gives rise to three equations emanating from equation (14). Adding these three equations results in two edges between these three nodes as given by value of x^t_i,j, hence, eliminating the subtour.
The mathematical formulation including the objective is given in the next section.
Mathematical Formulation
The objective function and the constraints are given in equations (1)-(14)
Data and Results
Here, we consider a real case of a hub of Ecom Express Limited which has 74 DCs mapped with it, namely DC1, . . ., DC74. The average daily demand of the DCs, geo-coordinates of hub and DCs are known. Total daily demand of these DCs is 17,424. We create the route distance matrix using OSRM distance API. We consider 3 vehicles each of capacity 2,600 and 12 vehicles each of capacity 1,100. As per our assumption, each vehicle of capacity 2,600 can cover at most 10 DCs and travel at most 750 km, whereas a vehicle with 1,100 capacity can cover a maximum of 7 DCs and 500 km. Table 1 presents the results for a hub.
We solved the optimization problem using Google OR tools with the above
set of vehicles and load configuration. The optimal solution of this optimization problem gave the total route distance of 4,823 kms with 13 vehicles (3 of capacity 2,600 and 10 of 1,100) and average vehicle utilization of 93%. Further, we also restrict that DC5 and DC11 can not be covered by the vehicles with capacity 2,600 because of narrow roads in their route, hence these two DCs are traversed by the vehicle of 1,100 capacity. Additionally, we consider that DC55 and DC24 must be covered consecutively by the same vehicle. In the visualization (Figure 1), the routes in different colours represent the vehicles and the hub is located at the center.
Conclusion
This blog discussed milk run optimization which is an important application of the capacitated vehicle routing problem to e-commerce logistics. The blog provided an integer programming model and its solution through Google OR tools for a heterogeneous vehicle fleet. The results provided the types of vehicles and the order of DC coverage for each vehicle route for the network configuration of 74 DCs and a hub. The model has been implemented on pan-India hubs at a leading e-commerce logistics company, Ecom Express Limited that resulted in about 5–8% savings in the milk run costs for each hub in a network of about 3,500 DCS and 70 hubs. The future extensions would include suggestions of optimal vehicle capacities as well to further optimize the utilization levels.
References
[1] Brar, G. S. and Saini, G. (2011). Milk run logistics: literature review and directions. In Proceedings of the world congress on engineering, volume 1, pages 6–8. WCE.
[2] Caric, T. and Gold, H. (2008). Vehicle routing problem. InTech.
[3] Oncan, T., Altınel, ˙I. K., and Laporte, G. (2009). A comparative analysis of several asymmetric traveling salesman problem formulations. Computers & Operations Research, 36(3):637–654.
[4] Verma, A., Kuo, Y.-H., Kumar, M. M., Pratap, S., and Chen, V. (2023). A data analytic-based logistics modelling framework for e-commerce enterprise. Enterprise Information Systems, 17(6):2028195.
[5] Sachdeva, A., Singh, B., Prasad, R., Goel, N., Mondal, R., Munjal, J., Bhatnagar, A., and Dahiya, M. (2022). Metaheuristic for hub-spoke facility location problem: Application to indian e-commerce industry. arXiv preprint arXiv:2212.08299.
Authors
Anirban Naskar — Data Scientist-I @Ecom Express Limited
Abhishek Bhatnagar— Manager- Data Sciences @Ecom Express Limited
