{'fraction_non_alphanumeric': 0.04341887714758105, 'fraction_numerical': 0.01664150672129969, 'mean_word_length': 4.47373598268739, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 21, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Uncertain multilevel programming with application to omni-channel vehicle routing problem

Multilevel programming is widely applied to solve decentralized decision-making problems. In practice, indeterminacies are presented in these problems due to volatile factors or emergencies. As a type of indeterminacy, uncertainty is introduced in multilevel programming. For resolving multilevel programming problems with uncertain parameters, this paper constructs the uncertain expected value multilevel programming model and chance-constrained multilevel programming. Then, these models are converted to their equivalent forms. Moreover, the Stackelberg-Nash equilibrium solutions are obtained by using a genetic algorithm. Finally, these models are applied to the omni-channel vehicle routing problem, and a numerical experiment is given. The numerical experiment shows that the established models can optimize the distribution efficiency by coordinating the interests of decision-makers.


Introduction
Multilevel programming (MP) is used for connecting each subsystem within a decentralized decision-making system (DDS). Such a system has extensively appeared in numerous large-scale and complicated decision-making problems confronted by government agencies and corporate organizations. Specifically, the MP problem essentially means the upper level decision-maker (the leader) has the authority to control or coordinate the lower level decision-makers (the followers). The leader first makes a decision based on his own constraints to optimize the objective which is dependent on the response of the followers. Then the followers make their decisions and achieve their own goals on the premise of ensuring the benefit of the upper authority. MP originates in two domains: game theory and mathematical programming (Bracken and Mcgill 1973). Since then, MP has been applied to many scenarios, such as supply chain management (Fathollahi-Fard et al. 2022) and electricity distribution economics (Wei et al. 2021).
Due to the real-life complexity of the social and economic environment, various indeterminate factors should be taken into account. These indeterminate factors are described by random variables in probability theory. For example, Patriksson and Wynter (1999) proposed stochastic bilevel programming which is in fact the expected value bilevel model. Patriksson and Wynter (1999) focused on solving stochastic hierarchical decision-making problems, where the leader controls or coordinates only one follower. Gao et al. (2004) considered multiple followers, and established the expected value multilevel programming (EVMP) and chance-constrained multilevel programming (CCMP), respectively. Gao (2004) also developed a general model for dependent-chance multilevel programming (DCMP) in the stochastic environment. The utility of the above models has been proved in practical application problems. Rahmani and Hosseini (2021) applied a stochastic EVMP model to solving an inventory competitive facility location problem.  employed a stochastic CCMP method to design a water-food-ecology interaction mechanism. Fan and Cheng (2014) took advantage of a stochastic DCMP model to resolve the transmission network planning problem.
However, when samples are unavailable, it is too difficult to find the statistical regularity, as well as ensure that the estimated probability distribution adequately approaches the frequency of indeterminate quantity (Liu 2015). At this moment, we have few choices but to request assistance from belief degrees provided by domain experts. To better overcome such a dilemma of indeterminacy, one mathematical system can be employed, uncertainty theory (Liu 2015), which is used to describe indeterminate phenomena associated with experts' belief degrees. In the past few years, researches on uncertainty theory have substantially increased in various scenarios, such as supply chain management , renewal reward process (Yao and Zhou 2018), uncertain reliability analysis (Ahmadzade and Gao 2018), operational law (Wang et al. 2018), uncertain differential equation (Ji and Zhou 2018) and uncertain wave equation (Gao and Ralescu 2019).
Mathematical programming is considered as uncertain programming (UP) when it contains uncertain variables (Liu 2015). In recent years, UP has been well developed in applications, such as black transport network design problem (Hosseini and Wadbro 2022) and minimum spanning tree problem (Majumder et al. 2022). With respect to dealing with the uncertainty in a DDS, Liu and Yao (2015) proposed a hybrid uncertain multilevel programming (UMP) model, where expected values of objective functions are maximized under the corresponding chance constraints for decision-makers in all levels. Thereafter, Ning and Su (2017) combined the uncertain multilevel approach and the classic vehicle routing problem with time windows. Jalil et al. (2018) presented a multilevel solid transportation problem with uncertain parameters.
A few existing MP models are proposed with uncertain factors, while many of them are under random or fuzzy environment. However, there are shortcomings in the applicability of stochastic MP and fuzzy MP. For example, probability theory relies on historical data heavily. Fuzzy set theory lacks self-duality, and the possibilities of two opposite events do not add up to 1. In addition, there are limited types of UMP models as well as finite application scenarios. For example, commuters in traffic assignment problems might seek to reach the destination on schedule (Ke et al. 2017), and the model built by Liu and Yao (2015) is improper for this case. For another instance, decision-makers of transportation companies or hotels may prefer the CCMP model to optimize their profits considering the impact of COVID-19 under uncertain environment. Inspired by such research status, EVMP and CCMP models need to be established to enhance their applicability.
This study differs from current literatures because of the following contributions. For one thing, this paper extends the study of Liu and Yao (2015) and suggests two uncertain multilevel models called EVMP and CCMP as well as their deterministic equivalents. For another, we apply proposed models to an omni-channel vehicle routing problem (OVRP), which has not yet been studied via the UMP approach. The proposed models are resolved by a genetic algorithm. The remainder of the study is constructed as follows. Related works are introduced in Sect. 2. Section 3 lists some preliminary knowledge of uncertainty theory. In Sect. 4, the UMP models are respectively built via the EVP and CCP approaches, and then the corresponding deterministic equivalents are presented. In Sect. 5, we introduce a computational approach of the Nash equilibrium for the multiple followers and a genetic algorithm to find the Stackelberg-Nash equilibrium of each launched uncertain multilevel model. And Sect. 6 gives the applications of proposed models in OVRP to evince the availability of the designed formulation and solution procedure. Last but not least, Sect. 7 provides a brief summary.

Related work
This section will introduce the related works containing UMP and OVRP.

Uncertain multilevel programming
MP was first proposed by Bracken and Mcgill (1973) to solve decentralized decision-making problems in a hierarchical system. So far, MP has been well applied to many real-life scenarios, such as missile defense (Haywood et al. 2022). Furthermore, since MP is NP-hard (Ben-Ayed and Blair 1990), scholars have introduced many algorithms, such as evolutionary algorithm (Abo-Elnaga and Nasr 2022) and branch-and-bound algorithm (Liu et al. 2021).
For handling MP with random parameters, Patriksson and Wynter (1999), Gao et al. (2004) and Gao (2004) studied three commonly used modeling techniques which are EVP, CCP and dependent-chance programming (DCP). After that, Huang and Ke (2016) built a hybrid MP model, where the random variables are handled by EVP for the leader but DCP for the followers. Roghanian et al. (2007) stated the stochastic multilevel multiobjective programming. Moreover, scholars have introduced plenty of applications such as facility location (Rahmani and Hosseini 2021) and energy dispatch (Su et al. 2022).
For dealing with uncertain variables in MP, Liu and Yao (2015) developed an UMP model. Thereafter, Xue et al. (2020) introduced the UMP into the bus line distribution problem. Guo et al. (2022) suggested a vehicle scheduling method for electric buses based on the UMP approach.
Existing researches on MP lacks sufficient consideration of uncertain coefficients. Specifically, there are EVP, CCP and DCP in UP, which are not completely studied in UMP. Moreover, UMP needs more research on algorithms such as ant colony optimization (Ramamoorthy and Thangavelu 2022c), and applications such as vehicular ad-hoc networks (Ramamoorthy and Thangavelu 2022b) and OVRP (Abdulkader et al. 2018).

Omni-channel vehicle routing problem
The vehicle routing problem (VRP) aims at designing the least-cost delivery routes from a depot to scattered nodes under some constraints. By now, many literatures on VRP have emerged, such as open VRP (Dutta et al. 2022a) and green VRP (Dutta et al. 2022b).
The OVRP (Abdulkader et al. 2018) is actually a rich vehicle routing problem under the omni-channel retailing scenario. In addition, Dethlefs et al. (2022) combined the rapid integrated order fulfillment and multi-depot VRP for omni-channel retailing. Schubert et al. (2021) integrated the order picking problem and VRP for same-day delivery. Janjevic et al. (2021) established a three-tiered supply chain network for omni-channel retail. However, the coordination of multiple channels cannot be achieved overnight. Guo et al. (2021) employed an auction mechanism for omni-channel on-demand logistics. There also exist studies on OVRP containing random variables. For example, Martins et al. (2020) proposed a stochastic OVRP model with the random vehicle travel time.
The related researches on OVRP is currently lacking consideration for more types of indeterminacies such as fuzzyness (Barma et al. 2021) and uncertainty (Ning and Su 2017), and modelling techniques such as MP (Guo et al. 2022) and multiobjective programming ). Additionally, more algorithms can be applied to solving OVRP, such as bio-inspired routing algorithm (Ramamoorthy and Thangavelu 2022), ant colony optimization (Ramamoorthy and Thangavelu 2022a) and genetic algorithm (Katoch et al. 2021).

