Tackling the Multi-Objective Vehicle Routing Problem With Uncertain Demands

Tackling the Multi-Objective Vehicle Routing Problem With Uncertain Demands

Méziane Aïder (LaROMaD, Faculté de Maths, USTHB, Algiers, Algeria) and Asma Skoudarli (LaROMad, Faculté de Maths, USTHB, Algiers, Algeria)
Copyright: © 2020 |Pages: 22
DOI: 10.4018/IJAMC.2020010101


In this article, the single capacitated vehicle routing problem with time windows and uncertain demands is studied. Having a set of customers whose actual demand is not known in advance, needs to be serviced. The goal of the problem is to find a set of routes with the lowest total travel distance and tardiness time, subject to vehicle capacity and time window constraints. Two uncertainty types can be distinguished in the literature: random and epistemic uncertainties. Because several studies focalized upon the random aspect of uncertainty, the article proposes to tackle the problem by considering dominance relations to handle epistemic uncertainty in the objective functions. Further, an epistemic multi-objective local search-based approach is proposed for studying the behavior of such a representation of demands on benchmark instances generated following a standard generator available in the literature. Finally, the results achieved by the proposed method using epistemic representation are compared to those reached by a deterministic version. Encouraging results have been obtained.
Article Preview

1. 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.

Complete Article List

Search this Journal:
Open Access Articles: Forthcoming
Volume 11: 4 Issues (2020): 1 Released, 3 Forthcoming
Volume 10: 4 Issues (2019)
Volume 9: 4 Issues (2018)
Volume 8: 4 Issues (2017)
Volume 7: 4 Issues (2016)
Volume 6: 4 Issues (2015)
Volume 5: 4 Issues (2014)
Volume 4: 4 Issues (2013)
Volume 3: 4 Issues (2012)
Volume 2: 4 Issues (2011)
Volume 1: 4 Issues (2010)
View Complete Journal Contents Listing