E-grocery Delivery Routing Problem

The habits of consumers shopping online have rapidly changed in the last decade as a result of remarkable developments in e-commerce and the constant search of online retailers for new and more profitable business models offering more flexibility and alternative shopping experience for consumers. Many leading and visionary online retailers look for up-and-coming business strategies to diversify their in-stock or in-store “standard” (or “staple”) product offerings with outsourced “premium” products, i.e. products such as organic or dietary food, specialty gifts, specialty wine, etc., that offer higher satisfaction value to consumers and higher profit margins to retailers.

The E-grocery Delivery Routing Problem (EDRP) problem is motivated by a large Turkish supermarket chain offering home delivery services to online shoppers. The company aims at gaining competitive advantage through a new business model that provides extended service to its customers. In this model, an online supermarket that normally uses its brick-and-mortar stores to fulfill online customer orders may now additionally collaborate with external vendors that offer an extended inventory of diverse consumer items. Hence, the shopping basket of an online customer is fulfilled either from the store or from an external vendor, depending on the items ordered.

Within the same context, Campbell and Savelsbergh (2005) give the more restricted partnership model of Staples that offers office supplies and a grocery delivery service in Canada. In a similar setting, Instacart, an independent grocery delivery service operating in several major cities in the U.S. (e.g. Seattle, San Francisco, Los Angeles, Austin, Maryland, Philadelphia) allows its customers to combine items from multiple groceries in their area (such as Whole Foods Market, Costo, Kroger, Safeway and other retailers) into one order and have them all delivered in one order on the same day, even within an hour. AmazonFresh offers same-day delivery of fresh grocery and local products from bakery to ethnic foods to gourmet meals or organic food from the neighborhood shops, restaurants and bakeries in Northern California. In this new business paradigm, Amazon has recently expanded its delivery network and started operating its own truck fleet in San Francisco area (Bensinger and Stevens, 2014, click here). Such online shopping and delivery service is obviously not limited to the groceries and may be extended to other retail sectors.

The EDRP is based on a distribution network, which consists of (1) a depot, i.e. a store of the online grocery that supplies “standard” products; (2) vendors, i.e. external stores that supply their own set of “premium” products not available at the depot; (3) “regular” customers, i.e. customers that only purchase standard products; and (4) “premium” customers, i.e. customers that additionally purchase premium products. Routing regular customers only is a straightforward special case of the EDRP in the form of VRP (Vehicle Routing Problem) with or without time windows. On the other hand, routing premium customers present an additional challenge as two additional sets of decisions are to be made simultaneously: i) allocation of vendor(s) to each premium customer so as to satisfy the customer’s order of premium product(s); ii) routing of regular and premium customers, and their respective vendor set while preserving feasibility concerns such as precedence, vehicle capacity, time windows. Under these circumstances, the delivery of goods to each premium customer takes place only after the entire set of premium products are collected and combined with the standard products already loaded at the depot. Transfers between vehicles are not allowed and the minimum total distance solution is sought in the presence of precedence, time windows, and capacity constraints.

Emeç et al. (2014) present the mathematical formulation of the model and develop an Adaptive Large Neighborhood Search (ALNS) approach to solve it. They validate the performance of the proposed ALNS using the well-known Vehicle Routing Problem with Time Windows (VRPTW) instances of Solomon (1987) and randomly generate a large set of EDRP instances based on Solomon’s data and report benchmark results for future studies. The EDRP data is available here.

We present a short case study based on a real dataset in the city of Istanbul, Turkey. We consider two different scenarios: 1) serving customers within classic time windows (a variant of the traditional VRPTW); and 2) serving customers within predefined time slots (a variant of the CVRP with time length restrictions). In both scenarios, premium products are collected from multiple vendor source locations and then delivered to customer locations in a single basket with standard products. The ALNS methodology proposed in Emeç et al. (2014) is integrated with the ArcGIS 10.0 development environment to provide a convenient user interface on a geographical information system. A cross-sectional image of this interface is given in Figure 1. Network data, premium products list, depots, vendors, regular customers, premium customers and vehicle capacity are all entered as a layer or data input via this interface. The user specifies the time window handling process, i.e. the scenario type, and selects the visualization of the routes as straight line or true shape format. After the problem is solved an analysis of the solution is reported. The report includes the total route distance, route duration, number of vehicles required, vehicle utilization, and average number of vendors visited.

Figure 1. A cross-sectional image of the ArcGIS-based interface

The study area covers the surroundings of an online retailer in the Ataşehir district located on the Asian side of Istanbul. We consider three different premium products, namely books, souvenirs, and sports equipment. In Figure 2, the individual suppliers of these products are represented by book, gift box, and sports equipment symbols, respectively. We also consider “super vendors” that supply more than one premium product at the same time. These super vendors are represented by super market symbols. Online retailer store (depot), premium customers and regular customers are shown with capital letter symbols D, P, and R, respectively. We have one depot, four super vendors, thirteen individual vendors, fifty-two regular customers, and twenty-three premium customers in this case study.

Figure 2. Problem setting in Ataşehir, Istanbul

In the first scenario, we solve the EDRP with traditional time windows by serving both premium and regular customers within their individual and independent time windows in a nine-hour time horizon. In the second scenario, we consider three consecutive time slots, which are three hours in length. In other words, the deliveries are grouped into specific time slots based on the time window preferences of customers. Thus, the deliveries in the same time slot may be treated as orders with no time windows. Compared to the first scenario, the second one is a less flexible approach but it reduces the problem size dramatically as a result of time-based clustering. In both scenarios, a number of vehicles leave the store with all standard products loaded and stop by some vendors, if necessary, on their way to visit customers sequentially to make deliveries. Figure 3 illustrates the routes obtained by running the proposed ALNS under a) Scenario 1 and b) Scenario 2 respectively.

(a) Scenario 1

(b) Scenario 2

Figure 3. Routes obtained under the two scenarios

We assume a specific number of time slots in the analysis illustrated in Figure 6.3. However, the number of time slots may not be foreseen in advance. In order to investigate and evaluate the effect of time slots, we conduct a sensitivity analysis in Table 6.1. This analysis exhibits that the required number of vehicles and solution time shows a concave relationship with the number of time slots. Furthermore, the total distance and total duration decrease as the number of time slots decreases, whereas the average vehicle capacity usage stays almost stationary with respect to the number of time slots.

Table 1. The comparative summary of results

Key Factors	Scenario 1	Scenario 2
Solution Time (sec.)	250	125
Required # of Vehicles	6	2
Total Distance (km)	178	156
Total Duration (h)	40	15
Average Vehicle Capacity Usage (%)	92%	90%

References:

Bensinger G, Stevens, L (2014) Amazon, in threat to UPS, tries its own deliveries. The Wall Street Journal. (online.wsj.com/news/articles/SB10001424052702304788404579521522792859890, last accessed on June 10, 2014)

Campbell AM, Savelsbergh MWP (2005) Decision support for consumer direct grocery initiatives. Transportation Science 39: 313–-327.

Emeç U, Çatay B, Bozkaya B (2014) An Adaptive large neighborhood search for an e-grocery delivery routing problem. Working Paper, Sabanci University.

Solomon MM (1987) Algorithms for the vehicle routing and scheduling problems with time window constraints. Operations Research 35: 254–265.

fresh.amazon.com, web reference, last accessed June 10, 2014.

www.peapod.com, web reference, last accessed on June 10, 2014.

www.instacart.com, web reference, last accessed on June 10, 2014.