Preliminary
This part of the paper briefly introduces some fundamental definitions and properties in uncertainty theory and MP.

Uncertainty theory
Suppose that is a nonempty set and let L represent a -algebra over . Any element in L is an event. However, we pay more attention to the belief degree of the event happening. To cope with belief degrees, Liu (2015) presented the definition of uncertain measure. Suppose that is an uncertain variable with uncertainty dis- has the unique inverse function −1 ( ) for each ∈ (0, 1) , then the uncertainty distribution (x) becomes regular.

Definition 2.2 (Liu 2015)
The uncertain variables 1 , ⋯ , n are thought to be independent if for any Borel sets B 1 , ⋯ , B n .
Theorem 2.1 (Liu 2015) Suppose 1 , ⋯ , n are independent uncertain variables and have uncertainty distributions 1 , ⋯ , n , respectively. Assume that f (x 1 , ⋯ , x n ) is a real continuous function, which monotonously increases as x 1 , ⋯ , x m increase and monotonously decreases as

an uncertain variable and has an inverse uncertainty distribution
where is a real number and 0 ≤ ≤ 1.

Definition 2.3 (Liu 2015)
The expected value of an uncertain variable is defined by on the premise that one integral is finite at least. (Liu 2015) Suppose is an uncertain variable and has a regular uncertainty distribution . We have on the premise that there exists the expected value.

