Satellite depots management for Last-Mile distribution in E-Commerce
Problem description
Nowadays, the urban distribution has to cope with the continuous growth of e-commerce and the changing of customers’ behavior. Indeed, customers have raised their expectations for fast (usually within very limited time slots as 2 hours), and cheap deliveries of purchased goods and they are connected, informed and empowered, and continually demand more choice and flexibility in delivery options.
To try to answer them and provide a faster service, enterprises, and the e-commerce giant platforms are moving from a push cost-driven supply to time and cost pull-driven approach (i.e., demand- driven logistics), changing the logistics chain completely.
In this approach, demand orchestrates the supply chain by pulling products into a double-layer of distribution centers located close to the urban areas, generating the so-called two-tier distribution system (Figure 1). Urban Consolidation Centers (UCCs). UCCs are logistic platforms located in a strategic node of the city, represent the first level of the system, while Satellites constitute the second tier, where the freight coming from the UCCs and other external points, may be transferred and consolidated into vehicles adapted for utilization in dense city areas (e.g., electric vehicles).
Moreover, to satisfy the growing demand for faster delivery, in the urban distribution is gaining popularity the Crowdsourced delivery (also called Uberization of the last-mile). This model refers to the increasing tendency to ask local and unprofessional drivers to manage deliveries, sometimes in less than an hour. Generally, once an order is placed, the delivery is assigned to one of the part-time nonprofessional couriers, usually using of a mobile application, according to their proximity to the pickup location. Finally, the assigned courier delivers the parcel to the final customer, using its vehicle.
Figure 1 – Two-tier distribution system (Crainic and Sgalambro, 2014)
1
The above-described system is a multi-actor complex system that involves multiple players, such as the courier company, the satellite manager, the local administrations, each one with their goals.
The objective of the courier company is to minimize delivery cost that includes the vehicle cost and tariff for renting space in the warehouse.
Satellite manager desires to deploy policy for the efficient use of capacity in satellite, including social and environmental perspectives.
Finally, municipality/city aims to guarantee an efficient adoption of infrastructures in the city, fostering the adoption of measures as pricing strategies, and to foster deliveries within a certain time interval.
For example, in some cities, local administrations impose congestion prices in a specific schedule to reduce traffic and pollution. Few European cities have implemented congestion prices like Milan, Italy: Area C (2012) evolved from the pollution tax scheme Eco pass (2008) on Weekdays, 7:30am-19:30 pm.
Despite congestion prices, there are some time slots for which the delivery faces traffic problems or huge mass density in the city, which affect the operational and economic efficiency of the delivery company, increasing the cost of the delivery.
Goals
The group supposes to be the decision maker represented by a courier company that adopts a satellite and distributes from there through private or, more often, contracted vehicles, to fulfill the demand of orders. In particular, it can adopt mixed-fleet composed by traditional vehicles, low- environmental vehicles (i.e., electric vans and cargo bikes) or traditional vehicles owned by unprofessional users. It aims to reduce the global cost composed by the cost of delivery and cost for using satellite. The first cost is directly related to the delivery of the goods in the city and thus, to the cost of vehicles, and the related costs, and the personnel cost. Notice that according to (Perboli et al., 2018), different vehicles types have different costs. The second cost is for renting space in satellite depots where the freight is consolidated, and for eventually additional handling operations.
The objective function is subjected to the satisfaction of the following constraints: 1. the demand for orders from customers must be fulfilled compulsory;
2.
3.
4.
Suppose that there are different types of vehicles (electric vans, cargo bikes, etc…), limited capacity, and they are
have a
at each timeslot, the capacity of the depot is not exceeded;
at each timeslot, the capacity of each vehicle in use the depot is not exceeded;
at each timeslot, each order must be fulfilled in a single timeslot.
Moreover, assume that the orders are split into different timeslots, which are characterized by different capacity (i.e., vehicles) and labor (i.e., unprofessional drivers) availability. For example, sometimes customers could require a delivery of parcel in a certain time slot in which warehouse manager has to pay more to the labor (selection of drivers, taking into account their availability, including timetables, maximum hours of work) increasing the relating costs.
It means that cost is not constant during the day, but time-dependent. Thus, the costs can be grouped as follows:
Depot cost: it depends on the time slot. Given an order i with size 𝑑𝑒𝑚𝑎𝑛𝑑 that we decide to deliver at timeslot h at a unit cost 𝑇𝑎𝑟𝑖𝑓𝑓, this cost becomes 𝑑𝑒𝑚𝑎𝑛𝑑𝑇𝑎𝑟𝑖𝑓𝑓-
Vehicle renting: it depends on the vehicle type we use. Thus, if we use a vehicle j of type t, we pay a cost VeicCost(t|j is type t)
Delivery costs. If we deliver order i with vehicle j in timeslot h, we pay a cost Elect_vehicle(j,h) There is also the possibility to skip the satellite by using an external parcel delivery courier with cost Ca (the cost is very high). In this case the cost of the delivery becomes 𝐶𝑎 𝑑𝑒𝑚𝑎𝑛𝑑.
which
defined according to the volume and the fixed cost associated.
2
The goal for each group is to find a plan of vehicles and warehouse to use each time slot to move or store orders. This plan has to minimize
Instances
represented by the routing costs of vehicles at a specific
time slot
the total cost composed by:
the sum of the tariff for using the space in the satellite;
the sum of the cost per delivery related to each order;
the sum of the cost of the vehicles
for the deliveries, and eventually
the cost of express delivery, expressed as the sum of the orders not delivered by the
electric vehicles times a unitary cost (fix it to 10000).
Notice that the express delivery cost is normally much higher than the other ones, because we
want to use it only if no spare capacity is present in the depot or at the electric fleet level.
To conduct numerical experiments, the group has a set of instances named SET 1, generated starting from bin packing problems variants (Monaci, 2002).
The instances, in .dat file format, are named as follows:
MPVSBPP_SET1_IT{instance_size}_ITV{number_type}_NT{volume_type}_TS{max_ti meslots}_WT{max_timeslots}_ WT1_VT1_REP{repetition_number}.dat
For example: MPVSBPP_SET1_IT500_ITV1_NT1_TS3_WT1_VT1_REP1.dat
The instances are characterized by the following parameters:
Number of orders equals to 500
Number of time intervals equal to 3 corresponding to the time intervals [9.00-
12.00], [12.00-15.00] and [15.00-18.00]
Orders volumes randomly generated according to a discrete distribution in the
set {1,2,…,20}.
Three orders volume types are considered as:
T1 : 50% of orders are small and 50% medium; T2: 75% small and 25% medium;
T3: 25% small and 75% medium.
The fleet is characterized by the volume and costs of vehicles.
In particular, there are three vehicles types: cargo-bikes, small electric vans, traditional (fossil-fueled) vans.
Concerning the vehicle capacity the following cases are considered:
– all vehicles with the same capacity of 150;
– three different capacities {100, 200 and 300}.
Concerning the vehicle cost. It is computed as 𝑐= 𝑐𝛿h, where 𝑐 10𝑉 (Crainic et al., 2011) and 𝛿h is the cost function modifier, which is continuous and discretized in three time intervals a day [9.00-12.00], [12.00-15.00] and [15.00- 18.00] where the cost function is [1, 0.3, 0.7], respectively (see Figure 2)
The aim is to drive usage of warehouse when traffic is quite lower or in some period of time in lower flows in the city, and thus, to integrate some policy of the municipality to push the freight transportation out of the rush hours.
3
Figure 2 – Cost function
The tariff for using the satellite is T =𝑇, where 𝑇 T𝜑h. It is a fixed
value multiplied by the tariff modifier function 𝜑h, which is discretized in three
time interval per day [9.00-12.00], [12.00-15.00] and [15.00-18.00] where the tariff function is [0.7, 1, 0.3], respectively (see Figure 3). The reason is that the nonprofessional drivers are more available in morning and afternoon, so it could be easy to find them that impact on lowest prices of drivers.
Figure 3 – Tariff function
Assignments
1. Each group has to formulate a linear programming model to optimize the objective function.
2. Implement the model on CPLEX and run the code
3. Analyze the results considering 500 customers.
Modeling recommendations
4
Before formulating this problem as a LP model, it is recommended to identify and define the nomenclature of indices, data, variables and generic constraints.
You have some instances with the known optimal solution. Use it to infer the decisions and check the f your model is correct.
In addition, the group is invited to analyze and try to propose possible improvements to increase sensitivity to the problem above described.
Hints:
Read the formulations of Bin Packing (file Mixed Linear–Integer Programming
Models) and the Variable Size and Cost Bin Packing (paper Variable Size and Cost
Bin Packing) on the website;
Two types of macrodecisions:
o When deliver an order and on which vehicle. So you also identify the vehicle type (remember the express delivery);
o Which vehicles to use and when.
Check the solution files and the dat files provided as example
References
T.G. Crainic, A. Sgalambro. Service network design models for two-tier city logistics. Optim Lett 8:1375-1387. 2014.
G. Perboli, M. Rosano, M. Saint-Guillain, P. Rizzo. Simulation-optimization framework for City Logistics: an application on multimodal last-mile delivery. IET Intelligent Transport System. 12(4): 262-269. 2018.
M. Monaci. Algorithms for packing and scheduling problems. PhD thesis, Università di Bologna, Bologna, Italy. 2002.
T. G. Crainic, G. Perboli, W. Rei, and R. Tadei. Efficient lower bounds and heuristics for the variable cost and size bin packing problem. Comput. Oper. Res., 38(11):1474–1482, Nov. 2011. ISSN 0305-0548. doi: 10.1016/j.cor.2011.01.001.
5