Article Preview
Top1. Introduction
The vehicle routing problem (VRP) is one of the most important problems in the field of combinatorial optimization. Such a problem consists in servicing a set of customers, with known demands, by a number of vehicles (routes) with limited capacities. These routes start from the depot to serve a number of dispersed customers in a scattered area, then return to the depot. On the one hand, the classical objective function is to minimize the total traveled distance, subject to a number of constraints such as vehicles capacity (Prins, 2004) and time windows (Tan et al., 2003). On the other hand, additional informations can be included to the problem, like the coordinates of the depot and customers, the distance between them and the vehicle capacity.
It is well-known that, in many real-world applications, some parameters tend to be unknown or uncertain in nature. Making decisions under uncertainty may be encountered in several domains such as transportation, logistics, telecommunication, reliability, production management, etc. Moreover, uncertainty can be categorized into two different types (Oberkampf et al., 2004): random and epistemic uncertainties. Generally, the random uncertainty is objective and it can directly use a variations’ probability distribution while the epistemic uncertainty, which is subjective, there is small information on these variations. According to the aforementioned cases, it is difficult to obtain the probability distributions associated with variations related to the demands using epistemic uncertainty. In such a case, the uncertainty can be handled by fuzzy or possibilistic variables, where uncertainty can be represented by the probability theory (Kolmogorov, 1960), fuzzy theory (Zadeh, 1965), possibility theory (Zadeh, 1978) or evidence theory (Dempster, 1967 and Shafer, 1976).
Because parameters' representation varies according to the constraints related to the applications, a variety of VRP under uncertainty has been investigated. For instance, (Bansal et al., 2017) studied a fuzzy VRP with hard time and fuzzy uncertainty demands. The problem was formulated as a two-stage recourse model with an objective of minimising the total cost and maximising the obtained sale in a competitive environment. It has been approximately solved by a new approach, where the route is built by applying an ant colony optimization. (Chang-Shi et al., 2016) tackled the fuzzy VRP with uncertain demands, where a fuzzy constrained program model was proposed. The proposed model has been solved with a hybrid ant colony optimization, where the total travel time is minimized. (Yan et al., 2016) dealt with the multiple time windows as fuzzy variables, where a particle swarm optimization has been used to solve the problem with multiple fuzzy time windows. (Yanwen et al., 2016) proposed a solution method based upon ant colony optimization for solving the VRP with fuzzy vehicle travel times and service times: such fuzzy data times are represented as fuzzy numbers and interpreted as possibility distributions. (Yousefi et al., 2017) proposed a new model for a bi-objective VRP with time windows, where uncertain demands are considered. The problem has been solved by a revised-multi-choice goal programming approach. A possibilistic programming method has been used to deal with the uncertain data. Finally, (Tavakkoli-Moghaddam et al., 2016) tried to solve the bi-objective capacitated VRP by considering two uncertain parameters: retailers' demand and products' volume. Each uncertain demand is expressed as fuzzy numbers and uncertain volume as robust parameters.