Multilevel programming
Consider a two-level decentralized decision-making problem with one leader and m followers, and all decision-makers have their own decisions and objectives. Firstly, the upper level authority makes the decision to minimize the leader's objective function which is dependent on the response of the followers. Then, after observing the leader's control vector, the followers generate their own decision vectors to achieve their own goals on the premise of ensuring the benefit of the upper authority. Then Ke et al. (2017)

Uncertain multilevel programming
Consider a two-level DDS with one leader and m followers, and the upper and lower levels have their own decisions and objectives. A simple instance of the DDS is shown in Fig. 1.
To better meet the different needs in practical circumstances, this section will respectively introduce the EVMP and CCMP under uncertain environment.

Expected value multilevel programming
In UP, the objective and the constraints cannot be directly ranked as both of them contain uncertain variables. One method is to compare the corresponding expected values. The expected value model is the mathematical programming where both the uncertain objective function and the uncertain constraints are handled by the expected value approach. Based on this point of view, we propose an expected value uncertain multilevel programming (EVUMP) model.
Firstly, the upper level authority makes the decision to minimize the leader's objective function which is dependent on the response of the followers. Then, after observing the leader's control vector, the followers generate their own decision vectors to achieve their own goals on the premise of ensuring the benefit of the upper authority. Then we have the following EVUMP model where x is the leader's control vector, y i is the ith follower's control vector, In Model (7), F, G, f i and g i ( i = 1, ⋯ , m ) are thought to be uncertain variables caused by the uncertain vector . This is said to be a Stackelberg-Nash equilibrium to Model (7) if there exists a feasible control vector x * of the upper level such that holds for any feasible decision x , where (y 1 , ⋯ , y m ) and (y * 1 , ⋯ , y * m ) are the followers' Nash equilibrium solutions and respectively dependent on x and x * . Now, we transform Model (7) into its crisp equivalent form by using Theorem 2.1 and Theorem 2.2.
Suppose that F is a real continuous function, which monotonously increases as 1 , ⋯ , k increase and monotonously decreases as k+1 , ⋯ , n decrease. In addition, 1 , ⋯ , n are independent uncertain variables and have uncertainty distributions 1 , ⋯ , n , respectively. Then Assume that f i is a real continuous function, which monotonously increases as 1 , ⋯ , k j increase and monotonously decreases as k j +1 , , ⋯ , n decrease, and 1 , ⋯ , n are independent. Then Suppose that G is a real continuous function, which monotonously increases as 1 , ⋯ , s increase and monotonously decreases as s+1 , ⋯ , n decrease, and 1 , ⋯ , n are independent. Then E[G(x, 1 , ⋯ , n )] ≤ 0 equals to Supppose that g i is a real continuous function, which monotonously increases as 1 , ⋯ , s j increase and monotonously decreases as s j +1 , ⋯ , n decrease, and 1 , ⋯ , n are independent. Then E[g i (x, y 1 , ⋯ , y m , 1 , ⋯ , n )] ≤ 0 is equivalent to Then Model (7) is equivalent to Model (15).

