Genetic Algorithm for the Vehicle Routing Problem with Time Windows and Fuzzy Demand

This paper considers a VRP with soft time windows and fuzzy demand (VRPTWFD). The objective is to minimize both the total distance covered by all vehicles as well as the sum of lateness at the customer's due to the violation of time windows. This VRPTWFD is formulated as a two stages recourse model in the context of stochastic programming. The goal is then to minimize the expected cost, which includes the initial cost of the solution found in first stage and the additional cost due to the route failure in second stage. The theory of possibility is applied in the capacity constraint. In addition, a route failure estimation method is proposed to evaluate the additional cost as well as the expected cost. A genetic algorithm, in which a simulation phase based on sampling scenarios to evaluate the fitness of chromosome, is specifically designed to solve the two stages recourse model for the VRPTWFD. Finally an experimental evaluation of this developed algorithm is validated on a few VRPTWFD modified from the Solomon benchmarks.