1 Introduction

1.1 An overview

Given the new competition environment and technical background, nowadays, global manufacturing industries are passing from mass production to customized production. This transition, in combination with the advances in production management, has created needs for flexibility, transformability and cost efficiency [1]. In this context, mobile robots and especially the AGVs are widely employed in an ever-growing number of areas, such as material handling in manufacturing, distribution, transshipment and transportation [2]. Efficient vehicle routing and motion planning play a significant role in the enhancement of AGVs’ performance and productivity.

In general, vehicle routing and motion planning are two basic and separate functions, which are designed to improve an AGVs’ efficiency. Typically, vehicle routing problem (VRP) lies at the heart of distribution management and logistics. It is faced every day by thousands of companies and organizations engaged in the delivery and collection of goods or people. Collection of household waste, gasoline delivery trucks, goods distribution, snow plough and mail delivery are the most used applications of the VRP. Because conditions vary for different applications, the objectives and constraints encountered in practice are highly variable.

The classical VRP involves a fleet of AGVs set off from a central depot to serve several workstations positioned at different known locations with various demands and return to the depot. The objective is to find the optimal routes of minimum total cost, beginning and ending at a central depot, such that each customer is visited exactly once by one vehicle, while satisfying some constraints. An undirected graph is used to present the network of the depot and the workstations, and the VRP is applied to this graph searching for an optimum route satisfying the related constraints. Since all versions of VRP belong to the class of NP-hard optimization problems, robust heuristics algorithms [3] or Petri-net based approaches [4] are preferable for the solution of these problems. For example, in [5], the authors proposed an approach for scheduling the routes of AGVs in order to ensure the smooth flow of materials in production and container terminal conditions. The proposed approach consists of a mixed-integer programming model and two meta-heuristics-based algorithms in order to achieve quality schedules within a reasonable amount of time. In [6], the authors proposed a new heuristic approach which is based on Benders decomposition for solving the conflict-free scheduling and routing of AGVs which operate in FMS.

On the other hand, motion planning is to plan a path that enables the AGV to undertake a predefined task avoiding at the same time collisions with the environment and with the other AGVs. Existing approaches for motion planning of multiple AGVs can be classified into two general categories [7]: (a) the centralized approaches and (b) the decoupled approaches. The centralized approaches treat the fleet of AGVs as a composite system [8] generating a composite configuration space which searched for a path for the whole composite system [9]. In the decoupled approaches [10], a collision-free path for each AGV is determined independently and then collisions between the AGVs are resolved by velocity tuning. The trade-off of these two approaches (centralized and decoupled) is that the decoupled approaches are considered faster while the centralized approaches have the advantage of being complete. Xidias et al. [11] proposed an approach where the AGVs’ workspace is represented through the Bump-Surface concept [12]. Then, the problem’s solution is searched globally onto a solution space in such a way that all moving AGVs satisfy the Motion Planning Problem objectives.

The problem becomes harder when we take into account the fuzziness of the system. In many real-world applications, one or more parameters of the vehicle routing problem tend to be uncertain in nature, giving rise to the fuzzy vehicle routing problem. Several researchers have proposed solution approaches for a version of vehicle routing problem considering fuzziness. Zarandi et al. [13] address the multi-depot-capacitated location routing problem in which the travel time between two nodes is a variable. Credibility theory is used in parallel with a simulated annealing procedure in order to solve the problem. The proposed approach aims at the minimization of the total travel cost of the vehicles including cost of depot and routing costs. The proposed approach is tested using a standard test problem, and the numerical results proved the robustness of the approach. The authors in [14] study the multi-objective dynamic VRP with fuzzy time windows. The optimization objectives are four. The total required fleet size, overall total travelling distance and waiting time imposed on vehicles are to be minimized, and the overall customers’ preferences for service is to be maximized. The proposed strategy is based on a genetic algorithm consisting of three basic modules. Erbao et al. [15] consider the vehicle routing problem with fuzzy demands. A hybrid intelligent algorithm is applied, and fuzzy credibility theory is used for the solution of the problem. The optimization is achieved in the context of the total expected distance, which is the total sum of planned route lengths and the additional distance covered by vehicles.

