The order sorting and route optimization described in this article are all based on the company’s self-built logistics distribution model. First, the customer orders need to be sorted in batches and batches according to the order volume and order time window, and then the optimal delivery route is determined according to the customer’s delivery address. Assuming that each customer has only one number of orders per day, and the research object is the number of n orders of n customers accumulated by the company in a day, construct a model for joint optimization of order batch sorting and distribution routes, and formulate the optimal solution plan, which efficiently completes the delivery of all customer orders. Order demand n under surge demand follows a Poisson distribution, \(n \in [a, b]\), and a is strictly greater than M.
The problem that the model needs to solve is to determine how customer orders are divided into batches, the order of batches, that is, the delivery schedule, and the optimal route for the order delivery vehicle.
When the order arrives, the order is integrated according to a certain batching rule to form multiple batches, and then the batches are sorted according to certain rules, and then different order batches are assigned to the corresponding vehicles for delivery, and the vehicle path optimize. Each vehicle needs to reach multiple customer demand points in a delivery process, so the order and route of arriving customers are planned. The two key factors that are mainly considered in the whole problem are distribution cost and order fulfillment time. Among them, distribution cost includes order distribution scheduling cost, total fixed cost of vehicles, transportation cost, cost of goods loss, time Penalty costs.
Parameter settings
Settings:
Set of orders: \(N=\{1,2,...,n\}\);
Set of orders with DC: \(N_{o}=\{0,1,2,...,n\}\);
Set of vehicles: \(V= \{1,2,...,u,u+1,...,w\}\); [1, u] are enterprise-owned vehicles, \([u+1,w]\) are leased vehicles.
Set of order batching: \(H=\{1,2,...,h\}\);
Set of delivery routing: \(R=\{1,2,...,r\}\);
Set of delivery areas: \(O=\{1,2,...,o\}\);
Parameters:
\(q_i\): The quantity of items included in order i, \(i \in N\);
\(Q_h\): Each batch h can hold the maximum amount of items, \(h \in H\);
\(Q_v \): Maximum capacity (load capacity) of vehicle v, \(v \in V\);
\(t_{ij}\): The time required for the delivery vehicle from delivery point i to delivery point j, \(i,j\in N_0\);
\(T_i\): Average service time required for each delivery point i (ie each customer);
\(t_i^{\mathrm{earliest}}\): The earliest time that delivery point i (customer i) can accept the order to be delivered;
\(t_i^{\mathrm{latest}}\): The latest time that delivery point i (customer i) can accept the order to be delivered;
\(t_i^{\mathrm{arrive}}\): Time when customer order i arrives;
\(t_i^{\mathrm{arrive'}}\): The actual time when the vehicle arrives at the delivery point i (customer i);
\(d_{ij}\): The distance between delivery point i and delivery point j;
\(l_v^{\max }\): The farthest mileage of vehicle v;
\(c_i^{\mathrm{pick}}\): Order i pick and determine the average cost of the batch; (/unit time);
\(c_u^{\mathrm{fixed}}\): Fixed cost of own vehicle u per using;
\(c_w^{\mathrm{fixed}}\): Fixed cost of renting a vehicle w per using;
\(c_u^p\): Unit transportation cost of own vehicle u;
\(c_w^p\): Unit transportation cost of renting vehicle u;
\(c_i^{\mathrm{earliest}}\): The unit penalty cost for an order earlier than the earliest acceptable time by the customer;
\(c_i^{\mathrm{latest}}\): The unit penalty cost for an order later than the latest acceptable time by the customer;
\(\alpha \): Proportion of cargo damage during transportation;
\(\beta \): Proportion of cargo damage during loading and unloading;
\(\theta \): Average cost of goods damage of the order;
Decision variables:
\(t_h^{\mathrm{start}}\): Start Picking time of batch h,\(h\in H\);
\(t_h^{\mathrm{sevice}}\): All the time required to complete the picking of batch h, \(h\in H\);
\(t_i^{\mathrm{complete}}\): Picking completion time of order i (the batch);
\(t_v^{\mathrm{leave}}\): Time when vehicle v left the distribution center;
\(t_v^{\mathrm{end}}\): The total time for vehicle v to complete a delivery service;
\(r_i\): Flow of distribution point i;
\(y_{hv} = {\left\{ \begin{array}{ll} 1, &{} \text {if order batching }h\text { is allocated to vehicle }\\ &{}\quad v\text {(including own vehicles } u\text { and rented}\\ &{}\quad \text {vehicles }w\text {);} \\ 0, &{} \text {otherwise};\quad {h=1,\dots ,H, v=1,\dots ,w.} \end{array}\right. }\)
\(z_{ijv} = {\left\{ \begin{array}{ll} 1, &{} \text {if vehicle }v\text { is delivered from distribution}\\ &{}\quad \text {point }i\text { to distribution point }j\text {;} \\ 0, &{} \text {otherwise};\quad {i=1,\dots ,n, j=1,}\\ &{}\qquad \qquad \quad {\dots ,n, v=1,\dots ,w.} \end{array}\right. }\)
\(\tau _{io} = {\left\{ \begin{array}{ll} 1, &{} \text {if the service address of order }i\text { belong to}\\ &{}\quad \text {delivery area }o\text {;} \\ 0, &{} \text {otherwise};\quad {i=1,\dots ,n, o=1,\dots ,O.} \end{array}\right. }\)
\(\delta _{hr} = {\left\{ \begin{array}{ll} 1, &{} \text {if order batching }h\text { is allocated to delivery}\\ &{}\quad \text {route }r\text {;} \\ 0, &{} \text {otherwise}; \quad {h=1,\dots ,H, r=1,\dots ,R.} \end{array}\right. }\)
\(\sigma _{or} = {\left\{ \begin{array}{ll} 1, &{} \text {if delivery route }t\text { belong to delivery area }o\text {;} \\ 0, &{} \text {otherwise};\quad {r=1,\dots ,R, o=1,\dots ,O.} \end{array}\right. }\)
Model construction
(1) The time function part of the objective function is to minimize the order fulfillment time. The total time for a vehicle to complete a delivery service is the sum of the transportation time of the vehicle for a delivery and the service time to the customer.
$$\begin{aligned} \min f_{1}= & {} min_{v \in V} \left\{ t_v^{leave}+\sum _{i \in N} z_{oiv}t_{oi}+\sum _{i \in N}\sum _{j \in N} z_{ijv}t_{ij}\right. \nonumber \\&\left. +\sum _{j \in N}z_{jov}t_{jo}+\sum _{i \in N}\sum _{j \in N} z_{ijv}T_{i}\right\} \end{aligned}$$
(1)
Equation (
1) is to minimize the order fulfillment time, including the leave time and travel time.
(2) The cost function part of the objective function. The cost function includes order picking and sorting costs, total fixed vehicle costs, transportation costs, cargo damage costs, and time penalty costs.
(1) Order delivery schedule cost
The surge demand will lead to increased costs in the process of order batching, picking, and batch sorting. The cost of order batching, picking and sorting includes picking labor costs, management costs, and technical costs. Therefore, the order picking and sorting cost function is:
$$\begin{aligned} C_{1} = \sum _{i=1}^N \sum _{h=1}^H t_{i}^{\mathrm{complete}} c_{i}^{\mathrm{pick}} x_{ih} \end{aligned}$$
(2)
(2) Vehicle fixed cost
The fixed cost of a vehicle is related to the vehicle itself and other factors, such as the depreciation expense of the vehicle, the use loss of the vehicle, the management cost of the vehicle, and the cost of the driver. In the case of a surge demand, the company’s own resources are limited, and its own capacity is difficult to meet the delivery requirements. Therefore, the total fixed cost of the vehicle is divided into two parts, one is the fixed cost of the own vehicle, and the other is the fixed cost of the leased vehicle. Whether to use the leased vehicle is determined by the 0-1 variable
\(z_{ijv}\), which is the same as whether to use the own vehicle. Therefore, the fixed cost of the vehicle is:
$$\begin{aligned} C_{2} = \sum _{j=1}^N \sum _{v=1}^u c_{u}^{\mathrm{fixed}}z_{ojv}+ \sum _{j=1}^N \sum _{v=u+1}^w c_{w}^{\mathrm{fixed}} z_{ojv} \end{aligned}$$
(3)
(3)Delivery cost
Delivery cost is related to factors such as vehicle transportation distance, delivery time, and vehicle path, and generally has a positive correlation with vehicle transportation distance or transportation time. In this article, an expression that is positively correlated with transportation time is adopted. Same as
\(C_2\), the cost of transportation vehicles is divided into two parts, one is the transportation cost of the company’s own vehicles, and the other is the transportation cost of the rented vehicles:
$$\begin{aligned} C_{3} = \sum _{i=0}^{N_0}\sum _{j=1}^N \sum _{v=1}^u c_{u}^{p}t_{ij}z_{ijv}+ \sum _{i=0}^{N_0} \sum _{j=1}^N \sum _{v=u+1}^w c_{w}^{p} t_{ij}z_{ijv} \end{aligned}$$
(4)
(4) Cargo damage cost
Due to the particularity of fresh food, the freshness of fresh food should also be considered as a factor in the model when the cold chain transportation guarantee mechanism in my country is not perfect and the damage is high. As time, temperature, humidity and other external factors change, the quality of food will also change, and the freshness of fresh food will also change due to the difference in warehouse, vehicle, and external environment conditions during loading and unloading. Therefore, the loss cost of fresh food is:
$$\begin{aligned} C_{4} = \sum _{i=0}^N\sum _{j=1}^N \sum _{v=1}^V z_{ijv}\theta (\alpha t_{ij}+\beta )q_{i} \end{aligned}$$
(5)
(5) Time penalty cost
In the process of order receiving, sorting, sorting, and delivery, it is inevitable that there will be delays in delivery or early arrival. The time penalty cost is as follows:
$$\begin{aligned} C_{5}= & {} \sum _{i=0}^N\sum _{j=1}^N \sum _{v=1}^V c_{i}^{\mathrm{earliest}}z_{ijv} \max (t_{i}^{\mathrm{earliest}}-t_{i}^{\mathrm{arrive}},o) \nonumber \\&\quad + \sum _{i=0}^N\sum _{j=1}^N \sum _{v=1}^V c_{i}^{\mathrm{latest}}z_{ijv} \max (t_{i}^{\mathrm{latest}}-t_{i}^{\mathrm{arrive}},o) \end{aligned}$$
(6)
In summary, the distribution schedule and path cost part of the model objective function is as follows:
$$\begin{aligned} \min f_{2}&=C_{1}+C_{2}+C_{3}+C_{4}+C_{5}\nonumber \\&= \sum _{i=1}^N \sum _{h=1}^H t_{i}^{\mathrm{complete}} c_{i}^{\mathrm{pick}} x_{ih}\nonumber \\&\quad + \sum _{j=1}^N \sum _{v=1}^u c_{u}^{\mathrm{fixed}}z_{ojv}+ \sum _{j=1}^N \sum _{v=u+1}^w c_{w}^{\mathrm{fixed}} z_{ojv}\nonumber \\&\quad + \sum _{i=0}^N\sum _{j=1}^N \sum _{v=1}^u c_{u}^{p}t_{ij}z_{ijv}+ \sum _{i=0}^N\sum _{j=1}^N \sum _{v=u+1}^w c_{w}^{p} t_{ij}z_{ijv}\nonumber \\&\quad + \sum _{i=0}^N\sum _{j=1}^N \sum _{v=1}^V z_{ijv}\theta (\alpha t_{ij}+\beta )q_{i}\nonumber \\&\quad + \sum _{i=0}^N\sum _{j=1}^N \sum _{v=1}^V c_{i}^{\mathrm{earliest}}z_{ijv} \max \left( t_{i}^{\mathrm{earliest}}-t_{i}^{\mathrm{arrive}},o\right) \nonumber \\&\quad + \sum _{i=0}^N\sum _{j=1}^N \sum _{v=1}^V c_{i}^{\mathrm{latest}}z_{ijv} \max \left( t_{i}^{\mathrm{latest}}-t_{i}^{\mathrm{arrive}},o\right) \end{aligned}$$
(7)
Since the function
\(f_1\) and the function
\(f_2\) have different dimensions,
\(f_1\) is a time function, and
\(f_2\) is a cost function. In order to improve the solution efficiency of the model, the model is normalized.
$$\begin{aligned} \min F&= \min \omega f_1+ \min (1-\omega ) f_{2}\nonumber \\&= \min \omega \left( \sum _{i \in N} z_{oiv}t_{oi}+\sum _{i \in N}\sum _{j \in N} z_{ijv}t_{ij}\right. \nonumber \\&\quad \left. +\sum _{j \in N}z_{jov}t_{jo}+\sum _{i \in N}\sum _{j \in N} z_{ijv}T_{i} +t_v^\mathrm{{leave}} \right) \nonumber \\&\quad + \min (1-\omega ) \left( \sum _{i=1}^N \sum _{h=1}^H t_{i}^{\mathrm{complete}} c_{i}^{\mathrm{pick}} x_{ih}\right. \nonumber \\&\quad + \sum _{j=1}^N \sum _{v=1}^u c_{u}^{\mathrm{fixed}}z_{ojv}+ \sum _{j=1}^N \sum _{v=u+1}^w c_{w}^{\mathrm{fixed}} z_{ojv}\nonumber \\&\quad + \sum _{i=0}^N\sum _{j=1}^N \sum _{v=1}^u c_{u}^{p}t_{ij}z_{ijv}+ \sum _{i=0}^N\sum _{j=1}^N \sum _{v=u+1}^w c_{w}^{p} t_{ij}z_{ijv}\nonumber \\&\quad + \sum _{i=0}^N\sum _{j=1}^N \sum _{v=1}^V z_{ijv}\theta (\alpha t_{ij}+\beta )q_{i}\nonumber \\&\quad + \sum _{i=0}^N\sum _{j=1}^N \sum _{v=1}^V c_{i}^{\mathrm{earliest}}z_{ijv} \max \left( t_{i}^{\mathrm{earliest}}-t_{i}^{\mathrm{arrive}},o\right) \nonumber \\&\left. + \sum _{i=0}^N\sum _{j=1}^N \sum _{v=1}^V c_{i}^{\mathrm{latest}}z_{ijv} \max \left( t_{i}^{\mathrm{latest}}-t_{i}^{\mathrm{arrive}},o\right) \right) \end{aligned}$$
(8)
$$\begin{aligned} \text {s.t.:}&\sum _{h \in H}x_{ih}=1, \quad \forall i\in N \end{aligned}$$
(9)
$$\begin{aligned}&\sum _{i \in N}x_{ih} q_i \le Q_h, \quad \forall h\in H \end{aligned}$$
(10)
$$\begin{aligned}&t_h^{\mathrm{pick}}=t_h^{\mathrm{start}}+t_h^{\mathrm{service}} \end{aligned}$$
(11)
$$\begin{aligned}&t_i^{\mathrm{complete}}=\sum _{h\in H}x_{ih}t_i^{\mathrm{pick}},\quad \forall i \in N \end{aligned}$$
(12)
$$\begin{aligned}&t_v^{\mathrm{leave}}= \max {t_i^{\mathrm{complete}}y_{iv}}, \quad \forall v\in V \end{aligned}$$
(13)
$$\begin{aligned}&\sum _{i \in N}\sum _{j \in N}q_i z_{ijv}\le Q_v, \quad \forall v\in V \end{aligned}$$
(14)
$$\begin{aligned}&\sum _{v\in V}y_{iv}=\left\{ \begin{array}{ll} V, &{}i=0\\ 1, &{}i \in N \end{array} \right. \end{aligned}$$
(15)
$$\begin{aligned}&\sum _{i \in N}\sum _{v\in V}z_{ijv}= \left\{ \begin{array}{ll} V, &{}j=0\\ 1, &{}j \in N \end{array} \right. \end{aligned}$$
(16)
$$\begin{aligned}&\sum _{j \in N_{0}}z_{ijv} = y_{iv}, \forall i \in N_0.v\in V \end{aligned}$$
(17)
$$\begin{aligned}&\sum _{j \in N}z_{0jv} = 1.\quad \forall v \in V \end{aligned}$$
(18)
$$\begin{aligned}&r_0 = 0 \end{aligned}$$
(19)
$$\begin{aligned}&r_j-r_i \ge (q_i+Q_v)\sum _{v\in V}z_{ijv}-Q_v,\ \forall i \in N_0, j\in N \end{aligned}$$
(20)
$$\begin{aligned}&r_j \le \sum _{i \in N}\sum _{v\in V}z_{ijv}Q_V,\quad \forall j \in N \end{aligned}$$
(21)
$$\begin{aligned}&\sum _{i=0}^N\sum _{j=1}^N z_{ijv}l_{ij}\le l_v^{max}, \quad \forall i,j \in N,v\in V \end{aligned}$$
(22)
$$\begin{aligned}&t_{ij}\ge 0, i,j \in N \end{aligned}$$
(23)
$$\begin{aligned}&c_w^{\mathrm{fixed}} \ge c_u^{\mathrm{fixed}} \end{aligned}$$
(24)
$$\begin{aligned}&c_w^p \ge c_u^p \end{aligned}$$
(25)
Constraint (
9)and (
10) are order batch constraints, to ensure that each order can only be allocated to one order batch, and the maximum amount of goods that can be accommodated in each batch does not exceed
\(Q_b\); Constraint (
11) represents the entire time for order batch
h to complete the picking, including the start picking time and service time; Constraint (
12) represents the entire time for the order to be picked; Constraint (
13) is the time that the vehicle leaves the distribution center after the batch picking of all orders in vehicle
v is completed; Constraint (
14) represents that the vehicle cannot exceed its maximum vehicle capacity in one delivery; Constraints (
15)-(
18) are the constraints of the delivery stage. (
15) represents that a delivery point
i is served by only one vehicle
v; Constraint (
16) represents that the vehicle departs from delivery point 0 and finally returns to delivery point 0; Constraint (
17) represents that if the vehicle entering the vehicle serves delivery point
i, it must leave from delivery point
i; Constraint (
18) represents that each car leaves once from the distribution point at 0:00; Constraint (
19)-Constraint (
21) represents the flow restriction of the distribution point; Constraint (
22) represents that the total mileage cannot exceed the maximum mileage of the vehicle; Constraint (
23) represents that the delivery travel time of the vehicle is not less than zero; Constraints (
24) and (
25) are measures for insufficient enterprise’s own capacity under the surge demand; Constraint (
24) represents that the fixed cost of a single use of rented vehicles
w is greater than the fixed cost of a single use of own vehicles
u, and Constraint (
25) represents that the transportation cost of rented vehicle
w per unit time is greater than the transportation cost of own vehicle
u per unit time.