Many supermarkets, such as Woodman’s in Madison, WI, provide home delivery service to their customers. To request a delivery on the next day, a customer must place an order the night before the delivery. Customers can select a desired time window for delivery, usually about 3 hours in duration. The aim of this case study is to demonstrate how supermarkets can make use of ridesharing vehicles to augment their delivery fleet and to develop a model that routes both the supermarkets vehicles and the ridesharing vehicles to satisfy customer demands. The problem can be modeled as a Heterogeneous Fleet Vehicle Routing Problem with Time Windows (HVRPTW). The model is implemented in GAMS and a sample instance is solved using CPLEX. Users can create their own scenarios with the interactive demo.
Problem Description
The retail industry is becoming more customer centric each day. Retailers are introducing new features and services to attract more customers. For example, Walmart is exploring ways to make shopping easier for their busy customers. In June 2016, the chain launched a pilot project to test last mile delivery through services like Uber and Lyft. Here is a quote from Walmart’s blog [1]:
A customer in one of the test locations places their grocery order online and selects a delivery window. Our personal shoppers, highly-trained Walmart associates, will carefully select and prepare their order. Then, our team may request a driver from one of these services to come to the store, pick up the customer’s order, and take it directly to the customer’s location. It’s all seamless to the customer. They pay us our normal $7-10 delivery charge online, and make no payment to the driver. We’ll also let them know their order is being delivered by a driver from Uber or Lyft.
Woodman’s Markets, a Wisconsin-based grocery retailer, facilitates home delivery of orders through its website. Currently, orders are delivered using Woodman’s own vehicles and drivers. Because demand is not the same every day, Woodman’s needs to be smart about how it sizes its fleet. If Woodman’s invests in vehicles based on a maximum demand, there will be high capital expenditure and there will be low utilization when demand is low. If Woodman’s invests in vehicles based on smaller demand, there could be times when demand for delivery exceeds vehicle capacity and customers could be lost. Woodman’s could approach this problem by adopting a similar strategy to Walmart of using rideshare services to satisfy excess demand. In this case study, we consider a hypothetical implementation of such a strategy.
The Woodman’s Grocery Delivery problem involves determining a minimum cost set of routes such that each customer will be visited once within its specified time window. Each route starts and ends at the depot (Woodman’s grocery store) and can be completed by a store-owned vehicle or by a rideshare vehicle. Each customer has a given demand, which is expressed in units of the number of standard cartons. The vehicles have capacity limitations, which may differ between the store-owned vehicles and the rideshare vehicles. The store-owned fleet is initially sized to satisfy average demand for delivery and the rideshare vehicles are intended to satisfy excess demand.
This grocery delivery problem can be modeled as a vehicle routing problem with time windows and vehicle capacities. Because the store-owned vehicles and the rideshare vehicles can have different capacities, this problem is a variant of the capacitated vehicle routing problem with time windows known as the heterogeneous vehicle routing problem with time windows. The objective of the problem is to minimize the cost of the routes. The constraints ensure that valid routes are constructed. The same vehicle must enter and exit a customer location or node, and the difference in the load carried by a vehicle before entering and after exiting a customer will be equal to the customer demand. Other constraints enforce the vehicle capacity restrictions, the time window constraints, and the requirement that customer orders are delivered by a single vehicle. There are upper limits on the number of vehicles of each type that can be used, so there may be demands that are rejected by the model because they cannot be accommodated on a route.
Literature
The Heterogeneous Fleet Vehicle Routing Problem with Time Windows is a variant of the Vehicle Routing Problem (VRP) in which the characteristics of the vehicles may vary and time windows must be observed. There is a large body of literature on the VRP and its many variants; a number of surveys and books have been written including Cordeau et al. (2007), Golden et al. (2008), and Laporte (2009).
Although the heterogeneous fleet VRP (HVRP) was introduced in the early paper of Golden et al. (1984), it has received more attention in recent years. Several papers survey the recent work and include many references. Baldacci et al. (2008) focus on lower bounding techniques and heuristics and compare the performance of heuristics on benchmark instances. Baldacci et al. (2010) review exact algorithms and provide a comparison of their computational performance on capacitated VRPS and HVRPs. Irnich et al. (2014) provide an update on HVRP papers published between 2008 and 2014. Koc et al. (2015) classify the various heterogeneous routing problems, present formulations, and provide a review of algorithms. Most of the algorithms in the literature are heuristic, with good heuristics able to provide high quality solutions with up to 100 customers in a reasonable time. For smaller instances, the integer programming formulation can be solved directly as in this case study.
Interactive Demo
For the interactive demo, we have created a data set with the depot at the Woodman’s in West Madison and 30 potential customers. Associated with each potential customer is an address and we use Google Maps to calculate distances between all pairs of customers. Orders are packed in cartons with dimensions of 3 ft by 3 ft by 3 ft. The demand of each customer is specified in terms of the number of cartons; the demand value for each customer is generated from a distribution, which can be selected below. We assume that there are two vehicle types: type 1 are Woodman’s owned vehicles and type 2 are rideshare vehicles. The demo allows the user to specify values for the maximum number of vehicles of each type, the vehicle capacity of each type, and the cost per mile of each type. The average vehicle speed value and the time to serve a customer are assumed to be the same for all types of vehicles. Finally, the demo accepts a penalty value to be applied to the demand of customers not able to be accommodated on a route.
The advantage of using Uber can be seen in the High demand scenario. Here, Uber is used to augment the delivery fleet of Woodman’s vehicles. When the demand is lower, Uber vehicles aren’t used since their capacity is low and their cost per mile is higher.
| Woodman’s | Uber | |
|---|---|---|
| maximum number of vehicles | ||
| vehicle capacity (# cartons) | ||
| cost per mile (\$) | ||
| average vehicle speed (mph) | ||
| time to serve customer (minutes) | ||
| # cartons at each customer location | ||
| cost for refusing delivery | ||
| solution accuracy | ||
Solution
The GAMS model for this data set is here and the distance matrix is available in gdx form here.
Mathematical Formulation
Consider a graph \(G=(V,A)\), where \(V\) is the set of nodes and \(A\) is the set of edges. The set of nodes \(V\) is comprised of the set of customers \(N\) and the depot {0}. Let \(K\) be the set of vehicle types and each type may differ in capacity and cost.
Parameters
n_k & = & \text{number of vehicles of type $k$, $\forall k \in K$} \\
q_i & = & \text{demand of customer $i$, $\forall i \in N$} \\
a_i & = & \text{opening of time window at customer node $i$, $\forall i \in N$} \\
b_i & = & \text{closing of time window at customer node $i$, $\forall i \in N$} \\
s_i & = & \text{time required at customer node $i$, $\forall i \in N$} \\
cap_k & = & \text{capacity of vehicle of type $k$, $\forall k \in K$} \\
c_k & = & \text{cost per mile of vehicle of type $k$, $\forall k \in K$} \\
d_{ij} & = & \text{distance from node $i$ to node $j$, $\forall (i,j) \in A$} \\
v_k & = & \text{average speed of vehicle of type $k$, $\forall k \in K$} \\
t_{ijk} & = & \text{time for vehicle of type $k$ to travel on arc $(i,j)$, defined as $d_{ij}/v_k$, $\forall (i,j) \in A$, $\forall k \in K$} \\
w & = & \text{penalty per unit of demand rejected}
\end{array}
Decision Variables
x_{ijk} & = & \text{1 if edge $(i,j)$ is included in a route for a vehicle of type $k$, $\forall (i,j) \in A$, $\forall k \in K$} \\
& = & \text{0 otherwise} \\
f_{ijk} & = & \text{load carried from node $i$ to node $j$ by a vehicle of type $k$, $\forall (i,j) \in A$, $\forall k \in K$} \\
p_{ik} & = & \text{arrival time of vehicle of type $k$ at customer $i$, $\forall i \in N$, $\forall k \in K$} \\
z_{i} & = & \text{1 if the customer is visited} \\
& = & \text{0 otherwise} \\
\end{array}
Formulation
\begin{array}{clclll}
\text{minimize} & \sum_{(i,j) \in A} \sum_{k \in K} c_k \cdot d_{ij} \cdot x_{ijk} + \sum_{i \in N} w \cdot q_i \cdot (1 – z_i) & & & & \\
& \sum_{j \in N: (0,j) \in A} x_{0jk} & \leq & n_k & \forall k \in K & (1) \\
& \sum_{k \in K} \sum_{j \in V: (i,j) \in A} x_{ijk} & \leq & 1 & \forall i \in N & (2) \\
& \sum_{k \in K} \sum_{j \in V: (j,i) \in A} x_{jik} & \leq & 1 & \forall i \in N & (3) \\
& \sum_{j \in V: (i,j) \in A} x_{ijk} – \sum_{j \in V: (j,i) \in A} x_{jik} & = & 0 & \forall i \in N, \forall k \in K & (4) \\
& \sum_{k \in K} (\sum_{j \in V: (j,i) \in A} f_{jik} – \sum_{j \in V: (i,j) \in A} f_{ijk}) & = & q_i \cdot z_i & \forall i \in N & (5) \\
& q_j \cdot x_{ijk} -f_{ijk} & \leq & 0 & \forall j \in N, \forall (i,j) \in A, \forall k \in K & (6) \\
& (cap_k – q_i) \cdot x_{ijk} – f_{ijk} & \geq & 0 & \forall i \in N, \forall (i,j) \in A, \forall k \in K & (7) \\
& p_{ik} & \geq & a_i & \forall i \in N, \forall k \in K & (8) \\
& p_{ik} & \leq & b_i & \forall i \in N, \forall k \in K & (9) \\
& p_{ik} – p_{jk} + s_i + t_{ijk} & \leq & M \cdot (1 – x_{ijk}) & \forall (i,j) \in A, \forall k \in K & (10) \\
& p_{ik} -p_{0k} + s_i + t_{i0k} & \leq & M \cdot (1 – x_{i0k}) & \forall i \in N, \forall k \in K & (11)
\end{array}
\end{eqnarray}
References
- Agra, A., M. Christiansen, R. Figueiredo, L.M. Hvattum, M. Poss, and C. Requejo. (2013). The robust vehicle routing problem with time windows. Computers & Operations Research 40(3), 856 – 866.
- Baldacci, R., M. Battarra, and D. Vigo. (2008). Routing a Heterogeneous Fleet of Vehicles. In The Vehicle Routing Problem: Latest Advances and New Challenges., B.L. Golden, S. Raghavan, and E.A. Basil, eds., 1 – 25.
- Baldacci, R., P. Toth, and D. Vigo. (2010). Exact Algorithms for Routing Problems Under Vehicle Capacity Constraints. Annals of Operations Research 175, 213 – 245.
- Bender, M. “Piloting Delivery with Uber, Lyft and Deliv.” Walmart Today, June 3, 2016. http://blog.walmart.com/business/20160603/piloting-delivery-with-uber-lyft-and-deliv
- Choi, E. and D.-W. Tcha. (2007). A column generation approach to the heterogeneous fleet vehicle routing problem. Computers & Operations Research 34 (7), 2080 – 2095.
- Cordeau, J.-F., G. Laporte, M.W.P. Savelsbergh, D. Vigo, C. Barnhart and G. Laporte. (2007) Vehicle Routing. In Transportation, Handbooks in Operations Research and Management Science, C. Barnhart and G. Laporte, eds., 367 – 428.
- Gendreau, M., G. Laporte, C. Musaraganyi, and E. D. Taillard. (1999). A tabu search heuristic for the heterogeneous fleet vehicle routing problem. Computers & Operations Research 26 (12), 1153 – 1173. http://dx.doi.org/10.1016/S0305-0548(98)00100-2
- Golden, B.L., A. Assad, L. Levy, and F. Gheysens. (1984) The Fleet Size and Mix Vehicle Routing Problem. Computers and Operations Research 11, 49 – 65.
- Golden, B.L., S. Rahavan, and E.A. Wasil. (2008). The Vehicle Routing Problem: Latest Advances and New Challenges. Springer, New York.
- Irnich, S., M. Schneider, and D. Vigo. (2014). Four Variants of the Vehicle Routing Problem. In Vehicle Routing: Problems, Methods and Applications, P. Toth and D. Vigo, eds., 241 – 271
- Koc, C., T. Bektas, O. Jabari, and G. Laporte. (2015). Thirty Years of Heterogeneous Vehicle Routing. European Journal of Operational Research 249 (1), 1 – 21.
- Laporte, G. (2009). Fifty Years of Vehicle Routing. Transportation Science 43 (4), 408 – 418.
- Ochi, L. S., D. S. Vianna, L. M. A. Drummond and A. O. Victor. (1998). A parallel evolutionary algorithm for the vehicle routing problem with heterogeneous fleet. Future Generation Computer Systems 14 (5 – 6), 285 – 292.
- Wassan, N. A. and I. H. Osman. (2002). Tabu search variants for the mix fleet vehicle routing problem. Journal of the Operational Research Societ 53, (7) 768 – 782. http://dx.doi.org/10.1057/palgrave.jors.2601344