The authors in [16] solve the location routing problem with fuzzy demands applying a hybrid simulated annealing with fuzzy credibility theory. The objective is the minimization of the total cost. The efficiency of the solution is demonstrated by numerical examples of different sizes. A multi-objective evolutionary algorithm is proposed in [17] that incorporates local search heuristics for the VRP with stochastic demand. There are three objectives to be optimized: travel distance, driver remuneration and number of vehicles required. Trade-off solutions are provided and the relationships among the three objectives are observed concluding that two of them are correlated to each other, and for the other two pairs, the objectives are conflicting with each other.

To the best of our knowledge, the integration of task routing and motion planning for a fleet of AGVs in real industrial environments considering fuzziness to deal with uncertainty embedded in the system has not been well studied. In this paper, we are motivated by a practical industry application of a large fleet of AGVs in material handling in a fully automated FMS such as at Amazon warehouses. We aim to investigate the integration of the above problems (i.e., vehicle routing, motion planning and fuzziness) for a fleet of homogeneous AGVs by proposing a unified approach.

The proposed approach using a mix of GA and A-star algorithm solves simultaneously the problem of vehicle routing and motion planning. In addition, in order to face the fuzziness of the system, the proposed approach is strengthened with the fuzzy set theory. The objective is to determine the number of AGVs used, the allocation of workstations to the AGVs and the AGVs’ safe (collisions-free) paths from depot to workstations and back to the depot, so that all workstations are served at the lowest possible cost.

1.2 Main contribution

In this study, the decision-making problem involving the tactical and operational planning is to be analysed; namely the study will cover the development of vehicle routing and motion planning problem. This paper studies an Intelligent Warehouse in which the equipment can be controlled automatically without any human intervention. A central management system assigns tasks and schedules the paths of multiple AGVs which are requested to serve a set of workstations in the warehouse.

The main innovations and contribution of the proposed approach are the following:

  • A global optimization problem is studied after integration of two NP-hard problems: vehicle routing problem and path planning. An optimum (or near-optimum) solution can be provided searching all over the search space.

  • The paths between successive workstations are not given. Obstacle avoidance is considered for the determination of the paths applying the A* algorithm. The optimization is achieved in the context of travelled distance satisfying the capacity constraint.

  • Unlike the traditional vehicle routing model, fuzzy travel distances and fuzzy workstation demands are considered instead of fixed deterministic. In real-world situations, multi-AGV systems depend on traffic conditions or unforeseen circumstances causing uncertainty to the AGV system.

Most of the versions of the problem assume that each AGV runs at a fixed route between the workstations. However, in the actual workshop environment, in order to avoid obstacles, the AGV’s route is more complicated, which leads these versions to have poor applications [18]. In most published works, vehicle routing and path planning problems are usually studied separately. This is because integrated vehicle routing and path planning form a very challenging NP optimization problem [19]. Eventually, most papers in literature consider the distances between nodes for optimization and the problem is limited to the minimization of the travelled distance.

Since determining the path between nodes is crucial for optimal vehicle routing and motion planning, the paper at hand focuses on the determination of the total travel cost. In this context, the travel cost between the nodes is not known or easily obtained since obstacle avoidance and traffic condition should be encountered too. In addition, the problem is studied as a global optimization problem that encompasses two NP-hard problems: the vehicle routing problem considered and the motion planning problem. The global problem is studied under fuzziness since there is uncertainty in travel distances and workstation demands. This type of problem is more challenging and sophisticated than the classical vehicle routing problem since it reflects real-life situations. Due to combinatorial explosion, meta-heuristics are of major importance because they can produce approximate solutions in polynomial time. Thus, the problem is solved using a genetic algorithm.

2 Problem statement and general assumptions