Chance-constrained multilevel programming
CCP remains an effective tool for UP. The core principal of CCP is that control vectors are permitted to mismatch the constraint conditions in a way, but should at least make the constraint conditions hold with a confidence level. This confidence level actually reflects the decisionmaker's desire that the uncertain constraints hold. Motivated by this ideology, we construct the following chanceconstrained uncertain multilevel programming (CCUMP). Firstly, the upper level authority makes the decision to minimize the leader's objective function which is dependent on the response of the followers. Then, after observing the leader's control vector, the followers generate their own decision vectors to achieve their own goals on the premise of ensuring the benefit of the upper authority. Then we have a CCUMP model as follows where x is the leader's control vector, y i is the ith follower's control vector, = ( 1 , ⋯ , n ) is the uncertain vector with independent uncertain variables 1 , ⋯ , n , F(x, y * 1 , ⋯ , y * m , ) is the leader's objective, G(x, ) ≤ 0 is the leader's constraint, f i (x, y 1 , ⋯ , y m , ) is the ith follower's objective, g i (x, y 1 , ⋯ , y m , ) ≤ 0 is the ith follower's constraint, F and f i are respectively critical values for the leader and the ith follower's objective, 0 , 0 , i and i are given confidence levels, and i = 1, ⋯ , m.
In Model (14), the CCP approach is employed as well as critical values for the leader and the followers. This is because the objective functions and the constraint conditions are uncertain variables, and directly minimizing them makes no sense mathematically.
Definition 3.2.1 For a feasible decision x of the upper level, the feasible array (y * 1 , ⋯ , y * m ) is said to be a Nash equilibrium of the lower level if it satisfies on the premise that (y * 1 , ⋯ , Definition 3.2.2 The array (x * , y * 1 , ⋯ , y * m ) is said to be a Stackelberg-Nash equilibrium to Model (15) if there exists a feasible control vector x * of the upper level such that holds for any feasible decision x , where (y 1 , ⋯ , y m ) and (y * 1 , ⋯ , y * m ) are the followers' Nash equilibrium solutions and respectively dependent on x and x * .
According to Theorem 2.1, Model (14) is able to be transformed to a deterministic equivalent model.
Assume that F is a real continuous function, which monotonously increases as 1 , ⋯ , k increase and monotonously decreases as k+1 , ⋯ , n decrease. In addition, 1 , ⋯ , n are independent uncertain variables and have uncertainty distributions 1 , ⋯ , n , respectively. We have equals to Proof Assume that is the uncertainty distribution of F(x, y * 1 , ⋯ , y * m , 1 , ⋯ , n ) . According to the definition of uncertainty distribution, we have Formula (18) equals to F ≥ 0 .
It follows from Theorem 2.1 that −1 ( 0 ) equals to

Hence, Formula (18) holds if and only if Formula (19) holds.
Assume that f i is a real continuous function, which monotonously increases as 1 , ⋯ , k j increase and monotonously decreases as k j +1 , ⋯ , n decrease, and 1 , ⋯ , n are independent. Similar to the above proof, we have Let G be a real continuous function, which monotonously increases as 1 , ⋯ , s increase and monotonously decreases as s+1 , ⋯ , n decrease, and 1 , ⋯ , n are independent. Similarly, we have M G(x, 1 , ⋯ , n ) ≤ 0 ≥ 0 equals to Let g i be a real continuous function, which monotonously increases as 1 , ⋯ , s j increase and monotonously decreases as s j +1 , ⋯ , n decrease, and 1 , ⋯ , n are independent. Then M g i (x, y 1 , ⋯ , y m , 1 , ⋯ , n ) ≤ 0} ≥ i equals to where i = 1, 2, ⋯ , m.

