A discrete Jaya algorithm for vehicle routing problems with uncertain demands

Abstract

Vehicle Routing Problem with Uncertain Demands (VRPUD) is one of the research hotspots in the field of logistics scheduling. In this paper, a Discrete Jaya (DJaya) algorithm is presented for the VRPUD to minimize the total cost. A novel dividing-point-based coding scheme is designed to represent solutions with higher robustness. In addition, an efficient repair strategy is embedded into the decoding process to avoid the failure of producing feasible solutions. The best and worst solutions are employed to generate offspring solutions in DJaya. Several efficient local search methods are also presented to enhance the exploitation ability and increase the diversity of solutions. Based on the benchmark data sets of the VRPUD, numerical simulations are carried out for the proposed DJaya algorithm with uncertain demands. Computational results and comparisons with the state-of-the-art algorithms demonstrate the superiority of the proposed algorithm in solving VRPUD.

KEYWORDS:

• Jaya algorithm
• vehicle routing problem
• uncertain demand
• local search

1. Introduction

Vehicle Routing Problem (VRP) was first proposed by Dantzig and Ramser, (1959), which has significant interests in both the engineering optimization field and real-world applications. The objective of VRP is to generate optimal vehicle routes for a distribution centre to achieve minimum distribution costs. So far, many forms of VRP have been presented with various practical constraints, including Split Delivery VRP (SDVRP) (Archetti et al., 2011), Capacitated VRP (CVRP) (Mazzeo & Loiseau, 2004), Weighted VRP (WVRP) (Wang et al., 2021) and VRP with Time Window (VRPTW) (Keskin & Çatay, 2016). It should be pointed out that customer demands are assumed to be constant in the mentioned VRP variants, while the diversity and uncertainty of customer demands possibly cause the corresponding routes to be infeasible. For example, if the customer makes a temporary increase in their order, the original delivery scheme may fail due to capacity constraints. Thus, VRP with Uncertain Demands (VRPUD) has received increasing attention in the past few years (Aïder & Skoudarli, 2020; Allahyari et al., 2021; Moghaddam et al., 2012; Qin et al., 2017).

As well known, VRP is a classical combinatorial optimization problem and has been proven to be NP-hard. The research results on VRP are extensive and various algorithms have been presented to solve VRP up to now (Braekers et al., 2016; Mor & Speranza, 2022). Generally speaking, these algorithms can be divided into exact algorithms and intelligent algorithms, respectively (Mor & Speranza, 2022). The exact algorithms include the branch and boundary method, branch cutting method and set covering method (Baldacci et al., 2012; Gendreau et al., 1995). Although convergence to the global optimal solution can be guaranteed for the exact algorithms, the computational cost becomes unacceptable as the number of customers and vehicles grows to certain extents. Actually, large-scale VRPs is more commonly seen than small ones in the modern logistics field. Thus, intelligent algorithms, including heuristic, meta-heuristic and hyper-heuristic algorithms, are employed to solve large-scale VRP with improved searching efficiency. The main objective is to find high-quality solutions rather than optimal solutions in acceptable computational times by using intelligent algorithms to solve VRP. Effective algorithms can be referred to as simulated annealing, Tabu search, genetic algorithm and genetic programming hyperheuristic (Brandão, 2011; MacLachlan et al., 2020; Potvin & Bengio, 1996; Tuzkaya et al., 2012). On the other hand, local search is always required for large-scale problems since the exploitation ability of meta-heuristic algorithms is not sufficient. There are many hybrid algorithms for solving VRP, for example, the inferior bidirectional search algorithm (Cabrera et al., 2020), hybrid evolutionary algorithm (Euchi et al., 2015) and the hybrid firefly algorithm (Altabeeb et al., 2019).