This paper considers a fleet of AGVs moving in a 2D industrial environment, an example layout of which is shown in Fig. 1, with L homogenous AGVs, M static obstacles (including storage shelves, machines and walls) and K workstations in which a fleet of AGVs is requested to accomplish a task. Here, the AGVs share the same depot. Furthermore, this paper considers two fuzzy factors: (a) travel cost between workstations and (b) workstation demands. Determination of the real values of travel costs and workstation demands prior to their realization is often too difficult or even impossible because of their uncertain nature. It is assumed that both (traffic condition and demands) are estimated based on expert judgement. The main assumptions are summarized in the following:

  • Assumption 1: The obstacles have fixed and known geometry.

  • Assumption 2: The AGV is a homogeneous mobile robot with the basic capabilities for navigation, obstacle avoidance and localization.

  • Assumption 3: Each AGV has a circular body shape and respects the kinematical constraints.

  • Assumption 4: Each AGV has a maximum available capacity VC.

  • Assumption 5:The locations of the workstations are fixed and known.

  • Assumption 6: Each workstation is associated with a fuzzy demand, expressed as a triangular fuzzy variable (see Section 3.2).

  • Assumption 7: The virtual travel distances between workstations are fuzzy variables, expressed as triangular fuzzy variables.

  • Assumption 8: There are L possible AGVs, but the number ℓ of AGVs used is variable.

  • Assumption 9: In order to handle conditions associated with AGVs in the FMS (communication among vehicles, the mapping of the environment etc.), we assume that there is a central management system which can manage all these info and design the appropriate velocity profiles for the robots in order to ensure their safe motion.

    Fig. 1
    figure 1

    The warehouse layout (https://www.mecalux.co.uk/)

    Full size image

Under these assumptions, the overall problem can be defined as follows:

Let G = (V, E) be an undirected network where V is a set of nodes in the graph G, and E is a set of edges in G connecting the vertices in V. V contains a central depot location, K workstations and M static obstacles. A fuzzy distance and a fuzzy traffic condition are associated with each element of E. A fuzzy demand \( \tilde{d}_{i} \) is associated with each workstation. The problem concerns a number of AGVs starting from a depot to serve a number of workstations at different locations with various uncertain demands and uncertain travel costs. The aim is to determine the number of AGVs used and the collision-free paths starting and ending at the depot so that all workstations are serviced exactly once. The objective to be minimized is the total travel cost of the AGVs while satisfying the demands at workstations regarding that the capacity of each AGV is not violated.

3 Vehicle routing and motion planning in FMS

We now present and discuss the developed solution approach. A schematic overview of the proposed approach is illustrated in Fig. 2.

Fig. 2
figure 2

A schematic overview of the developed approach

Full size image

3.1 Collision-free path

In order to design a collision-free path for each AGV, we consider that each AGV is considered as a point while the obstacles have been enlarged accordingly in order to take into account the AGV’s shape [8] and the 2D-enlarged FMS environment W has been normalized.

The first step is to divide the W into equally spaced subintervals along the two orthogonal directions forming a square grid. By decomposing the environment W, we reduce the searching area into a simple two-dimensional array. Each element in the array represents one of the squares on the grid, and its status is recorded according to the corresponding state, i.e. we set the value 0 for a free cell and 1 for a cell occupied by an obstacle. An example of the divided environment W is show in Fig. 3.

Fig. 3
figure 3

The divided layout of a warehouse into squares

Full size image

In the above example, a cell cluttered by an obstacle (black colour) takes the value 1 while cell in the free space takes the value 0. The red circles represent the position of the workstations while the blue star represents the depot.

Then, using the A-star algorithm, we create a distance matrix by computing the distances from the depot to the workstations and between the workstations. Once the paths are found, our vehicle moves from the centre of one square to the centre of the next one until the target is reached. These set of points are called control points.

3.1.1 Feasible path

The major objective of this sub-section is to calculate a feasible path for each AGV. We choose to represent the AGV’s path by a two-degree NURBS curve [20]. We assume that the point-AGV traces a path C(s) = (u1(s), u2(s)) in W. The path is given by

$$ \boldsymbol{C}(s)=\frac{\sum_{i=0}^{K-1}{N}_i^2(s){w}_i{\boldsymbol{p}}_i}{\sum_{i=0}^{K-1}{N}_i^2(s){w}_i},s\in \left[0,1\right] $$
(1)

where pi ∈ [0, 1] × [0, 1] are the control points which define the AGV’s path. It holds that

  • p0 = pK − 1 symbolizes the depot

  • The set of points {p1, …, pK − 2} are the workstations and the number of the squares (Section 3.1)

  • \( {N}_i^2(s) \) is the base function

  • wi is the weight factor and initially is set equal to 1

In order to generate for each AGV a path which is smooth and respects the AGV’s kinematical constraints, we tune the values of K weight factors wi, i = 1, …, K. It should be mentioned that increasing the value wi, i = 1, …, K will pull the curve toward control point pi while decreasing the value of wi, i = 1, …, K will push the curve away from control point pi. Figure 4 presents the influence of the weight factor w2 to the curve. Here, the black dashed polygon represents the control polygon of a 3-degree NURBS curve which is defined by three control points (black dots) P1, P2 and P3.

Fig. 4
figure 4

The effect of the weight w2 to the curve’s shape

Full size image

Each set of control points defines the NURBS curve (Eq. 1) and creates the proposed paths for the AGVs. In this paper, since the orientation of the AGV’s front wheel is mechanical limited, a curvature constraint Cu(s) is incorporated in the path C(s) which is described by

$$ Cu(s)\le {Cu}_{\mathrm{max}},s\in \left[0,1\right] $$
(2)

where Cumax is the maximum allowed curvature. In order to compute the curvature Cuj at each point Cj, j = 1, …, Np of C(s), we follow the procedure below:

The path C(s) is discretized by Np − 1 equal sequential chords where at each point Cj, j = 1, …, Np, the corresponding curvature Cuj is approximated by

$$ {C}_j=\left\Vert {C}_{j-1}-2{C}_j+{C}_{j+1}\right\Vert \le {Cu}_{\mathrm{max}},j=2,\dots, {N}_p-1 $$
(3)

The tuning of the wi is done by using a GA following the procedure similar with the paper [21].

3.1.2 Optimization criteria and constraints

Assume that the AGVs are initially filled with goods when they leave the distribution depot. Each vehicle should fulfil the fuzzy demands at each workstation before it returns to the depot. For convenience, the capacity VC of the vehicles is the same. The available fuzzy capacity of each vehicle after serving the k workstations will be

$$ {\overset{\sim }{Q}}_k= VC-\sum \limits_{i=1}^k\tilde{d}_{i} $$
(4)

If the available fuzzy capacity is greater than the fuzzy demand at the next node, then the vehicle is sent to the next node; otherwise, the vehicle should return to the depot. In other words, the capacity constraint imposes that the fuzzy demand at each workstation should not exceed the available fuzzy capacity of the vehicle.

$$ {\tilde{d}}_{k+1}\le {\tilde{Q}}_k $$
(5)

The capacity constraint is checked for each workstation to establish a decision about sending the vehicle to the next workstation or sending it back to the depot. If the capacity constraint is satisfied, the vehicle should be sent to the next workstation. If the capacity constraints are violated, the vehicle returns to the depot and the route ends. Another vehicle is sent from the depot to the next workstation starting a new route, and this process is repeated until all workstations are served. Since the vehicles depart concurrently from the depot, the optimization criterion is the minimization of the maximum travel distance TDmax among all vehicles that is computed as

$$ {TD}_{\mathrm{max}}=\max \left({TD}_i\right),i=1,\dots, r $$
(6)

and TDi is given by:

$$ {TD}_i={x}_{d1}^i+\sum \limits_{j=1}^{k-1}\left({x}_{j,j+1}^i\right)+{x}_{1d}^i $$
(7)

where \( {x}_{d1}^i \) is the distance from depot to the first workstation of the route i, \( {x}_{j,j+1}^i \) is the distance from workstation j to workstation j + 1, \( {x}_{1d}^i \) is the distance from the first workstation of the route i to the depot and r is the total number of routes resulting from the capacity constraint. It is worth noting that the distances\( {x}_{d1}^i \), \( {x}_{j,j+1}^i \) and \( {x}_{1d}^i \) are not the actual distances, but they are the virtual distances yielded by the fuzzy model (described in Section 3.2) that have been calculated considering the traffic conditions.

3.2 Fuzzy sets and fuzzy numbers: concepts and applications

Data in real-world problems are often afflicted with uncertainty, imprecision and vagueness due to both machine and human factors; thus, they can only be estimated as within uncertainty. The concept of fuzzy sets, which deal with vague, ambiguous, incomplete and imprecise information, paved the way for applying them to real and complex tasks [22].

Fuzzy logic and probabilistic logic are mathematically similar (representing degrees of certain kinds of subjective belief) but conceptually distinct, considering different forms of uncertainty. Fuzzy set theory is based on the concept of fuzzy set membership, whereas probability theory is based on the concept of subjective probability. The concept of fuzzy sets was firstly introduced in [23] and the term fuzzy variable was presented in [24], and they can both be constructed by a membership function, where each element in the universe of discourse represents a membership grade. Fuzzy numbers can be used to represent the uncertainty in data variables (demands, travel distance etc.). In this study, the fuzziness of data is represented by triangular fuzzy numbers (TFNs) because they are simple in structure and fit well to represent the fuzzy demands at the workstations, as well as the fuzzy traffic conditions and distances. A TFN \( \overset{\sim }{A} \) (see Fig. 5) is denoted as a triplet (a1, a2, a3), where a2 is the most plausible value, a1 is the most optimistic value (less than a2) and a3 is the most pessimistic value (greater than a2). In other words, the actual data variable may be equal to a2 (most plausible value), smaller (up to the optimistic value a1) or greater (up to pessimistic value a3) than a2. Thus, the value of α2 corresponds to a grade of membership of 1. In practice, a dispatcher or analyst studying the problem can subjectively estimate the boundaries (α1, α3) of the variable data as well as the most plausible value (α2) based on experience and/or intuition.

Fig. 5
figure 5

A typical triangular fuzzy number A

Full size image

The triangular membership function corresponding to TFN \( \overset{\sim }{A\ } \)is defined by

$$ {\mu}_{\overset{\sim }{A}}(x)=\left\{\begin{array}{c}\frac{x-{a}_1}{a_2-{a}_1},{a}_1\le x\le {a}_2\\ {}\frac{a_3-x}{a_3-{a}_2},{a}_2\le x\le {a}_3\end{array}\right. $$
(8)

3.2.1 Fuzzification of demands

Since demands are modelled as triangular fuzzy numbers, fuzzy operations are needed for the calculations. Ranking fuzzy numbers is important in the context of comparing fuzzy numbers. A flexible method has been developed in [25] for ranking fuzzy numbers based on the integral value concept. It is independent of the type of the membership functions and uses an index of optimism to reflect the decision-maker’s optimistic attitude. According to this method, the total integral value for a TFN \( \overset{\sim }{A}=\left({a}_1,{a}_2,{a}_3\right) \) is a convex combination of the left and right integral values through an index of optimism β ∈ [0, 1]. The left integral is used to reflect the optimistic viewpoint and the right integral is used to reflect the pessimistic viewpoint of the manager. The left integral value is computed by

$$ {E}^L(A)=\frac{1}{2}\left({a}_1+{a}_2\right) $$
(9)

and the right integral value is computed by

$$ {E}^R(A)=\frac{1}{2}\left({a}_2+{a}_3\right) $$
(10)

The total integral value is

$$ {E}^{\beta }(A)=\beta {E}^R(A)+\left(1-\upbeta \right){E}^L(A)=\frac{1}{2}\left({\beta a}_3+{a}_2+\left(1-\beta \right){a}_1\right) $$
(11)

and is used as the ranking function. Therefore, for any two fuzzy numbers Α and Β, if Eβ(A) < Eβ(Β), then Α < Β; if Eβ(A) = Eβ(Β), then Α = Β and if Eβ(A) > Eβ(Β), then Α > Β. The index of β represents the degree of optimism of a decision-maker. A larger β indicates a higher degree of optimism, and a smaller β indicates a pessimistic decision-maker’s viewpoint. For a moderate decision-maker, β is equal to 0, 5.

3.2.2 Fuzzification of travel cost

Fuzzy sets can be used with little knowledge about the historical data. They express intuitive knowledge rather than exact uncertainty distribution. Fuzzy systems have the capability of translating the expert knowledge into linguistic rules inside a robust mathematical framework in order to draw conclusions and generate responses.

Based on the concept of virtual distance proposed in [26], a fuzzy model is formulated for determining the travel cost between the workstations. The decision system consists of two input variables (actual distance and traffic condition) and one output variable (virtual distance). Figure 6 displays the block diagram of the system, which is regulated by 25 fuzzy rules resulting from the five triangular membership functions used for each input. Each input variable is characterized by five fuzzy sets. The linguistic values corresponding to actual distance are: {very short (VS), short(S), medium (M), large (L), very large (VL)}. The linguistic values corresponding to traffic condition are: {poor (PR), fair (F), good (G), excellent (E), perfect (PT)}. The virtual distances are represented by seven linguistic variables namely {extremely short (ES), very short (VS), short(S), medium (M), large (L), very large (VL), extremely large (EL)}. The membership functions of the fuzzy decision system, shown in Fig. 7a, b and c, have been designed based on the experience gained from studying the system.

Fig. 6
figure 6

The block diagram of the system

Full size image
Fig. 7
figure 7

The membership functions for the two inputs and the output

Full size image

Expert knowledge, often afflicted with uncertainty, is summarized in the proposition:

The larger the actual distance and the heavier the traffic condition is, the larger the virtual distance should be.

In other words, as far as the traffic condition deviates from its perfect condition, the travel cost associated with the virtual distance gets even worse. The fuzzy associative memory (FAM) of the system (Table 1) obtained through experience consists of 25 rules. For the rule evaluation, the “min” operator is used, and for the aggregation mechanism, the “max” operation is used. The centroid defuzzification method is used to determine the virtual distance.

Table 1 FAM of the system
Full size table

3.3 The evolutionary algorithm and solution methodology

The integration of vehicle routing and motion planning under fuzziness is a very challenging problem that can hardly be solved using traditional methods. Genetic algorithms (GAs) are proved to be a very promising tool for solving a wide variety of real-world combinatorial optimization problems. While traditional optimization techniques require one starting point, GAs perform a search in a population of points and are based on probabilistic transition rules instead of deterministic rules. As a result, they are more likely to escape from local optima and converge to the near global solution very fast. In this study, a modified GA is developed as shown in Fig. 8 and its main characteristics described analytically in the following:

Fig. 8
figure 8

The flowchart of the developed genetic algorithm

Full size image

Chromosome representation and initialization

An integer-point representation is applied, where each chromosome is a K-dimensional vector that is a permutation of integer numbers. Each integer number represents a workstation; thus, the set of integer numbers represents the order with which the vehicle visits the workstations.

The initial population is generated randomly in an attempt to produce solutions over the search space expressed by uniform distribution. Each chromosome represents a possible path for the AGV starting and ending to the depot.

The evaluation mechanism

The fitness function expresses the possibility that the chromosome will survive and reproduce in the next generation and is strongly associated to the objective function. The fitness function of the problem at hand is expressed by

$$ \mathrm{fitness}=\raisebox{1ex}{$1$}\!\left/ \!\raisebox{-1ex}{$ TD$}\right. $$
(12)

Genetic operators

In the proposed GA, reproduction is based on the roulette wheel selection scheme, where the parent chromosomes are selected with rates proportional to their fitness. In general, chromosomes with higher fitness value have more chances to be selected for reproduction. Crossover is a recombination operator that combines the genetic information of the parents to produce new offspring. The Order Crossover (OX) [27] is applied according to a randomly chosen crossover rate. Mutation is applied in order to inject new genetic material into the population and thereby maintain genetic diversity. The inversion [27] is used for mutation according to a randomly chosen mutation rate.

4 Experimental results

In this section, numerical results are provided to illustrate our treatment. The simulations ran using Matlab version R2015b and the machine used is a dual-core Celeron 2.16 GHz PC. The control settings were selected after extensive experimental efforts with various control schemes adopted following the indications of the literature. The control settings for the parameters are as follows: population size = 100, maximum generation number = 300, a random crossover rate taken values in the range [0.7–0.85], a random mutation rate taken values in the range [0.06–0.1].

4.1 Numerical results

In this sub-section, we study the performance of the proposed method through several simulation experiments for a fleet of vehicles moving in a cluttered environment. For each fuzzy demand, a triangular fuzzy number is built (see Fig. 5). For all the test instances examined in this sub-section, the demands are fuzzified by setting the two extreme (least likely) values of the triplet α1 = α2 ∙ δ1 and α3 = α2 ∙ δ2, where δ1 = 0.85 and δ2 = 1.3. Concerning the index of β, for a moderate decision-maker, β is set to 0.5. In Section 4.2, we will investigate the impact of δ1 and δ2 values as well as the impact of index β on the solution quality. In the following, an example is indicatively presented and discussed.

The experimental tests are conducted on the 2D indoor industrial environment shown in Fig. 3, containing several rooms with wide corridors and a single depot. A fleet of AGVs are requested to deliver supplies to the workstations (WSs). For sake of simplicity, AGVs have the same capacity quantity. The total number of WS is 10.

The problem is solved for different values of vehicle’s capacity, and full characteristics for the solutions provided are summarized in Table 2, where d stands for depot. Furthermore, the crossover and mutation rate generated to obtain the optimal solution for each test case are given in Table 3 while the distance matrix is given in Table 4.

Table 2 Characteristics of the best solution attained by the proposed approach
Full size table
Table 3 The parameter setting in GA to obtain optimal solution
Full size table
Table 4 The derived distance matrix (ws = workstation)
Full size table

It is clear from the results that increasing the vehicle’s capacity, the number of vehicles used is decreased, since each vehicle can fulfil more demands and serve more workstations. In addition, an increase in the vehicle’s capacity leads to a decrease of the total travel distance since fewer vehicles result in lower total travel cost.

As presented in Table 2, for a vehicle’s capacity C = 30, the optimal fleet size is two and the optimal routing yielded by the proposed GA is: AGV1 d → 4 → 6 → 9 → 8 → 5 → 7 → d and AGV2 d → 2 → 1 → 10 → 3 → d. The fuzzy demands fulfilled by each AGV is (21.3, 25.0, 32.5) and (16.2, 19.0, 24.7) and the travel distance is 408.6 and 410.5, respectively. Therefore, the total travel distance is 819.1. In Fig. 9, the two optimal tours are illustrated. The brown closed curve shows the tour solution for AGV1, and the red closed curve shows the tour for AGV2. Similarly, the optimal tours for the rest simulation tests are illustrated in Fig. 10. One should keep in mind that the resulted optimal tours are not the shortest tours, but they are the tours that have been yielded considering the traffic conditions as well as the fuzzy demands at the workstations. This fact can explain why the resulted optimal tours are not the expected VRP tours.

Fig. 9
figure 9

The solution tours for the two AGVs when C = 30

Full size image
Fig. 10
figure 10

The solution tours for the AGVs when aC = 10, bC = 20, cC = 30, dC = 40

Full size image

As already mentioned, decreasing the vehicle’s capacity leads to increasing the number of vehicles used, which in turn leads to the increase of travel cost due to the fact that more routes from depot and to depot are added. The maximum travel costs among all vehicles used to fulfil the demands are depicted in Fig. 11, for the different values of vehicle’s capacity. As expected, the maximum travel distance is increased, since less vehicles are requested to serve the workstations implying that each vehicle will serve more workstations resulting in an increase of the travel cost corresponding to each vehicle. Figure 11 depicts the maximum travel costs considering fuzziness in distances, as well as considering the conventional travel distances (ignoring traffic condition). As resulted from Fig. 11, the maximum travel distance considering fuzzy virtual distances is greater from the corresponding one considering conventional distances implying that traffic condition tends to increase the real travel cost.

Fig. 11
figure 11

The maximum travel distances versus the vehicle’s capacity considering virtual distances and conventional distances

Full size image

4.2 Discussion and validation of results

In this sub-section, we conduct a sensitivity analysis through simulation in order to validate the results of the proposed model. In an attempt to control the uncertainty of the demands fulfilled by each AGV, one should control the uncertainty of the demands at the workstations. This is achieved by minimizing the support of the demands. In practice, this means that the more accurate the minimum and maximum values of the demands are, the better the estimate of the support is. Moreover, controlling the decision-maker’s attitude toward a situation by feeling more or less optimistic (i.e. the choice of β) has an impact on the capacity constraint.

To investigate the effect of the uncertainty in demands at the workstations on the uncertainty of the demands fulfilled by each AGV, two different approaches are applied. First, changing the width of the intervals, and second, choosing different values for β for the computation of total integral value of fuzzy demands.

Firstly, we change the width of the intervals from which the parameters of the fuzzy demands are withdrawn. We consider the following three combinations: (δ1, δ2) = (0.85, 1.3), (δ1, δ2) = (0.7, 1.6) and (δ1, δ2) = (0.9, 1.2). It is obvious that choosing a low value for δ1 and a high value of δ2 causes more uncertainty in the demands. On the contrary, a higher value for δ1 and a lower value for δ2 results in a narrow support for the demands. The results for the fulfilled fuzzy demands are shown in Fig. 12. As one can see from Fig. 12, more uncertainty in demands at the workstations results in a wider support (i.e. more uncertainty) of the fulfilled fuzzy demands. On the contrary, less uncertainty in demands (i.e. when δ1 = 0.9 and δ2 = 1.2) results in more accuracy of the generated fulfilled fuzzy demands (see green triangles in Fig. 12 a and b). Similar results are yielded from both AGVs. Therefore, we can conclude that increasing the uncertainty in demands at the workstations, the supports of the fulfilled fuzzy demands are broadened. Conversely, decreasing the uncertainty in demands at the workstations, the supports of the fulfilled fuzzy demands are narrowed.

Fig. 12
figure 12

The effect of range of fuzziness on the resulted demands fulfilled by a AGV1 and b AGV2

Full size image

The second approach employed considers different values for β for the computation of total integral value of fuzzy demands. As already mentioned, the index of β expresses the degree of the decision-maker’s optimism. For a pessimistic decision-maker, β = 0; conversely, for an optimistic decision-maker, with β = 1. Lower values of β express the pessimistic decision-maker’s viewpoint regarding the expected demands at workstations. Therefore, lower values of β indicate the decision-maker’s confidence that each AGV is able to serve as many demands as possible, since each fuzzy demand is evaluated by lower values. In other words, lower values of β express higher values for the expected available capacity. On the contrary, higher values of β express the optimistic decision-maker’s viewpoint, i.e. higher values for the demands served by each vehicle and therefore lower values for the expected available capacity. As shown from Fig. 13, an increase in the value of β results in a decrease of the integral value of available capacity of each AGV.

Fig. 13
figure 13

The integral value of fuzzy demands versus the β index for C = 30

Full size image

5 Conclusions

This study contributes to the literature of vehicle routing and planning problems in the following aspects: (a) studying the integration problem of vehicle routing problem and path planning as a global optimization problem, (b) proposing a fuzzy model of the problem considering fuzziness in distances and demands to deal with uncertainty in real-world problems and (c) determining the paths between successive workstations considering obstacle avoidance.

The paper presents an innovative approach for routing and motion planning a fleet of AVs used for logistics operations in indoor factory environments. The proposed approach can deal with uncertainty embedded in real-world factory environments affecting both the demands at workstations and the travel distance between the workstations. The objective is to determine the fleet size, the allocation of workstations to the AGVs, and the AGVs’ safe (collisions-free) paths starting and ending to the depot, so that all workstations are served at the lowest possible cost.

In the proposed approach, an A-star algorithm is applied on an image of the environment to construct a distance matrix between the depot and the workstations and among the workstations. In order to resolve the derived optimization problem, a genetic algorithm is proposed which is based on fuzzy sets and fuzzy numbers to deal with uncertainty in demands and distances. Numerical examples of different vehicle’s capacity are conducted to validate the efficiency and effectiveness of the proposed method. On this basis, a genetic algorithm is applied, which is integrated with a fuzzy model foe distances and capacity. The optimal solution is presented for different values of vehicle’s capacity. A sensitivity analysis is also presented to assess the effect of uncertainty in the total amount of demands fulfilled by each AGV. This analysis showed that the better estimate we can have for the demands at workstations, the less uncertainty we get for the total amount of demands fulfilled by each AGV. Moreover, the choice of β-index affects the available capacity of each AGV.

Future work will be devoted to apply the proposed concept in dynamic partially known environments, where a fleet of AGVs is assigned to serve a set of workstations while moving safely and concurrently avoiding collisions with static and dynamic obstacles getting advantage of artificial intelligent methods.