Intelligent algorithm
To calculate the Stackelberg-Nash equilibrium, we intend to present a genetic algorithm with the Nash equilibrium computation based on Liu (1998).

Nash equilibrium computation
Define y −i = (y 1 , y 2 , ⋯ , y i−1 , y i+1 , ⋯ , y m ) . After observing decisions of the other decision-makers in MP, the ith follower is able to make the optimal response y i = h i (y −i ) by solving the following problem The formula y i = h i (y −i ) essentially turns the subproblem of the ith follower to a parametric optimization problem, where x and y −i form the parameters. Then, the followers' Nash equilibrium solution should solve the following subproblem for EVUMP or the following optimization model for CCUMP We regard y * 1 , ⋯ , y * m as the followers' Nash equilibrium if it satisfies Otherwise, we suggest that there is not a Nash equilibrium solution with respect to a given decision x.

Genetic algorithm
Combined with the Nash equilibrium computation, we give the following procedures of the genetic algorithm as well as a pseudo-code.
Step 1: Initialization. Generate a fixed amount of feasible chromosomes to form a population.
Step 2: Crossover. Randomly choose chromosomes to cross and keep feasible offsprings.
Step 3: Mutation. Randomly choose chromosomes for mutation and remove the infeasible ones.
Step 4: Fitness evaluation. For each chromosome, calculate the related Nash equilibrium to compute the leader's objective which is the fitness.
Step 5: Selection. Run the tournament selection operator for a specified scale.
Step 6: Return to step 2 for a given number of iterations, and print out the best chromosome.

Uncertain multilevel omni-channel vehicle routing problem
UMP will be introduced into the classic OVRP (Abdulkader et al. 2018) in this part, which is inspired by the following two factors. For one thing, an omni-channel approach seeks to provide a coherent cross-channel experience for consumers by coordinating the divided resources of multiple channels (Liu et al. 2020). For another, the multilevel approach has been studied in the transport field (Ning and Su 2017).

Problem description
In an OVRP, online consumers' orders and offline replenishment orders are fulfilled by a same fleet simultaneously, which differs from classic VRPs. We consider an omnichannel distribution system that includes a warehouse, retail stores, consumers and homogeneous vehicles. Some assumptions are listed below: -One vehicle is dispatched only once.
-Both the start and end points are the warehouse.
-The start time of all vehicles is 0.
-Each node is only visited once, except the warehouse.
-Consider various products with known inventory levels.
-Demands of all nodes are known.
-The vehicle capacity should not be exceeded, and consumer demands could be ignored at this time. -Consumers are only supplied by retail stores, and retail stores are only supplied by the warehouse. -Consumers are only visited after the retail store that supplies them.
In addition, the travel time of vehicles is considered to be an uncertain variable due to the changeful weather and traffic jams.

