Solving the time capacitated arc routing problem under fuzzy and stochastic travel and service times

Abstract

[EN] Stochastic, as well as fuzzy uncertainty, can be found in most real-world systems. Considering both types of uncertainties simultaneously makes optimization problems incredibly challenging. In this paper we propose a fuzzy simheuristic to solve the Time Capacitated Arc Routing Problem (TCARP) when the nature of the travel time can either be deterministic, stochastic or fuzzy. The main goal is to find a solution (vehicle routes) that minimizes the total time spent in servicing the required arcs. However, due to uncertainty, other characteristics of the solution are also considered. In particular, we illustrate how reliability concepts can enrich the probabilistic information given to decision-makers. In order to solve the aforementioned optimization problem, we extend the concept of simheuristic framework so it can also include fuzzy elements. Hence, both stochastic and fuzzy uncertainty are simultaneously incorporated into the CARP. In order to test our approach, classical CARP instances have been adapted and extended so that customers' demands become either stochastic or fuzzy. The experimental results show the effectiveness of the proposed approach when compared with more traditional ones. In particular, our fuzzy simheuristic is capable of generating new best-known solutions for the stochastic versions of some instances belonging to the tegl, tcarp, val, and rural benchmarks.