As for the VRPUD, the uncertain demands of customers cause additional constraints and make the problem more difficult to solve (Subramanyam et al., 2020; Zhang et al., 2021). Generally speaking, the main issue is that the obtained routes may be infeasible if the capacity of the vehicle is exceeded. Thus, solutions with robustness against uncertainty are required for the VRPUD. In the existing literature, stochastic variables and fuzzy logic are commonly used to describe uncertain demands (Ismail & Irhamah, 2008; Kuo & Zulvia, 2017). Few results were VRPUD with stochastic variables representing the uncertain demands. Sungur et al. (2008) proposed a robust optimization problem for the VRPUD with the objective of minimizing the transportation cost. The results showed that moderate uncertainty can be tolerated by a small additional cost. Moghaddam et al. (2012) presented an advanced particle swarm optimization algorithm that was proposed to solve the VRPUD with a novel decoding scheme. A hybrid variable neighbourhood search was presented by (Zhang et al. (2019) for electrical VRPUD considering battery swap stations. Ismail and Irhamah (2008) presented a novel genetic algorithm that automatically adapts the mutation probability to capture dynamic changes in the population. These research results were shown to be effective. However, one drawback of these algorithms is that they always involve some parameters to adjust before applications.

The Jaya algorithm was first proposed by Rao et al. (2016). Based on the principle of continuous improvement, the Jaya algorithm keeps individuals closer to excellent ones and away from poor ones in continuous iteration to improve the quality of solutions. Different from other algorithms, the Jaya algorithm obtains new solutions through the iterative evolution of formulas. Thus, it only needs to adjust the parameter required by iteration for specific problems, reducing the time increase caused by excessive parameters. At present, the Jaya algorithm has been extensively applied in many specific fields, such as project scheduling (Li et al., 2022), flow-shop scheduling (Alawad & Abed-Alguni, 2022), text document clustering (Thirumoorthy & Muneeswaran, 2021), unconstrained numerical optimization problems (Farah & Belazi, 2018) and parameter estimation (Premkumar et al., 2021). In this paper, a Discrete Jaya algorithm (DJaya) is proposed to solve the VRPUD with the objective of minimizing the total cost. Coding and decoding schemes are designed to represent the solution efficiently and avoid infeasible solutions. The best and worst solutions generate offspring to guide the searching direction in DJaya. Additionally, local search operators are presented to increase the diversity of solutions. Experimental results show the effectiveness of the proposed DJaya algorithm.

The main contribution of this paper is summarized as follows: (1). A novel encoding scheme based on dividing points is proposed to encode a feasible solution more effectively. (2). an efficient repair strategy is embedded into the decoding process to avoid the failure producing feasible solutions. (3). A set of local search strategies is designed and embedded within the DJaya framework. The rest of the paper is organized as follows: Section 2 describes the VRPUD by a mathematical model while Section 3 introduces the Jaya algorithm. The framework is illustrated in Section 4. Section 5 shows the simulation and comparison analysis, and a conclusion is given in Section 6.

2. Problem description

The notations used in the optimization model of VRPUD are presented in Table 1.

Table 1. Notations used in the optimization model for the VRPUD.

Indices
$i$,$j$	Index for customers where $i=1,\dots ,n$, $j=1,\dots ,n(i\ne j)$
$k$	Index for vehicles where $k=\text{1,}\dots ,m$
Parameters
$n$	The number of customers
$m$	The number of vehicles
$K$	The set of vehicles
$X$	The set of individuals
$ϵ$	The perturbation percentage of the demand
$\mathrm{\Lambda }$	A given feasible schedule
Variables
$x_{\mathrm{ijk}}$	Define whether vehicle $k$ goes from customer $i$ to customer $j$
$y_{\mathrm{ik}}$	Define whether the customer is delivered by vehicle $k$
$r$	Uniform random number in the interval [0,1]
${\tilde{d}}_i$	The demand of the customer $i$
$c_{i,j}$	The travel distance from node to $i$ node $j$
$R_k$	The route of vehicle $k$
$C_{min}$	Makespan value

Different from the traditional VRP, VRPUD additionally requires the obtained delivery scheme to be robust enough to avoid the negative impact of demand uncertainty. As shown in Figure 1, the factory receives a number of customers’ orders (c₁, c₂ … c_n) from everywhere with their various demands, which are displayed as various graphics, while these demands are treated as the same unit in this research. Then, intelligent optimization algorithms are applied to produce a delivery route, in which each customer is assigned to the delivery vehicle (k₁, k₂ … k_m) provided by the factory in a planned way, thus each vehicle forms a corresponding delivery route. The algorithm proposed in this paper achieves the distribution route with a specified number of vehicles, and the expression form of the result is shown in the schematic diagram. As can be seen from Figure 1, seven customers are assigned to three vehicles, each vehicle starts from the central point, passes by customers needing service and eventually returns to the centre. The routes of the three vehicles are marked in red, green and blue, respectively.

Figure 1. Illustration of the VRPUD.

It should be pointed out that feasible solutions for a given demand may become infeasible after fluctuation. In order to deal with this situation, a specific value is given to represent the fluctuation degree of customers’ actual demand. An example shown in Table 2 is given to further illustrate this point. The example has six customers and two vehicles where the depot is the starting and returning locations of the vehicles, while the relative coordinates and demands of each customer are listed in the table. Feasible distribution routes for vehicle 1 and vehicle 2 are [1-3-4] and [2-5-6], respectively. However, when the disturbance factor is added, the actual demand of customers may be greater than the value provided in the table, which leads to the infeasibility of the original distribution scheme because the total demand ofcustomers 2, 5 and 6 exceeds the maximum load of vehicles. This kind of problem often occurs in the actual allocation process, so how to design the algorithm to make the solution to deal with the difficulties caused by uncertain demands is the key point of the research.

Table 2. An example of VRPUD including six customers served by two vehicles.

Customer	Depot	1	2	3	4	5	6
Coordinates	50	42	55	21	45	85	60
	50	36	62	48	70	20	38
Demand	0	27	35	20	38	25	40
Capacity of each vehicle: 100

The VRPUD problem can be described by a mathematical model as follows: there is a directed graph $G=(V,E)$, where $V=\left\{0\right\}\cup V_C$ represents a set of nodes, where the node 0 represents the depot, $V_C=\{1,2,\dots ,n\}$ is a set of edges, each representing a customer with uncertain demand. Additionally, it is supposed that ${\text{c}}_{\mathrm{ij}}$ represents the distribution cost between nodes $i$ and $j$, which is proportional to the distance between two points, $k=\{1,2\dots K\}$ represents the collection of available distribution vehicles, and $d_i$ is the demand of corresponding customers. This research considers no known or assumed distribution for demands. Let $\widetilde{d_i}$be the customer demand $(d_i-ϵd_i\le \widetilde{d_i}\le d_i+ϵd_i)$, where $ϵ$ is a constant indicating the perturbation percentage and $d_i$ is the nominal demand. Define the variables as follows: (1) $\begin{array}{rl}{y}_{\mathrm{ik}}& =\{\begin{array}{ll}1& \begin{array}{c}\begin{array}{c}\begin{array}{c}i\text{is}\end{array}\text{delivered}\end{array}\text{by}k\end{array}\\ 0& \text{otherwise}\end{array}\end{array}$(1) (2) $\begin{array}{rl}{x}_{\mathrm{ijk}}& =\{\begin{array}{ll}1& \begin{array}{c}\begin{array}{c}\begin{array}{c}k\text{goes}\end{array}\text{from}\end{array}i\begin{array}{c}\mathrm{to}j\end{array}\end{array}\\ 0& \text{otherwise}\end{array}\end{array}$(2)

The mathematical model is established as follows: (3) $\begin{array}{rl}& min\sum _{i\in V}\sum _{j\in V}\sum _{k\in K}{c}_{\mathrm{ij}}{x}_{\mathrm{ijk}}\end{array}$(3) (4) $\begin{array}{rl}& \text{s}\text{.t}\text{.}\sum _{i\in V}\sum _{j\in V_0}x{}_{\mathrm{ijk}}\cdot {\tilde{d}}_i\le M,\mathrm{\forall k}\in K\end{array}$(4) (5) $\begin{array}{rl}& \sum _{i\in V}{x}_{\mathrm{ijk}}=\sum _{i\in V}{x}_{\mathrm{jik}}=1,\mathrm{\forall j}\in V_0,\mathrm{\forall k}\in K\end{array}$(5) (6) $\begin{array}{rl}& x_{\mathrm{ijk}}=0,\mathrm{\forall i}=j,\mathrm{\forall i},j\in V,\mathrm{\forall k}\in K\end{array}$(6) (7) $\begin{array}{rl}& \sum _{j\in V_0}{x}_{\mathrm{ojk}}=\sum _{j\in V_0}{x}_{\mathrm{jok}}\le 1,\mathrm{\forall k}\in K\end{array}$(7) (8) $\begin{array}{rl}& \sum _{k\in K}{y}_{\mathrm{ik}}=1,\mathrm{\forall i}\in V_0\end{array}$(8) (9) $\begin{array}{rl}& \sum _{j\in V}{x}_{\mathrm{ijk}}=y_{\mathrm{ik},}\mathrm{\forall i}\in V_{0,}\mathrm{\forall k}\in K\end{array}$(9) (10) $\begin{array}{rl}& \sum _{i\in V}{x}_{\mathrm{ijk}}=y_{\mathrm{jk}},\mathrm{\forall j}\in V_0,\mathrm{\forall k}\in K\end{array}$(10) (11) $\begin{array}{rl}& \sum _{i\in S}\sum _{j\in S}{x}_{\mathrm{ijk}}\le |S|-1,\mathrm{\forall S}\subseteq V_0,\mathrm{\forall k}\in K\end{array}$(11) (12) $\begin{array}{rl}& x_{\mathrm{ijk}}\in \left\{0,1\right\},y_{\mathrm{ik}}\in \left\{0,1\right\},\mathrm{\forall i},j\in V,\mathrm{\forall k}\in K\end{array}$(12)

Equation (3) indicates that the objective function is to minimize the distance; Equation (4) represents the constraint on customer demand which forms a random variable; Equation (5) ensures that each customer has and is only served by one vehicle; Equation (6) indicates that there is no connected path between the same nodes; Equation (7) means that each vehicle only serves one route when driving, and the starting point is the distribution centre. Equation (8) guarantees that every customer is served; Equations (9) and (10) show that when a customer is delivered by a vehicle, there must be a path connected to it. Equation (11) determines the elimination of subloops and Equation (12) is the value of the decision variable.

3. Jaya algorithm

Many meta-heuristic algorithms have multiple stages of evolution that necessitate fine adjustment of algorithm-specific parameters. The Jaya algorithm, on the other hand, has only one evolution phase and two key control parameters (population size and stopping criterion) so it reduces the trouble in testing caused by adjusting too many parameters and is easier to understand and implement than other meta-heuristic algorithms. Suppose that $x_{i,j,k}$ is the value of the $k_{\mathrm{th}}$ variable for the $j\text{th}$ candidate solution at the $i\text{th}$ iteration, $r_1$ and $r_2$ are two random variables within [0,1], $x_{i,B,k}$ and $x_{i,W,k}$ are the best and worst value of the $k\text{th}$ variable at $i\text{th}$ iteration respectively. Then, the new solution can be determined by Equation (13): (13) ${x^{\mathrm{\prime }}}_{i,j,k}=x_{i,j,k}+r_1\times (x_{i,B,k}-|x_{i,j,k}|)-r_2\times (x_{i,W,k}-|x_{i,j,k}|)$(13) The procedure of the Jaya algorithm can be stated as follows and the flowchart is given in Figure 2:

Figure 2. The flowchart of the Jaya algorithm.

Step 1: Initialize the population size and stopping criterion.

Step 2: Identify the best and worst solutions in the population at each iterative process.

Step 3: Generate new solutions based on the best and worst solutions. Replace the old solution and preserve the better one.

Step 4: Repeat the procedure from Step 2 to Step 3 until the termination condition is satisfied, and output the best solution found so far.

4. DJaya algorithmic framework for VRPUD

4.1. Encoding and decoding schemes

The M1 encoding scheme proposed by Babak Moghaddam et al. (2012) is frequently used to represent the feasible solutions for VRPUD. In the DJaya algorithm, an efficient encoding and decoding scheme based on dividing points is presented to produce feasible solutions with higher robustness and a novel repair strategy is also embedded into the decoding process to avoid the failure of producing corresponding solutions, while it is called the repair-based decoding scheme (RDS) in this paper. The solution is represented by an integer sequence with length $n+m-1$. For the $i\text{t}{\text{h}}_{}$ individual $i_{\mathrm{th}}$, its corresponding solution is $X_i=\left[\begin{array}{cccc}{x}_1^i& x_2^i& \dots & x_{n+m-1}^i\end{array}\right]$, where $x_j^i=n+1,n+2,\dots ,n+m-1$ are dividing points. The dividing points divide $i_{\mathrm{th}}$ into $m$ sub-sequences to represent the routes of the $m$ vehicles, respectively. Assuming that seven customers have placed orders that need to be allocated to three vehicles for delivery, then a corresponding solution $\mathrm{\Lambda }$ can be illustrated in Figure 3. The route for vehicle 1 will be [2-5-4]. Similarly, the route for vehicle 2 and vehicle 3 will be [7-3] and [1-6], respectively.

Figure 3. Illustration of the encoding of a solution.

The makespan value is calculated by the proposed decoding scheme and used as the fitness to evaluate the solution. However, due to the randomness of the location of the dividing points, it may be impossible to divide the sequence into sub-sequences equal to the number of vehicles, resulting in the inability to generate valid solutions. Towards this issue, a RDS is developed and applied to the sequencing vector to guarantee that each customer can be scheduled successfully. Specifically, every route is built for each individual $i_{\mathrm{th}}$ of a vehicle. First of all, for the former $m-1$ vehicles, from left to right, in turn, judge whether $x_j^i$ is the dividing point, if not, then estimate the service point $x_j^i$ after joining the route $R_k(k<m)$ whether the constraints of maximum load are met, if so, add it to the end of $R_k$, if not satisfied, add the dividing point to the end of $R_k$. The route $R_m$ of the last vehicle is constructed of the remaining service points added successively, regardless of whether the $R_m$ meets the constraint conditions. Thus, the solution individual $i_{\mathrm{th}}$ is updated as $X_i=R_1\cup R_2\cup \cdots \cup R_m$.

4.2. Local search algorithm

After applying the decoding scheme, some local search algorithms are employed and embedded into the DJaya algorithm to further improve the exploitation ability. Many local search algorithms can be applied to the VRP (Moghaddam et al., 2012; Potvin et al., 1996). In this paper, 2-OPT algorithm, exchange 1–1 algorithm and sub-sequence exchange (SE) operation are utilized to avoid falling into local optimal.

4.2.1 2-OPT algorithm

The 2-OPT algorithm was produced by Ulder et al. (1991) which was designed to solve the Travelling Salesman Problem (TSP). The basic idea is to traverse two cities through two pointers P and Q, and each traverse will reverse the route between P and Q. As for VRP, this method can only be carried out in the same delivery route shown in Figure 4.

Figure 4. Illustration of the 2-OPT algorithm.

4.2.2 Exchange 1–1 algorithm

The exchange 1–1 algorithm makes it possible to switch customers in different distribution routes. If the distance between two customers is less than a given constant, the two customers will be exchanged and the objective function will be updated. If the solution is feasible and improves the objective function, the customers’ assignments to the vehicles are updated and other assignments are checked; otherwise, the algorithm will proceed without updates. Figure 5 illustrates the exchange procedure for two routes.

Figure 5. Illustration of Exchange 1–1 algorithm.

4.2.3 Sub-sequence exchange

In this operation, there is a crossover between the sequences of the two obtained solutions, and the same sub-sequence is arranged in different order in the two solutions. So, by swapping the corresponding order of the two solutions, two new solutions can be achieved, that is, the corresponding allocation routes of the solutions will be updated at the same time, and the resulting new solutions will be evaluated separately. If either solution improves the objective function, the corresponding customer assignment will be updated. An example is given in Figure 6. The practical means of this operator is to exchange the visiting order for selected customers of two solutions.

Figure 6. Illustration of sub-sequence exchange.

4.3. Algorithmic framework

The main procedure of the proposed DJaya algorithm can be detailed as follows:

Step 1: Set the main control parameters (the population size N and the maximum iteration number G). Initialize the first population by uniform random distribution and evaluate each solution.

Step 2: Preserve the best and worst solutions into different sets at the beginning of each iterative process. Generate random values of variables $r_1$ and $r_2$, and then stochastically select the solution $x_{i,B,k}$ or $x_{i,W,k}$ from their respective solution sets.

Step 3: Execute the crossover operation to generate new solutions and apply the local search algorithm to improve the solution quality. The newly produced solutions are accepted by Algorithm 1 and used as the offspring solutions. Meanwhile, the best solution will be updated.

Step 4: Estimate the pros and cons relationships in the union of parent and offspring solutions and remove the solutions with the same fitness. The better ones among them are stored in the parent population and are also utilized to construct a new population for the next generation. If the number of stored solutions is less than the population size, the remaining solutions in population will be generated randomly.

Step 5: Repeat the procedures from Step 2 to Step 5. Output the best solutions with the highest fitness if the maximum iteration number is reached.

In addition, the pseudo-code of replacement between the former and newly generated solutions is given as follows:

Table

Algorithm 1: Solution update strategy.
Procedure Solution update strategy for Jaya
Set an initial population $X$;
Identify xbest, xworst and record;
Generate new population $X^{\mathrm{\prime }}$ from $X$ using xbest and xworst;
Select a solution $x_{}^{\mathrm{\prime }}$ from the set of $X^{\mathrm{\prime }}$ and $x_l^{\mathrm{\prime }}$ represents the solution after local search;
If $x^{\mathrm{\prime }}$ is better than $x_l^{\mathrm{\prime }}$ then
$x^{\mathrm{\prime }}=x^{\mathrm{\prime }}$;
Else $x_l^{\mathrm{\prime }}$ is better than $x^{\mathrm{\prime }}$ then
$x^{\mathrm{\prime }}=x_l^{\mathrm{\prime }}$;
Do
Select a solution $x_p$ from $X$;
While $x_p$ is the best solution;
If $x_{}^{\mathrm{\prime }}$ is better than
$x_p$ then
$x_{\mathrm{best}}=x_{}^{\mathrm{\prime }}$;
End if
End if
End procedure

5. Computational results and comparison

In this section, computational simulations are carried out for the proposed DJaya algorithm. The benchmark data sets generated by Moghaddam et al., (2012) are used for the test and comparison here. Sets A, B and P include 75 small-sized instances and sets E, F and M include 11 large-sized instances. An instance is represented by A-nb-kc, an instance taken from set A, which contains b customer points and c vehicles are arranged for delivery. The performance of DJaya is compared with the existing algorithms, including the heuristics developed in Moghaddam et al. (2012) and exact robust solutions in Sungur et al. (2008). DJaya is coded in Visual C++ 6.0 and performed on a core i7-4800U processor with 2.40 GHz and 16 GB RAM.

5.1. Effect of the improved repair-based decoding scheme

In this subsection, the effectiveness of the presented RDS to SR-1 (Ai & Kachitvichyanukul, 2009) and M1 (Moghaddam et al., 2012) schemes is discussed. To make a fair comparison, the population size is set to 50, which is the same as used in the literature. The results are shown in Table 3, where the better results for each instance are marked in bold.

Table 3. Comparisons of RDS algorithm with M1 and others.

Instance	Best known	SR-1	M1	RDS	Instance	Best known	SR-1	M1	RDS
An32k5	784	784	784	784	Bn52k7	747	747	747	747
An33k5	661	661	661	661	Bn56k7	707	709	707	707
An33k6	742	742	742	742	Bn57k7	1153	1153	1153	1153
An34k5	778	778	778	778	Bn57k9	1598	1603	1598	1598
An36k5	799	799	799	799	Bn63k10	1496	1500	1496	1496
An37k5	669	670	669	669	Bn64k9	861	866	863	861
An37k6	949	949	949	949	Bn66k9	1316	1318	1316	1316
An38k5	730	730	730	730	Bn67k10	1032	1035	1035	1032
An39k5	822	825	822	822	Bn68k9	1272	1278	1272	1272
An44k6	937	940	937	937	Bn78k10	1221	1239	1221	1221
An46k7	914	914	914	914	En30k3	534	541	534	534
An60k9	1354	1366	1354	1354	En51k5	521	521	521	521
Bn31k5	672	672	672	672	En76k7	682	691	682	682
Bn34k5	788	788	788	788	Fn72k4	237	237	237	237
Bn35k5	955	955	955	955	Fn135k7	1162	1184	1167	1162
Bn38k6	805	809	805	805	Mn101k10	820	821	821	820
Bn39k5	549	549	549	549	Mn121k7	1034	1041	1035	1035
Bn41k6	829	829	829	829	Pn50k8	631	631	631	631
Bn43k6	742	742	742	742	Pn50k10	696	696	696	696
Bn44k7	909	915	909	909	Pn51k10	741	741	741	741
Bn45k5	751	751	751	751	Pn55k15	989	998	989	989
Bn45k6	678	678	678	678	Pn65k10	792	799	792	792
Bn50k7	741	748	741	741	Pn70k10	827	828	827	827
Bn50k8	1312	1315	1312	1312	Pn76k5	627	628	629	627
Bn51k7	1032	1033	1032	1032	Pn101k4	681	686	688	684

As we can see in Table 3, for almost all instances, RDS can obtain the optimum value while SR-1 and M1 achieve the best in 25 and 43 cases, respectively. From Table 3 data, compared with the theoretical optimal value, the average error of the value obtained by RDS is 0.0107%, for SR-1 and M1, this index rises to 0.2579% and 0.0446%, respectively. It can be concluded that RDS based on dividing points can obtain much better solutions and achieve a lower degree of deviation.

5.2. Evaluating indicator

Before comparing with other algorithms on the VPRUD, appropriate evaluating indicators should be given in advance. There are two main evaluating indicators used in the experiment:

1. Unmet demand (U)

When needs are unpredictable, it is required to define certain performance indices in order to evaluate the performance of the suggested modification. Let $U_D$ and $U_R$ represent the percentages of unmet demands for the deterministic and robust solutions, respectively. To find them, the demands are produced randomly within the interval $\left[d_i-ϵd_i,d_i+ϵd_i\right]$, and the unsatisfied needs are counted based on the vehicle capacity. Here, $ϵ$ is set to 10%.

1. Extra cost (E)

Another index to be determined is $E_{\mathrm{DR}}$ which indicates the extra cost of the robust solution compared to the deterministic one, which can be calculated in Equation (14). (14) $E_{\mathrm{DR}}=\left(E_R-E_D\right)/E_D$(14)

5.3. Comparison with other algorithms on VRPUD

To further evaluate the robustness of the proposed DJaya algorithm under uncertain conditions, the above indexes are designed for calculation. The performance of the DJaya algorithm is compared with the advanced PSO (APSO) proposed by Moghaddam et al. (2012) and the exact robust optimum solutions (ERS) presented by Sungur et al. (2008). Table 4 lists the results of applying the methods mentioned above. Sungur et al. (2008) applied the exact algorithm to gain the solution, so that their U_RE is equal to zero for all instances. As with Moghaddam et al. (2012), these data are not recorded in Table 4.

Table 4. Comparison with advanced PSO and exact robust solutions.

		ERS	APSO		DJaya			ERS		APSO		DJaya
Instance	UD	EDRS	URP	EDRP	URJ	EDRJ	Instance	UD	EDRS	URP	EDR	URJ	EDRJ
An32k5	2.5	1.5	0	1	0	0.8	Bn52k7	2	0.7	0	0.3	0	0.2
An33k5	1.7	2.1	0	2	0	1.6	Bn56k7	3	3	0	3.2	0	2.4
An33k6	1.8	2.7	0	1.5	0	1.2	Bn57k7	5	IN	1.5	0.9	1.2	0.7
An34k5	0.3	1.5	0	0.6	0	0.5	Bn57k9	3.1	NA	0	1.2	0	1
An36k5	2.1	1.8	0	0.9	0	0.6	Bn63k10	3	NA	0.21	2.1	0.2	1.9
An37k5	1.6	2.7	0	1.9	0	1.2	Bn64k9	3.3	IN	0.9	3	0.7	2.5
An37k6	2.4	NA	0.2	0.5	0.15	0.4	Bn66k9	3.6	IN	0.91	2.1	0.72	1.8
An38k5	3.8	IN	0.67	1.5	0.33	0.7	Bn67k10	2.5	NA	0.87	3	0.69	2.7
An39k5	3.1	1.5	0.48	1.3	0.2	0.6	Bn68k9	3.9	NA	0.27	4.1	0.29	4.2
An44k6	2.2	1.5	0	0.9	0	0.8	Bn78k10	3.7	NA	0.7	2.4	0.8	2.6
An46k7	3.4	4.2	0.2	4.5	0.15	3.5	Pn23k8	3.4	IN	0.71	2.8	0.4	1.7
An60k9	2.1	NA	0.35	2.1	0.25	1.5	Pn40k5	1.2	0.7	0	0.3	0	0.2
Bn31k5	0.7	1.3	0	0.4	0	0.3	Pn45k5	3.3	2	0	1.1	0	0.6
Bn34k5	2.5	0.1	0	0.1	0	0.1	Pn50k7	2	2	0	1.5	0	0.9
Bn35k5	2.3	2.8	0	0.8	0	0.5	Pn50k8	3.9	IN	1.54	3	0.5	1.2
Bn38k6	2	0.1	0	0.1	0	0.1	Pn50k10	2.1	IN	0.82	2.1	0.67	1.8
Bn39k5	2.7	2.2	0	1.4	0	0.8	Pn51k10	3.2	IN	0.72	2	0.68	1.8
Bn41k6	2.4	4.2	0.4	2.1	0	1.8	Pn55k7	2	NA	0	0.4	0	0.4
Bn43k6	3.5	1.5	0	0.9	0	0.6	Pn55k8	1.9	NA	0	0.8	0	0.6
Bn44k7	3.6	4.6	0.3	3.5	0.2	2.7	Pn55k10	2.9	NA	0	1.1	0	0.9
Bn45k5	3.1	IN	0.79	1.2	0.54	0.8	Pn55k15	4.4	IN	1.4	2	1.25	1.8
Bn45k6	4.4	IN	0.84	1.1	0.6	0.8	Pn60k10	1.7	NA	0.68	1.8	0.35	1.3
Bn50k7	1.5	0.5	0	0.2	0	0.2	Pn60k15	2.3	NA	0.9	3	0.86	2.8
Bn50k8	3	2.7	0	1.1	0	0.7	Pn65k10	1.8	NA	0.94	2.5	0.72	1.9
Bn51k7	3.2	IN	0.83	0.9	0.64	0.6	Pn70k10	2.3	IN	1	2.7	0.84	2.3
							Average	2.7	2	0.383	1.638	0.286	1.272

According to Table 4 data, 50 instances were selected for the experiment, the solutions obtained by each method are first compared with the deterministic solution to prove its robustness. For the exact robust solution, its data became infeasible or not available on 26 instances so E_DRS is calculated on other existing data and the average is 2. Compared the advanced PSO with DJaya, neither algorithm produces unmet demand under random requirements in 23 instances. In the other 25 instances, the DJaya algorithm produces a lower unmet demand than the advanced PSO while in two large-scale instances, the contrary is the case. The average for the value of U_RP equals 0.383 and for the value of U_RJ equals 0.286 which shows that the DJaya algorithm proposed in this paper has stronger robustness, and the solution obtained by it has a higher probability of remaining applicable under the condition of random demand. In addition, the average of E_DRP equals 1.638 while this value for E_DRJ equals 1.272 which means in most cases, on the premise that the feasible solution is satisfied, the solution proposed by DJaya will incur less extra cost than the solution obtained by Moghaddam et al. (2012).

From the three sets of benchmark instances studied herein, it can be concluded that the proposed DJaya is significantly better and more effective than the other compared algorithms in solving the VRPUD. However, when the data size of the problem instance becomes larger, the performance of the solution obtained by the Jaya algorithm still needs to be improved. To further illustrate the solutions obtained by the Jaya algorithm, the vehicle route map for the instances P-n55-k10 and E-n51-k5 is presented in Figure 7. Additionally, two pair-wise t-tests at a 95% confidence level are also carried out for DJaya with ERS and APSO, respectively, to verify the statistical difference. The relative results are shown in Table 5, where SD represents the standard deviation, SEM equals the standard error of the mean, and IC-lower and IC-upper are the confidence intervals of the difference. The significances yield in Table 5 shows the superiority of DJaya over ERS and APSO in solving the VRPUD. As for the computational cost, there are no significant differences among these three algorithms. The average CPU times for all instances are between 30 and –45 s, as shown in Table 6.

Figure 7. Solutions obtained by Jaya for CVRP instances: (a) P-n55-k10 and (b) E-n51-k5.

Table 5. Pair-wise t-test of the compared algorithms.

Algorithms	Mean	SD	SEM	IC-lower	IC-upper	t	Significance
DJaya – ERS (for EDR)	−0.97500	0.71764	0.14649	−1.27803	−0.67197	−6.656	0.000
DJaya – APSO (for UR)	−0.11540	0.29041	0.04107	−0.19793	−0.03287	−2.810	0.007
DJaya – APSO (for EDR)	−0.26200	0.48902	0.06916	−0.40098	−0.12302	−3.788	0.000

Table 6. Average CPU times for the compared algorithms.

Algorithms	ERS	APSO	DJaya
Average CPU time	36.85	38.67	33.76

6. Conclusions

In this paper, an effective discrete Jaya algorithm was proposed to solve the Vehicle Routing Problem with Uncertain Demands (VRPUD), which is more realistic for the real-world applications of logistics than traditional VRP. In addition, this is the first work to apply the Jaya algorithm for solving the VRPUD. The computational results and comparisons with state-of-the-art algorithms demonstrated the feasibility and robustness of the proposed hybrid scheme. Compared to the existing results, the encoding and decoding schemes can obtain the optimal solution for almost all cases. Under the constraints of uncertain demands, the DJaya algorithm has stronger robustness and can realize distribution with less extra cost.

In our future work, some research on large-scale instances will be done to design more effective methods which can reduce the probability of producing unfeasible solutions. Moreover, in order to simulate vehicle distribution more realistically, vehicle routing problems under dynamic conditions will be the mainstream in the future.

Acknowledgements

The authors would like to thank the anonymous reviewers for their valuable comments and suggestions.

Disclosure statement

No potential conflict of interest was reported by the author(s).

Additional information

Funding

This work is part of a project supported by the National Natural Science Foundation of China (Grant Nos. 61973267 and 61503331), the Zhejiang Province Public Welfare Technology Application Research Project (Grant Nos. LGF21G030001) and the Zhejiang Provincial Natural Science Foundation of China (Grant No. LY22F030020).