Mathematical models
For the online channel and omni-channel retail industries, one year can be simply divided into two periods: peacetime and shopping festivals such as Black Friday in North America. For these two different periods, we will construct the EVMP and CCMP models for the OVRP, respectively. In MP, decision-makers have their own decisions and objectives. In this problem, we presume that the retailing company first determines the promising assignments and then the travelers optimize the routes of these assignments. In addition, we assume that the retailing company desires to minimize the total operational time for improving distribution efficiency and providing seamless services for consumers. The seamless services are highlighted by Abdulkader et al. (2018) in OVRP. For the lower level, the travelers seek to reduce the cost by minimizing the total travel distance. ij : uncertainty distribution of ij , i, j ∈ N; d p i : demand of consumer i for product p, i ∈ C, p ∈ P; d i : demand of store i provided by the warehouse, i ∈ R; I p i : inventory level of product p at store i, i ∈ R, p ∈ P; D ij : travel distance of vehicles from i to j, i, j ∈ N. The leader's decision vectors are listed as follows, u i,j : binary variable equals 1 if the product consumer j ordered is provided by retail store i and 0 otherwise, i ∈ R, j ∈ C. v k,i : binary variable equals 1 if retail store i is visited by vehicle k and 0 otherwise, i ∈ R, k ∈ K.
For ease of demonstration, let u and v respectively denote the control vector containing every u i,j and v k,i for i ∈ R , j ∈ C and k ∈ K . Let R k and C i indicate the set of retail stores assigned to vehicle k and the set of consumers assigned to retail store i, respectively. Then we have R k = 1 ⋅ v k,1 , ⋯ , r ⋅ v k,r , and C i = (r + 1) ⋅ u i⋅v ki ,r+1 , ⋯ , (r + c) ⋅ u i⋅v ki ,r+c . Let N k present the set of nodes visited by vehicle k. For any k ∈ K , we have N k = R k ∪ C 1⋅v k,1 ∪ ⋯ ∪ C r⋅v k,r .
Suppose that there are n k elements in N k . The kth (k ∈ K) follower's decision vector is listed as follows is a rearrangement of all elements in N k . Let x i k x k , present the departure time of vehicle k at node x i k , where x i k ∈ N k . For any vehicle k with k ∈ K , if there is any non-zero element in the N k , then we have

EVUMP models for OVRP
In peacetime, the number of orders should not be particularly large, and it is unnecessary to worry about delayed deliveries. In this case, decision-makers are risk-neutral, so we have the EVUMP model as follows For the leader, the first inequality confirms that the vehicle capacity should not be exceeded. The second inequality ensures that inventory levels should not be surpassed for each kind of product. The third and fourth constraints jointly confirm that every node is served. For the followers, the inequality implies that consumers are visited after their service providers. Other constraints depict the decision vectors.

CCUMP models for OVRP
A large number of orders are produced during the shopping festivals. In these periods, decision-makers are risk-averse and desire to avoid express delivery backlogs. Consequently, we launch the following CCUMP model 0 , i are known confidence levels, and i ∈ N.

Numerical experiment
This section suggests a numerical example for UMOVRP. Assume there are 1 warehouse, 4 retailing stores and 6 consumers. Three vehicles form the fleet and the vehicle capacity is 100. Three types of products can be ordered online by consumers. Assume that the travel time from node i to node j is a linear uncertain variable L(0.1|i − j| − 1, 0.1|i − j| + 1), i ≠ j, i, j = 0, ⋯ , 10. And we also assume that is the uncertainty distribution of the uncertain departure time . More data about the distribution network are listed in Table 1, where the notation "X" and "Y" jointly denote the two-dimensional coordinates of nodes and other notations are already declared in Sect. 5.1.

Expected value model
In the peacetime, Model (29) for this example can be converted to Model (31) according to Sect. 3.1.

Chance-constrained model
During shopping festivals, we assume that confidence levels 0 , i all equal to 0.90 for i = 1, ⋯ , 10 . For this instance, we have Model (32) which is the crisp equivalent of Model (30) according to Sect. 3.2.
According to Table 2, the travel cost of the EVUMP model increased by 3.1% compared to the classic OVRP, while the total operational time decreased by 16%. Although disappointing about the increase in cost, this result shows that EVUMP helps to coordinate the interests of the upper and lower levels in peacetime. For the CCUMP model, its travel cost increased by 7.7% compared to the classic OVRP, while the total operational time decreased by 20%. This result is reasonable because retailing companies are willing to avoid delayed deliveries and the loss of consumers by sacrificing a part of profits for higher efficiency during shopping festivals.

Conclusion
The contributions of this work are as follows. For one thing, this paper built EVUMP and CCUMP models as well as their equivalent crisp models. For another, this paper applied the presented UMP models to the OVRP. Then, a numerical example is given. The results of the numerical experiment are obtained by an intelligent algorithm. The results show that the proposed models are able to optimize the distribution efficiency by coordinating the interests of the leader and followers.
For future research, we have the following directions. Firstly, it is worthwhile to consider the multi-objective case in UMP. Thereafter, another research direction is to apply UMP to many more fields, such as the attacker-defenders scenario. Furthermore, we will continue to design more effective algorithms.